Chessmate Java Chess AI Published Thu May 30 17:45:00 SAST 2013

Update: My 10-year old Java Chess AI code has made it into a Minecraft mod called MineChess:

Chessmate is a simple Java-based chess engine I wrote in high school, which is now open source under the MIT licence. It's buggy and has a few crippling limitations, but still plays a decent game.

At the time I was 17, so I thought the code would be really bad, but it still works and beats me most of the time (I'm not very good at chess). It won a regional prize or something (cash must have gotten lost in the mail). Overall I'm pretty proud of it :).

See the source code on GitHub.

Limitations

Chessmate has no opening book and cannot castle, take en passant or promote pawns. If you harbor sado-masochistic tendencies, you can easily modify the Board class and positionEvaluation heuristic function to add castling.

How does it work?

Chessmate uses an iterative deepening minimax search algorithm with alpha-beta pruning and simple horizon detection during exchanges with an original heuristic function.

That's a fancy way of saying it builds a tree of moves, rates each move with a number using an estimate called a "heuristic function", then keeps exploring promising leaf branches. Minimax assumes its opponent will make the best sequence of moves it can think of and will then counter with a move that minimises your opportunities while maximising its own.

Performance

Chessmate has a terrible early game due the lack of an opening book, an average medium game and a pretty strong end game. It runs pretty fast for a Java application. I remember it searching through 500k moves/second on my shitty PC in 2005. I now get about 1.2M nodes/second on my Macbook Air running on a single thread.

Heuristic Function

The original heuristic function is quite simple, but performs well given sufficient search depth (5 seems to be the sweet spot). The positionEvaluation method returns a float value that is positive or negative based on whether it's winning or losing, respectively. It also uses some of the board control data set in the setControlData method.

The following factors are weighted to evaluate each board position:

• Material gain (sum of the value of your pieces minus the opponent's)
• Attacking the opponent's pieces
• Defending it's own pieces
• Controlling the board, with extra weight for controlling the four squares in the centre of the board.

The structure of these evaluation functions are terrible and really hard to unit test. Having read through the evaluation code, I am almost certain that the board control data is fundamentally broken. Oh well.