4x4 Chess

Unique Legal Positions

The number of unique legal positions (NULP) is a basic measure of game state-space complexity. The defining features of this number: 1. Only legal positions are counted. 2. Only unique positions are counted. Please check the NULP web-site for detailed discussion.

Some definitions:

Position - Any placement of pieces on a 4x4 board (one piece per square, so from 0 to 16 pieces can be present), plus information about what side has the right to move (either white or black).

Legal position - Any position that has one white and one black king, where side to move does not give a check (does not attack opponent's king), and where there are no white pawns on 4-th rank and no black pawns on 1-st rank.

Unique position - In the context of counting positions, number of unique positions means that we count all symmetrical variants of one position as single position. All possible symmetries are considered, including horizontal, vertical, diagonal or any combination (which effectively includes board rotation as well). Also this includes changing the side to move and swapping the piece colors. Example - all of the following positions are counted as just one position for the NULP:

k3/4/4/KR2 wwhite to move 3k/4/4/2RK wwhite to move KR2/4/4/k3 wwhite to move 2RK/4/4/3k wwhite to move 4/4/R3/K2k wwhite to move K2k/R3/4/4 wwhite to move 4/4/3R/k2K wwhite to move k2K/3R/4/4 wwhite to move
K3/4/4/kr2 wblack to move 3K/4/4/2rk wblack to move kr2/4/4/K3 wblack to move 2rk/4/4/3K wblack to move 4/4/r3/k2K wblack to move k2K/r3/4/4 wblack to move 4/4/3r/K2k wblack to move K2k/3r/4/4 wblack to move

In this case 16 different positions in fact correspond to just one unique position. In other cases proportion of unique positions may differ from 1/16, particularly when pawns are included, or when position is diagonally symmetrical.

Game or Puzzle?

A game should have a starting position. 4x4 chess does not have one, so technically it's not even a game, but perhaps some sort of puzzle. A puzzle can have many possible initial positions, and some goal should be reached through a sequence of legal moves. This is exactly what 4x4 chess is in the current form. All possible initial positions are allowed, and the goal is to checkmate against the best defense (or against any defense).

In a game (like 8x8 chess) legal positions are those that can be reached from the starting position with a sequence of legal moves. This strict definition makes for a very narrow set of legal positions. In a puzzle setting (like 4x4 chess), on the other hand, any position can be the initial one, creating a much larger and more interesting set of positions.

Most games can be generalized into puzzles by discarding the starting position and instead looking at all possible positions that don't directly break the other rules. Strong solution of such puzzle may be harder to obtain, but also provides more information and more fun. For example, it may allow to find alternative interesting starting positions. Such "ultra-strong" solution was obtained for 3x4 chess in 2009, and is what I am aiming for in 4x4 chess.

4x4 chess NULP

The total number of unique legal position in 4x4 chess is 3,677,542,994,054,890. About 3.68 quadrillions, or about 3.68 peta-positions. A 16-digit (52-bit) number.

This number was obtained by meticulously counting all possible unique legal positions, using idle mode of the solver (where it just counts the positions without solving them). This task itself already took some weeks (faster counting is possible, but was not a priority).

Of course, independent verification would be more than welcome!

Comparing 4x4 chess with other games and puzzles:

3x3 Chess,
all unique legal positions (no starting position)
5.5 x 107sashawww, 2011
6x6 Othello (Reversi),
all reachable from standard starting position
4.0 x 1010Feinstein, 1993
3x4 Chess,
all unique legal positions (no starting position)
1.7 x 1011Kryukov, 2009
5x5 Go4.1 x 1011Tromp, 2005
Connect Four (standard 7x6 board)4.5 x 1012Tromp, 2010
4x4 Chess,
all unique legal positions (no starting position)
3.7 x 1015
6x6 Go6.3 x 1016Tromp, 2005
Rubik's cube, all positions that can be solved
without disassembling the cube
4.3 x 1019Rokicki, Kociemba and Davidson, 2010
English Draughts (Checkers),
all reachable from starting position
5.0 x 1020Schaeffer et al., 2007

In particular, 4x4 chess is 21,981 times larger than 3x4 chess and 67,075,421 times larger than 3x3 chess.

If you spend 1 millisecond thinking about each 4x4 chess position, it will take about 117 thousand years to visit all of them.

If you use 1 byte to store each position, you'll need 3.68 petabytes, which means 1226 hard disks of 3 TB each. If you only use 1 bit per position, you still need 460 terabytes, or 153 x 3 TB hard disks. (Fortunately, even better compression is possible).

(Also 3,677,542,994,054,890 factorizes into 2 x 5 x 367,754,299,405,489).

NULP by number of pieces

PiecesUnique legal positions

The plots below shows how NULP depends on adding extra pieces in 4x4 chess, compared to other board sizes.

The 8x8 chess numbers are based on Eugene Nalimov's statistics (summed up by Guy Haworth and posted at the EGTB forum), so they are not NULP values. Some unique positions are not counted (those with castling rights, as well as 5-vs-1-man positions), and some positions are counted twice (diagonally symmetrical with both kings on the a8-h1 diagonal).

NULP by number of pawns

These plots show how the 4x4 chess NULP varies depending on number of pawns and the total number of pieces.

The plot below shows the proportion of positions with each particular number of pawns among all positions with the same total number of pieces.

Home © 2011 Kirill Kryukov
Available under the CC BY 3.0 License