4x4 chess

[Kirill Kryukov]

Bugs reported by Codeman are now fixed too. Thanks a lot and please let me know if anything else is broken!

[Kirill Kryukov]

MaxDTM positions with 7 and 8 pieces:

7 pieces, 54 moves
8 pieces, 56 moves

[Kirill Kryukov]

There are 3,677,542,994,054,890 unique legal positions in 4x4 chess. This time it's not an estimate, but the exact number. This is 21,981.3 times more than in 3x4 chess.

[Kirill Kryukov]

Current size of my tables (in bytes):

Code: Select all

Pieces       NULP         DTM Size       DTC Size       DTZ Size       WDL Size
   3           3,378            872            730            702            416
   4         227,362         44,591         34,102         30,259         13,056
   5       8,803,638      1,515,735        958,352        835,240        373,192
   6     226,104,696     34,832,691     18,260,652     16,001,827      7,592,409
   7   4,143,416,867    568,131,821    241,138,993    214,736,705    113,724,796
   8  56,389,004,075  6,861,607,004  2,362,903,007  2,153,528,857  1,286,948,587

NULP = Number of Unique Legal Positions.

This gives the following compactness (in unique legal positions per byte):

Code: Select all

Pieces   DTM     DTC     DTZ     WDL
   3    3.874   4.627   4.812   8.120
   4    5.099   6.667   7.514  17.414
   5    5.808   9.186  10.540  23.590
   6    6.491  12.382  14.130  29.780
   7    7.293  17.183  19.295  36.434
   8    8.218  23.864  26.184  43.816

[Kirill Kryukov]

Spectrum of DTM values in 4x4 chess, for 3 to 8 pieces. Horizontal axis = DTM value, in order: draw, checkmate, win in 1, loss in 1, win in 2, loss in 2, etc. Vertical axis = Proportion of positions with this value among all positions with the same number of pieces, in percents (logarithmic).



The same kind of spectrum for DTZ metric:



The slowly declining slope of the DTM spectrum shows why it's difficult to compress DTM data - quite many values are above 1%. Also you can see that the DTM slope does not change much when adding more pieces - it actually becomes a bit less steep, which means less compressible.

DTZ, on the other hand, declines rapidly after a sharp peak at "win in 1" and "loss in 1". It declines more sharply after adding extra pieces, which means DTZ compression ratio increases with more pieces.

DTC and DTX look similar to DTZ, slightly less steep.

Nothing unexpected here, just a convenient representation.

[Kirill Kryukov]

Mate in 59:


(white to move)

N1p1/1k1p/1B1B/BK1b w - - 0 1
1.Nc3!! Bc2+ 2.Kc1☉□ Kb4 3.Na2+!! Ka4 4.Nb4♢ Kb3 5.Bd4♢ Ka3 6.Bac3! Kb3 7.Bb2! Ka4 8.Na2! Kb3 9.Nc3☉! Kb4 10.Nb1+! Ka4 11.Na3!! Kb3 12.B4c3!! Ka2 13.Nxc4♢ Ba4 14.Na3♢ Bb3 15.Bb4♢ Bc2 16.Bd4! Kb3 17.B2c3! Ka2 18.Nc4! Ba4 19.Ba3♢ Bb3 20.Nd2! Ba4 21.Bcb2! Bb3 22.Nb1! Bc2 23.Nc3+! Kb3□ 24.Kd2!! Kc4 25.Na2! Kb3 26.Nb4! Kc4 27.Bbc3! Kb3 28.Ba1! Kc4 29.Bdc3♢ Kb3 30.B1b2! Ka4 31.Kc1! Kb3 32.Bd2! Ka4 33.Na2! Kb3 34.Nc3☉! Kc4 35.Ba1! Kb3 36.Bb4☉! Kc4 37.Kb2! Kxb4 38.Nb1+♢ Ka4 39.Na3! Bb3 40.Bc3! d2 41.Bxd2!! Bc4 42.Nc2♢ Bb3 43.Nb4! Bc4 44.Bc3! Bb3 45.Nd3! Ba2 46.Nc1! Bc4 47.Bd2! Bb3 48.Bb4! Kxb4 49.Nxb3!! Ka4 50.Nd2♢ Kb4□ 51.Kc2♢ Ka4 52.Nb1♢ Kb4□ 53.Bd4♢ Ka4 54.Bb2! Kb4□ 55.Nc3! Kc4□ 56.Ba3! Kd4□ 57.Nb1! Kc4□ 58.Nd2+! Kd4□ 59.Bb2#

