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
abcdefgh 11 22 33 44 55 66 77 88 abcdefgh
Figure 1: Initial arrangement of pieces for standard 8×8 Reversi
Rules of Reversi (Othello) Board and Pieces
• The game is played on a rectangular board divided into squares as shown in Fig- ure 1. The standard size is 8×8.
• Columns are labelled with letters starting with “a”. Rows are labelled with numbers starting with 1. Squares are referred to by column and row, from in “a1” to “h8” (on an 8×8 board).
• The pieces are disks with two sides, corresponding to the two players. Traditionally the pieces are dark on one side and light on other, and we refer to the two players as “dark” and “light” also.
• The initial configuration of the board for standard 8×8 reversi (Othello rules) is shown in the figure. Two pieces are placed with their dark side up at locations d5 and e4, and two pieces are placed with the light side up at locations d4 and e5.
2
Moves
When it is their move, a player must place a piece with their color up such that there is a line of one of more pieces of the opponent’s color between the new piece and one of the player’s own pieces already on the board. That is, each move must “trap” a line of the opponent’s pieces between the player’s own pieces, including the piece being played.
The dark player must play pieces with the dark side up trapping a line of light pieces between the new piece and an existing dark piece. The light player must do the same with a light piece trapping a line of dark pieces.
The line of one or more trapped pieces may be horizontal, vertical, or diagonal.
For example, from the initial configuration of the board, dark has four possible moves. The first is at c4, trapping the light piece at d4 horizontally between the dark piece at e4 and the new piece. The other moves are at d3 (trapping d4 vertically), at e6 (trapping e5 vertically), and at f5 (trapping e5 horizontally). I suggest that you draw this on a piece of paper or a whiteboard to see what’s going on.
After playing their piece, the player flips over the line of trapped pieces so that they all show the player’s own color. That is, the dark player plays a piece dark side up, trapping a line of light pieces. They then flip the trapped pieces to be dark side up. Similarly for the light player.
For example, if dark plays at c4, then the light piece at d4 is flipped to dark, resulting in a line of dark pieces from c4 through d4 to e4. This is shown in Figure 2.
Note that a player may capture more than one line of their opponent’s pieces in a single move. All of the opponent’s pieces that are “between” the newly-placed piece and any of the player’s other pieces (in a line) are flipped.
Players take turns moving.
The player with the dark pieces moves first.
If a player cannot make a legal move, they forfeit their turn and play passes to the other player.
3
reversi-dark-c4
abcdefgh 11 22 33 44 55 66 77 88 abcdefgh
Figure 2: Board position after dark play at c4
End of Game
The game ends when neither player can make a legal move. This can happen when:
• The board is completely full.
• The board is not full but neither player make a legal move (that is, play a piece that
traps a line of the opponent’s pieces). Wikipedia has some examples of this FYI.
At the end of the game, the player with the most pieces on the board (the most pieces with their color up) is the winner.
Ties (draws) are possible.
4
reversi-4×4
abcd 11 22 33 44 abcd
Figure 3: Initial board configuration for 4×4 Reversi
Requirements
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 pro- gram, 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.
5
• 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.
Your programs should use standard input and standard output to interact with the user. An example is shown on the next page. You are welcome to develop graphical interfaces if you like, but that’s not the point of this course and will not be considered in grading.
Here’s a quick example of what your program might look like when it runs. A transcript of a complete game with some interesting situations is at the end of this document.
Reversi by George Ferguson
Choose your game:
1. Small 4×4 Reversi
2. Medium 6×6 Reversi
3. Standard 8×8 Reversi
Your choice? 1
Choose your opponent:
1. An agent that plays randomly
2. An agent that uses MINIMAX
3. An agent that uses MINIMAX with alpha-beta pruning
4. An agent that uses H-MINIMAX with a fixed depth cutoff and a-b pruning
Your choice? 1
Do you want to play DARK (x) or LIGHT (o)? x
abcd 11 2ox2 3xo3 44 abcd
Next to play: DARK
Your move (? for help): a2
Elapsed time: 3.284 secs
x:a2
6
abcd 11
2xxx 2 3xo3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:a1
abcd 1o1 2xox 2 3xo3 44 abcd
Next to play: DARK
Your move (? for help): d3
Elapsed time: 8.672 secs
x:d3
abcd 1o1
2xox 2
3 xxx3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:d4
abcd 1o1 2xox 2
3 xox3 4o4 abcd
Next to play: DARK
7
How To Do This Project
I will assume that you are using Java for this. Why wouldn’t you use Java for a pro- gram that involves representations of many different types of objects with complicated relationships between them and algorithms for computing with them? Seriously. That’s the kind of thing that Java was designed for. If you want to ignore my advice and use Python, well ok, but it has to be well-designed and object-oriented, not a mishmash of lists and dictionaries. C/C++: you’re on your own (and must love tracking down memory problems). See “Programming Practice,” below.
Start by designing your data structures.
What are the elements of the state-space formalization of a two-player, perfect knowl- edge, zero sum game? We’ve seen them in class and in the textbook. They can be used to formalize any game, not just Reversi.
In Java, you would probably turn these into interfaces. Python now has some things similar to interfaces, but Python is philosophically opposed to careful specfication of behavior (see “duck typing”), which is one reason why I don’t recommend Python for large projects.
Now, how would you represent the specifics of Reversi using this framework? Don’t forget to think about supporting different board sizes and/or starting configurations, per the requirements. Design classes that implement the abstract specifications (interfaces) for this specific game (problem domain). You can write simple test cases for these as you go and include them in each class’ main method.
Next: The algorithms for solving the problem of picking a good move are defined in terms of the formal model. So you can implement them using only the abstract interfaces. Write one or more classes that answer the question “Given a state, what is the best move (for the player whose turn it is to maove in that state)?” Usually this involves generating all the possible moves in a state, so you should probably start there, and then figure out how to pick the best move. Hint: An agent that picks randomly but legally is not hard, using what you get from the formal model. So start there, but you should know what algorithms you really need for this problem.
Once you have one or more of these “agents” for playing the game, write the program that puts the pieces together to generate the gameplay shown in the example transcript. This will get you through Part 1.
What do you predict will happen if you use this program to play the full version of the 8
game required in Part 2? Try it. You should know from class and from the textbook what algorithms and techniques you need to make imperfect real-time decisions. This may require some “additional information,” which you will need to decide on and then add to your game-playing agent(s). The algorithm(s) apply to any game. The “additional information” is specific to a given game, or more precisely, to a specific way of playing a specific game. You might want to try several ways.
The great thing about using the state-space search framework is that you can try differ- ent algorithms using the same representation of the problem. Even better, you can use the same algorithms to play different games just by changing the game-specific imple- mentation of the abstract interfaces derived from the formal model of state-space search. And if the descriptions of the games were themselves machine-readable. . . general game playing perhaps?
9
Project Submission
Your project submission MUST include the following:
1. A README.txt file or PDF document describing:
(a) Any collaborators (see below)
(b) How to build your project
(c) How to run your project’s program(s) to demonstrate that it/they meet the requirements
2. All source code for your project. Eclipse projects must include the project set- tings from the project folder. Non-Eclipse projects must include a Makefile or shell script that will build the program per your instructions, or at least have those instructions in your README.txt.
3. A completed copy of the submission form posted with the project description. Projects without this will receive a grade of 0. If you cannot complete and save a PDF form, submit a text file containing the questions and your (brief) answers.
Writeups other than the instructions in your README and your completed submission form are not required.
We must be able to cut-and-paste from your documentation in order to build and run your code. The easier you make this for us, the better grade your will be. It is your job to make both the building and the running of programs easy and informative for your users.
Programming Practice
Use good object-oriented design. No giant main methods or other unstructured chunks of code. Comment your code liberally and clearly.
You may use Java, Python, or C/C++ for this project. I recommend that you use Java. Any sample code we distribute will be in Java. Other languages (Haskell, Clojure, Lisp, etc.) by arrangement with the TAs only.
10
You may not use any non-standard libraries. Python users: that includes things like NumPy. Write your own code—you’ll learn more that way.
If you use Eclipse, make it clear how to run your program(s). Setup Build and Run config- urations as necessary to make this easy for us. Eclipse projects with poor configuration or inadequate instructions will receive a poor grade.
Python projects must use Python 3 (recent version, like 3.7.x). Mac users should note that Apple ships version 2.7 with their machines so you will need to do something differ- ent.
If you are using C or C++, you should use reasonable “object-oriented” design not a mish-mash of giant functions. If you need a refresher on this, check out the C for Java Programmers guide and tutorial. You must use “-std=c99 -Wall -Werror” and have a clean report from valgrind. Projects that do not follow both of these guidelines will receive a poor grade.
Late Policy
Late projects will not be accepted. Submit what you have by the deadline. If there are extenuating circumstances, submit what you have before the deadline and then explain yourself via email.
If you have a medical excuse (see the course syllabus), submit what you have and explain yourself as soon as you are able.
Collaboration Policy
You will get the most out of this project if you write the code yourself.
That said, collaboration on the coding portion of projects is permitted, subject to the following requirements:
• Groups of no more than 3 students, all currently taking CSC242.
• You must be able to explain anything you or your group submit, IN PERSON AT
ANY TIME, at the instructor’s or TA’s discretion. 11
• One member of the group should submit code on the group’s behalf in addition to their writeup. Other group members should submit only a README indicating who their collaborators are.
• All members of a collaborative group will get the same grade on the project.
Academic Honesty
Do not copy code from other students or from the Internet.
Avoid Github and StackOverflow completely for the duration of this course. There is code out there for all these projects. You know it. We know it.
Posting homework and project solutions to public repositories on sites like GitHub is a vi- olation of the University’s Academic Honesty Policy, Section V.B.2 “Giving Unauthorized Aid.” Honestly, no prospective employer wants to see your coursework. Make a great project outside of class and share that instead to show off your chops.
12
Full Game Transcript
Here’s the transcipt of a full game of 4×4 Reversi. I played dark against a computer player that picks randomly among its legal moves. I still managed to lose. It’s an interesting game. . .
Note 1: When I play at d1 (my fourth move), it flips the pieces at both c2 (diagonal to b3) and d2 (vertical to d3).
Note 2: On my second-to-last move, I have no legal moves. So I have to pass. But the game is not over until we both don’t have any legal moves. Once they play at b4, then I have a legal move at a4.
Reversi by George Ferguson
Choose your game:
1. Small 4×4 Reversi
2. Medium 6×6 Reversi
3. Standard 8×8 Reversi
Your choice? 1
Choose your opponent:
1. An agent that plays randomly
2. An agent that uses MINIMAX
3. An agent that uses MINIMAX with alpha-beta pruning
4. An agent that uses H-MINIMAX with a fixed depth cutoff and a-b pruning
Your choice? 1
Do you want to play DARK (x) or LIGHT (o)? x
abcd 11 2ox2 3xo3 44 abcd
Next to play: DARK
Your move (? for help): a2
Elapsed time: 2.445 secs
x:a2
abcd 11
2xxx 2 3xo3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
13
Elapsed time: 0.000 secs
o:a1
abcd 1o1 2xox 2 3xo3 44 abcd
Next to play: DARK
Your move (? for help): d3
Elapsed time: 13.415 secs
x:d3
abcd 1o1
2xox 2
3 xxx3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:a3
abcd 1o1 2oox 2 3oxxx3 44 abcd
Next to play: DARK
Your move (? for help): b1
Elapsed time: 11.911 secs
x:b1
abcd
1ox 1
2oxx 2 3oxxx3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:d2
14
abcd
1ox 1 2oooo2 3oxxx3 44 abcd
Next to play: DARK
Your move (? for help): d1
Elapsed time: 5.991 secs
x:d1
abcd
1ox x1 2ooxx2 3oxxx3 44
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:d4
abcd
1ox x1 2ooxx2 3oxox3 4o4 abcd
Next to play: DARK
Your move (? for help): c3
Invalid move!
Valid moves are: [x:b4, x:c4]
Try again!
Your move (? for help): c4
Elapsed time: 22.495 secs
x:c4
abcd
1ox x1 2ooxx2 3oxxx3
4 xo4
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:c1
15
abcd 1ooox1 2ooxx2 3oxxx3
4 xo4 abcd
Next to play: DARK
Your move (? for help): pass
Elapsed time: 15.510 secs
x:pass
abcd 1ooox1 2ooxx2 3oxxx3
4 xo4
abcd
Next to play: LIGHT
I’m picking a move randomly…
Elapsed time: 0.000 secs
o:b4
abcd 1ooox1 2ooxx2 3ooxx3
4 ooo4 abcd
Next to play: DARK
Your move (? for help): a4
Elapsed time: 7.263 secs
x:a4
abcd 1ooox1 2ooxx2 3oxxx3 4xooo4
abcd
Next to play: LIGHT
Winner: LIGHT
Total time:
DARK: 79.031 secs
LIGHT: 0.000 secs
16