CSC 456
Spring 2008
AI Project
Due Dates:
· Phase 1 is due no later than 10:00am, Monday, February 11, 2008
· Phase 2 is due no later than 10:00am, Wednesday, March 12, 2008
· Final Complete Project is due no later than 10:00am, Friday, April 18, 2008
Turn in (for each phase):
· Source listing on paper
· Zipped file of your entire Java project submitted to Blackboard.
Game Description:
Hexapawn is played on a n x n chessboard. The two players face each other across the board. Each player begins with n pawns, placed one to a square in each of the n squares nearest that player. Pawns are black and white; the white team begins. A player may choose to move one of his or her pawns in one of these ways:
· A pawn may be moved one square forward to an empty square
· A pawn may be moved one square diagonally forward to a square occupied by an opponent's pawn. The opponent's pawn is then removed.
The players alternate moving pawns until one of the players wins. A player wins when:
· A player's pawn has advanced to the other end of the board.
· The opponent has no pawns remaining on the board.
· It is the opponent's turn to move a pawn but is unable to do so.
As envisioned by its inventor, whose name is now forgotten but whose ideas live on, hexapawn was intended to be played with only six pawns on a 3 x 3 board (hex = 6). Now, however, we are extending the definition of hexapawn to include any similar game involving n white pawns, n black pawns, and a n x n board.
Your Mission:
Over the semester, you are to construct a Java Project which will play the game of Hexapawn. Your project should include a package with your last name (to avoid conflict when we have our tournament). It will include two classes that extend classes that I provide, and can/should use additional capabilities in packages that I provide. The tournament will be run by code in another package that I will provide. I give a quick introduction to my classes below, and my classes will include Javadoc documentation (but I wouldn’t be surprised if you needed to ask me some questions about the capabilities provided).
Phase I
Your deliverables include:
· A class YourlastnameGameSituation that extends GameSituation (in my HexapawnUtils project). It does not include any additional data. Included (In Phase I) should be:
o Constructors corresponding to the Constructors in GameSituation, which will merely call the appropriate super (for GameSituation constructors). This will allow YourlastnameGameSituation objects to be created with appropriate info, which will allow your methods for this class to be called via polymorphism (allowing me to run a contest among any two players)
o A Constructor that given (passed) a GameSituation will construct a YourlastnameGameSituation with the same contents (not merely the same reference). If this is a little rusty (on new) to you, I’m happy to talk to you about it.
o A clone() method overriding inherited clone() method. It should pass back an Object with the same contents as the “invoking” YourlastnameGameSituation. The “signature” (method header) needs to match the inherited clone() so that it is overridden. If this is a little rusty (on new) to you, I’m happy to talk to you about it.
o A toString() method overriding the version in GameSituation. It should merely return the string with yourlastname followed by super.toString().
o A ratePosition method overriding the (dummy) version in GameSituation. It should be given (passed) a PawnColor (enumerated type in my utility project) for which color it is playing for (black or white) and return a numeric (double) heuristic evaluation indicating the “goodness” of the current YourlastnameGameSituation for the given PawnColor. (if you’re evaluating for black, higher results should correspond to situations that are more favorable to black). You have freedom (and creativity) to explore how you want to rate situations. Since this is one area where you program will be different from others, it will be a factor in whether you win the competition. You can make upgrades after the Phase I due date, but you must turn in a credible functioning version by Phase I due date. NOTE – this is a static heuristic evaluation; it is not allowed to look ahead.
§ ratePosition should also add 1 to the GameSituation static variable numBoardsEvaluated
I will test your Phase I with a driver that I will construct later.
Phase II
Your deliverables include:
· A moveGenerate method in YoulastnameGameSituation overriding the (dummy) version in GameSituation. It should be given (passed) a maximum number of moves it is allowed to return, and should return an array of Move (class defined in my utilities project) holding the moves generated. The array should be of length equal to the number of moves generated, so its length can be reliably used by other methods. I am open to hearing convincing arguments that would convince me that it is worth my effort to change my code to use ArrayLists, Vectors etc (but it has to be significantly ahead of the due date so others can work in the same direction).
o If more moves exist than the passed maximum, and the GameSituation static variable genTraceOn is set to true, write all possible moves to the trace file indicated via the GameSituation static variable genpw (even though you can’t return them all). By the way, this situation (in which more moves are possible than you are allowed to return) is another way that your program can be different from others. However, it may only come up if a tiebreaker is needed in the contest.
I will test your Phase II with a driver that I will construct later.
Phase III
Your deliverables include:
· A class YourlastnamePlayer that extends Player (in my HexapawnUtils project). It does not include any additional data. Included should be:
o Constructors corresponding to the non-default Constructors in the Player class. These cannot depend on calling super versions, because the current GameSituation must be an instance of the child class YourlastnameGameSituation instead of the parent class GameSituation, so that your versions of ratePosition and moveGenerate will run on it
o A playMove() method that overrides the (dummy) version in Player. It needs no parameters, and will return a Boolean indicating if it has found a move. It will call your yourinitialsMinimaxMax method, passing the current GameSituation (in this) cast as a YourlastnameGameSituation so that proper versions of ratePosition and moveGenerate will run, along with a current depth of 0, and initial alpha and beta values. It also needs to pull out the returning GameSituation passed back in the MinimaxInfo object and use it to update the current situation in the invoking Yourlastnameplayer object.
o A transferGameSituation method that overrides the version in Player. It can be similar to Player’s version, it just needs to make sure that the current GameSituation stashed in your YourlastnamePlayer object is a YourlastnameGameSituation rather than a GameSituation, so that your methods run on it.
o A toString() method overriding the version in Player. It should merely return the string with yourlastname followed by super.toString().
o Minimax search with alpha-beta pruning. Provided via:
§ A yourinitialsMinimaxMax that is passed a current YourlastnameGameSituation, a depthSoFar, alpha, and beta, and will return a MinimaxInfo object containing appropriate results of the search. General pseudocode will be presented in class.
§ A yourinitialsMinimaxMin that that is passed a current YourlastnameGameSituation, a depthSoFar, alpha, and beta, and will return a MinimaxInfo object containing appropriate results of the search. General pseudocode will be presented in class.
I will test your Phase III with a driver that I will construct later, before entering it in the tournament. I will run the tournament with the main method in the Main class in the HexDriver project. You should test your program with the driver.
Even though I am giving you semi-detailed pseudocode for the complicated methods in this phase, I do not expect this to be easy. Work ahead on this!!!! We will have covered everything you need to know about this by mid-February if not earlier.
Details:
· See the tournament driver for the expected set up. An object of your YourlastnamePlayer class will be constructed using either the trace on or trace off Constructor. This will establish in your object important aspects of the game, including the size of the board, the color you are playing, the maximum width of search (which will be used by you as the parameter to moveGenerate), the maximum depth of search (which your minimax methods will use to determine whether they have searched to their end depth), whether tracing is on, and if so, the PrintWriter (file) to write to.
· My driver will get a lot of info from “command line arguments”. To set these so you can run thru the IDE (NetBeans), on the HexDriver project right-click and choose Properties, then select “Run”, then type into “Arguments”. I will show you my set-up in class.
· Beware of references!!!! When exploring hypothetical game situations, it is important that you not get rid of the existing game situation. Remember that in Java when you assign an object you are setting the objects to be the same object, not just have the same value. In minimax, there will definitely be places where you need to clone() things so that you are working with a separate copy.
· If tracing is on for minimax, I want a detailed trace written to the file so that I can tell if your minimax is working properly without stepping through it with the debugger!! Don’t think ‘User want to know’, think ‘Professor need to know’. I should see a complete report of your search, preferably indented to help illustrate the tree structure (see Board.indent) including at least:
o Entering a minimax function, with at least the level, whose turn it is, alpha, beta, and the game situation (see drawIndentedGameSituation).
o Returning from a minimax function, with at least the heuristic evaluation being returned and preferably the move path expected and the adjusted game situation after the return (note that with multi-level search, this return could be significantly after the entering!).
o Successor moves generated by moveGenerate (see Move.arrayToString)
o Occurrence of alpha-beta cutoff, and preferably also the nodes or moves skipped)
Preferrably also:
o Play by play of looping through successor moves – which produces a new best, which doesn’t give any improvement
Some extra notes:
1) I may need to modify the specifications a bit here or there in case I forgot something. Try to be flexible. Don't whine.
2) A static board evaluation function is exactly that -- static. It doesn't search ahead. Ever. In deciding which moves to look ahead from, the move generation function doesn't search ahead. Ever.
3) I am not asking you to write the human-computer interface so that your program can play against a human. Don't Do It!! You have enough to do on the project. Maybe I’ll do it.
4) I have written a driver program that will allow your project to play against the projects written by your classmates. Your project will be loaded alongside your opponent's project. Yes, two projects, trying to do exactly the same thing, sharing the same IDE environment ... yikes! The potential for disaster exists because you're now programming in a very communal environment. What I want you to do is (I think doing all of these is overkill, but just to be careful):
a) Make sure you create your own project, don’t just add to mine. There are a few things you have to do to make this work (imports, and letting the IDE know where the other projects are); I will try to talk about this in class.
b) Don’t change ANY of my files. If you think there is a bug or missing capabilities, contact me (this means, don’t plan on waiting until the last moment to do the work!).
c) Follow the detailed instructions for methods above so that polymorphism can work for us.
d) Make sure that you use a package name using yourlastname (definitely DO NOT just use the default package)
e) Name your minimax methods yourinitialsMinimaxMax and yourinitialsMinimaxMin.
f) Make you minimax methods private (that way only your code can call them).
5) Your program MUST work for larger sizes
e.g. 5 X 5 board with 5 pawns each side ...
6) Your program MUST work for any search depth specified. I don't think it should matter to your program, so I won't announce what search depth will be used for the tournament.
7) Syntax errors will automatically result in a low grade. Run time errors will in most cases result in a low grade (unless there is something freaky which you have talked to me about ahead of time) Making your program *work* is more important than making it play well.
8) Program early and often. The board evaluator is something you can get going on immediately. The move generation is more difficult, but can be started on before Phase 1 is due if you can get ahead (hint, hint). The final phase is significantly more difficult. First understand the game. Then get the board evaluator out of the way in a hurry, then start working on the rest of it as soon as you can (work ahead of due dates if you can!). Get the move generator working. Then get the minimax to work, then the alpha beta cutoff. Finally, if you have time then go back and tune your evaluator. Note that you do not have to understand minimax before you program the board evaluator or move generator.
9) Remember - 10% extra credit for winning tournament (up to 110 for grade on the assignment).
10) Remember, when you send your code to me (each time) -- submit all of your project (the whole folder structure) in one zip archive to Blackboard.
Introduction to Provided Classes/ Code:
All classes provide related functions, including constructors, inspectors (gets), mutators (usually sets) and some include other useful or important methods. Javadoc documentation is provided (internal documentation is not up to my standards). Methods whose name starts with “is” return Booleans.
· HexapawnUtils project (edu.lasalle.redmond.hexapawnutils package) – utilities available for Hexapawn project
o PawnColor – really just an enumeration – provides colors white, black, none (for empty spaces), and illegal (can flag errors – don’t think I used)
o Pawn – indicates its color (including none for empty spaces) and an ID#.
o Board – includes a board size and a two-dimensional array of Pawns
o Location – includes a row and column number. It provides a controlled way to refer to positions on the board. Following normal array notation, Locations begin with (0,0).
o Move – includes a “from” Location and a “to” Location. It is not connected to Board, so there is no guarantee that such a move is real or legal.
o GameSituation – includes a Board, whose turn it is (a PawnColor), the number of moves that have been made, and a name for the game situation
o Player – includes a GameSituation (should be a child of GameSituation), what color the Player is playing (a PawnColor), max width and depth of search allowed, the player’s name, whether tracing is on, and the PrintWriter to write the trace to.
o MinimaxInfo – to be used to pass info back from minimax methods – includes returning GameSituation, heuristic evaluation, the path of Moves expected to be taken from the next Move to the end of search depth, the path of GameSituations expected to result from those Moves
· HexDriver project (hexdriver package) – driver to run the tournament
o Main – only contains the main method used to drive the tournament
· IO project (edu.lasalle.redmond.IO package) – provides Input Box and MsgBox capabilities slightly above raw Java
o RedmondMsgOut – provides the static method display which displays something both in a message box and also to the console so that historical info can be seen
o RedmondMsgInBasic – provides static methods to prompt the user for a response and do basic validation on their response. Avoids throwing Exceptions, making use a little more convenient than some alternatives (but you get a crash if user Cancels).