The Redfish chess engine

Redfish is an open-source chess engine using the MinMax-algorithm, bit- and 0x88-boards and -up to this point- a simple piece counting evaluation function.

During my recent climbing trip to Spain I spent some time to start the realization of a chess engine in C++. My main goal with this project is to strengthen my C++ programming skills therefore it relies on well-known techniques regarding the implementation of chess engines and does not have the aspiration of developing something completely new. Nevertheless I want to share my thoughts with you as Redfish might be helpful as a starting point for other projects.

The big picture

In terms of game theory chess is a sequential, finite, perfect-information, zero-sum game being played by two players. This results in the ability to model the game as a finite, uni-directed, acyclic and rooted graph with each vertex representing a game state, each edge representing a legal move on the game state related to the outgoing vertex and each leaf representing a final game state with an associated value for a draw (= 0) or a win for one of the players (+1/-1). Each possible game can now be thought of as a path from the root to some leaf of the resulting graph.

Decision rule

With a graph as the game model and the knowledge of chess being a zero-sum game the problem of finding the best move for a given position comes down to a search problem: One tries to find a path in that graph that leads to the maximum benefit (= value of leaf) possible for the current player taking into consideration that the other player will try to minimize this exact same benefit value leading to a maximum of his own benefit. This is formalized as the MinMax-Algorithm also used by Redfish.

Node evaluation

For some move-based zero-sum games the MinMax algorithm can be applied directly and the algorithm will compute the best possible move for ever game state. The problem with chess though is that the game tree is far too large to be searched exhaustively (the number of possible paths is estimated to be at the order of \(10^{123}\)¹). Therefore the game tree is built up to a defined depth where it is cut off and an evaluation function is applied as approximation for the definitive +1/0/-1 values at the leafs. This function is a heuristic and can be defined on various factors like the type and count of pieces per player or some measurement of positional strength. Defining a useful evaluation function is one of the major issues when building a chess engine.

Implementation overview

Redfish (find the source on GitHub) is split into four major components:

• Board representation: A data structure representing a game state including the board constallation itself and other information like whether casteling is possible or which player moves next. Redfish uses a mixture of the 0x88 representation and Bitboards as the 0x88 form is better to lookup whether at all and which piece is on a given position while 64-Bit Bitboards sometimes allow faster computations on individual piece types e.g. their count as hamming weights.
• Move generation: The move generator generates all legal moves possible on a given game state. As this is a performance critical component I put some effort into it and managed to implement it completely branch-less using pre-generated jump tables and a square-centric iteration over all possible moves. The jump tables consist of 64-Bit masks for every board square and piece-type representing possible move targets. Another set of pre-generated tables indicate squares that need to be empty for the movement of a given origin and target to be valid - e.g. for sliding pieces. A nested loop iterating for every source square over every target square is now able to use those tables to generate all legal moves using only bit-operations and arithmetics (see src/MoveGenerator.hpp in the repo).
• Evaluation function: The evaluation function evaluates a given board and returns some numeric value representing the advantage for one player and the disadvantage for the other player. At the time I was writing this post Redfish used a simple piece-counting evaluation using commonly associated values for each type of piece. Any type of positional strength has not been taken into consideration yet.
• Engine: The MinMax algorithm is the central “glue”-piece using the first three components to find the best move for a given game state.

User interface

In order to actual run the game engine I wrote a basic console interface looping in printing the current board state, reading and applying a move from stdin and responding with a calculated move using the game engine:

Redfish Copyright (C) 2016 Arne Groskurth.
(Licensed under the GNU General Public License v3.0.)

    a   b   c   d   e   f   g   h
  +---+---+---+---+---+---+---+---+
8 + r + n + b + q + k + b + n + r +
  +---+---+---+---+---+---+---+---+
7 + p + p + p + p + p + p + p + p +
  +---+---+---+---+---+---+---+---+
6 +   +   +   +   +   +   +   +   +
  +---+---+---+---+---+---+---+---+
5 +   +   +   +   +   +   +   +   +
  +---+---+---+---+---+---+---+---+
4 +   +   +   +   +   +   +   +   +
  +---+---+---+---+---+---+---+---+
3 +   +   +   +   +   +   +   +   +
  +---+---+---+---+---+---+---+---+
2 + P + P + P + P + P + P + P + P +
  +---+---+---+---+---+---+---+---+
1 + R + N + B + Q + K + B + N + R +
  +---+---+---+---+---+---+---+---+

To be continued…

At the time I wrote this post Redfish is just barely able to play a valid game. Some types of moves like casteling and some game rules like timing in general and the 50-move draw are not implemented yet. Further points like switching to Alpha-Beta pruning, introducing move ordering and implementing lookup tables for already evaluated board positions are kept in a Todo-list in the README.md.