A 5×5 chess engine, and porting it to JS

For my second-year artificial intelligence coursework, I developed an agent for Chess Fragments, a 5×5 chess variant. Each player has five pieces, including the Right: a piece combining the movement of a rook and a knight. Pawns retain their double move, en passant and promotion. The agents were evaluated by playing against each other, so performance depended on searching accurately within a fixed time.

The version on the front page is a later JavaScript port of the original Python engine. The first part of this post describes the design presented for the coursework; the second covers the differences and errors found during the port.

Bitboards

As the board contains only 25 squares, the position of each piece type can be represented by a single 25-bit integer. Combining piece positions becomes a bitwise OR operation, testing occupancy becomes a bitwise AND, and the available moves for a knight can be found from a precomputed table masked against friendly pieces.

Sliding pieces require a different method because their moves depend on the occupied squares along each ray. Magic bitboards reduce the relevant occupancy to a table index. For each square, the possible blockers are masked, multiplied by a selected constant and shifted to produce an index into a precomputed attack table. A sliding-piece attack can therefore be found with one multiplication, one shift and one lookup.

The magic constants are found by testing random values. Each candidate is checked against every relevant occupancy for that square and retained only when any collisions map to the same attack set.

Search algorithm

The engine uses negamax with alpha-beta pruning and iterative deepening. It completes a search at depth one, then depth two, followed by increasing depths until the time limit is reached. The selected move is taken from the deepest completed iteration.

Although the earlier searches repeat some work, they improve move ordering for the next iteration. Alpha-beta pruning is most effective when strong moves are examined first, and the previous principal variation provides that ordering.

The time allocated to a move is calculated from the remaining clock and the estimated number of moves left in the game, with a reserve kept to reduce the risk of losing on time.

Search enhancements

Several additional methods reduce the number of positions that must be searched:

Null-move pruning. The engine temporarily gives the opponent an extra move. If the position still exceeds beta, the current player is assumed to have a move strong enough to cause a cutoff and the remaining subtree is skipped.

Late move reductions. Moves examined later in an ordered move list are less likely to be best. They are first searched at a reduced depth and receive a full search only if the reduced search improves alpha.

Check extensions. Positions in check are forcing and are searched for an additional ply before the static evaluation is accepted.

Futility and late move pruning. Near the leaves, quiet moves are omitted when the static evaluation is sufficiently below alpha that they are unlikely to improve the result.

Quiescence search. A fixed-depth search may stop part-way through an exchange and evaluate an unstable position. At the leaves, the engine therefore continues searching captures until the position is quiet. Delta pruning omits captures that cannot recover the difference between the current evaluation and alpha.

A transposition table stores earlier search results using Zobrist hashes. Because the hash is constructed with XOR operations, it can be updated incrementally when a move is made. Positions reached through different move orders produce the same key, allowing the previous result to be reused.

Move ordering

The effectiveness of alpha-beta pruning depends on examining strong moves first. The engine prioritises the transposition table move, captures ordered by most valuable victim and least valuable attacker, killer moves, counter-moves and finally quiet moves ranked by the history heuristic.

Evaluation

The static evaluation combines material values with piece-square tables. Each piece type has a material value and a 25-entry table rewarding suitable positions. The Right is valued at approximately twice a queen because the combination of rook and knight movement controls a large proportion of a 5×5 board.

Porting the engine to JavaScript

Running the engine in the browser required a JavaScript implementation. Most of the code could be translated directly, but the magic-bitboard indexing relied on wrapped 64-bit multiplication. JavaScript numbers are double-precision values, its bitwise operators use 32-bit integers, and BigInt was too slow for the search loop.

Math.imul provides wrapped 32-bit multiplication. On a 25-square board the relevant occupancy contains at most six bits, so 32-bit magic constants are sufficient. I generated a new set and checked every constant exhaustively.

The first browser version still selected moves that lost major pieces without compensation. Since the Python and JavaScript engines were intended to implement the same design, the Python version could be used as a reference.

I compared both engines directly under Node. Their attack sets were bit-identical across 150,000 random lookups, perft matched to depth four, and the evaluation matched across hundreds of random positions. These checks ruled out move generation, make and unmake, and static evaluation, leaving the search as the source of the disagreement.

Three separate search errors were identified:

The null-move window. The null-move search used a null window. At the root, however, the window was infinite. Negating infinity to construct the child window produced a degenerate bound that returned positive infinity immediately, causing a false beta cutoff and invalid mate scores.

The check extension. The Python version calculates an effective depth when deciding whether to enter quiescence, but recurses using the original depth. The port increased the depth itself, so repeated checks could prevent the search depth from decreasing and generate false mate results.

Mate scores in the table. The Python engine stores mate as positive or negative infinity. The port used a finite score containing the distance to mate, but did not adjust the score by the current ply when writing to and reading from the transposition table. A mate found deep in the tree could therefore be returned as though it were much closer.

In each case, the Python implementation depended on a property that was lost during translation rather than on an obvious difference in the overall algorithm.

Current result

After these fixes, the browser engine still selects a different move from the Python version in approximately one position out of forty, sometimes with an evaluation several hundred centipawns lower. This is expected because the Python engine contains additional pruning refinements that were not included in the port, making it stronger at the same search depth.

With a limit of 350 milliseconds per move, the JavaScript version normally reaches depth ten or eleven and searches about 400,000 nodes. The submitted Python coursework is not public, but the JavaScript port is unminified and can be read in js/chess.js.