BackgroundBlocksNotationTranscriptsNetwork ProtocolThe ProblemYour TaskAdviceCS61B, Fall 2002 Project #3: Ataxx P. N. HilfingerDue: Wednesday, 4 December 2002 at 24001 BackgroundAtaxx is a two-person game played with red and blue pieces on a 7-by-7 board (in this black-and-white handout, we’ll use black for red and white for blue). As illustrated below, there aretwo possible kinds of move: you can extend from a piece of your own color by laying down anew piece of your color in an empty square next to that existing piece (horizontally, vertically,or diagonally), or you can jump: move a piece of your own color to an empty, non-adjacentsquare that is no more than two rows and no more than two columns distant. In either case,all opposing pieces that are next to the previously empty destination square are replaced bypieces of your color. Here is an example of a starting position (in the middle) and two possiblemoves with the same piece. Squares marked × show black’s other possible jumps with thatpiece:Starting positionAfter black move to adjacent square× × × ×× ×× ×× ×× ×After black jumpAt the beginning of the game, we start with pieces in all four corners:7654321a b c d e f gThe red (here, black) player goes first, and play alternates until no more moves are possible.You are allowed to skip a move only if you have no legal move. The winner is the player whohas the most pieces at the end of the game (thus, you don’t automatically lose just becauseyou can’t move).1Project #3 21.1 BlocksTo make things even more interesting, you can place a set of blocks symmetrically about thecenter of the board before playing. These are “pre-filled” squares that may never be movedto (the blocks themselves never move). In the illustration below, the left figure is an exampleof a starting configuration with 11 blocks. The pattern of blocks in the 4 × 4 square in theupper-left is always reflected across the middle row and the middle column. Therefore, todescribe the configuration of blocks being used, we need merely indicate which squares in theupper-left 4 × 4 portion of the board have blocks in them. To do so, we denote these squareswith the digits 1–6 and the letters a–h and x as shown in the illustration on right below.Thus, the configuration on the left would be described “3ghx”. A board with no blocks isdenoted by “0”.Initial configuration 3ghxd e 4a g f 5b c h 61 2 3 xDesignations of possible block positions1.2 NotationWe’ll denote columns with letters a–g from the left and rows with numerals 1-7 from thebottom, as shown in the illustration of the initial position on the previous page. An ordinarymove consists of two positions separated by a hyphen in the format “c0r0–c1r1” (e.g., g1-f2).The first position gives a piece owned by the current player, and the second gives an emptysquare to which the piece jumps or extends. A single hyphen (surrounded by whitespace)denotes a case where one player must skip a move.1.3 TranscriptsA transcript of a game consists of a string describing the configuration of blocks (see §1.1)followed by a sequence of moves (as described in §1.2). If the transcript denotes a completegame, then the last item must be the final score, in the form Nr–Nb, where Nris the numberof red pieces and Nbthe number of blue pieces (e.g., 22-27, which indicates a win for blue),or the word resign, which indicates that the player who would normally have moved at thatpoint decided to resign (and lose) instead.Project #3 32 Network ProtocolYou are going to build a program that can play other programs, possibly on other machines.To do this, we need to agree on a common protocol (common conventions for sending mes-sages) used to communicate moves.First of all, we’re providing you with a standard mailbox type for actually sending andreceiving messages. Basically, a mailbox is a container with an externally visible name (aString) to which one can send and from which one can receive messages (which in our casewill just be strings containing moves in the transcript format described previously plus afew additional commands). Just as for input from the terminal, programs asking to receivemessages wait until a message actually arrives. A program can send to and receive frommailboxes it creates (so that the mailbox is just a glorified queue data structure), or it cansend to and receive from mailboxes created by other programs, even those running on othermachines, and it’s all relatively transparent (so that if you write things properly, the samemethods will work against both local and remote opponents.)As far as the protocol is concerned, the two players in a game are called the host and theclient. Each of the two players sends the following sequences of messages to the other.1. The string ‘red’ or ‘blue’ depending on whether the player that receives this stream issupposed to play red or blue.2. A description of the blocks configuration (see §1.1).3. The rest of the transcript (that is, the two players’ moves, including the score or theword ‘resign’ at the end).4. The message quit.The host decides items 1 and 2. If item 1 is “red”, the client echoes back “blue” andvice-versa. The then client echoes back item 2. After that, each side sends its moves andalso echoes back the opposing player’s responses, so that, except for message 1, both playersreceive the same sequence of messages. The reason for this redundancy is simply to allow you(if you want) to write one module that can display the board by looking at just one messagestream, whether you are red or blue, host or client.If you ever discover that the other player has made an illegal move, send the message‘error’ and then act as if you never received the message in the first place. Your machineplayers must not send illegal moves.You send these messages by using the deposit method in ucb.util.mailbox.Mailbox toput them into a Mailbox that the opponent provides. You receive messages from the opponentby using the receive method on your own Mailbox. When you are done playing, be sure toclose your receiving Mailbox. Also, be prepared at any time to have the opponent “disappear”on you (this is indicated by an exception during the deposit or receive operation). Thisis especially apt to happen during a ‘quit’ message, but might happen at any time. Yourprogram can safely exit at that point.Project #3 4Annoying, sticky point. Do not send quit until you receive the score
View Full Document
Unlocking...