
|

CSE 573 –
Artificial Intelligence - Autumn 2004
|
|
Mini Project 1 -
Adversarial Search
[ CSE
573 2004 Autumn Home | Problem Sets | Mini Project 2 ]
In this project you should pick a game (some suggestions below),
implement board manipulation functions, implement a min-max or
alpha-beta search algorithm and explore some interesting ideas as time
permits. For example,
- Do an experimental comparison of several board evaluation
functions (i.e. heuristics).
- Evaluate the effect of singular extension (R & N, p174) or
other techniques.
- Look into conspiracy search (see
last paper in 1988 on this page)
- Read ahead on reinforcement learning and use learning to improve
the heuristic function as the program plays against itself (ala
Tesauro's TD-GAMMON).
- [Your idea here]
Regardless of what you choose, your objective should be to conduct an
experiment so that you can report on it in your report.
I think it is a great idea if several groups choose to do the same
game. You could have fun by pitting the programs against each other in
a tournament (note that this isn't a subsitute for some controlled
experiments as a basis for your report). But even if you don't choose
to battle the programs, you could probably save considerable time by
sharing the job of building infrastructure (board viewer etc).
Here are some resources that you may find helpful when considering
which game to choose.
- Othello (reversi) is classic, and used in many undergraduate
courses. Some potentially helpful material is here.
- Abalone
is a two-person, turn taking, deterministic game of perfect information, i.e. an ideal target for the game
playing algorithms we have covered in class.
The rules of the game can be found at:
http://en.wikipedia.org/wiki/Abalone_game
In order to reduce the branching factor to a
manageable number, we suggest that you disallow broadside moves
for the purposes of this assignment.
Note that the above web page describes a notation for reporting
board positions and moves -- please use it when you display the board
and when you enter or report moves.
You can practice playing the game at: http://www.clickhere.nl/abalone/ This implementation also does not allow
broadside moves.
Abalone is a good choice, moderately difficult, but not too
bad. You'll need to consider what to do about repeated board positions
tho.
- Some people have suggested Go. A useful information source for
this challenging game is here.
- Matt Ginsberg (Oregon) has built a very strong Bridge playing
program, so if games of incomplete information appeal, check out some
of his papers here.
- If people have other suggestions or useful links, please send
them in and I'll post them.