In general, if you have a question about the detailed rules,
the simplest choice is usually
the right choice - the goal being to encourage participation.
If you have questions - please post them to the forum.
LINES and BOXES rules are different from "Dots and Boxes" ... be sure to
read the details below. Your program must
be able to play a game on square and rectangular
board sizes from 3x3 boxes through 8x8 boxes.
A1
B1
C1
D1
E1
A2
B2
C2
D2
E2
A3
B3
C3
D3
E3
A4
B4
C4
D4
E4
(P1) Numero_Uno vs. (P2) Second_Guy
Player
Score
Time
Numero_Uno
0
60.00
Second_Guy
0
60.00
?
?
Begin; back up; advance; advance 10; End
Use the above buttons to step through your game.
Any change made after the initial (03/01) post
will be marked (and dated) in red.
Deadline for LINES and BOXES is May 31, 2006.
You must create a program that plays the game of LINES and BOXES
on square and rectangular board sizes 3x3 boxes through 8x8 boxes.
Although the goal of capturing boxes by making the final surrounding
move remains the same, LINES and BOXES differs from Dots and Boxes
in three ways:
Players alternate turns regardless of whether they capture a box or not;
Your move may connect any two dots on a horizontal or
vertical line
provided that your move does not overlap an already "taken" segment;
You play on a square or rectangular board that may not
be empty when the game begins.
At each turn, your
program will be given the current score and remaining time along
with a list of all previous moves. Your program will output your
next single move. You have 60 seconds to complete the game.
Full details are below - please read them!
errata
POTM is pronounced "PAH-TUM"
The M stands for Month - but problems are posed irregularly
The POTM-MASTER is omnipotent, but is allowed to change his
mind whenever he sees fit.
Have fun ... if you're not having fun, do something else for a while!
SPECIAL RULES FOR LINES and BOXES
NOTATION
A Vertex is labeled with a letter and a number ... the letter represents
the column and increases left to right and the number represents the row and
increases top to bottom.
A Box is represented as the letter and number of the upper left vertex. (B2)
A line segment is represented by the starting and stopping vertex. (A3 C3)
For this POTM, all line segments are horizontal or vertical.
The number of rows in this example is 3 (count boxes not vertices).
and the number of columns in this example is 4 (count boxes not vertices).
THE STARTING BOARD
You will be told how many rows and columns there are in the starting board
in terms of "boxes" not vertices ... in the example there are three rows
and four columns. For board definition in the input file,
rows will come first and columns second.
The starting board may have from 3 to 8 rows and from 3 to 8 columns -
thus it may be either square or rectangular.
The starting board may already have some moves made or have some
boxes filled in ... or it may have no lines drawn yet at all.
THE GAME
Your move may connect any two dots on a horizontal or
vertical line provided that your move does not overlap an already "taken" segment.
Note that (unlike the original dots and boxes) your line segment may be
more than one box long.
In making a move, you may capture a box if your line segment provides the
fourth side of a box. A line segment may simultaneously capture multiple
boxes. Your "score" is the total number of boxes you "capture".
Players alternate turns and do not move again even if they capture a box
(unlike the original dots and boxes).
The game ends when no more moves are possible. At that time, the player
with the most captured boxes will win that game.
A match consists of two games on identical boards, with each player
having the opportunity to go first in one of the games.
2 match points are awarded for a win, 1 match point for a tie, and none
for a loss. POTM winners will be determined based on total match points.
WINNING LINES and BOXES - updated 05/19/2006
The winner of this POTM will be determined based on the results of two
rounds of play.
During the first round each entry will play one match against every
other entry. Advancement to the second round will be based on total match
points accumulated during the first round. The number of entries advancing
to the second round will be approximately five based solely on the decision
of the omnipotent one.
During the second round, those advancing will play each other in
additional games on varying baord sizes and initial setups. The number of
boards and design of boards during the second round is again left to the
POTM-MASTER. (The boards will be defined before the matches are run.)
The POTM winner will be that entry amassing the greatest number of match
points during the second round.
ONLY if two players are tied (in second round match points) will the
tiebreaker of "total boxes captured during all round two matches" be applied.
If two entries remain tied after applying the final tiebreaker, the
trophy will be engraved with the names of both entrants.
THE INPUT FILE
will be provided as a full pathname argument to your executable, as in:
my_entry /tmp/inputfile
Line one will contain three numbers. The first is
either a "1" or a "2" indicating
whether you are the first player or the second player in this game, the second and
third numbers on the first line are the number of rows and columns in the
starting board. NOTE: Rows precedes columns and counts boxes not vertices.
The second line will contain three numbers: The first number will
be "1" indicating this line will provide the current score and time
remaining for player "1". The second number on the line will be the
current score (initialized with "0") of player one. The third number
on the line will be the total REMAINING time for player one expressed
as a floating point number (for example 23.4 or 0.22). This will be
initialized with 60.0 indicating you have 60 seconds to work with.
The third line of the input file will be similar information for
player number two.
Following these lines will be one line for each move made thus far
in the game. A move is described with a number followed by two vertices.
The number may be "1" or "2" indicating the player that made that move or
may be "0" indicating that this move appears on the starting board. All
zero moves will immediately follow the three starting lines and precede
the moves of the two players. Moves will appear in the order that the
players made them during the game thus far.
Moves in the input file will
always move left to right or top to bottom (so the
second vertex on the line is "greater than" the first vertex).
There will always be at least one move available on the board represented
by the input file.
A five by five board with no initial moves at the beginning of the game.
Starting game position on a 5 row and 7 column board with one box already surrounded before either player makes a move.
8 rows and 3 columns with two initial lines drawn and three player moves already made. Player 2 has captured one box on his first move followed by a single box capture by player 1 - it is now player 2's turn again.
OUTPUT OF YOUR ENTRY
Important: The ONLY output of your program is a single line containing the
starting vertex and ending vertex of the line you choose to draw.
Output the vertices in the letter-number notation (like A4 C4)
on a single line separated by white space.
Vertices must be legal vertices on the given sized board and the
line should always move left to right or top to bottom (so the
second vertex on the line is "greater than" the first vertex).
The move must be a valid move according to the rules of LINES and BOXES.
LINES and BOXES PROGRAMMING RESTRICTIONS
You may use temporary files IN THE LOCAL DIRECTORY to store
information about the current game. If the file you create is
"too big" you will hear from the POTM-MASTER. If you have to
ask, then it is too big.
Your temporary file must be named with
a file name that references your program name (like entry.temp for
example).
You may NOT store information about previous games against
the same opponent or other opponents. Each game is intended to
be completely independent of all other games.
Cooperation between opposing entries is strictly forbidden.
Any effort to identify or recognize your opponent and take
action based on that identity will result in banning from the
POTM and will earn the wrath of your fellow competitors.
Note that recognition and response to "strategies" is no problem -
this rule is intended solely to prevent cheating or teaming
of entries to defeat the intent of the contest.
Incorporating a "book" of openings, endgame, or mid-game
positions is permitted. However, in order to discourage the
pre-storing large numbers of positions, I will impose
a limit of 250,000 bytes on the executable. Note this is
smaller than the limit used for previous POTM contests.
Exceptions to this limit may be granted if it can be shown
that the program does not store a large dataspace.
COMMON RULES FOR POTM PROBLEMS
WINNING
Entries completing system test will be eligible for the final runs.
one entry per forum login
multiple submissions of the same algorithm by the same person or team will NOT be tolerated - please don't do this - it will be obvious in the end and only cause pain for the other participants
Your official entry must be submitted for system test by the
deadline (23:59 Eastern time on the deadline date) using the sandbox tools
in order to participate in the finals.
Specific winning criteria will vary for each POTM and should be
clear from the above sections. If there are questions, use the forums please.
Personal info, Consolation Awards and Other Fun Stuff
Your email will never be made public and will not be shared
with anyone. To communicate, use the "private message" capabilities
in the forums.
Your full name (provided for the sandbox) will appear on the trophy
as you are announced with pride as the winner, and may appear on your
program description at the conclusion of the POTM. Of course, I will have
no way of knowing if it is your real name.
Your code will be publicly available via the website (if you are worthy)
and the top finishers are usually given an opportunity to make their
code "pretty".
The POTM is for fun. In that spirit, there are generally
awards for things like best program name and the like ...
basically anything that I feel like at the end of a contest.
Participants are also encouraged to provide an exposition
on their algorithm after the deadline passes ... these responses are
often the most fun to read and offer insights into the foibles and
quirks of the participants.
Running The Tests - the POTM-MASTER's job
I will subject all entries to a "system test" to qualify them
for the actual event - these are run regularly via cron (in general).
Scores on the system test problem may (or may not) be public - this
will vary by POTM at my discretion.
System test results are sent to the participant via email including
whatever might be of use for debugging purposes.
If asked nicely (via private message in the forums) it may be
possible to make a debugging run and supply the output, but in general
all debugging should be done on YOUR machine.
Programming Stuff
Input will (most frequently) be provided as a full path argument
to your entry
my_entry /tmp/inputfile
Input file format will be explicitly defined for each POTM problem.
Your POTM problem output (with no extra output) goes to stdout
Explicit required output format will be defined for each POTM problem.
Nothing should be written to stderr
You may "save" information in small temp files in
the local directory (at present there is no enforced size limit)
if not explicitly prohibited by a particular problem.
These files should have "unique" names - their names should
relate to your program name somehow. You may write and read this file.
You may create a file named "DEBUG" which will be attached to
the mail you receive after a system test. This file should only
be written to.
There will be a per execution time limit (60 sec. sys+user time
as measured by /usr/bin/time unless otherwise stated).
Entries that exceed the time limit will receive a default score.
A signal (9) is sent to the program by the host when the time limit is exceeded.
any attempt to do anything whatever outside of your personal
run directory will be cause for disqualification and banning.
C and C++ programs will be compiled with only the math library
added to the standard libraries and no optimization.
Assember language optimizations are not permitted.
Non C/C++ entries must contain a first line beginning with "#!" as
specified in the sandbox instructions.
