* Overview ========== The contest task is to write a program that plays "pousse," an odd variant of tic-tac-toe. Contestant programs will then be entered into a tournament to determine the first- and second-place program. The contest main web page is http://www.ai.mit.edu/extra/icfp-contest/ * Description of the game ========================= The name of the game is "pousse" (which is french for "push"). It is a 2 person game, played on an N by N board (the original game was 4x4 but NxN is a simple generalisation to adjust the difficulty of the game, and its implementation). Initially the board is empty, and the players take turns inserting one marker of their color (X or O) on the board. The color X always goes first. The columns and rows are numbered from 1 to N, starting from the top left, as in: 1 2 3 4 +-+-+-+-+ 1 | | | | | +-+-+-+-+ 2 | | | | | +-+-+-+-+ 3 | | | | | +-+-+-+-+ 4 | | | | | +-+-+-+-+ A marker can only be inserted on the board by sliding it onto a particular row from the left or from the right, or onto a particular column from the top or from the bottom. So there are 4*N possible "moves" (ways to insert a marker). They will be named "Li", "Ri", "Ti", "Bi" respectively, where "i" is the number of the row or column where the insertion takes place. When a marker is inserted, there may be a marker on the square where the insertion takes place. In this case, all markers on the insertion row or column from the insertion square upto the first empty square are moved one square further to make room for the inserted marker. Note that the last marker of the row or column will be pushed off the board (and must be removed from play) if there are no empty squares on the insertion row or column. A row or a column is a "straight" of a given color, if it contains N markers of the given color. The game ends either when an insertion 1) repeats a previous configuration of the board; in this case the player who inserted the marker LOSES 2) creates a configuration with more straights of one color than straights of the other color; the player whose color is dominant (in number of straights) WINS *** Clarification: a configuration of the board includes the identity *** of the active player. See the query log for details. A game always leads to a win by one of the two players. Draws are impossible. * Program specification ======================= The standard input of the program will contain N on the first line and this will be followed by a sequence of moves (in the notation previously described) with one move per line. There are no intervening spaces or empty lines. If the standard input only contains a single line, it simply means a null sequence of moves. This sequence of moves specifies an incomplete game. The program must read the incomplete game from standard input and find which is the best move to make next. The program's sole output, on standard output, is a single line indicating the best next move. The program can assume that all moves in the sequence are valid. The program must not take more than 30 seconds of real time to perform its task. Programs exceeding this limit will automatically lose the game (so a simple way to resign is to pause or go into an infinite loop). Here is a sample standard input (between the horizontal lines): -------------------------- 4 L2 T2 L2 B2 R2 -------------------------- which means the configuration of the board for this incomplete game is: 1 2 3 4 +-+-+-+-+ 1 | |O| | | +-+-+-+-+ 2 |X|X| |X| +-+-+-+-+ 3 | | | | | +-+-+-+-+ 4 | |O| | | +-+-+-+-+ The program's output could be -------------------------- T2 -------------------------- The player's program must be named "runme"; it may be a binary executable or a driver shell script that starts up the actual program. It will be invoked as ./runme with the program's top-level directory as the current working directory; libraries and other support data may thus be accessed with the relative path name support/... (see below for more on directory structure). The program is run once for every move and then terminates; the current move state will be passed to the program on standard input. Persistent inter-move state may be kept in the "support/" directory if desired. When the program has chosen a move, it should print the move to standard output and exit. If the program has not done so after 30 seconds (real or "wall clock" time), the program will be terminated forcibly, and lose the game. The program will have the entire machine to itself when it runs; the machine won't even be on the Net. There should be no child processes alive after the top-level process exits; the program must ensure that all its child processes have exited before the top-level process exits itself. The board size will be a value between 4 and 20 (inclusive), which the contest organisers will reveal after the tournament. A correct "runme" program can be very short, for example the following 2 line "sh" script: -------------------------- #!/bin/sh - echo T1 -------------------------- Obviously selecting the "best" move will require a more elaborate program than this. Do not rely on having certain system libraries available, even libraries as basic as libc (since there are multiple libc's out for linux). Either statically link your program or place all of its needed libraries in your "support/" directory. Driver shell scripts can rely upon having the generic suite of Unix programs available from the directories in the $PATH environment variable passed to the "./runme" program, such as sh, bash, ps, ls. If you have a question about the availability of a specific program, send mail to email@example.com ...or just play it safe and put the program in your "support/" directory. * Submission details ==================== Contestants will submit the program as a gzip'd tar file. This tar file should contain (1) an executable driver program "runme", (2) a text file "readme" containing general remarks, (3) a directory "src/" containing source code. The tar file may also contain an optional "support/" directory containing support libraries, binaries, and other data required by the application at run time. The driver program will be invoked with the "support/" directory's parent as its working directory; it may access the files it contains as "support/..." Note that if the chosen language implementation does not permit building a standalone binary executable, it is permissible for the "runme" driver program to be a shell script that starts up the program using binaries contained in the "support/" directory. The "readme" file may contain general remarks, such as a description of how the program works, or the programming language(s) used for implementation; it *must* be signed with the team members' names and email addresses. Here is the layout of the directory packaged up in the tar file: ./runme binary executable or shell script ./readme text file ./src/... the source files ./support/... the support files A submissions could be prepared using the commands: tar cf submission.tar runme readme src support gzip submission.tar You may upload your submission by following the link found on the contest main web page http://www.ai.mit.edu/extra/icfp-contest/ A word of warning on Web submission: MIT has reasonably good Net bandwidth -- but your site might not. Or there may be congestion at some intermediate point. This may be a problem, especially if your tar file is particularly large. You may wish to try a test upload before the Sunday deadline. You may wish to upload a known-good submission well before the deadline before working on extra features for your system -- just in case you get stuck at the last moment.
Olin Shivers / firstname.lastname@example.org Marc Feeley / feeley@IRO.UMontreal.CA