BackgroundNotationThe ProblemCommunicating with a Remote ProgramAdviceWhat to Turn InOptional: The GUIOptional: Minimax SearchesCS61B, Fall 2001 Project #3: Amazons P. N. HilfingerDue: 30 November 20011 BackgroundThe game of Amazons is a simple, but rather interesting board game, usually for two players. Theboard is a 10 × 10 checkerboard. Each player gets four pieces, traditionally red for the player whomoves first, and blue for the other. Initially, the board is set up as in the diagram on the left ofFigure 110987654321a b c d e f g h i j10987654321a b c d e f g h i jFigure 1: On the left: an Amazon board showing the standard numbering of squares, and the initial placementof the pieces. The light pieces are red; the dark are blue. On the right: the board that results after the two movesd1 d7 (g7) and d10 c9 (h4).Each move consists of two parts: first, a player moves one of his pieces (“amazons”) any non-zero number of squares in a straight line horizontally, vertically, or diagonally, with the restrictionthat the piece may not move onto or through an occupied square (pieces are not captured in thisgame; the board keeps getting fuller). Next, the piece that moved “throws a spear” from her finalposition1. Spears move exactly like pieces, and are subject to the same restrictions. The spearsticks permanently in the (previously empty) square in which it lands. That square is counted asbeing occupied for the rest of the game (so no piece or spear may move through it). For example,the right diagram in Figure 1 shows the result of two moves. From the initial position, red movedfrom d1 to d7 and from there threw a spear to g7. Then blue moved from d10 to c9, and fromthere threw a spear to h4.A player who has no legal move loses. For example, after blue moves a7 a6 (a7) in Figure 2,he will have used up all his moves, and red (who still has plenty of room) will win after his nextmove.1.1 NotationA square is denoted by a column letter followed by a row number (as in e4). An entire move thenconsists of the starting and ending position of the piece that is moved, followed, in parentheses,1Accounts vary as to whether this weapon is an arrow or a bullet or what. I choose a spear, since that typicallytends to be about as long as a person in real life, and hence, I figure, as long as a piece in game life.1Project #3: Amazons 2Figure 2: A lost position for blue. After a7 a6 (a7), blue has no move10987654321a b c d e f g h i jby the position to which the spear is thrown. Thus, d10 c9 (h4) means “Move from d10 to c9and then throw a spear to h4.”Transcripts consist of sequences of lines like this:# Jack Jill1. d1 d7 (g7) d10 c9 (h4)2. g1 c5 (e7) g10 i10 (d5)Anything after a ‘#’ to an end of line is a comment, which is ignored. Otherwise, a transcript isin free form; whitespace may be used freely within a line, and is, in fact, optional.Transcripts may be used as input to the program (the -i switch described in §2). The machineshould print all moves except the human player’s input on the standard output using the transcriptformat (so that when the machine plays itself with -m, you should get a complete transcript ofthe game on the standard output). When using the GUI interface to your program, you shouldalso print a complete transcript of the moves on the standard output. When one side wins, theprogram should print out one of# Red wins.# Blue wins.# Red resigns.# Blue resigns.as appropriate.2 The ProblemYour job is to write a program to play Amazons. Your program must be called amazons. It shouldallow command lines of the following form (brackets ([]) indicate optional arguments):java amazons [-i INITIAL] [-b] [-S SEED] [-m] [-t] [NAME]This sets up a game between two entities that we will call “the player” and “the opponent.” Themeanings of the various options are as follows:Project #3: Amazons 3-i INITIAL Read an initial sequence of moves from the file INITIAL. The moves are in thetranscript format described in §1.1. The program makes the moves from the file and thenthe game continues normally. This option is ignored if you are joining an existing game (seethe NAME parameter below).-b The player gets the blue pieces, and therefore moves second. By default, the player gets thered pieces, unless it joins a remote game (see below).-m The machine is the “player” (that is, the program figures out what moves the player is supposedto make). Otherwise you (the human user) are the player.-t Use a text interface on the standard input and output for making and reading moves. Otherwise,uses a GUI (Graphical User Interface).-S SEED Use the value SEED (a long integer) as the initial seed for the random number generatorused by the program. If this option is not supplied, the program picks an arbitrary (andpresumably unpredictable) seed for making machine moves. The idea is that your programwill behave identically each time it is given the same seed value. This is important whenyou are trying to reproduce errors in your program, for example.NAME When this argument is present, the opponent is a remote player (that is, another program,possibly running on a different machine). NAME has either the formTAG or TAG : HOSTwhere TAG is some arbitrary word (composed of letters and digits), and HOST is a host name(like torus.cs). When no host is specified, your program is the originator of the game andgets to choose its color (red by default, or blue if -b is specified). Otherwise, your programjoins an existing game with the given TAG on the given HOST, and accepts whatever color theremote program tells it to. Without the NAME option, the program selects the opponent’smoves.Following standard UNIX conventions, all the ‘-’ arguments can appear in any order, and theNAME argument, if present, appears at the end.What all this means is thatjava amazons -tlets you play (as red) against the machine using the terminal, andjava amazons -m -tplays the machine against itself, printing the moves on the terminal. You can originate a gamethat another program (or a human, possibly on another machine) can join with something likejava amazons -t ourgame # You playjava amazons -m -t ourgame # Your program playsjava amazons -t -b ourgame # You play as bluejava amazons -t -m -b ourgame # Your program plays as blueAnother player can connect to this game by typing something like this:java amazons -t ourgame:torus.cs # If he wants to playjava amazons -m -t ourgame:torus.cs # If he wants his program to
View Full Document
Unlocking...