ICFP'98 Contest WinnersThe J team won the Judge's Prize in the ICFP'98 Functional Programming Contest. Here are the judges' comments on the J program: The contest judges selected the J program because we felt it was the most thought-provoking entry. In brief, it is everything the number one Cilk Pousse entry is not:
And yet the J entry proceeded to beat 17 compiled C entries, which we view as at least a partial testament to the productivity gains of working with a powerful notation (and a partial testament to the skill and expertise of the isi team members, of course). We felt there were several lessons in the J entry for the programming community. Like the other two prize-winners, it is a strong statement. Congratulations to the isi team! Without a doubt, "a bunch of extremely cool hackers" -- and an extremely cool programming language. Here is a write-up from the ISI team...IntroductionThe "isi" entry in the ICFP'98 Functional Programming Contest is from Iverson Software Inc.; the team members are Chris Burke, Roger Hui, Eric Iverson, Ken Iverson, and Kirk Iverson. The entry is written in J, a dialect of APL. The motivation for entering the contest was the belief that J is a functional language, as reflected in item 7 of the list of major characteristics on page 1 of the J dictionary:
We normally use the carefully-defined term tacit instead of functional because we do not know of a uniformly accepted definition of the latter term. The GameThe specifications for the game are available at the contest website. In brief, the game of Pousse is played on an N by N board (N is between 4 and 20). Players X and O alternately enter a piece from the left, right, top or bottom, in one of 4*N possible moves, pushing the row or column forward to the next empty space or pushing a piece off the opposite end of the board. A player wins if he (it!) has a surplus of "straights", a row or column all of the same color; a player loses if he repeats a position, or takes more than 30 seconds on a move. The arena is a 4-processor 150 Mhz Pentium Pro machine with 128 Mbytes of memory, running Linux SMP. The ProgramExcept for some knowledge of overall strategies (such as "hold the center" in chess) we know little of games; except for ideas like "evaluation function" and "minimax" dimly remembered from college courses taken long ago, we know little of game-playing programs. We did observe that central positions in Pousse were more difficult to dislodge, and adopted a weighting scheme based on addition tables on lists of the form 0 1 2 2 1 0, computed by the function dedge: dedge=: >: @: (+/~) @:
(i. <. i.@-) The definition of dedge may be read as increment (>:) the addition table (+/~) of the minimum (<.) of the lists of increasing (i.) and decreasing (i.@-) non-negative integers. The program has three main parts: run, ump, and evaluation functions. run is a dyadic function on the board size and a matrix of the moves in the game so far. It checks whether the saved sequence of boards (one board per move) is valid, and as appropriate computes the entire sequence or adds an additional element to the sequence, and in so doing creates the global variables required by the other parts. ump ("umpire") is a dyadic operator in the sense of Heaviside, an entity that applies to function argument(s) and produces a function. The syntax is s (ex ump eo) n . ex is the evaluation function for X; eo is the evaluation function for O; n is the board size; the optional argument s is 1 or 0 indicating whether to display the internal state. ump is not required for purposes of the contest, but is very useful for evaluating the goodness of evaluation functions. Evaluation functions are dyadic. The left argument is the parity, 'X' or 'O'; the right argument is a 2- or 3-dimensional array of boards; the result is a vector of the scores corresponding to the boards. The main evaluation function is: ev=: evline + evcount + 1e8"_ * evrepeat + evstraight That is, ev is a linear function of the component evaluation functions evline, evcount, evrepeat, and evstraight; multiplication by the constant function 1e8"_ ensures that nonzero scores reported by evrepeat (negative one for a repeated board position) and evstraight (difference in the number of straights) dominate the calculation. It is instructive to consider evcount in detail. (The other component functions of ev work similarly, and are similarly brief.) The definitions are: flip =: 'X'&=@[ { 'XO'"_ flip switches the parity of a board, changing X to O and vice versa; count computes the product of each board (*"2) and the weights computed by dedge (discussed above), then the sums of the products in each matrix (+/"1@:(,"2)); finally, evcount computes the difference in the counts on the two parities. Thus: b=: (?. 2 6 6$3){' XO' NB.
two pseudo random 6 by 6 boards 0 0 1 0 0 0
0
0 3 0 0 0 (,"2) (dedge@{:@$ *"2 ]) 'X'=b
NB. ravel
each matrix +/"1 (,"2) (dedge@{:@$ *"2 ]) 'X'=b NB.
sum each vector 'X' count b 'O' count b 'X' evcount b Benchmarks performed on our machines and extrapolated onto the contest machine indicated that 30 seconds are sufficient to execute the evaluation function, without any need for timer interrupts or multi-processor execution. The program uses the same strategy on any size board, applying the evaluation function on (4*N)^2 boards, selecting at random from the set of move(s) that minimize the maximum score for the opponent. This strategy was sufficient to play surprisingly well. The program source text is a script of of 229 lines and 7078 characters (including comments and development support "dead" code). A playing version of the program for Windows 9x/NT (with a GUI front-end added subsequent to the contest) is available for free. See if you can beat our program! The ProcessThe contest ran from Thursday, August 27 at 5 PM EDT until Sunday, August 30 at 5 PM EDT, but we did not start working in earnest until the end of the paid work week on Friday at 6 PM EDT. Team members worked separately in their own homes, and kept in contact by telephone calls and by dial-up e-mail access (about 70 e-mail messages); it was only on Sunday that two of us (Hui and Kirk Iverson) met to execute the last mad rush and the final packaging. Much time was spent in developing the infrastructure for the program (running the moves, saving the state, implementing the umpire, etc.) before we arrived at a point of being able to work more seriously on evaluation functions and game playing strategy. The structure of the evaluation function facilitates parallel development; for example, someone could work on a weighted count of the pieces while someone else is devising a measure for the goodness of partial straights. Work would have proceeded rapidly, but time ran out, alas. Intermediate stages of the code were distributed as e-mail attachments. The brevity of the code was a definite advantage: the thirteen successive versions of the script file ranged in size from 389 to 7588 bytes and required very little transmission time even at dial-up speeds. The development was done under Windows 95/NT, and only the packaging and a short prima facie check were done under Linux. Our associate Martin Neitzel of Gärtner Datensysteme GbR in Germany kindly offered to perform this packaging for any J programmer who wished to enter the contest, but did not have access to Linux. The portability of J meant that the offer could be made with confidence. |