ICS 180: Strategy and board game programming
Your course project will likely include the
- 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
- 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.
- 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
- Write final report of project accomplishments.
Dept. Information & Computer Science,