* 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 
    feeley@iro.umontreal.ca
...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.