* 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 

* Description of the game

The name of the game is "pousse" (which is french for "push").  It is a 2

     1 2 3 4
  1 | | | | |
  2 | | | | |
  3 | | | | |
  4 | | | | |

where the insertion takes place.

row or column from the insertion square upto the first empty square
the insertion row or column.

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

* Program specification

The standard input of the program will contain N on the first line and
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 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):


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


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
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 
(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 
...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

 (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

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

Olin Shivers / shivers@ai.mit.edu
Marc Feeley / feeley@IRO.UMontreal.CA