ICS 180: Strategy and board game programming
The first task required of each programming team is to submit a proposal,
naming the project members, describing the game to be programmed, and
assigning responsibilities for programming and other project tasks to the
Choose a game to program.
The game should be complicated enough that a heuristic search is
necessary to solve it (so tic-tac-toe programs will not be allowed).
It should not involve chance (i.e., no card games or backgammon).
Its rules should be simple, since I'd prefer you spend more time on
evaluation and search and less time on just getting your program running
(chess is borderline, I'd prefer you chose other games, and besides you
need to use all the tricks in the book to match
the performance of existing chess programs).
Both players should be able to know the whole board situation
(so no hiding information from each other as in battleship).
Finally, I'd suggest you stay away from Go, even though it fits all
these other criteria, because the number of different moves that can be
made at each step makes it very difficult for computer search algorithms
to make good Go players.
With all these negatives, what are some good
games that you could propose to program? I've listed them on
a separate web page.
Your proposal should list the software
components that will be included in your project,
and determine which team members are responsible for
Your proposal should say how many different legal moves are available
at a typical position in your game (this number is known as the
branching factor). If there are b legal moves, and you perform
minimax search to a depth of k moves, you should search roughly
bk positions. Assuming you can search 100,000 positions/second
(a pretty typical number), how large can k be if you want your search to
finish in one second?
(Note, the actual search depth will likely be better than this estimate.
Alpha-beta pruning will roughly double the depth you can reach, but other
pruning techniques are available and
may turn out to be necessary depending on the branching factor of your game.)
Your proposal should make a preliminary guess at
what sort of information needs to be included in the
and describe how you will go about computing that information.
Probably this will not end up describing how your final product
works, but you need to start with something here.
Your proposal should state what kind of machine you use and what
language you will program in.
My preference would be Java (due to its portability and ease of setting
up user interfaces) but you may use other languages
such as C, C++, etc.
If you use a Mac, Linux-based PC, Windows '98, or other platform not generally
available in the ICS labs, you should make sure that
a portable machine will be available for project demonstrations.
If you wish to have your code preserved on a web site,
I will make room available for this on the course web page.
This may give you another reason for choosing Java over other languages.
Using other people's code
You may use user interface code written by people other than project
members, as long as the code is available for such use and you give full
credit for it in your project documentation.
All components of the game engine itself, including the board
representation, search code, move generation, and position evaluation,
should be written yourselves.
Dept. Information & Computer Science,