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–08–28 —
The average value of the right to move in 3x4 chess is 0.32 of a point.
Total number of fullpoint zugzwangs is 2,778,286.
Total number of halfpoint zugzwangs is 58,296,519.
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–13 —
Example MaxDTM and MaxDTC 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 —
Website 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 sidetomove 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.
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 43move 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 whitetomove positions are counted.
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 kB  1,504 kB 
All  184,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:
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%) 
All  52,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:
2  0 (0.00%)  0 (0.00%)  20 (100.00%)  50.00% 
3  299 (22.13%)  180 (13.32%)  872 (64.54%)  54.40% 
4  16,546 (38.18%)  8,843 (20.41%)  17,948 (41.41%)  58.89% 
5  390,402 (46.07%)  185,456 (21.89%)  271,492 (32.04%)  62.09% 
6  5,625,146 (50.71%)  2,620,833 (23.63%)  2,846,940 (25.66%)  63.54% 
7  54,688,738 (54.00%)  25,103,956 (24.79%)  21,485,693 (21.21%)  64.61% 
8  366,893,022 (56.18%)  168,927,276 (25.87%)  117,219,872 (17.95%)  65.16% 
9  1,703,235,592 (57.98%)  784,348,420 (26.70%)  450,040,895 (15.32%)  65.64% 
10  5,228,410,654 (59.23%)  2,416,894,780 (27.38%)  1,181,550,685 (13.39%)  65.93% 
11  9,639,423,017 (60.26%)  4,458,227,207 (27.87%)  1,899,262,491 (11.87%)  66.19% 
12  8,068,122,833 (60.79%)  3,748,182,712 (28.24%)  1,455,555,567 (10.97%)  66.27% 
All  25,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 enpassant 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 halfpoint 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 fullpoint zugzwangs,
58,296,519 (0.29%)  halfpoint 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 antizugzwang positions for each ending.
Copy/paste any of those positions into query interface to explore in detail.
Here is a DTM fullpoint 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 halfpoint and a fullpoint 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 fullpoint zugzwangs?  kqqqqqkqqqqq, it has 1 fullpoint zugzwang, and 15 piece placements in total.
 Which ending has fullpoint zugzwangs, but in smallest proportion?  kqqrbnkbbnp, it has only one fullpoint 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:
2  13  0 (0.00%)  0 (0.00%)  13 (100.00%)  0 (0.00%)  0 (0.00%)  +0.00 
3  643  0 (0.00%)  84 (13.06%)  553 (86.00%)  6 (0.93%)  0 (0.00%)  +0.06 
4  21,911  556 (2.54%)  4,997 (22.81%)  16,260 (74.21%)  97 (0.44%)  1 (0.00%)  +0.14 
5  385,449  19,477 (5.05%)  117,959 (30.60%)  246,424 (63.93%)  1,585 (0.41%)  4 (0.00%)  +0.20 
6  5,264,465  456,609 (8.67%)  1,691,226 (32.13%)  3,101,300 (58.91%)  15,164 (0.29%)  166 (0.00%)  +0.25 
7  47,546,435  5,680,227 (11.95%)  14,775,300 (31.08%)  26,995,289 (56.78%)  94,116 (0.20%)  1,503 (0.00%)  +0.27 
8  314,445,228  47,610,961 (15.14%)  90,935,197 (28.92%)  175,433,318 (55.79%)  453,411 (0.14%)  12,341 (0.00%)  +0.30 
9  1,414,598,213  251,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 
10  4,309,547,463  865,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 
11  7,814,285,713  1,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 
12  6,533,974,591  1,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 
All  20,440,070,124  4,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 12piece 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 (3to12 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 
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,320  7.616 
10  10,015,711,560  3.248  3,759,951,770  8.653 
11  19,358,502,196  3.338  6,908,500,440  9.353 
12  17,379,753,389  3.346  6,102,661,423  9.529 
All  50,631,046,260  3.306  18,410,423,059  9.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 12piece 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 
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,136  9.073  394,576,510  24.762 
10  3,556,897,767  9.147  1,170,933,630  27.786 
11  6,943,627,615  9.306  2,131,786,873  30.312 
12  0   0  
All  11,834,486,016  14.137  3,808,404,796  43.930 

Solver software
You can download the solver and build your own copy of 3x4 chess database:
Requirements:
 OS: Any modern Windows OS  XP, Vista, 7.
 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 3to12piece '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.
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 5vs1
(EGTB Forum, 20090928).
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, 20100525).
Any additional verification would be welcome.
Also, by chance, if you notice any glitch or inconsistency in the webinterface,
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.
Any comments, questions and suggestions are warmly welcome!
Please join the discussion at the EGTB Forum (preferable),
or feel free to Contact me directly.