3x4 Chess

Introduction

3x4 chess is now strongly solved. This means that game result and the best move is known for any possible position. Firstly, what is 3x4 chess? The board is 3 squares wide and 4 squares tall. There is no castling and no pawn's double first move. All other chess rules apply as usual. Starting position is not defined, instead all possible positions were analyzed, including all possible combinations of forces. Pawns are allowed on the first rank, for completeness.

In total there are 167,303,246,916 unique legal positions in 3x4 chess. 12 squares, 12 digits. All symmetry is taken into account, only one of all possible symmetrical variants of each position is counted. Also these are only positions where white is to move. This is about 3,000 times more than in 3x3 chess.

The result

Is 3x4 chess generally won, lost, or drawn for the side to move? Since starting position is not defined, all we can do is count wins, draws and losses among various possible positions. There are 48,713,659,039 wins (29.12%), 103,995,040,255 losses (62.16%), and 14,594,547,622 draws (8.72%) in the complete database. Taking this literally we would have to conclude that 3x4 chess is won for black, with side to move (or white) scoring only 33.48%.

Of course the above score is not real since we counted all legal positions, which include checkmates too. Checkmate is a position where side to move is already lost, yet it is perfectly legal. In fact 31.11% of legal positions in 3x4 chess are checkmates — 52,048,121,059 of them. After removing checkmates we are left with only 51,946,919,196 losses. Now white score becomes 48.60% which looks much better. Is this the answer then?

Not yet. For one thing, we are still counting stalemates. No moves are possible from a stalemate position, the game is over, so we probably don't want to count them. But this is not a big problem because there are very few stalemates in 3x4 chess (0.15% of legal positions) and because they are all draws anyway.

The bigger problem is with positions where side to move is in check. The identical position with opposite side to move would be illegal, so it is not counted or stored in the database. However when side to move is in check, it's totally fine, and such positions in fact constitute 43.76% of the complete database — 73,205,819,459 of them in total. The solution is to not count these positions too, restoring the symmetry.

So, only positions where side to move can in fact make a move, and is not in check, should be used to compute the side-to-move score. There are 41,799,558,387 such positions in 3x4 chess, or 24.98% of all unique legal positions. Among them there are 25,066,806,249 wins for the side to move (59.97%), 11,604,499,663 losses (27.76%), and 5,128,252,475 draws (12.27%). This means that side to move scores 66.10%.

Query interface

Here you can check the true value for any imaginable 3x4 chess position. Input the position in FEN format, then press "Analyze" to query the database, and "Play" - to play against a perfect opponent. Alternatively, the shorter format from 3x3 chess is also supported.

Problems

A random problem will be picked every time you click on one of these links:

The longest line

The longest checkmate line in 3x4 chess takes 43 moves (85 plies). White aims for the shortest mate, black for the longest. Here is one of such positions:

• wKb.pPrrNBkBN

So, even with 11 pieces the 43-move long winning line is already possible, but not with 10 pieces.

Some of the longest lines to conversion (with DTC metric):

• 7 pieces — 26 moves — wKBk..P.BR.b.
• 9 pieces — 16 moves — wkpnpRpK..P.N
• 10 pieces — 14 moves — wRQBKB.PPPk.q
• 11 pieces — 7 moves — wN.BNRPQNqKPk

In case if you want to see the longest possible line with particular piece combination, now you can. For every piece combination I saved an example position, resulting in longest winning line. And another one, resulting in longest losing line. You can download the list of all such positions:

• Kirr-3x4-max-DTM-All.zip (2.5 MB).
• Kirr-3x4-max-DTC-All.zip (1.8 MB).

Just copy/paste any position into the query interface above.

Statistics

Number of unique legal positions with every distance to mate (or conversion) in each piece configuration. Only unique legal white-to-move positions are counted.

Number of checkmates, stalemates, positions in check, and all other positions in the complete database, by piece count:

Proportion of wins, losses, and draws among the positions with legal moves and not in check:

Spectrum

Metric spectrum for DTM and DTC. Horizontal axis shows metric value, in the order: draw, checkmate, win in 1, loss in 1, win in 2, loss in 2, and so on. Vertical axis shows how large is relative number of positions with each given metric among all unique legal positions, in percents, log scale.

Zugzwangs

Zugzwang is a position where the side to move would prefer if it was the other side's turn to move. There is no en-passant and no castling in 3x4 chess, so each placement of peaces on board corresponds to exactly two positions - one with white to move, and another with black to move. When one of such positions is a zugzwang, it necessarily means that the other one is a zugzwang too. So, for simplicity, in 3x4 chess we can discuss piece placements as being zugzwangs or not, rather than individual positions. (see Zugzwang in Wikipedia for discussion on zugzwangs in standard chess).

