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