The Ancient Game of Pah-Tum

The game of PAH-TUM is played on a board of 7x7 squares. Like it's distant relatives Renju, Pente, Gomoku, Naughts and Crosses, and Tic-Tac-Toe, players alternate in an attempt to form collections of markers which score points. PAH-TUM gameboards have been discovered in Mesopotamia and Assyria and a board fashioned in ivory was discovered in the tomb of Reny-Seneb, XII dynasty, and dated at roughly 1800 BC.

==================  T H E   L O N G   R U L E S  =================

I.  YOUR TASK AND YOUR PROGRAM IN SUMMARY

	1. There is a 7x7 grid onto which you must place one of
	   your markers (either an X or an O).  There are several
           "unavailable" squares in the grid.  You and your opponent
	   alternate turns placing your markers until all "available"
           squares are filled.  Then I score the finished board and
           see who "won" the game by examining the length of any
	   horizontal and vertical strings of your markers.
	   
	2. Your program will read a 7x7 grid from standard input, 
	   make a single move by placing an X or an O in one of the
	   available squares, and then output the new grid to
	   standard output.  You take one turn at a time, taking no
	   more than 10 seconds per turn.

II.  The Starting Board
     =====================
The following example shows 5 "unavailable" squares in the grid -
 it is for sample purposes only ... 

-------  row A     There are seven columns in each row
------+  row B     for a total of 49 "squares" on the
---+---  row C     playing board.  A square with a "-"
-------  row D     in it is empty, a square with a "+"
--++---  row E     in it cannot be used.  On the sample
-------  row F     starting board B7,C4,E3,E4 and G1
+------  row G     cannot be used - leaving 44 available.

    1.  The playing surface will always be 7x7
    2.  There will always be an odd number of "+" on
        the board and therefore an even number of
        playable squares marked with "-".  There will
        be between 1 and 25 squares marked with a "+".
    3.  The "+" marks may appear in any of the 49 psoitions.
    4.  Once a game is underway, any of the squares
        marked with a "-" may be replaced with an "X"
        or an "O" (upper case letters).
    5.  The input (and output) will contain no white space or
        characters other than the 7x7 grid and the NL (X(0a) or \n) 
        at the end of each line for a total of 56 characters.

III.  The Board of a Game In Progress
      ===============================
XO-OXX-  row A     This board shows a sample game after each
------+  row B     program has made eight moves (there are 8
---+-O-  row C     X's and 8 O's on the board).  There are
O------  row D     28 = 49-5-8-8 remaining moves to choose
--++---  row E     from.
--XXXX-  row F     
+X-OOOO  row G     

    1.  Moves (placing an "X" or an "O") may be made by
        replacing any of the "-" positions with your letter.
    2.  You may assume that there will always be at least
        one "-" position remaining on your input board, so
        it will always be possible to make a move.

IV.  Alternating Turns - Who Am I?
     =============================

    1.  Your program will play either the "X" letter or the
        "O" letter during any single game.
    2.  "X" goes first.  If you are presented a board with
        no X's or O's on it, you may assume that your program
        is playing "X" and should place the first "X" on the
        board in any position marked with a "-".
    3.  If there are X's and/or O's already on the input board,
        you must count the number of X's and O's to determine
        which letter you are playing.  Add the number of X's to
        the number of O's - if the total is even you are playing
        X and should place the next X.  If the total is odd then
        you are playing O and should place an O.  Similar 
        comparisons yielding the same result are OK - clearly
        there should either be the same number of X's and O's
        on the board (in which case you play an X), or one more
        X than O (in which case you play an O).

V.  Scoring
    =======

    1.  After all turns have been completed (there are no more
        "-" on the board), the final position will be scored.
	There will always be the same number of X's and O's on
        the board at the conclusion of the game.
    2.  Scores are determined by examining HORIZONTAL and VERTICAL
        strings of X's and O's.  Diagonal strings, or strings that
        wrap around the edges of the board are NOT considered.
    3.  For each HORIZONAL or VERTICAL string of the same letter,
        a score will be assigned according to the following chart:

        CONSECTUTIVE LETTERS:   3     4     5     6     7
                       SCORE:   3    10    25    56   119

        Strings of length 1 or 2 will not count in the scoring.
        Note that this scoring ALREADY INCLUDES the scoring of
        any imbedded substrings: score(n) = 2*score(n-1) + n 
        (shorter sub-strings within a larger string are ignored
         for purposes of this scoring - only the complete string
         is scored)
    4.  Example - NOTE THAT THE O's HAVE BEEN REMOVED FOR THIS EXAMPLE:

