Chess Bot
This is a full chess program with a chess engine to play against. It supports both human vs. computer and computer vs. computer matches. The source code can be found on GitHub.
Installation Instructions
Download chess.jar. To run the chess program, double click on "chess.jar" and it should launch. It requires Java 6 or later installed. Most computers have a recent version of Java installed.
Issues on Windows
First, verify your Java installation. If that works, right click on "chess.jar", click on "open with", and select Java Platform SE binary (or a similarly named Java program).
Issues on Mac
First, verify your Java installation. If double clicking on "chess.jar" says: "chess.jar" can't be opened because it is from an unidentifed developer. You have to go to spotlight and search for "System Preferences". Click on "Security and Privacy". You'll see the following: "chess.jar" was blocked from opening because it is not from an identified developer. Click on "Open Anyway". Then click on "Open".
If that doesn't work, go to spotlight and search for "Terminal". Navigate to where you saved "chess.jar" by changing directories using the cd command (quick guide to terminal). Then run: java -jar chess.jar.
Issues on Linux
Make sure you have Java 6 or later installed. Run: java -jar chess.jar.
How It Works
This program is based on a project from one of my CS classes at CMU. The goal was to write a competitive chess bot. Most of the GUI code and chess logic was provided. My focus was on the search algorithm used. Modern chess programs use brute force to determine the optimal move, using a game tree. Because chess has so many moves, it becomes increasingly difficult to look a move ahead. To combat this, alpha-beta pruning is used, which removes parts of the search tree that won't provide an optimal move. My bot uses negamax as the main search algorithm, combined with alpha-beta pruning.
Alpha-beta pruning works best when there is good move ordering. If you try the best move first, all subsequent moves will fail to improve the score and most of the game tree will be pruned away. Most enhancements to chess programs focus on improving move ordering. Because there are substantially fewer nodes at depth n-1 than n, we can use the results from prior searches to improve move ordering. This process is called iterative deepening and is implemented in this bot.
In addition, I cache the results of previous searches in a transposition table, which provide a substantial speed up. This bot also uses quiescence search, the killer heuristic, and check extensions to improve its performance. Because chess openings are well studied, opening books are commonly used to allow programs to select moves from a pre-computed database of moves. This bot has an opening book, along with support for Polyglot books.
Chess programs evaluate how strong a position is by giving every board a "score" through an evaluation function. The simplest functions calculate how many pieces are on the board and how valuable they are. If you have more points than your opponent, you're ahead. My evaluation is fairly simplistic, based mainly on the scores of pieces, positioning of pieces, and bonuses for certain piece combination (e.g., two bishops are more valuable than one, more so if there are few pawns on the board). I'd like to add pawn structure and king safety to my evaluation function in the future.