SHOWDOWN
You are blindfolded. You are in one corner of a rectangular room.
Your opponent is in the opposite corner. Moving one square at a time,
can you occupy your opponent's home square before your home square is
captured?? Sound trivial?? Then consider adding radar, wall-building,
and sleep-guns. Design a program that can play this game, win the
elimination tournament, and gain POTM fame!
=========================== THE DETAILS ======================
(Please do not be afraid of all these details ... the intent of most POTMs
is straightforward, but I've found that I need to be very explicit to try
and close any "loopholes" for all you "requirements lawyers" out there.)
*** IMPORTANT: this one may seem to have alot of rules,
but I found them necessary to fully define the problem!
It seems to me that the emphasis is on TESTING, TESTING,
TESTING ... just two reminders of items below:
1) send entries to enter@potm.ffast.att.com
2) be sure to include the header in your program with
the program name and your name (at least!)
I. WHAT DOES YOUR PROGRAM HAVE TO DO?
Your program will read standard input, and write to standard output.
The first time your program runs, it will be told which square
you start on - your program will then output a legal turn from the
options below (to standard output). Your program may record
anything it wishes in a temporary file (provided by ARG1) and
then must exit - it only has a single turn per execution.
On your second execution, the result of your first turn will be
reported to your program on standard input ... your program may
consult (and/or modify) the temporary file in order to deduce
your best second turn. Your program takes the second turn and
exits. The next time around, you see the results of your previous
turn and take another. And so on until one player or another wins
(or until 100 turns have elapsed).
Your moves are given to a "mediator" program, who will tell you
the results of your turn. You and your opponent never communicate.
II. TELL ME MORE ABOUT THE "PLAYING BOARD"
The playing board will be 9 ROWS (labeled A,B,C,D,E,F,G,H,I) by
26 COLUMNS (numbered 1 through 26). This means there will be a
total of 9x26=234 legal positions on the playing board. You will
start the showdown at either position A-1 (indicating that you get
to go first) or I-26 (indicating you are going second).
Graphically:
1 1 2 2
1 5 0 5 0 6
A X-------------------------
B -------------------------- 9 rows by 26 columns - always.
C -------------------------- You will start at either X or Y.
D -------------------------- If you start at X, your goal is
E -------------------------- to get to Y. if you start
F -------------------------- at Y, your goal is X.
G -------------------------- Rows are expressed as upper case
H -------------------------- letters (A-I), columns
I -------------------------Y are numbered 1 through 26.
III. WHAT CAN I DO ON MY TURN???
Each execution of your program is a SINGLE TURN. You will announce
your turn on standard output to the "MEDIATOR" ... your opponent
will NOT know what you chose to do on your turn. It is completely
up to you to keep track of where you are through use of a
temporary file and to use this information to take legal turns!
On each execution, your program MUST ouput one of the following:
MOVE row column Means that you want to move to the row
and column indicated. The row and column
indicated MUST be one square vertically
or horizontally from your current position.
RADAR Means that you want to know the row and
column of your opponent before their next
turn is taken.
WALL row column Means that you want to build a WALL on
the position indicated by (row,column).
===> (row,column) may be anywhere on the board.
ZAP row column Means that you want to send out a "ray".
The ray will travel from your current
===> position toward the row and column indicated.
These two positions MUST describe a vertical
or horizontal path. The ray will continue
until it "hits" something. The first thing
the ray "hits" will be affected as follows:
a WALL will be removed by the ray; your
OPPONENT will be "put to sleep" for a single
turn (your opponent will not know they were
hit, but you will get another turn before
they go again). If the ray reaches the end
of the playing area without hitting anything,
===> there is no effect. Only the first thing hit
===> will be affected.
HELP will return YOUR current row and column if
you get lost!
IV. WHAT KINDS OF INPUT WILL MY PROGRAM RECEIVE?
===> On all turns, your program will receive both <===
===> a standard input line and an argument. <===
The agument will indicate the full path name of a file which
you may use for any records you care to keep over the course
of the game ... ONLY this file may be used. You may put anything
you wish in this file in whatever format you choose. When your
program begins, it will find the file exactly as you left it on
your previous turn. The file name will change for every game but
will be the same for any single game. (At a minimum, you will
need to store your own position in this file - this will be the
only way to keep track of where you are!)
===> The standard input on the FIRST turn will be one of the following:
INIT A 1 indicating you go first [or]
INIT I 26 indicating you go second
For example, your first execution may be as follows:
echo "INIT I 26" | your.program /tmp/file93344 | mediator
(where your.program is your executable and mediator is the
scoring program the POTM-master provides - you'll
have to write something like this if you want to test!)
===> On each subsequent turn, your program will receive feedback
from the mediator on the results of your previous turn (so
you might want to try and remember - in the file - what your
previous turn WAS!!). For each valid output, here are the
possible inputs your program will receive next time:
PREVIOUS TURN POSSIBLE INPUTS ON NEXT TURN (RESULTS)
============= ======================================
MOVE row column OK if move was valid and made
ERROR if move was illegal. You
do NOT move in this case.
OUCH if (row,column) was valid
but contained a WALL. You
do NOT move in this case
HELLO if (row,column) was valid
and your opponent was there!
You do NOT move in this case
RADAR AT row column will indicate the row and
column of your OPPONENT.
Note that your opponent may
move from this spot by the
time you receive this result!
WALL row column OK if wall is now at (row,column)
(the position may have been
empty or may have already
contained a wall)
ERROR if (row,column) is illegal:
off the board or at your
current location.
OOPS you tried to drop a wall on
the square where your opponent
was. No wall will be built.
ZAP row column MISS nothing was hit! The ray
went to the end of the field.
BOOM you hit a wall and removed it.
HIT you hit your opponent. your
opponent will miss a turn but
won't know about it!
ERROR you tried to ZAP somewhere
other than the row or column
===> you are currently on. (Or you
===> tried to ZAP yourself)
HELP LOC row column tells you that you are now
at the row and column given.
V. LIMITS ... IMPORTANT THING TO KNOW ABOUT THE CONTEST!!!
1. Each player will get the same number of turns ... if player
one wins the game, player two will get one more turn.
2. A game will consist of at most 100 turns for each player.
3. During the system tests, there will be only a single game -
your entry will go first and will play against a
standard entry written by the POTM-master
4. Based on the last system test runs, all entries that complete
the system test game will be "seeded" according to the
scores they achieve during system test.
5. The finals: All seeded entries will compete in a single
elimination tournament until only a single entry remains.
Each one-on-one "match" will consist of two games - each
of the players will have a chance to go first. After
these two games, the scores of the two games are added
and the better score moves on to the next round.
Scores are not carried into the next match ... every match
starts the two competitors evenly.
6. on the FIRST finals round, some of the top-seeded entries may
receive a "bye" (automatic advancement to next round) in
order to insure that the number of players remaining
in the second round is a power of two. From that point
on there will be no byes.
EXAMPLE: if there are seven entries seeded 1 through 7:
ROUND 1 (7) ROUND 2 (4) FINALS (2)
1 gets a bye
a) 2 plays 7 d) 1 plays winner of c
b) 3 plays 6 d vs. e
c) 4 plays 5 e) winner of a plays
winner of b
===> Revision: Note that some form of standard seeding will be used based
===> on your position after the system testing. It will be to your
===> advantage to do well during the system tests in order to receive
===> bye rounds and/or weaker opponents.
7. SPECIAL RULE: Previous winners WILL COMPETE with everyone
else - there is NO SPECIAL TOURNAMENT OF CHAMPIONS!
VI. THE SCORING - HOW TO WIN!
Each game will result in a score for both players. The score
will be computed as follows:
1000 bonus points awarded for a "win" (you got to your opponent's
home square and your opponent did NOT get to yours.)
500 bonus points awarded for a "tie" (both players got to their
opponent's home square in the same number of moves - this
is possible since player TWO gets a final turn if player
ONE reaches the destination first)
15 bonus points awarded each time your opponent bumps into a wall
that either program constructed. (YOU get points every
time your opponent gets an OUCH - even if they bump into
their own walls.)
7 bonus points awarded each time you ZAP your opponent and put
them to sleep for a turn.
ONLY IF THERE IS A WINNER OR A TIE:
3*(100-N) points are awarded to the WINNER, or, in the event of a
tie, to BOTH players. The intent is to award quick wins!
Since the quickest game is 33 turns, you can earn up to
3*67=201 points this way - but ONLY if you win!
(NOTE: this is based on TURNS ... not necessarily MOVES)
ONLY IF THERE IS NO WINNER AFTER 100 TURNS, BOTH PLAYERS ARE AWARDED:
11 points per square based on the number of rows and
columns the final position is AWAY from the starting
square at the game's conclusion ... (the closer you are
to your opponent's home, the more points you get). This
score is computed by adding the rows and columns. (You can
get at most 11*(7+25)=352 points this way without winning)
IMPORTANT: I have received much mail about the scoring. Particularly
about the fact that repeated ZAPPING may be rewarded too heavily.
While this is probably true, it IS what it IS!! While this may
change the problem from a MOVEMENT game to a ZAP-AVOIDANCE game,
that will be for the participants to figure out! As always, I
am surprised by the strategies and counter-strategies of the players
(many of which I am unable to predict when defining the problem!!!).
After all, a SHOWDOWN in the Wild-Wild-West didn't "really" involve
exchanging places with your opponent, did it?
HOW WILL I RESOLVE TIES? (Well, I hope there aren't any, but just in case):
Tiebreakers - in order:
a) fewest MOVEs (wandering is bad)
b) fewest OUCHs (hitting things is bad)
c) most RADARs (just for the heck of it)
d) most WALLs (why not???)
e) smallest executable (it will NEVER get to this!!!)
IF ALL THIS ISN'T CONFUSING ENOUGH FOR YA, I'LL MAKE UP SOME MORE!!!
VII. INPUT/OUTPUT
1) The output to the mediator must be ONLY in the form described
above. Your output must appear on standard output.
2) NO OUTPUT to stderr is permitted.
3) All input from the mediator arrives on standard input.
Input will conform to the rules above. There will
also be a single argument containing the pathname
of a temporary file you may use to save information
between turns. Neither the mediator nor your
opponent will have access to this file.
VIII. LOOPHOLE CLOSING
1) You may not attempt to read the other person's temp file.
2) You may not communicate outside the POTM machine.
3) Once your program compiles successfully you may not submit
more than once a week in an effort to deduce the
playing habits of the system test player. (Tuning
your program specifically to improve your seeding is
not playing fair.)
4) You may NOT attempt to save information from one game to
another ... no files other than the one in the
argument may be created or read.
5) If you're thinking of something sneaky ... ask first! I'll
give you a ruling and keep it private!
IX. READ THE Frequently Asked Questions (FAQ) list distributed every
week ... it often contains corrections to this problem statement!
(Or stuff I just plain forgot!!!)
=============================================================================
The following items are standard stuff for ALL the POTMs ....
(but they occasionally will change ... so READ 'EM!)
=============================================================================
I. About your programming:
a) I compile on one machine (usually) and execute on
another as follows:
compilation machine: SunOS 5.3 Generic_101318-59 sun4m sparc
execution machine : SunOS 5.3 Generic sun4c sparc
b) The compilers I have available are (at least):
SPARCompiler C++ 4.0
SPARCompiler C ANSI C compiler
SVID compliant under SunOS 5.x
gcc/g++ version 2.7.2
PERL version 5.002
Java version 1.0
Scheme48 - a Lex variant
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!!!
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!!!
awk and nawk are OK too.
(again - submit early in case there are version differences)
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) Maximum malloc'able space is a bit over 50 Meg ....
h) sizeof(short)=2; sizeof(int)=4; sizeof(long)=4; sizeof(char)=1
i) a = 0x80000000 = -2147483648
a - 1 = 2147483647
a + 1 = -2147483647
{a} is true. {a == 0} is false.
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!
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!)
Your seeding for the finals will be determined based on your
last submission before the deadline.
d) please make sure your program works in the right way ... it
must accept input and generate output as described above ...
you gotta test, test, test ... it's up to YOU!!!!
e) your program must average no more than 10 seconds per turn over
the course of a 100 turn game. My intent is not to measure too
hard ... but programs which appear to abuse the total will
be measured and asked to speed up. If you have a compute
intensive algorithm, you may want to ask me for some timing runs.
Hopefully - this won't be an issue for this POTM!!!
III. SENDING ME YOUR ENTRY - PLEASE USE EMAIL!!!
Please email (not uuto, no attachments) your source code to me at:
enter@potm.ffast.att.com (preferred)
hicinbothem@att.com (use only as a last resort!)
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: If you submit a shell program, please include these lines
with a leading "#" and indicate which shell to run it under!
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 few days - 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@potm.ffast.att.com)
=Fred