AI Project 2: Search Strategies
Due: 11:59pm Wed March 28th (seems like a long time, but two weeks of that is break)
Summary:
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.
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. games.py
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:
- Your Name
- How do I run your program. (both running and "playing" the game)
- Is therere anything left undone in your program.
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?