XXXXXXX  row A     Row A scores 119 for 7 in a row.
XX-XXX+  row B     Row B scores 3 for the string of 3.   
X-X+XX-  row C     Rows C/D/E score 0
----X--  row D     Row F scores 10 for a string of 4
--++X--  row E     Column 1 scores 3 for the string of 3
---XXXX  row F     Column 5 scores 56 for the string of 6
+------  row G     Column 6 scores 3 for the string of 3

        The total score for X is thus 119+3+10+3+56+3 = 194

        Similarly, scoring for "O" when the "O" replaces all
        of the "-" in the diagram is 10+3+56+3+25+3 = 100

        In this example, X wins by 94 points  (94=194-100)

    5.  Each "MATCH" will consist of two games - each contestant
        will have the opportunity to go first.  The winner of the
        MATCH will be the program accumulating the most points
        over the two games.  Thus, if A beats B by 10 points, and
        then B beats A by 25 points, B will win by 15 points.

    6.  In the event of a tie, both programs will advance to the
        next elimination round.  In the event of a tie in the final
        round of the elimination tournament, additional boards
        will be used to determine the final winner(s).

VI.  YOUR PROGRAM

    1.  Each move must be made within 10 seconds.  Thus, a total
        game will take no more than 24 moves * 10 seconds * 2 players
        equals 480 seconds or eight minutes.  This will keep the
        running of a tournament manageable.

    2.  Your program (say a.out) must read from standard input and
        write to standard output (the terminal for you non-UNIX folks).
        There are no arguments to the program.  If done properly,
        your program should be able to "play against itself by running:

        cat STARTING_POSITION | a.out | a.out | a.out | a.out ....

        (recall that your program must recognize if it is playing X
         or O by examining the board it starts with)

    3.  Your program may NOT save any history from move to move by
        creating files or any other mechanism.  The only information
        permitted is the current state of the board you are presented with.

    4.  The input (and output) will contain no white space or
        characters other than the 7x7 grid and the NL (X(0a) or \n) 
        at the end of each line for a total of 56 characters.  Further
        description is given above.

VII.  The finals

    1.  There will be an elimination tournament run to determine the
        winner.  The precise rules of the seeding will be published
        midway through the POTM.  

    2.  Each MATCH will consist of two games (as above) and the lower
        score (taken over both games) will be eliminated.  A tie will
        result in the advancement to the next round.  

    3.  In any given round, all matches will occur using the same
        starting board.  Each round may (or may not) use a different
        starting board.

    4.  The final rounds will likely consist of an environment where
        everyone plays everyone else.  This will occur only after
        the number of contestants has been reduced with the single
        elimination tournament.  I will figure all that out in a
        manner which I plan not to disclose until after it's happened.

=============================================================================
    The following items are standard stuff for ALL the POTMs ....
    (but they occasionally will change ... so READ 'EM!)
=============================================================================
I.  About your programming:

    a) As of 9/98 the POTM compiles and executes on and Ultra-2:

        potm potm 5.5.1 Generic_103640-17 sun4u sparc SUNW,Ultra-2
        The Ultra-2 I'm on has 128Mb physical
        memory and 350Mb virtual memory.  It runs Solaris 2.5.1.

        I must insist that your entry be contained in
        a SINGLE ASCII file, mailed in plaintext from a mailer that
        does not split long lines or insert strange characters.  
        Please help keep my life simple!!!

    b) The compilers I have available are (at least):

        Sun WorkShop Compiler C 4.2         (ANSI C Compiler SVID compliant)
        Sun WorkShop Compiler C++ 4.2 
        GNU compilers gcc/g++ version 2.8.1

*** C/C++ Note:  please do not use platform dependent include files
***   (like conion.h for example) since they will cause my compilation
***   to fail.  If YOU need them, consider using ifdefs so that only
***   YOUR compilation will see them ... thanks!

        PERL version 5.004
	Python 1.5.1
        Java, version 1.1.6 of the Java Developer Toolkit from SUN
                (as downloaded to a SPARC workstation)

        FORTRAN compilers from SUN, sorry - no PASCAL support!
        FORTRAN 90: WorkShop Compilers 4.2 10/22/96 FORTRAN 90 1.2
        FORTRAN 77: WorkShop Compilers 4.2 30 Oct 1996 FORTRAN 77 4.2

    All compilation will be done WITHOUT ANY OPTIMIZATION, and the
    standard math library will be loaded (even if not used).  While
    this might not reflect the real world, it is at least consistent.
    No makefiles are permitted, if there are special instructions
    please so indicate in your program header comments.

