CSC242: Intro to AI
Project 1: Game Playing
This project is about designing an implementing an AI program that plays a game against
human or computer opponents. You should be able to build a program that beats you,
which is an interesting experience.
The game for this term is Reversi, also known as Othello.
Reversi is an easy game to describe, which makes it easy to learn for humans and easy
to program for computers. But it’s also difficult to play well, at least for humans, for a
couple reasons. One is that all the pieces are the same, unlike a game like chess. And
unlike a game like checkers (draughts), the number of pieces on the board increases
rather than decreases. Pieces also change color between dark and light during the
game. These factors may make it harder for humans to track the evolution of the game,
to quickly evaluate positions, and to memorize positions and strategies for playing from
them. You’ll find out whether that’s true for computers also.
Please Note: There is a long history of computer programs that play Reversi/Othello.
Wikipedia says that it was one of the first arcade games developed by Nintendo and was
available on a home game console as early as 1980. If you want to learn anything, avoid
searching for information about the game beyond the Wikipedia page linked above until
you have done the basic implementation YOURSELF.
1. Develop a program that plays Reversi on a 4×4 board. The four initial pieces go
in the middle of the board, as shown in Figure 3. This is not a hard game, but
it is simple enough that you can see how your program is playing. And you can
probably play pretty well yourself, even if you’ve never played Reversi.
• You MUST use an adversarial state-space search approach to solving the
• Design your data structures using the formal model of the game. We MUST
see classes corresponding to the elements of the formal model (see below).
• You MUST use the appropriate standard algorithm to select optimal moves.
Do not use algorithms that make imperfect decisions for this part of the project.
• You should be able to search the entire tree for 4×4 Reversi and hence your
program should be able to play perfectly and quickly (on modern computers).
• You may, if you want, also play larger boards with your optimal player. It
should require almost no additional code. You should gain an appreciation for
the complexity of search problems if you try it.
• Your program MUST validate the user’s input and only allow the user to make
legal moves. This is not as hard as it may seem. Think about it. Your program
knows a lot about what is possible and what isn’t.
2. Develop a program that plays standard 8×8 Reversi. This can be a separate program, or you can have a single program that asks the user which game to play.
• You MUST again use an adversarial state-space search approach to solve
• If you design this right for Part 1, you will be able to reuse it with almost no
work. In fact, you will be able to adapt your program to any two-player, perfect
knowledge, zero-sum game with very little work. How cool is that?
• Choosing the best move in this game is significantly harder than the smaller
game of Part 1. (You should be able to figure out at least an upper bound on
how much harder it is.) You MUST use heuristic MINIMAX with alpha-beta
pruning for this part of the project.
• Your program should be able to play well. In particular, it should not take too
long to choose a move. Your program should give the user a chance to specify
the search limit, using one or more of the ideas described in the textbook and
discussed in class.
• Again, you may also try playing different board sizes with this player if you
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: [email protected] 微信:itcsdx