The goal of this lab is for you to understand some of the programming issues involved in building a system that does adversarial search. You also have an opportunity to use an existing Lisp program as the basis for your own program, which will require you to strengthen your Lisp reading skills and broaden your knowledge of the language.
Earlier in the lab, you did some thinking about a generalized search function like the one we discussed in class. For this lab, I'd like for you to think about adversarial search and then implement some tools of your own.
We'll use Tic-Tac-Toe as our demonstration domain again. I realize that Tic-Tac-Toe is simple enough so as not to require search to play it well; indeed, we could implement a perfect player using table look-up without much effort. But the game's simplicity also means that it won't consume too much of your time, allowing you to focus on the search issues at the heart of the exercise. And, so that you can begin thinking about search sooner, we'll use an existing Tic-Tac-Toe framework written in Common Lisp.
Prior to doing the in-lab activity, be sure that you have done the following:
None this week.
Your task is to implement a program of playing Tic-Tac-Toe, either against itself or against a human player. I've broken this task down into several steps so that you can approach it piecemeal.
Submit an e-mail message containing only a single, gcl-loadable file containing your Common Lisp solutions to Tasks 1-4 and 6 by Wednesday, October 10, at 4:00 PM. If you forget what "gcl-loadable" means, please review the instructions in Laboratory Exercise 2.
Submit two separate e-mail messages containing the text files you generate in Tasks 5 and 7.
By that same time, submit print-outs of all three files, stapled in order, to me in person or to the department office.
Wouldn't it be nice to be able to play your a match between two minimax players, one using your static function and one using Knight's, with an arbitrary depth cut-off placed on lookahead?
Modify the Tic-Tac-Toe code so that we can pass to minimax-player two more arguments, the static and deep-enough functions that it uses to do its search.
After testing your function to be sure that it works, implement a (tic-tac-toe-match x-player o-player number-of-games search-depth) function that plays a match of number-of-games games between x-player and o-player, in which each is allowed to search no deeper than search-depth ply. tic-tac-toe-match returns as its value the number of games won by x-player.
Submit an e-mail message containing only a single, gcl-loadable file containing your Common Lisp solutions to these tasks by Friday, October 12, at 4:00 PM.
Submit a separate e-mail message containing a text file you generate in playing our dream match between your static evaluation function and Knight's, at three different levels of search (shallow, medium, and deep).
By that same time, submit print-outs of both files, stapled in order, to me in person or to the department office.
If you are interested in game playing, then you can have a lot of fun reading and programming beyond this exercise. I highly recommend that you read One Jump Ahead: Challenging Human Supremacy in Checkers by Jonathan Schaeffer, which details the development of Chinook, the World Man-Machine Champion of checkers--the first computer program to win a human world championship in any game. This book is both a good description of the technical issues that Schaeffer and his team faced in building Chinook and an entertaining human story of a researcher driven ro solve a problem.
There are many, many books on computer chess, and our library contains a few good ones. Books on computer programming for other games are less plentiful but still numerous and useful!