The AI of ChessCraft

This page is a description of the artificial intelligence (AI) in ChessCraft. This page assumes you:

have seen a gameplay video, or played around a bit with the ChessCraft board editor and piece editor
have some introductory chess ability, like how to checkmate a king with just a rook and king.

There are two major sections. First I describe the problem, then my solutions.

See also the ChessCraft - How It's Made playlist.

Overview

ChessCraft is a mobile game where the player creates their own chess pieces and boards, then plays a custom built AI opponent. Only about half of classic chess AI techniques apply to ChessCraft. For the other half, I had to get creative with graph theory. Instead of explaining the classic chess AI techniques, I'll provide links.

Heads up! This next paragraph lists dense computer science subjects from classic chess AI. However the rest of this page is more human readable.

The AI uses an alpha-beta search with quiescence, move ordering, killer moves, and check extensions inside an iterative deepening framework with zobrist hashing for the transposition table. The piece square table and point value for pieces is calculated dynamically with graph theory. An extensive unit test suite and an automated chess puzzle test stabilizes and sanity checks the AI during development.

Heatmap of a piece square table.

This is a heatmap of a dynamically generated piece square table for white knights. On this board, white knights that reach any of the top squares on the board promote to powerful wizards. Knights want to be on redder tiles because they are close to a promotion. The AI uses these dynamically generated values to shuffle its pieces to better positions.

A Hard Problem

In this section I will explain why building an AI for ChessCraft is hard. It's a much harder problem than a classic chess AI.

Precomputation