***      IMPORTANT:  submit early so we can resolve any
***      portability problems!!!  (Particularly if you 
***      are working in a PC environment.

       NOTE: assembly code submissions are NOT acceptable.  I must be
       the one to compile your code so I can check for cheating!

    c) if you wish to submit a shell program, Bourne, Korn, and csh
         are available ... along with any bin or /usr/bin tools that
         are available as generic Unix tools - my judgement!!!
         Also nawk, awk, dc, or whatever.
         (again - submit early in case there are version differences)

    d) Temporary files may be created in /tmp, but MUST be removed
         when you are done ... creation of files anywhere else is
         strictly prohibited.

    e) Maximum size of the source code is roughly 25K characters - 
         different rules may apply for specific POTMS, and 
         comments don't count against you.

    f) Maximum size of executable is 1 Megabyte ... please!!!!

    g) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1

    h)       a    = 0x80000000  = -2147483648
         a - 1                  =  2147483647
         a + 1                  = -2147483647
           {a} is true.  
           {a == 0} is false.

    i) RAND_MAX = 2^15 - 1 (32767) when using the rand() function.

II.  The system testing ....
    
    a) mail me an entry as soon as possible - you can always submit
         another entry if you improve your solution .. but try and
         keep it down to one a week once the porting issues are 
         resolved .... please!

    b) one entry per person (or team) please.  I associate each entry
         name with an email address and a person for communication
         purposes.  Communication is fine - and encouraged - but
         everyone's code should be their own unless there is a
         stated collaboration and a single team entry.  Honor system!
         Use the POTM bulletin board at:
         http://www.sitepowerup.com/mb/view.asp?BoardID=100152

    c) on receipt of your entry, I'll run a system test to make sure
         your program works ... you'll receive the results and
         a weekly standing of how you fared against other entries.
         (I usually will get to new mail once a night but perhaps not!)

    d) please make sure your program works on the system test problem.

    e) your program must perform the task specified within the
       specified time limit (usually ten minutes)
       sys+user time as measured by timex on MY execution system.
       Your time will be provided along with your system test run
       so you can see the differences in speed between your machine 
       and mine.  All execution time measurements used for 
       tiebreakers (if any) will be measured using (sys+user) 
       time via timex (similar to time command).  
       
       ****   NOTE: A code fragment to measure elapsed time
       ****     is available from the POTM-master for the asking.

III.  SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!

   Please email (not uuto, no attachments) your source code to me at:

         enter@att.com                       (preferred)
         hicinbothem@att.com                 (use only as a last resort!)

WARNING!!!  Please be sure your mailer does NOT truncate long lines
    or make any substitutions for characters.  These kinds of problems
    will prevent the program from compiling when I receive it!

    IMPORTANT:  Please use the following (or equivalent) lines at the
    front of the program you mail to me (this will help immeasurably!):

/*  POTM ENTRY:  entryname (something clever please!)        */
/*  Your Name:   First Last                                  */
/*  Your email:  log@machine.att.com (or whatever)           */
/*  compile instructions (if other than "make entryname")    */

    NOTE:  These comments should be referenced in whatever method
    is appropriate for your programming language of choice.

    IMPORTANT:  ENTER EARLY - you will receive weekly standings and
    you will resolve any portability issues early.  You may improve
    your entry at any time by simply sending me another entry - so it
    pays to enter earlier!  (I process most everything in a day or so)

    IMPORTANT:  If you don't hear from me within a week it may
    mean that the mail got screwed up .... please follow up with an 
    inquiry to hicinbothem@att.com ....

Thanks!  If you have any questions, mail 'em to me - if I answer them
I'll include them in the Frequently Asked Questions (FAQ) list I 
circulate with the weekly standings!!!  Don't call me ... please!

WATCH THE FAQ - ESPECIALLY IN THE FIRST FEW WEEKS AS ALL THE STUPID
  ERRORS I MAKE IN THE PROBLEM STATEMENT TURN UP!!!!

Looking forward to your entry!        (remember:  enter@att.com)
=Fred