Adversarial Search

Laboratory Exercise 6


810:161

Artificial Intelligence Laboratory


[ Goals | Background | Pre-Lab | In-Lab | Post-Lab | More Info ]

Goals for the Laboratory Exercise

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.


Background

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.


Pre-Lab Activities

Prior to doing the in-lab activity, be sure that you have done the following:

  1. Read Chapter 4 in Graham. This chapter doesn't cover material specific to this lab, but rather discusses some of Common Lisp's data structures beyond lists. You may or may not find these helpful when implementing your lab program, but you'll know more about how to use Common Lisp after reading it.

  2. Study Kevin Knight's implementation of basid Tic-Tac-Toe functions. Play with all the functions so that you know what they do and how they work. Keep in mind that you will be using these functions to to implement a minimax Tic-Tac-Toe player.

  3. Read this document in its entirety.

Deliverables

None this week.


In-Lab Activities

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.

  1. Implement a random-player function that chooses a move randomly from the set of moves available to it. random-player takes two arguments, a game position and the player's token (X or O), and returns its move as a number in the range [0..8].

  2. Implement a human-player function that asks the user to enter a move from standard input. human-player takes two arguments, a game position and the player's token (X or O), and returns a legal move, also as a number in the range [0..8].

  3. Implement a tic-tac-toe function that plays a game of Tic-Tac-Toe between two players. tic-tac-toe takes two arguments, a player function for X and a player function for O, in that order. It returns the game result as its answer: 1 if X wins, -1 if O wins, or 0 if the game is drawn.

  4. Implement a minimax-player function that chooses a move by doing a minimax search of the search space. minimax-player takes two arguments, a game position and the player's token (X or O), and returns its move as a number in the range [0..8].

  5. Demonstrate the use of your minimax-player function by playing several games of Tic-Tac-Toe. You can play minimax-player against yourself, against another human, against random-player, and against itself. Use a dribble file or a Lisp/Emacs buffer to capture your session as a text file.

  6. Implement your own static evaluation function, one that will work better on interior nodes than Knight's. static takes two arguments, a game position and the player's token (X or O), and returns its evaluation as a number.

  7. Demonstrate the use of minimax-player with your own static function by playing more several games of Tic-Tac-Toe, as described above. Use a dribble file or a Lisp/Emacs buffer to capture your session as a text file.

Deliverables

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.


Post-Lab Exercise

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.

Deliverables

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.


Further Information

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!


Eugene Wallingford ==== wallingf@cs.uni.edu ==== October 3, 2001