Project 4: Checkers

Overview

You will develop an intelligent AI for the game of Checkers. You will implement alpha-beta search as well as some customized board evaluation functions.

Setup

Clone the Github repository csci335. Push your own copy to your Github account as a private repository, and add the instructor as a collaborator.

Programming Assignment:

The files are placed in three packages.

  • checkers.core
    • Checkerboard: Represents a checkerboard. Key methods include (but are not limited to):
      • getLastMove(): Returns the last move played on this Checkerboard.
      • gameOver(): Returns true if the current player to move has no legal moves.
      • getCurrentPlayer(): Returns a PlayerColor representing the player who is about to move.
      • playerWins(): Returns true if the specified player has won the game.
      • getNextBoards(): Generates every possible successor board given the current position.
      • numPiecesOf(): Returns the number of pieces in play for the specified player.
    • CheckersSearcher: An abstract class that your search algorithms will extend.
    • Move: A game move from one location to another.
    • Piece: An enum representing the color and king-status of a given checkers piece on the board.
    • PlayerColor: An enum representing a player color.
  • checkers.gui
    • AutoCheckers: A GUI that can run exprimental tournaments to compare the ability of different AI players.
    • Checkers: A GUI that allows a human to play against either another human or a computer opponent. To move a checker, click and drag it to the target location.
  • checkers.evaluators: Package where you will place your board evaluation functions that implement the ToIntFunction<Checkerboard> interface. A dummy evaluation function that rates all positions equally (NoPreference.java) is included as an example.
  • checkers.searchers: Package where you will place your search algorithms that extend the CheckersSearcher class. A simple search algorithm that looks only at the next move (OneLevelGreedy) is included as an example.

Implementation

  • Implement a basic material board evaluation function. It should subtract the number of pieces the opponent has from the number of pieces the current player has, and return that difference.
  • Implement NegaMax search. Determine the depth it can generally reach in about ten seconds of time. This number will vary considerably based on the specifics of the board position, so for this purpose try to figure out what the worst case is like.
  • Play against the program. Assess its performance subjectively. In your written asssessment, use concrete examples of its play.
  • Use AutoCheckers to run your NegaMax player with the basic material evaluator against a random player 32 times. Assess its performance.
  • Make a copy of your NegaMax searcher, and modify it to implement alpha-beta search. Determine the
    depth it can generally reach in about ten seconds of time. Assess the improvement.
  • Play against the alpha-beta searcher with your basic evaluation function but the increased search depth. Again, subjectively assess its performance.
  • Having evaluated your player, attempt to improve the evaluation function. Then evaluate it again as you did for the first function. In addition, use AutoCheckers to compare your first and second evaluation functions.
  • Attempt to improve your search algorithm. The requirement is to perform two modifications, but you may
    choose more if you would like. You may choose to do any of the following:
    • Extend the search with the search-until-quiescent strategy
    • Extend the search with a singular extension
    • Create a database of solved endgame positions
    • Create a database of openings
    • Implement a transposition table
    • Implement an ordering heuristic
    • Perform any other modification of your choice
      • Your modification must be approved in advance by the instructor if it is one of the two required modifications.
      • There is no need to discuss with the instructor additional modifications beyond the first two.
  • Continue to modify both the search algorithm and the evaluation function until you find performance to be satisfactory.

Paper

Your paper should include the following:

  • A description of each search strategy you implemented, along with its rationale.
  • A discussion of how you modified the board evaluation function, again with its rationale.
  • Qualitative assessment of the quality of play.
  • Quantitative information about the time necessary for alpha-beta searches of varying depths.
  • A quantitative assessment of relative quality of board evaluation functions.
  • A quantitative assessment of impact of the modifications to the search algorithm.

Submission

  • Post your code on Github in your private repository. Make sure the instructor is added as a collaborator.
  • Upload your paper to Microsoft Teams.

Assessment

  • Level 1
    • Complete NegaMax and the basic material evaluation function.
    • Write up a performance evaluation in your paper as described above.
  • Level 2
    • Complete alpha-beta search and an improved evaluation function.
    • Include evaluation of these improved search and evaluation functions as described above.
  • Level 3
    • Implement at least two additional search extensions.
    • Include evaluation in the paper.
    • Continue improving the search and evaluation function until performance is impressive in some way.
    • Document in your paper the iterative improvement process that produced impressive performance.