3x4 Chess

(Please check 4x4 chess too, if you haven't yet)
History:
2011–04–09 — Added selection of mates in 2.
2010–11–30 — Both DTM and DTC databases are fully verified.
2010–11–18 — Added playing interface, and selection of mates in 1.
2010–11–10 — Added MD5 signatures of all database files, for a fast integrity check.
2010–11–09 — New sections: Value of the right to move, Verification, Counting positions. Updated Zugzwangs. Query interface now supports FEN, tracks the history of played moves, shows moves in short algebraic notation, shows more meaningful interpretations of DTC values, and has other small improvements.
2010–08–28 — The average value of the right to move in 3x4 chess is 0.32 of a point. Total number of full-point zugzwangs is 2,778,286. Total number of half-point zugzwangs is 58,296,519.
2010–03–25 — Version 1.1.0 of the solver is released. See the list of changes.
2009–12–20 — Added Database and Download the solver sections. You can now download the solver software and build your own copy of 3x4 chess database.
2009–10–17 — Example zugzwang and anti-zugzwang positions are posted in "Zugzwangs" section.
2009–10–13 — Example Max-DTM and Max-DTC positions (one for each piece configuration) are available in "The longest line" section.
2009–10–09 — Interface to DTC database is added.
2009–10–04 — The longest checkmate line is 43 moves!
2009–09–30 — Interface to DTM database is available. Any positions from 2 to 12 pieces can be checked.
2009–09–28 — Web-site created.

Introduction

3x4 chess is now 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 1000 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 database value for any possible position. Input the position in FEN format, then press "Query!" to query the database, "Play!" - to play against a perfect opponent.

Metric:
Distance to mate
Distance to conversion
Position:

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:

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):

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:

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


Statistics

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

Pieces Piece
configu-
rations
Unique
legal
positions
Longest
distance
to
mate
Longest
distance
to
conversion
Download
DTM
statistics
Download
DTC
statistics
2 1 20 - - - -
3 10 1,746 8 moves 6 moves 1 kB 1 kB
4 55 69,556 20 moves 20 moves 2 kB 2 kB
5 220 1,635,355 26 moves 16 moves 13 kB 7 kB
6 715 25,117,392 31 moves 20 moves 54 kB 24 kB
7 2,002 264,331,909 40 moves 26 moves 188 kB 69 kB
8 5,005 1,936,519,455 40 moves 20 moves 554 kB 172 kB
9 11,440 9,770,507,866 41 moves 16 moves 1,429 kB 380 kB
10 24,310 32,535,116,698 42 moves 14 moves 3,260 kB 741 kB
11 48,620 64,617,989,055 43 moves 7 moves 6,592 kB 1,167 kB
12 92,378 58,151,957,864 43 moves 1 move 11,328 kB1,504 kB
All184,756 167,303,246,916 43 moves 26 moves 23,420 kB 4,066 kB

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

Pieces Checkmates Stalemates In check Remaining
(can move,
not in check)
2 0 (0.00%) 0 (0.00%) 0 (0.00%) 20 (100.00%)
3 29 (1.66%) 65 (3.72%) 301 (17.24%) 1,351 (77.38%)
4 3,376 (4.85%) 2,666 (3.83%) 20,177 (29.01%) 43,337 (62.31%)
5 141,803 (8.67%) 47,122 (2.88%) 599,080 (36.63%) 847,350 (51.81%)
6 3,181,564 (12.67%) 467,277 (1.86%) 10,375,632 (41.31%) 11,092,919 (44.16%)
7 44,047,756 (16.66%) 2,916,355 (1.10%) 116,089,411 (43.92%) 101,278,387 (38.31%)
8 398,291,666 (20.57%) 12,098,298 (0.62%) 873,089,321 (45.09%) 653,040,170 (33.72%)
9 2,375,805,393 (24.32%) 33,816,227 (0.35%) 4,423,261,339 (45.27%) 2,937,624,907 (30.07%)
10 9,068,649,416 (27.87%) 62,659,186 (0.19%) 14,576,951,977 (44.80%)8,826,856,119 (27.13%)
11 20,175,615,185 (31.22%)74,771,423 (0.12%) 28,370,689,732 (43.91%)15,996,912,715 (24.76%)
12 19,982,384,871 (34.36%)62,969,392 (0.11%) 24,834,742,489 (42.71%)13,271,861,112 (22.82%)
All52,048,121,059 (31.11%)249,748,011 (0.15%)73,205,819,459 (43.76%)41,799,558,387 (24.98%)

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