Note that both positions, corresponding to a piece placement, should be legal for a meaningful zugzwang. Furthermore, I analyzed only piece placements where both positions have legal moves. (There should exist some half-point zugzwangs involving a stalemate as one of the positions, but I did not consider those). Note that while normally a piece placement corresponds to two different positions, sometimes the two positions are mirrored images of one another, which means that such piece placement effectively corresponds to just one unique legal position. Therefore the number of piece placements does not equal the number of corresponding unique legal positions divided by 2, but is somewhat larger than that. Also note that not all positions have a legal counterpart. Particularly, any position where the side to move is under check, has an illegal counterpart position.

With all this in mind, I counted the unique piece placements where both positions are legal and have legal moves. There are 20,440,070,124 of them in 3x4 chess. 2,778,286 (0.01%) of them represent full-point zugzwangs, 58,296,519 (0.29%) - half-point zugzwangs.

Below you can download the list of example zugzwang positions for every ending. The one with larger DTM values is chosen as example in each case. Another file is for DTC. Both lists also include examples of anti-zugzwang positions for each ending. Copy/paste any of those positions into query interface to explore in detail.

• Kirr-3x4-maxzug-DTM-All.zip (1.4 MB)
• Kirr-3x4-maxzug-DTC-All.zip (1.1 MB)

Here is a DTM full-point zugzwang with longest lines:

• wKbNRPbBprnBk

Value of the right to move

Generalizing the zugzwang analysis, it is possible to classify all those unique piece placements (20,440,070,124 of them) into five classes, depending on how much each piece placement favors the side to move. This means - how much more (in points) the side to move will score (with perfect play of both sides), compared to how much it would score if it was the other side's right to move. This value can be 1, 0.5, 0, −0.5, or −1. The latter two cases correspond to a half-point and a full-point zugzwang, respectively.

Some of the questions I was curious about (always talking about those 20 billion unique piece placements):

• What is the overall average value of the right to move? - It appears to be about 0.32 of a point.
• Which ending has the largest average value of the right to move? - krrrrrkrrrrr, where the right to move is worth +0.938 of a point, on average. (Out of 129 piece placements there, 120 have +1 for the side to move, 2 have +0.5 and 7 have 0).
• Which ending has the smallest average value of the right to move? - kqqqqqppppkn, where the rigth to move is worth -0.215 of a point, on average.
• Which ending has the largest proportion of zugzwangs? - kqqqqqbnnnk, where 53.8% of piece placements are zugzwangs (14 out of 26).
• Which ending has zugzwangs, but in smallest proportion? - kqqrnnkbnp, where there is only one zugzwang among 855115 piece placements.
• Which ending has the largest proportion of full-point zugzwangs? - kqqqqqkqqqqq, it has 1 full-point zugzwang, and 15 piece placements in total.
• Which ending has full-point zugzwangs, but in smallest proportion? - kqqrbnkbbnp, it has only one full-point zugzwang among 1571511 piece placements in total.

Value of the rigth to move, for all unique piece placements where both sides are not under check and have legal moves:

As well you can download the detailed statistics, which lists the number of piece placements of every class in each individual ending.

• Kirr-3x4-value-of-the-right-to-move-All.zip (3.6 MB)

The database

I solved 3x4 chess by constructing a database of all possible positions. Please see Endgame tablebase in Wikipedia for introduction to this technique.

I constructed two databases: one using DTM (distance to mate), and another using DTC (distance to conversion) metric. Both databases are available to query online above, in the Query interface section. Although the interface does not need the 12-piece tables, they are still constructed for statistics and mining purposes.

In both DTM and DTC cases it turned out (as expected) that one byte is enough for one position. I don't store any broken, illegal, or redundant positions, so the complete (3-to-12 pieces) uncompressed database takes 167 GB (for DTM, and another 167 GB for DTC metric). Adding compression achieves 50.6 GB for DTM, and 18.4 GB for DTC database.

Please note that DTC provides a significant space saving (x2.75 for complete database) compared to DTM. With DTZ the effect should be even larger. Also, you can see that DTC advantage increases as the board becomes more filled with pieces, as expected.

