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












Make your own free website on Tripod.com