ICS 180: Strategy and board game programming

Project Components

Phase I

• Board representation. This is a data structure that represents all the information needed to store a single position in a game. (E.g. in chess, it would include not just the position of each of the pieces, but also a bit indicating whose turn it is, and some extra information about whether either player can castle or capture en passant.) You should define a concise way of inputting and outputting moves; e.g. in chess a typical method is computer algebraic notation: the move e2e4 means to move the piece currently on square e2 (row 2, column e) to square e4. Your board representation code will include code to input these codes and update the position. It should also detect illegal move codes, and represent the position in a form convenient for move generation and evaluation.
• Move generation. This code should look at a board position, and output a list of all the moves that are legal to make from that position.
• Basic user interface. A fancy graphical interface would be nice, but I won't mark you down if you just do Unix stdio-based text input and output. For phase I of the projects, your user interface should allow a sequence of moves to be input (either in the concise form described above or using the mouse), test whether those moves are legal, and if so output the list of possible moves available at the resulting position.

Phase II

• Evaluation function. This component examines a board position, and returns a numerical score indicating which player is likely to win. A large positive score should mean that one player has a very good position, a large negative score should mean that the other player has a very good position, and a score near zero should indicate a game that's either likely to lead to a draw or too close to decide who is likely to win. For instance, in chess the following very simple "materialistic" evaluation works pretty well: sum up +1 for each white pawn, +3 for each white knight or bishop, +5 for each white rook, and +9 for each white queen. Subtract the corresponding values for each black piece. However in other games (e.g. Othello) counting pieces is much worse than other more careful evaluations.
• Search strategy. Typically this will be alpha-beta or a variant on it. We will discuss this part of the program extensively in the course lectures.
• Advanced user interface. Add features to reset the board, decide which side the computer is going to play, and call the search strategy when the computer needs to make a move.

Phase III

• Testing. Playing many games against your computer will reveal its strengths and weaknesses.
• Evaluation function. The more time you spend on this, the better your computer will play. You should work on making it more intelligent and faster.
• Search strategy. There are many sophisticated enhancements to alpha-beta, which you can try implementing once you have the basic search working.
• Write final report of project accomplishments.