|
|
|
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]
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.