ICS 180: Strategy and board game programming

Project Proposal

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 project members.

The Game

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.

Project tasks

Your proposal should list the software components that will be included in your project, and determine which team members are responsible for which components.

Search complexity

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 b^k 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.)

Evaluation terms

Your proposal should make a preliminary guess at what sort of information needs to be included in the evaluation function, 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.

Platforms

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.

David Eppstein, Dept. Information & Computer Science, UC Irvine, .