Somehow "light-colored vs dark-colored bishops"often produce very long lines, especially DTC and DTZ. This line has 4 zugzwangs and 7 "!!" moves (although there are some alternative lines I did not check).

Browse in web-interface

[Kirill Kryukov]

Another mate in 59, with more normal material this time:


(white to move)

2NR/1Pp1/K2P/1qkN w - - 0 1
1.Ka3□ c2 2.Ndb2!! Qa1+ 3.Kb4□ Kb1 4.Rd3!! c1N 5.Kc3!! Na2+ 6.Kd4□ Kc2 7.b4Q♢ Nxb4 8.Rc3+!! Kb1□ 9.Rb3!! Na2 10.Na3+!! Kc1□ 11.d3!! Nb4 12.Kc4! Nxd3 13.Nxd3+!! Kd1 14.Nb4! Kc1 15.Rd3! Kb2 16.Nbc2! Qa2+ 17.Kb4!! Kc1 18.Ka4!! Kb2 19.Nb4! Qa1 20.Rb3+! Kc1□ 21.Nd3+! Kd2 22.Kb4! Qd4+ 23.Nc4+□ Kc2 24.Ndb2!! Kc1 25.Ra3♢ Kc2 26.Na4! Qd3 27.Nc3!! Kc1 28.Ra4♢ Kc2 29.Ra2+! Kc1□ 30.Ra3! Kc2 31.Rb3! Kc1 32.Na2+! Kc2 33.Na3+! Kd2 34.Nb1+! Kc2 35.Nac3! Kc1 36.Ka3! Qc2 37.Na2+!! Kd1 38.Nbc3+! Kd2 39.Rb4! Kd3 40.Nb1!! Qd1 41.Kb2! Qc2+ 42.Ka1! Qc4 43.Rb2!! Qd4 44.Nb4+♢ Kc4 45.Na3+! Kc3□ 46.Nac2! Qd1+ 47.Ka2!! Kc4 48.Na3+!! Kc3 49.Nb1+! Kc4 50.Nc2! Qc1 51.Nba3+! Kc3 52.Rb3+! Kd2□ 53.Nb4! Kd1 54.Nd3! Qc2+ 55.Nxc2♢ Kxc2 56.Ra3♢ Kd2 57.Kb2♢ Kd1□ 58.Nb4♢ Kd2□ 59.Rd3#

No zugzwangs, but it has an underpromotion by black and 17 "!!" moves by white. Fairly quickly (in 13 moves) it converts into 6-piece KRNNKQ, where incomprehensible piece shuffling continues for another 40+ moves.

Unfortunately the first move is forced, so this one does not make a very good problem.

Browse in web-interface

[Kirill Kryukov]

All 9-piece positions are solved, in DTM metric. The longest line is 59 moves. All solved positions can be queried in the web-interface.

[Kirill Kryukov]

I changed DTX, DTC and DTZ from move-counting to ply-counting. This results in about 14% size increase of compressed tables, but allows to correctly implement the N-move rule. All DTX, DTC and DTZ tables will have to be recomputed. Fortunately DTM and WDL are not affected, also 1 byte per position should be still enough.

[rivenburg]

Kirill,

Any chance of making the 4x4 chess solver available, like the 3x4 chess solver was made available to the public?

John

[Kirill Kryukov]

Hi John,

Here is the current version. 64-bit Windows binary, command line, single threaded, you need at least 4 GB of RAM total. Pre-release test build, so it's incomplete and slow. Still it computed 3-to-9-piece DTM and WDL tables already.

To build the 3-piece DTM database:

4x4c.exe -build DTM 3

To query a position:

4x4c.exe -query DTM "2k1/4/1K2/3R w - - 0 1"