web/index.html

   1 <html>
   2 <head>
   3   <title>Stratego Based Programming Competition</title>
   4 </head>
   5
   6 <body>
   7
   8 <h1> Quick Details</h1>
   9 <p> The git repository is listed on <a href="http://git.ucc.asn.au/"/>The UCC git page</a> as "progcomp2012.git" </p>
  10 <p> We will use the same mailing list as last year (progcomp). </p>
  11 <p> </p>
  12 <p> There is a #progcomp irc channel on the ucc irc server where you can ask questions or help with setting things up. </p>
  13
  14 <h1> Stratego </h1>
  15 <p> <a href="http://www.edcollins.com/stratego/"/>This site</a> explains what Stratego is. </p>
  16 <p> I have never played this game. But it sounds cool. So naturally I decided to make a competition based on it. </p>
  17 <p> My original idea was to force people to write AI for <a href="http://matches.ucc.asn.au/Astral"/>Astral</a>, but then I realised that that was a terrible idea. </p>
  18
  19 <p> There is in fact, already a <a href="http://www.strategousa.org/wiki/index.php/2010_Computer_Stratego_World_Championship"/>World Stratego Championship</a>. However, you have to use Metaforge. Using stdin/stdout will probably make it slightly easier for us. And its better to work out how to do these things ourselves. </p>
  20
  21 <h2> Programming Competition </h2>
  22 <p> Create an AI to play Stratego. </p>
  23 <p> Yes, I <i> know </i> people are inherently lazy and won't be bothered to do this. But so far in setting this up I have learn quite a lot about inter-process communication, so thats good. </p>
  24 <p> Programs are written independently and interface through stdin/stdout with a manager program, which queries them on setup and moves. </p>
  25 <h3> The Manager Program </h3>
  26 <p> The manager program takes two executable paths, one to each of the AI programs to pit against each other. <p>
  27 <p> It first requests each program to print the setup of its pieces to stdout. Then the programs take turns (Red, then blue, etc) to move one piece. </p>
  28 <p> The first program is Red (top of the board), the second is Blue (bottom of the board). </p>
  29 <p> The manager program now has switches to enable/disable graphics and set the move speed of the match. </p>
  30 <p> Use "-g" to enable graphics (by default disabled) and "-t TIMEOUT" to set the move speed (default 0 (as fast as possible)). </p>
  31 <p> <b> This program now has a <a href="http://matches.ucc.asn.au/progcomp2012/manager/manual.txt"/>manual page</a> </b> </p>
  32
  33 <h2> Messaging Protocol and Rules </h2>
  34 <p> <b> The rules are now also available in the <a href="http://matches.ucc.asn.au/progcomp2012/manager/manual.txt"/>manual page</a> of the manager program </b> </p>
  35 <h3> Setup </h3>
  36 <h4> Query </h4>
  37 <p> The manager program prints one line in the following format to each program: </p>
  38 <p>     COLOUR OPPONENT BOARD_WIDTH BOARD_HEIGHT </p>
  39 <p> At the moment BOARD_WIDTH and BOARD_HEIGHT are always 14. The arguments are followed by a newline. </p>
  40 <p> OPPONENT will be the identity of the opposing AI program. </p>
  41 <h4> Response </h4>
  42 <p> The AI program queried must print <i>four</i> (4) lines containing its initial setup. Each character represents a unit or empty space. The characters are as follows: </p>
  43 <p> </p>
  44
  45 <p><b>Warning:</b> I have changed the characters from mostly letters to mostly digits, indicating the actual worth of a piece</p>
  46 <table border="1">
  47 <tr> <th>Name</th> <th>Character</th>  <th> Number </th> <th> Notes </th> </tr>
  48 <tr> <td>Marshal</td> <td>1</td>  <td>1</td> <td> Dies if attacked by the Spy </td> </tr>
  49 <tr> <td>General</td> <td>2</td>  <td>1</td> <td> </td> </tr>
  50 <tr> <td>Colonel</td> <td>3</td>  <td>2</td> <td> </td> </tr>
  51 <tr> <td>Major</td> <td>4</td> <td>3</td> <td> </td> </tr>
  52 <tr> <td>Captain</td> <td>5</td> <td>4</td> <td> </td> </tr>
  53 <tr> <td>Lietenant</td> <td>6</td> <td>4</td> <td> </td> </tr>
  54 <tr> <td>Sergeant</td> <td>7</td> <td>4</td> <td> </td> </tr>
  55 <tr> <td>Miner</td> <td>8</td> <td>5</td> <td> Defuses Bombs and survives. </td> </tr>
  56 <tr> <td>Scout</td> <td>9</td> <td>8</td> <td> May move any number of times in a single direction. </td> </tr>
  57 <tr> <td>Spy </td> <td>s</td> <td>1</td> <td> If the Spy attacks the Marshal, the Marshal is destroyed. </td> </tr>
  58 <tr> <td>Bomb</td> <td>B</td> <td>6</td> <td> Immobile. Destroys both self and any unit that attacks the Bomb. </td> </tr>
  59 <tr> <td>Flag</td> <td>F</td> <td>1</td> <td> Immobile. Capture the opponent's flag to win. </td> </tr>
  60 <tr> <td>Unoccupied</td> <td>.</td> <td> </td> </tr>
  61 <tr> <td>Obstacle</td> <td>*</td> <td> </td> </tr>
  62 </table>
  63 <p> The AI program can't place any obstacles, and must at least place the Flag for its setup to be valid. </p>
  64 <p> RED will always occupy the top four rows of the board, and BLUE occupies the bottom four rows. </p>
  65
  66 <p> All pieces except the Scout, Bomb and Flag can move 1 square horizontally or vertically (not diagonally). </p>
  67 <p> When two pieces of different ranks encounter each other, the piece with the highest rank (lowest numbered rank!) is the victor, unless a special rule applies. </p>
  68 <p> When two pieces of <i>equal</i> rank encounter each other, the victor is randomly chosen </p>
  69 <p> Pieces of the same colour may <i>not</i> pass through the same squares </p>
  70
  71 <h3> Turns </h3>
  72 <h4> Query </h4>
  73 <p> RED starts the game. The manager queries RED to make the <i>first</i> move by printing: </p>
  74 <p>     START </p>
  75 <p> Followed by a WIDTH*HEIGHT grid. '*' or '#' characters are used to indicate positions of unknown (BLUE/RED) enemy units. </p>
  76
  77 <h4> Response </h4>
  78 <p> The AI program must respond with a <i> single </i> line of the following form: </p>
  79 <p>     X Y DIRECTION [MULTIPLIER]</p>
  80 <p> Where X and Y represent valid co-ordinates, upon which there is a piece of the AI program's colour. </p>
  81 <p> DIRECTION must be either "UP", "DOWN", "LEFT", or "RIGHT", and is, obviously, the way the piece is supposed to move </p>
  82 <p> MULTIPLIER is optional, and should only be given if the AI program is moving a Scout. Scouts may move multiple times in the same direction if possible. </p>
  83 <p> </p>
  84
  85 <h4> Outcome </h4>
  86 <p> The manager program will indicate the result of a move by responding with: </p>
  87 <p>     X Y DIRECTION [MULTIPLIER] OUTCOME </p>
  88 <p> Where X, Y, DIRECTION and MULTIPLIER are as above. </p>
  89 <p> OUTCOME signals the result of the turn, and will be one of the following: </p>
  90 <table border="1">
  91         <tr> <th> OUTCOME </th> <th> Description </th>  </tr>
  92         <tr> <td> OK </td> <td> The piece was successfully moved, nothing eventful happened </td> </tr>
  93         <tr> <td> FLAG </td> <td> The piece moved onto the opposing Flag; the game will end shortly </td> </tr>
  94         <tr> <td> KILLS RANK1 RANK2 </td> <td> The piece landed on a square occupied by an enemy, and destroyed it, moving into the square </td> </tr>
  95         <tr> <td> DIES RANK1 RANK2</td> <td> The piece landed on a square occupied by an enemy, and was destroyed. The piece is removed from the board. </td> </tr>
  96         <tr> <td> BOTHDIE RANK1 RANK2</td> <td> The piece landed on a square occupied by an enemy, and <i>both</i> pieces were destroyed. </td> </tr>
  97         <tr> <td> ILLEGAL </td> <td> The moving player attempted to make an illegal move, and has hence lost the game. The game will end shortly. </td> </tr>
  98 </table>
  99 <p> If printed, RANK1 and RANK2 indicate the ranks of the moved piece and the defending piece (the piece who occupied the destination square) respectively. </p>
 100 <p> Originally RANK1 and RANK2 were never printed, but when I actually tried to write an AI myself I got very annoyed at this restriction... indicating it was probably a bad idea :P </p>
 101
 102
 103 <h4> Additional Turns </h4>
 104 <p> The Outcome of each turn is printed to <i>both</i> AI programs. </p>
 105 <p> The state of the board is then printed to BLUE, who makes a move, then the process repeats. </p>
 106
 107 <p> </p>
 108
 109 <h4> Overview </h4>
 110 <p> This is a description of the signals the AI programs recieve, in order:
 111 <ol>
 112         <li> Previous turn's outcome (other player's move) OR "START" if it is the first turn </li>
 113         <li> A BOARD_WIDTH*BOARD_HEIGHT grid indicating the board state, with the AI program's own pieces revealed </li>
 114         <li> After the AI program makes a move, the outcome is printed to it, and the other program, which continues from step 1 </li>
 115 </ol>
 116 <p> I am considering removing Step 2, since <i>all</i> information needed for an AI to keep the board state is contained in the initial board state and then the movement result messages </p>
 117
 118 <h3> End Game </h3>
 119 <h4> Query </h4>
 120 <p> At the end of the game, the manager program outputs the following: </p>
 121 <p>     VICTORY </p>
 122 <p> To the winning AI program, and </p>
 123 <p>     DEFEAT </p>
 124 <p> To the losing program. </p>
 125 <p> Both programs then have 2 seconds to exit succesfully, or the manager will kill them. </p>
 126 <h3> Invalid Responses and Timeouts </h3>
 127 <p> If any program fails to respond correctly, or gives an invalid move, or does not respond within 1 second, it will lose by default. </p>
 128 <p> In this case, the message </p>
 129 <p>     ILLEGAL </p>
 130 <p> will be sent to the malfunctioning program, and </p>
 131 <p>     DEFAULT </p>
 132 <p> to the other program </p>
 133 <p> Both programs then have 2 seconds to exit succesfully, or the manager will kill them. </p>
 134
 135 <h2> Modifications/Clarifications to Rules </h2>
 136 <p> Refer to <a href="http://www.edcollins.com/stratego/"/>This site</a> for the original rules again </p>
 137 <p> Currently, the pieces taking part in the combat are not revealed; only the outcome of the combat is revealed. In a human game, the pieces would normally be revealed. I am planning to reveal the pieces, since not revealing pieces significantly reduces the value of low ranked pieces (normally used for working out enemy piece values). </p>
 138 <p> It is up to the AI program to keep track of pieces. The manager program will only reveal the identity of the AI program's own pieces; the other player's pieces will be marked with * or # characters. </p>
 139 <p> In a traditional game, two pieces of equal value will both be destroyed in combat. Currently, only one piece is destroyed and the outcome is randomly chosen. </p>
 140
 141 <h2> Example Programs </h2>
 142 <h3>"Dummy" AI</h3>
 143 <p> Dummy randomly moves pieces. It attempts to not make illegal moves (although sometimes it still does). </p>
 144 <h3>"Forfax" AI</h3>
 145 <p> Forfax iterates through all possible moves and allocates a score between 0 and 1 to each move based on how desirable the move is. It then selects the highest scoring move. </p>
 146 <p> Forfax is pretty terrible, but can beat the Dummy AI <i>most</i> of the time. </p>
 147 <p> It is possible Forfax can be greatly improved by altering the scoring algorithms. </p>
 148 <p> Since we don't want the Sample AIs to beat every entrance, I'm not really going to try and improve Forfax unless I get bored. </p>
 149 <p> If you are writing an AI in C++, Forfax already contains a lot of useful functions. </p>
 150
 151 <h2> Longterm Scoring </h2>
 152 <p> I haven't started a system for pairing AI's and keeping track of scores and winners etc yet </p>
 153 <p> I'll probably have a bash script that chooses who will play, and stores all the scores in files. I've done this before for a BrainF*** based "survival of the fittest" style thing, so I can probably recycle it </p>
 154 <p> </p>
 155 <p> I believe it will make things more interesting if programs are allowed to keep state of who they have played, and the various tactics used. </p>
 156 <p> Its kind of hard to implement this... at the moment programs are killed every time a game finishes</p>
 157 <p> Perhaps it will be easier if each program is allowed access to one directory, where it can create and read files? </p>
 158 <p> This would allow me to keep the manager program which actually plays the games seperate from the program for scoring and matching of opponents </p>
 159 <p> There'd probably be security issues with that though. </p>
 160 </body>
 161
 162 </html>