Game Playing with Minimax

Table of Contents

Overview

Your goal is to create an system that can accurately play Othello (also known as Reversi). The website eOthello lets you play it online, and it shows you the rules to play immediately below the game if you scroll down. Play a few games, especially if you haven’t played before. If you’d rather learn the rules from a video, here is a video to learn how to play Othello.

Get started

To get started with your assignment, copy the files othelloBoard.py and othelloPlayers.py into your directory. othelloBoard.py contains everything necessary to get the Othello game moving. Use Python’s help facility to see what what methods are in there that you might find useful. In other words, do the following: 

$ python
Python 3.5.2 (default, Jul 10 2019, 11:58:48) 
[GCC 5.4.0 20160609] on linux
Type "help", "copyright", "credits" or "license" for more information.
>>> import othelloBoard
>>> help(othelloBoard)

You should not modify othelloBoard.py in any way, but you may find it instructional to look at. To actually start up an Othello game, run 

python othelloBoard.py

from a command prompt. The game allows for two players, each of which can be a human player or a computer player. You’ll find a class for each of these players in othelloPlayers.py.

Your tasks

You need to submit code for following two functions/methods inside othelloPlayers.py:

heuristic(board)

  • Given a particular Othello board, return a heuristic value indicating the value of the board where a large positive number indicates a good position for white, and a large negative number indicates a good position for black. I have already given you code for the function heuristic, but it is very silly. You might need to experiment with this to come up with a good heuristic function. (You may not call the chooseMove function from within heuristic. Doing so would effectively not be calculating the heuristic on the current state, but would instead be looking ahead further.)

chooseMove(self,board) (within the ComputerPlayer class)

  • Given an Othello board, return a tuple (row,column) indicating the move that the computer chooses to make. Note that rows and columns start at 1, not 0, in order to make the game more playable for non-programmers.
  • You will code this up twice: once with basic minimax (that’s part 1), and the second time with alpha-beta pruning (that’s part 2).
  • Some more details: The number of plies is stored as an instance variable in the ComputerPlayer class. For example, a value of 1 for plies means that you should consider all possible moves you might make, and merely choose the one that gets you the best heuristic value. We will test your code by supplying our own heuristic function to see if your chooseMove method provides a move to a board position that yields the same heuristic value that ours does. Therefore, code this up carefully keeping that in mind, and make sure that you use self.plies as the number of plies to work with. Similarly, make sure that you do not call your heuristic function directly; rather, use the heuristic function that was initialized in the constructor for your ComputerPlayer object (e.g., use self.heuristic).

Multiple parts breakdown

Part 1 (team)

Grab the code, run it, and familiarize yourself with it. Turn in your program with a better heuristic function, and with chooseMove fully implemented with minimax, without alpha-beta pruning.

Part 2 (individual)

Start with the code that you wrote as a team, then turn in your program again, this time with alpha-beta pruning implemented (which you’ll do individually). Do this by having another ComputerPlayer class, this time called ComputerPlayerPruning. In your submitted code, chooseMove within ComputerPlayer should not have alpha-beta pruning, whereas chooseMove within ComputerPlayerPruning should. By doing so, you can debug by switching back and forth which kind of player object gets created by renaming your classes.

Grading

Part 1

Here’s how we will grade the first part of this assignment:

You will receive a grade M (meets expectations) for this assignment if…

  • when we run python othelloBoard.py and run it with one computer player against another, it seems plays itself
  • as we increase the number of plies for one player relative to the other, it should be more likely to win.
  • if we drop in a heuristic of our own (perhaps the simple one I provided), the number of times the heuristic is evaluated at each move should approximately match our results, especially at the early stages of the game.
  • if your heuristic seems to give reasonable values. If we try it out on boards of our creation, it should give high positive values for board positions that favor white, and high negative values for board positions that favor black.
  • when we look at your code, it appears to us that you have coded minimax.
  • your program is written to work in general, and not to only work for the specific tests that we have provided.
  • we see the expected behavior when comparing the results for the two different heuristics.

You will receive a grade of E (exemplary) for this assignment if you satisfy the above M requirements, and …

  • your code demonstrates a clear sequence of actions to achieve the goal at hand, and each piece is essential. Your code does not have notably more cases or conditions than it needs to.

Part 2

We will grade part 2 nearly identically to part 1. The key difference in the M grading is attempting to verify if you have done alpha-beta pruning correctly. This is challenging, but we will do our best. Specifically, we will be looking to see if the number of times the heuristic gets called drops relative to the non-pruning case, while still maintaining win performance.

Submitting your work

You should submit your files via Moodle. Do not put your name inside; we are going to grade the assignments anonymously, where Moodle will keep track of who you are but we won’t know until we’re done grading.