LINES and BOXES DETAILS

POTM: LINES and BOXES: The Details

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.
  • Some sample input files follow:
    1 5 5
    1 0 60.00
    2 0 60.00
    
    1 5 7
    1 0 60.00
    2 0 60.00
    0 A2 A3
    0 A2 B2
    0 B2 B3
    0 A3 B3
    
    2 8 3
    1 0 58.32
    2 1 43.16
    0 A2 D2
    0 B1 B9
    1 A1 C1
    2 A1 A5
    1 C1 C9
    
    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.


  • The POTM is unsponsored and just for fun.       Friday 12:14:11 PM      Copyright © 2004-6 - Fred Hicinbothem