CSE 573 –
Artificial Intelligence - Autumn 2004
Mini Project 1 -
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
- 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
- [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.
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:
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
Abalone is a good choice, moderately difficult, but not too
bad. You'll need to consider what to do about repeated board positions
- 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.