PiecesWinsLossesDrawsScore
20 (0.00%)0 (0.00%)20 (100.00%)50.00%
3299 (22.13%)180 (13.32%)872 (64.54%)54.40%
416,546 (38.18%)8,843 (20.41%)17,948 (41.41%)58.89%
5390,402 (46.07%)185,456 (21.89%)271,492 (32.04%)62.09%
65,625,146 (50.71%)2,620,833 (23.63%)2,846,940 (25.66%)63.54%
754,688,738 (54.00%)25,103,956 (24.79%)21,485,693 (21.21%)64.61%
8366,893,022 (56.18%)168,927,276 (25.87%)117,219,872 (17.95%)65.16%
91,703,235,592 (57.98%)784,348,420 (26.70%)450,040,895 (15.32%)65.64%
105,228,410,654 (59.23%)2,416,894,780 (27.38%)1,181,550,685 (13.39%)65.93%
119,639,423,017 (60.26%)4,458,227,207 (27.87%)1,899,262,491 (11.87%)66.19%
128,068,122,833 (60.79%)3,748,182,712 (28.24%)1,455,555,567 (10.97%)66.27%
All25,066,806,249 (59.97%)11,604,499,663 (27.76%)5,128,252,475 (12.27%)66.10%

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 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.

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


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):

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

PiecesPiece
placements
Piece placements where the right to move is worth:Average
value of
the right
to move
(in points)
+1 point+0.5 pointnothing−0.5 point
(half-point
zugzwangs)
−1 point
(full-point
zugzwangs)
2130 (0.00%)0 (0.00%)13 (100.00%)0 (0.00%)0 (0.00%)+0.00
36430 (0.00%)84 (13.06%)553 (86.00%)6 (0.93%)0 (0.00%)+0.06
421,911556 (2.54%)4,997 (22.81%)16,260 (74.21%)97 (0.44%)1 (0.00%)+0.14
5385,44919,477 (5.05%)117,959 (30.60%)246,424 (63.93%)1,585 (0.41%)4 (0.00%)+0.20
65,264,465456,609 (8.67%)1,691,226 (32.13%)3,101,300 (58.91%)15,164 (0.29%)166 (0.00%)+0.25
747,546,4355,680,227 (11.95%)14,775,300 (31.08%)26,995,289 (56.78%)94,116 (0.20%)1,503 (0.00%)+0.27
8314,445,22847,610,961 (15.14%)90,935,197 (28.92%)175,433,318 (55.79%)453,411 (0.14%)12,341 (0.00%)+0.30
91,414,598,213251,216,441 (17.76%)367,668,519 (25.99%)794,017,586 (56.13%)1,628,263 (0.12%)67,404 (0.00%)+0.31
104,309,547,463865,364,581 (20.08%)1,010,644,891 (23.45%)2,428,324,672 (56.35%)4,927,761 (0.11%)285,558 (0.01%)+0.32
117,814,285,7131,710,286,048 (21.89%)1,638,719,675 (20.97%)4,450,978,578 (56.96%)13,444,739 (0.17%)856,673 (0.01%)+0.32
126,533,974,5911,534,152,384 (23.48%)1,243,755,078 (19.04%)3,716,781,116 (56.88%)37,731,377 (0.58%)1,554,636 (0.02%)+0.33
All20,440,070,1244,414,787,284 (21.60%)4,368,312,926 (21.37%)11,595,895,109 (56.73%)58,296,519 (0.29%)2,778,286 (0.01%)+0.32

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


The database

I solved 3x4 chess by constructing a database of all possible positions. Please see 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.

v.1.1.0 database size, 'auto' compressed
PiecesDTMDTC
Size in bytesUnique
Legal
Positions
/ Byte
Size in bytesUnique
Legal
Positions
/ Byte
2 0  0  
3 877 1.991 853 2.047
4 25,025 2.779 21,751 3.198
5 553,392 2.955 388,523 4.209
6 8,343,783 3.010 4,958,570 5.065
7 93,393,388 2.830 49,597,310 5.330
8 650,694,333 2.976 301,503,099 6.423
9 3,124,068,317 3.127 1,282,839,3207.616
1010,015,711,5603.248 3,759,951,7708.653
1119,358,502,1963.338 6,908,500,4409.353
1217,379,753,3893.346 6,102,661,4239.529
All50,631,046,2603.30618,410,423,0599.092

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.

v.1.1.0 database size, 'auto' compressed, after shrinking
PiecesDTMDTC
Size in bytesUnique
Legal
Positions
/ Byte
Size in bytesUnique
Legal
Positions
/ Byte
2 0  0  
3 345 5.061 329 5.307
4 9,813 7.088 8,539 8.146
5 185,838 8.800 130,681 12.514
6 2,871,879 8.746 1,631,944 15.391
7 30,684,740 8.614 15,182,184 17.411
8 223,318,883 8.672 94,154,106 20.568
9 1,076,889,1369.073 394,576,510 24.762
103,556,897,7679.147 1,170,933,63027.786
116,943,627,6159.306 2,131,786,87330.312
120  0  
All11,834,486,01614.1373,808,404,79643.930

Solver software

You can download the solver and build your own copy of 3x4 chess database:

Requirements: Older versions, for reference only:

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).

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, by chance, if you notice any glitch or inconsistency in the web-interface, or in the function of the downloaded 3x4 chess solver software, 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

Any comments, questions and suggestions are warmly welcome! Please join the discussion at the EGTB Forum (preferable), or feel free to Contact me directly.


  © 2009-2011 Kirill Kryukov
Last modified on 2011–04–09