Homework #2
|
Fall 2003
|
Turn these in at the end of class or in room 001A Computer Science on or before the due date.
1. Consider the following search problem:
The states are the vertices of this graph. The start state is S, and the goal state is G. The actions permit movement along directed edges with costs as indicated. (For instance, the cost of moving from S to U is 2; the cost from U to V is 9.) The numbers in blue by each vertex indicate heuristic h values. (For instance, h(S)=9; h(U)=10.)
a. Show that this choice of h is consistent.
b. Draw the search tree that would result from running greedy best-first search. Also number the nodes of the search tree in the order in which they would appear. For instance, place the number 1 by the start node (associated with the start state S).
c. Do the same thing for A*. Also indicate the g and f values associated with each search node.
2. Prove that if h never overestimates the true path cost to the goal by more than some constant c, then A* using h returns a solution whose cost exceeds that of the optimal solution by no more than c.
3. Exercise 4.7 in R&N.
4. Exercise 6.1 in R&N.
5. Exercise 6.3 in R&N with the following modifications:
a. You can write states as indicated in R&N, or you can do something more natural but clear. For instance, you can draw the position of A and B, with blanks for unoccupied squares. Thus, the start state would be written:
A B
c. Rather than "briefly sketching" how to fix the minimax algorithm, describe in some detail how you would compute minimax values for games with loops, giving pseudocode and a clear justification why your algorithm works in general for games with a finite number of states. You may wish to think about other games, such as a modification of the game in R&N Figure 6.14 in which players are permitted to "pass" (not make any move) when its their turn.
d. Skip this part.
In this programming assignment, you will implement the algorithm you came up with in Problem 5 above, and apply it to tic-tac-toe with moveable pieces. Code has been provided for the nitty-gritty of creating game states, moving pieces around, input/output, etc. You only need to implement a player based on your search strategy which will play the game optimally. We also are providing other players described below, as well as a referee program for playing two players against one another.
Martin Gardner, writing in 1959, described this game as follows:
Variants of ticktacktoe more exciting mathematically than the present form were played many centuries before the Christian era. All of them employ six counters and can be played on the board pictured in Figure 18 -- one player using three pennies, the other, three dimes.
In the simplest form, popular in ancient China, Greece and Rome, players take turns placing a counter on the board until all six are down. If neither player has won by getting three in a row (orthogonally or diagonally) they continue playing by moving on each turn a single counter to any adjacent square. Only moves along the orthogonals are permitted.
Ovid mentions this game in Book III of his Art of Love, including it among a group of games which he advises a woman to master if she wishes to be popular with men. The game was common in England in 1300 when it was called "three men's morris," the ancestor of nine, eleven, and twelve men's morris, or "mill" as it is usually called in the United States today. Since the first player has a sure win by playing first in the center, this opening is usually barred. With this restriction the game is a draw if played rationally, but it swarms with potential traps on both sides.
A variation of this game permits moves to neighboring cells along the two main diagonals of the square. A further extension (attributed to early American Indians) allows any counter to move one step in any direction, orthogonally or diagonally (e.g., a move can be made from cell 2 to cell 4). In the first version the initial player can still force a win if allowed to open on the center, but the second variant is probably a draw. A free-wheeling version called les pendus (the hanged) in France, permits any piece to be moved to any vacant cell. This also is believed drawn if played rationally.
[From Martin Gardner, Mathematical Puzzles & Diversions, pp. 38-40, Simon and Schuster, 1959.]
Apparently, in 1959, it was not known for certain (at least to Martin Gardner) if some of these variants are drawn if played optimally. In this assignment, you will implement code capable of determining this for any of the mentioned variants.
As noted above, there are many versions of this game. Your code should work with any of them, and will be tested with games different from those provided or even those mentioned by Gardner.
To implement your algorithm, you will need to make use of three classes and one interface that we are providing:
GameState - An object of this class represents the state of the game, including the positions of all pieces and whose turn it is. The most important methods here are the constructor, which can be used to build the initial GameState; and applyMove, which applies a Move from the given GameState and returns the new GameState.
Move - An object of this class represents a move in the game.
GameRules - An object of this class stores and provides information about the rules of the version of the game that is being played (as noted above, many variants are possible and your implementation should work for any of them). The most important methods here are isWin, which determines if either player has won in a given GameState; and legalMoves, which returns an array of legal Moves from a given GameState.
Player - This interface describes the form of any player, particularly the MyPlayer object that you are creating. In particular, every Player must provide a method getNextMove which returns the next Move that is to be played from a given GameState. (You can assume that this GameState is one that can be reached by some sequence of plays from the start state.)
Further documentation on these is provided here. Even though additional methods have been provided, the ones mentioned above should be sufficient for completing this assignment.
Your job is to create a Player called MyPlayer.java that will play optimally. The constructor for your class will accept a single argument, a GameRules object describing the rules of the version that is to be played. We are providing dummy code for MyPlayer.java which you can use as a template in creating your own (this dummy code simply chooses each move at random from the possible legal moves).
We are also providing several players, as well as a referee program for playing MyPlayer against any of the players provided on three provided games. After compiling, you can run the Referee with the command:
java Referee rules[+|-] player [maxMoves]
where:
rules specifies the game that is to be played and can be alldiag (meaning all diagonal moves are allowed), centerdiag (meaning only diagonal moves along the main diagonal are allowed) or nodiag (meaning that no diagonal moves are allowed). In every case, all orthogonal (up, down, left and right) moves are allowed.
the optional +/- tag will change whether MyPlayer plays as the + or - player (the + player always goes first). There is no space between rules and the +/- tag.
player indicates which player MyPlayer is playing against. This can be opt, which plays optimally (for these three games only); opt90, which plays optimally 90% of the time; random, which plays completely at random; or stdin, in which you yourself can play against the player you created.
maxMoves (optional) indicates how many moves are to be played before terminating the program.
In a nutshell, here is what you need to do:
Download the code that we have provided. The files you need are in this directory -- be sure to download all the files in this directory. Alternatively, you can download this single tar file containing everything.
Optionally compile everything and try it out with our dummy version of MyPlayer.
Modify the class MyPlayer.java to implement your own algorithm.
Compile everything and test it using the other provided players. Debug as necessary.
Create a readme.txt file describing anything that would be helpful to understand your code, such as its organization, main data structures, etc. (The algorithm itself should have been carefully explained as part of Problem 5 above.)
Submit your code and readme file using Whiteboard. Once on whiteboard, click on "Assignment submission". Enter your Princeton OIT Unix login and password (this will not work if you did not complete HW#0). You can upload MyPlayer.java, readme.txt and any other files by entering them (or browsing for them) in the file upload boxes and clicking "Submit". Once submitted, click "Run script" which will attempt to compile your uploaded files, printing any error messages. If necessary, you can delete or resubmit previously submitted files. An email confirmation will be sent for all successfully uploaded files.
First and foremost, your program should work and give correct answers, i.e., optimal moves from any given game state (reachable from the start state) and for any variant of this game. Your code should also follow good programming practice, including reasonably adequate documentation. (This is especially important if you want to get partial credit for code that works less than perfectly.)