There are more possible boards in ChessCraft than there are atoms in the universe (10^80), and over a trillion different pieces that can be made (5^8*40*40*2^13 ?) (that's not even counting special piece rules).

All strong AI systems for classic chess today will take advantage of a lot of precomputation. This means a computer will think a lot before the game starts to compute the best strategy. Sometimes this takes minutes, or even months on powerful computers. However the ChessCraft AI can't know the board or pieces in advance, so this kind of massive precomputation is impossible. For a good user experience, all precomputation must be done on a mobile device in just a few seconds.

Strategy

Most classic chess strategy is irrelevant in ChessCraft.

In classic chess, a decent check mate strategy in the endgame might include "get the king in a corner or next to a wall". However in ChessCraft, there are endless cases where this is the opposite of what you want to do. Consider this board with a white king versus black rooks (Krrrr):

A board where purple means the tile is disabled. Note that the outer black tiles are enabled.

If the white king slips into the outer black tiles, no black rook can attack there, and white can force a repetition draw.

However, consider a second board: a white king that moves like a rook, versus many black bishops (Kbbbb). In that case, black does want the king to move to the outside of the board (or similar places). Clearly, the idea of "corners" in classic chess strategy is insufficient.

In fact, much of classic chess strategy (connected pawns, passed pawns, knights in corners, bishop pairs, piece values) does not apply in general to ChessCraft. Those strategies were custom tailored to the classic chess board, and classic chess pieces.

Piece Values

In classic chess, you might roughly assign the following values to your pieces:

Pawn: 1
Bishop and knight: 3
Rook: 5
Queen: 7

However consider the following board:

A diagonal board where rooks are worth less.

A rook is arguably worth less than a bishop here. But how much less, and why? The AI must determine how good a piece is for any board.

The AI must also consider move distances. What if rooks can only move a distance of 1 or 2? On this diagonal board they are functionally the same as classic rooks, and their value should be identical. Whereas on an open 16x16 board, the range-2-rook is very weak compared to a classic rook.

For a decent AI, a heuristic needs to be made to estimate piece value which is useful on all boards.

Play Like a Human

A good AI is also fun. This means making mistakes appropriate for the computer difficulty, and non-determinism.

Getting an AI to play like a human in ChessCraft is more difficult than a classic chess AI because it is more difficult comparing move scores to eachother. Suppose there are three moves available with these scores, where high is good:

4.7
3.9
3.8

If this were classic chess where pawns are worth 1, we would know that not playing the best move means losing a pawn (roughly). An easy AI could make this mistake frequently, but a hard AI should almost never make this mistake. However:

A board where losing 1 point is not so bad.

In the example above, 1 point probably means a minor loss of position for one of many powerful pieces. However on other boards:

A board where losing 1 point is a big mistake.

Here, losing 1 point could cripple the game. A hard AI should never make that mistake.

Accepting and Refusing Draws

Knowing when the AI should accept, refuse, or offer a draw is a surprisingly hard and interesting problem. Consider the following cases describing human-like behaviour:

This game is not progressing, it is boring lately, I agree to draw.
I am losing badly so I happily agree to draw.
The game is not progressing, though I'm doing very well, so I'd like to see it "not progressing" for longer before agreeing to draw.
I'm doing badly, but this board design is so wild that scores are jumping all over the place. I refuse the draw because maybe things will work out.
I'm doing slightly bad near the start of the game. A grandmaster might agree to a draw but I won't - because playing is fun.

The ideas of "not progressing", "doing badly", and "fluctuate wildly" are relevant and easily describable with classic chess. However they are hard to describe for all variants in ChessCraft.

The concept "fluctuate wildly" has a lot of assumptions. Take for example this series of scores from a hypothetical stockfish game:

0.04
-0.1
0.01
-0.09

You might say that is fairly static. Well what if we multiply all values by 10:

0.4
-1.0
0.1
-0.9

Now you might say the game is "fluctuating wildly". The reason we think this is we're assuming these are classic chess scores - where a pawn is worth 1, bishop 3, etc. We're also assuming "0" is neutral - which only makes sense in classic chess since both sides start fairly even.

Whereas with ChessCraft, a change of 1 doesn't mean much if all pieces are queens and dragons. In another game 1 might be fluctuating wildly.

See also a discussion I started on a chess programming wiki titled: AI offer/agree to a draw like a human?.

Solutions

In this section I will explain some of my solutions to these hard problems. I'll focus on the solutions unique to ChessCraft, and will not explain the components of classic chess AI which I also used.

Piece Square Tables (PST)

Where do pieces generally want to be? I considered guidelines from classic chess like:

Knights want to avoid corners.
Kings want to stay in corners at the start.
Kings want to move to corners for the endgame.
Advanced pawns are worth more.

and generalized them with graph theory. Consider the following board which I used as a test while building the AI:

A board where purple means the tile is disabled.

Now consider the generated PST heatmaps for that board, where red is a high value location, and green is a low value location.

A heatmap PST for bishops.

Note: a piece can start on a disabled tile (this is allowed in the editor) and later jump off (but not return). That's why some disabled tiles have value in the PST.

A heatmap PST for knights.

To build the PST, we first construct a directed graph where every tile is a node, and every possible move is an edge. This allows a quick lookup of which tiles are accessible from which tiles for any piece. For example, on a classic board the position (0,0) and (6,6) are neighbours for a bishop because it can move from one to the other in one step. However they are four steps away for a knight.

Each tile is scored with a formula. The score is:

Where CountNeighbours counts how many tiles this piece can jump to if it starts at (x,y), with exactly d number of jumps, excluding neighbours it can jump to in fewer than d jumps.

There is also a penalty for disconnected graphs, or "colour locked" pieces like a bishop.

Two graphs are computed - one for movement, and another for captures.

Another bonus is applied for promotion tiles, taking into account promotions to higher (or lower) value pieces. For example, a queen could promote to a bishop, which is bad. So a piece closer to a good promotion is worth more, and a piece closer to a bad promotion is worth less. As a sanity check, this produces results very similar to the PST generated for top classic chess AIs like Stockfish.

A heatmap PST for pawns in classic chess.

Note how edge pawns only have two ways to reach their promote tile (one move and one attack), whereas the center tiles have three ways to promote (one move and two attacks).

Finally, consider this chess variant:

A board where knights promote to wizards.

If knights reach the other side, they promote to very powerful wizards. So knights prefer tiles with many knight-hop options to approach promotion tiles. Here's the generated heatmap:

A heatmap PST for knights in a chess variant.

Mistake Probability

The AI does not always pick what it considers the best move. This is for fun and for non-determinism. Suppose an AI has these three choices, and high numbers are good:

12.8
12.7
4.1

The AI will likely pick the top move (12.8). But there is a chance it will pick the second best move (12.7). There is a tiny chance, approaching zero, that it will pick the third (4.1). The AI difficulty setting tightens or loosens this probability.

I solved this problem by exponentially scaling the probability of choosing a move, based on the statistical variance of the move score compared to all move scores. Easier computer difficulties are more generous with the probabilities. Finally, I scale according to the sum of all piece values when the game starts.

Draws

Under what conditions does the AI offer, refuse, or accept a draw? It should behave like a human.

This is in my opinion one of the most interesting problems for the ChessCraft AI! I've only reached a partial (but useful) solution. The problem is described here, with my solution described in the last post.

Conclusion

Thanks for reading! Send me an email if you have any questions or suggestions. Or if you just want to chat about chess variant AI.

I have plans to further improve the AI, especially with parameter tuning. If you'd like to stay up to date on this, consider subscribing to the newsletter.