Overview

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!

Provided Code

• 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 ArrayBoard class:

  • 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.

  • SimpleEvaluator.java:

    public int eval(Board board)

    Returns a number representing “how good” the provided board is. Note that the Board class maintains information about the current player (white or black), and eval will 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.

• play:

  • 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

    http://goldendoodle.caltech.edu

    Make sure to write down the password the server provides as we have no way of recovering it for you.

• edu.caltech.cs2.project08.bots

  • 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 Entry class from previous projects.

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.

Commands

Command	Description
match name	Challenges name to a match. The match will start immediately if the bot is not busy.
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 Searchers: MinimaxSearcher and AlphaBetaSearcher.

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 return a 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: Better and 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:

• 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

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.