Additional space saving can be achieved by further "shrinking" the database. "Shrinking" here means deleting one table from every pair of tables with switched side to move (with asymmetric meterial). For example, normally both kpk (side to move has a king and a pawn) and kkp (side to move has a bare king) tables are present. Perfect play is still possible even if one of these tables is removed - it will just require an extre ply (or more) of search. In this example kpk can be safely deleted. This is what "shrinking" does. In addition it deletes all 12-piece tables.

After shrinking the complete database size is reduced to 11.8 GB for DTM and 3.8 GB for DTC.

Solver software

Here I am sharing the old Windows binaries of the solver. You can use it to build and query your own copy of the 3x4 chess database:

• v.1.1.0: files/3x4-Chess-Solver-1.1.0-2010-03-25-Win32.zip

• OS: Windows XP or later.
• RAM: 2 GB per instance is what I tested. Less may or may not work.
• Storage: 18.4 GB for complete DTC and 50.6 GB for complete DTM database, with 'auto' compression. Uncompressed database is 167 GB (either DTM or DTC), but normally you don't need it.
• Time: A complete 3-to-12-piece 'auto' compressed DTM database can be built in about 10 days on Phenom II X4 905e with 8 GB or RAM (running 4 instances). DTC is slightly faster, disabling compression is also faster.

• v.1.0.0: files/3x4-Chess-Solver-1.0.0-2009-12-20-Win32.zip

MD5

These files contain MD5 signatures of all files in the complete 3x4 chess database (version 1.1.0). You can use them as one of the ways to check the integrity of your local copy of 3x4 chess database. (Use "md5sum –c <filename>" command on each .md5 file).

• Kirr-3x4-MD5-DTM-All.zip (3.8 MB)
• Kirr-3x4-MD5-DTC-All.zip (3.8 MB)

Alternative ways to check your database include computing statistics with "3x4c –stat" command (and compare with the reference statistics that you can download from this site), and running full verification with "3x4c –verify" command. Both of these methods will take longer time to complete than MD5 check (much longer for the latter one).

Verification

This is the only complete 3x4 chess solution I am aware of. I did my best effort to make sure there are no errors, but only comparison with another independently obtained solution can make it certain. If someone else created a complete or partial solution, we could compare the statistics, and hopefully get the same numbers. My data is available above for anyone interested.

For a partial verification, Marc Bourzutschky applied his generalized chess solver to 3x4 board, and kindly posted the statistics for endings with up to 6 pieces, excluding 5-vs-1 (EGTB Forum, 2009-09-28). Our maximum DTM values matched for each ending. Ideally we would compare the number of positions with each DTM in each ending. In this case it was unfortunately not possible, because of differences in counting. I count only unique legal positions, while Mark's statistics includes some redundant positions.

With a long computation there is always a possibility of spontaneous errors caused by hardware (even with correct algorithm). I think it is safe to exclude the possibility of such errors affecting the 3x4 chess solution now, because I already constructed the complete database at least twice (both DTM and DTC), getting the exact same statistics both times. (I had to reconstruct the database when transitioning to version 1.1.0 of the solver, because of changes in indexing). Additionally Lutz Nebe downloaded the solver and constructed the complete database (probably DTM) on his machine, obtaining statistics identical to mine (EGTB Forum, 2010-05-25).

Any additional verification would be welcome. Also, if you notice anything strange in the web-interface or on this page, please let me know.

Counting positions

I chose to count only unique legal positions in all statistics reports, because it's the smallest meaningful position count. There are many ways to get a larger number, for instance, counting separately symmetrical positions (vertical, horizontal, or both; only some or all), counting some illegal positions, also "broken" positions (featured in some popular chess EGTB formats). It's difficult to choose one out of all the inefficient counting schemes.

In case of my 3x4 chess solution it was natural to use unique legal positions as a unit, because these are the only ones I store in the database. However even with a different indexing technique it would be useful to report statistics for unique legal positions only, as it would allow more easy comparison between different solutions. For a reasonably large project the work to produce statistics in terms of unique legal positions should be insignificant compared to the actual solving effort.

Contact

Please email any comments to kkryukov@gmail.com, or post in the EGTB Forum thread.

Links

• 3x4 chess discussion in EGTB Forum: https://kirill-kryukov.com/chess/discussion-board/viewtopic.php?t=4597.
• NULP: https://kirill-kryukov.com/chess/nulp/. The site describes "Number of Unique Legal Positions" (NULP), which is a systematic method for measuring the size of chess variants.
• 3x3 chess: https://kirill-kryukov.com/chess/3x3-chess/. A strong solution of 3x3 chess.
• 4x4 chess: https://kirill-kryukov.com/chess/4x4-chess/. A partial strong solution of 4x4 chess.

History