This is a partners project. Yay! You may discuss high-level ideas with other groups, but any viewing, sharing, copying, or dictating of code is forbidden. Dean’s Tutors may not read your code.
In this project, you will write several Othello bots and compete against other bots on the CS 2 Othello server. You will implement several (graph/tree) algorithms and be able to see a significant difference in the quality of the bots. Unlike in previous projects, you should feel free to use any and all Java data structures (since you’ve now implemented them all yourself).
Before attempting this project, click here to read the handout on the algorithms!
The project is designed so that you need minimal Othello knowledge, but we recommend you familiarize yourself with the basic rules just in case. We have written all of the Othello-specific code (evaluator, move generation, board, GUI, etc.); all you will be responsible for is implementing the game tree searching algorithms. You may, of course, improve the board/evaluator/etc. to your liking.
Always Forward, Never Backward
This project is NOT data structures project! Because the built-in Java Stacks and Queues are…deficient, we’ve chosen to still use your
IDeques. You will need to copy those forward
as usual, but you should feel free to remove these dependencies if you prefer to!
edu.caltech.cs2.project08.board: You also shouldn’t need to look at any of these files. In Othello, the game position consists of the board and some auxilliary information that these classes keep track of. We list below the only relevant methods you need to be aware of are from the
public IDeque<Move> getMoves()
Generates a list of valid moves that the current player could make.
public void makeMove(Move m)
Applies the provided move to the board changing the state of the game.
public void undoMove()
Undoes the last move applied to the board.
edu.caltech.cs2.project08.game: This package contains classes related to playing a game of Othello. It includes our provided evaluator (which you may edit) and a timer class which might be useful if you want to stop your bot after a certain amount of time. We list the methods you might need for these classes below.
public int eval(Board board)
Returns a number representing “how good” the provided board is. Note that the
Boardclass maintains information about the current player (white or black), and
evalwill return a value from the perspective of the current player.
SimpleTimer.java: This class gives you a way to only allow
generateMove(the method that finds the next best move) to be time limited. You do not have to use it, but if you do, feel free to add/change methods to your liking.
Bot.java: This class sets up the bot that will be used on the Othello server. You must register your team with the Othello server by going to
Make sure to write down the password the server provides as we have no way of recovering it for you.
BestMove.java: This class will be useful when writing your bots, because you’ll need to return both a move and its value. In substance, this is a lot like the
Entryclass from previous projects.
- take the very last ten games you play against a bot,
- count a loss as 0, a draw as 0.5, and a win as 1,
- if your “bot score” is at least 8, you “beat” the bot
The Othello Server
For this project, you will eventually need to compete with our bots. To do this, you will connect to the CS 2 Othello Server using the provided client. We recommend playing games with your bots on the server relatively frequently, because it is a fun and interesting way to debug your code. Additionally, you can use the server to compete with other students’ bots.
|who||Lists all the players currently on the Othello server.|
|scores||Lists the results of the last ten games your bot has played with every bot.|
Playing on the Server
To have your bot play on the server, edit
Bots.java until you’re satisfied and then run the “Run” target. You will need to
log in with your chosen bot name and password from the Othello server. Your account may only play one game at a time.
Part 1: Minimax and AlphaBeta
In this phase, you will write two
MinimaxSearcher: Implementing Minimax
MinimaxSearcher should implement the Minimax algorithm as described in the games handout.
While you may use a
bestMove global variable that keeps track of the “best move so far”, we recommend that you
BestMove object from your
minimax method instead.
AlphaBetaSearcher: Implementing Alpha-Beta Pruning
When starting to implement this
Searcher, it will help to copy over your
MinimaxSearcher code and edit it directly. The hardest
part of this particular implementation is understanding exactly how the algorithm works. We recommend you look very carefully at the diagrams
in the games handout. Feel free to look up other explanations of the algorithm on the internet or in your textbook.
Part 2: Using Your Algorithms
In this part, you will attempt to beat our bots on the CS 2 Othello Server.
Beating The Bots
We have placed two bots on the server:
Oogee. Your next task is to consistently beat one or both of these bots.
We will consider you to have “beaten” a bot based on the following calculation:
Beating both of the bots gets you an A (assuming you also pass Minimax/AlphaBeta). You may implement anything to beat these bots. Go nuts.