AI Project 2: Search Strategies

Due: 11:59pm Wed March 28th (seems like a long time, but two weeks of that is break)


For the second project in the AI class, you will write a simple turn taking tron-light-cycle style program. 

What you must do:

The Program:

Your program needs to show the board. You can do this using a text display if you like. Alternately you can use the TKinter package (Tkinter is available for the old version of python on eagle. I also have it installed on my local machine for those who want to work on their own install at home).  Or you can use the curses library for terminal graphics(also installed on eagle for the older python).  My board, written using Tkinter, is shown below. Your board must be a minimum of 10 x 10. The two players must have at least 4 spaces between them to start.
view of possible tron board.

You also need a mechanism to allow users to move. Use whatever mechanism you like so long as it is documented.

Rules of the game: One player moves, that player's light path is extended one square in the direction of the move. Then the other player moves, its own light path is extended by one square in the direction moved. The first player to move into a square that already has a light path on it loses. (you lose whether you run into your own light path or the other players)

Now for the AI:

The branching factor for this game is 4. Thats not too bad. However, the maximum depth of the search tree is at least 50 (depending on whether you use a larger board size or not.) With such a large depth, lets limit the depth of the search.

Then implement minimax search with alpha-beta pruning and a depth limit of 14-ply to determine what the next move should be. You *may* but are not required to, use a quiescence search to search a couple of plys more on the most interesting few possible moves at the depth limit.

Because this is a depth limited search you will need an evaluation function that evaluates the board state at the depth limit and assigns some numeric value to those states.

You may use any of the python code from the textbook website. is particularly useful since some of the minimax and alpha-beta algorithms that you need to implement are in that code. 

The writeup:

Include the standard header in your writeup:

Then you need to write a report on your AI player. This report should be a page or two long and address at least the following issues.

Minimax is a well known algorithm for adverserial search and game playing. Playing games has long been an area that only humans could do well. Game-playing was therefore considered a good test of intelligence. Does minimax search play a good simplified game of tron light-cycles? and if so, is this a good indicator of intelligence?

Much of the intelligence in a program like this is built into the evaluation function. The evaluation function has to be able to recognize the difference between a good state and a bad one for the AI player. Describe your evaluation function and how it works. Having described it, discuss how intelligent it is. How well does it work?

Finally discuss what you might do to produce a more intelligent game playing agent for these sorts of deterministic, fully-observable game problems?