To begin, the choice of the game to be implemented should lie somewhere between tic-tac-toe and chess, the former being trivial to play and the latter perhaps too complicated for a short assignment. I have had moderate success with versions of checkers.The choice of game is important for most of the dimensions discussed below; it should be any game that is amenable to the 2-person, zero-sum game algorithms. It should be a non-trivial, even largely unfamiliar game. It should also allow the possibility for students to think about, develop, and implement heuristics.

There are several pedagogical dimensions that such an exercise could facilitate. First and foremost, such an exercise serves as a big motivating factor. The typical undergraduate these days has grown up playing video and computer games. This would more than likely be this or her first "behind the scenes" exposure to how such games may be built. That in itself serves to encourage curiosity and motivate the student to put a good amount of effort in the exercise. Add to that the freedom to explore and design the student's own heuristics that would characterize the game as his or her own creation.

If planned ahead of time, the completion of the exercise could culminate in a tournament where not only the students' programs, but they themselves may also play in it. While I have seen courses where similar tournaments were held, most involve programs playing against programs. However, inserting the students (or other human recruits) into the tournament brings about the "human against machine" angle and serves to contextualize the tournament in an AI course.

There is also the computer science dimension. In not-so-large departments, where faculty resources are stretched, there are often concerns over offering elective courses like AI. However, just in the context of a game playing programming assignment, there is potential for putting together several aspects of a student's preparation in computer science. For a non-trivial game, the amount of programming expertise required could serve challenging to most students. They have to design data structures (class descriptions for the OOP types), implement costly search algorithms that most of the time involve several optimizations, and also implement algorithms involving moves of the game as well as heuristics. You may want to leave the choice of the programming language itself to the individual student.

All put together, this represents a comprehensive task. Probably for the first time for most students, they are faced with an assignment specified as an "application". The potential can be stretched further by specifying the addition of a graphical interface. For the web-inclined, this can be a client-server implementation using CGI or written entirely in Java.

Such an exercise can (and should) also serve to introduce the experience of doing research. Students could be asked to submit a comprehensive report that outlines their strategies, heuristics, and design of their programs, as well as record and analyze empirical data regarding estimates of branching factors, the number of evaluations, the effect of their performance optimizations, etc. Gathering of such data from individual reports at the end of the assignment also facilitates a comparative analysis in class to arrive at conclusions that may not be easy to locate in the literature (for instance, what is the average branching factor for a specific game?).

Once completed, this exercise can be further extended into a more specific research assignment (in the same course or in a follow-up semester). Students could explore parallel programming techniques to make the searches more extensive. They could experiment with various learning strategies: neural networks, evolutionary algorithms, user modeling, etc. Students can be asked to turn their program into a generic game-playing shell: supply the game-specific data structures and functions and plug them in to get a complete game-playing program.

It is clear that there are multiple dimensions to a well designed programming assignment on game playing. This can serve to highlight several aspects of the learning process, and can be rewarding for the individual student as well as for the entire class.