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 problem.
• 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 the problem.
• 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 want.
本网站支持淘宝 支付宝 微信支付 paypal等等交易。如果不放心可以用淘宝交易！
E-mail: email@example.com 微信:itcsdx