3x4 chess is solved

[Kirill Kryukov]

I constructed a complete DTM (distance to mate) database for 3x4 chess. In total there are 167,303,246,916 unique legal positions (taking into account all possible symmetry).

I still need to complete verification, compress the database, and run some statistics (including search for the longest DTM position). I also plan to make a web-interface to the database, eventually.

This is a pre-release information, for discussion. It's still possible that I will find some problem and will have to re-compute the database. So far automatic verification of up to 9 pieces is complete without errors, which is a good sign.

The longest forced checkmate line is a breath-taking 43 moves (85 plies).

More information to follow soon. Any questions or comments are welcome.

Best,
Kirill

[ernest]

Great achievement!!!
I am waiting for the 5x5 minichess (with all pieces on 1st rank)

Can you give us a quick definition of your 3x4 chess?
And what is the result: value of the game (1, 1/2, 0?)

[mbourzut]

I constructed a complete DTM (distance to mate) database for 3x4 chess. In total there are 167,303,246,916 unique legal positions (taking into account all possible symmetry).

I still need to complete verification, compress the database, and run some statistics (including search for the longest DTM position). I also plan to make a web-interface to the database, eventually.

This is a pre-release information, for discussion. It's still possible that I will find some problem and will have to re-compute the database. So far automatic verification of up to 9 pieces is complete without errors, which is a good sign.

The longest forced checkmate line is a breath-taking 43 moves (85 plies).

More information to follow soon. Any questions or comments are welcome.

Best,
Kirill

One point of comparison are all the pawnless endings with up to 6 men (excluding 5 vs 1) I generated with a rigged Nalimov program for 3x4. I'm attaching the relevant .tbs files. The counts should be a little higher than yours because not all symmetries have been eliminated, but the DTMs should match.

-Marc

[Kirill Kryukov]

Great achievement!!!
I am waiting for the 5x5 minichess (with all pieces on 1st rank)

Can you give us a quick definition of your 3x4 chess?
And what is the result: value of the game (1, 1/2, 0?)

Hi ernest, and thanks. 5x5 with 10 pieces will take some time, I'm afraid.

3x4 chess definition: The board is 3 squares wide and 4 squares tall (not the other way around). With 4 ranks there is longer way for the pawns to travel, so I liked this one over the 4x3, although 4x3 should be slightly easier to solve. The rules: same with chess, except no castling, no double pawn move, no en-passant and no 50 moves rule. Starting position: Not defined, instead I analized all possible positions, with any possible combination of pieces, including those with pawns on the 1-st row. Although I am going to search for good candidate starting positions (those allowing complex and interesting gameplay).

The result. Out of 167,303,246,916 possible legal positions 52,048,121,059 are checkmates (31.11%). Out of the remaining 115,255,125,857 non-checkmate positions 48,713,659,039 are wins (for the side to move) (42.27%), 51,946,919,196 are losses (45.07%) and 14,594,547,622 are draws (12.66%).

Summing up: Draw is unlikely in 3x4 chess (only 12.66%). Side to move surprisingly has disadvantage: 45.07% chance to lose vs 42.27% chance to win.

[Kirill Kryukov]

One point of comparison are all the pawnless endings with up to 6 men (excluding 5 vs 1) I generated with a rigged Nalimov program for 3x4. I'm attaching the relevant .tbs files. The counts should be a little higher than yours because not all symmetries have been eliminated, but the DTMs should match.

-Marc

Thanks Marc! Our longest DTM values agree for a few tables that I compared manually, but comparing all of them will take a little time (I'll have to write a script for this).

EDIT: OK I compared my max DTM values with yours. We are in total agreement for the 424 tables you included. (I did not compare the counts, because as you say we count differently).

[Kirill Kryukov]

Here is my statistics for up to 6 pieces, including pawns and 5-vs-1 combinations (exactly 1000 tables).

[Kirill Kryukov]

News: Simple web-interface is now open for testing: http://kirr.homeunix.org/chess/3x4-chess/ (the web-page itself is under construction). Example position - longest pawnless 5-piece line. Any testing reports or suggestions will be appreciated.

Any possible position can be checked, even with 12 pieces. Actually it only requires 11 piece database, the 12-piece tables are not used by the web-interface at all. 12 piece tables are useful for statistics and position mining.

[Kirill Kryukov]

The result. Out of 167,303,246,916 possible legal positions 52,048,121,059 are checkmates (31.11%). Out of the remaining 115,255,125,857 non-checkmate positions 48,713,659,039 are wins (for the side to move) (42.27%), 51,946,919,196 are losses (45.07%) and 14,594,547,622 are draws (12.66%).

Summing up: Draw is unlikely in 3x4 chess (only 12.66%). Side to move surprisingly has disadvantage: 45.07% chance to lose vs 42.27% chance to win.

Actually please ignore this number. Side to move still in fact has big advantage in 3x4 chess. To get the real score we should not count positions where side to move is under check.

[George Tsavdaris]

The result. Out of 167,303,246,916 possible legal positions 52,048,121,059 are checkmates (31.11%).

Having in mind the symmetry of white-black (positions where white checkmates the black side and black checkmate the white side, are equal), shouldn't this number be even and not odd?
Or (i guess this is it) do you treat for example w....k....RKR the same as brkr....K.... and you count it as one position?

Out of the remaining 115,255,125,857 non-checkmate positions 48,713,659,039 are wins (for the side to move) (42.27%), 51,946,919,196 are losses (45.07%) and 14,594,547,622 are draws (12.66%).

Summing up: Draw is unlikely in 3x4 chess (only 12.66%). Side to move surprisingly has disadvantage: 45.07% chance to lose vs 42.27% chance to win.

This is definitely counterintuitive!! I wonder how this is possible, i will thin about it later.

[George Tsavdaris]

The result. Out of 167,303,246,916 possible legal positions 52,048,121,059 are checkmates (31.11%). Out of the remaining 115,255,125,857 non-checkmate positions 48,713,659,039 are wins (for the side to move) (42.27%), 51,946,919,196 are losses (45.07%) and 14,594,547,622 are draws (12.66%).

Summing up: Draw is unlikely in 3x4 chess (only 12.66%). Side to move surprisingly has disadvantage: 45.07% chance to lose vs 42.27% chance to win.

Actually please ignore this number. Side to move still in fact has big advantage in 3x4 chess. To get the real score we should not count positions where side to move is under check.

Oh thanks, that answers instantly my previous wondering about it. Things are more logical now.

And do you have any idea of when all the cool stuff("Also most of the cool stuff is still missing") will appear and the project with all details will be available?

[Kirill Kryukov]

The result. Out of 167,303,246,916 possible legal positions 52,048,121,059 are checkmates (31.11%).

Having in mind the symmetry of white-black (positions where white checkmates the black side and black checkmate the white side, are equal), shouldn't this number be even and not odd?
Or (i guess this is it) do you treat for example w....k....RKR the same as brkr....K.... and you count it as one position?

Correct (the latter one) - the white-black symmetry is figured in, and these two positions are counted as one position. Only white-to-move positions are stored in the database.

[Kirill Kryukov]

And do you have any idea of when all the cool stuff("Also most of the cool stuff is still missing") will appear and the project with all details will be available?

Please check this thread and the project web-site (http://kirr.homeunix.org/chess/3x4-chess/) time to time and you won't miss it. Cool stuff is being worked on, and parts of it will be gradually added as soon as they are ready.

[Kirill Kryukov]

The complete DTM statistics and partial DTC statistics files are now available for download at the 3x4 chess homepage (scroll down to the end)

DTC is not finished yet, but already looks at least as amazing as DTM. And of course it compresses much better. A 12-men DTC is basically a bitbase.

[Kirill Kryukov]

OK, the result: White score: 66.10%, draws: 12.27%. Counting only unique legal white-to-move positions where white has legal moves and is not under check.

[Mark]

This is very interesting! Thanks for posting.

What position has the mate in 85 ply?

[Kirill Kryukov]

This is very interesting! Thanks for posting.

What position has the mate in 85 ply?

The longest checkmate line (43 moves) is now posted now on the project site. Enjoy! May be you can understand what's going on there? (Also, do let me know if you notice any error).

[Mark]

This is very interesting! Thanks for posting.

What position has the mate in 85 ply?

The longest checkmate line (43 moves) is now posted now on the project site. Enjoy! May be you can understand what's going on there? (Also, do let me know if you notice any error).

Wow, thanks! It's still unbelievable that there is a mate this deep. Seems to be a fairly even position, too. I'm going to have a good time exploring this position further!

Any thoughts on future projects (4x4 maybe)?

[Kirill Kryukov]

Wow, thanks! It's still unbelievable that there is a mate this deep. Seems to be a fairly even position, too. I'm going to have a good time exploring this position further!

Any thoughts on future projects (4x4 maybe)?

Yes, it's much deeper than I could imagine. In that particular position I also like that out of 4 moves the only one which is not a capture is winning.

4x4 is an obvious target, 3x5 is also interesting. However don't expect anything soon.

[Kirill Kryukov]

I added 3x4 chess solver binary to the project page. If anyone is curious to construct your own 3x4 chess database, now you can.

[rivenburg]

Greetings,

I have downloaded the "solver" from the project page, so I can generate my own databases, however I keep getting the message "Can't interpret" type 'help' as a result,.......I am running Windows XP with 4G Ram and plenty of hard drive space in which to store it,....... John

[Kirill Kryukov]

Greetings,

I have downloaded the "solver" from the project page, so I can generate my own databases, however I keep getting the message "Can't interpret" type 'help' as a result,.......I am running Windows XP with 4G Ram and plenty of hard drive space in which to store it,....... John

Hi John,

It's a command line tool, you have to start it from the command line with parameters telling it what to do. If you just start it without parameters (like double-clicking on the executable), it will open the query interface where all you can do is query positions.

To see the list of available command line options, run "3x4c.exe -help".

To generate 3-piece DTM database, run "3x4c.exe -build DTM 3". etc..

Command line is accessible at Start menu -> Programs -> Accessories -> Command Prompt (at least in my Windows it's there). Alternatively, you can create a .bat file, write some commands inside that file, save it, then double-click on it.

This is a research tool, so there is no GUI, unfortunately. Although I'll probably add more functional interactive console interface at some point.

Best,
Kirill

[rivenburg]

Kirill,

You would think I would have remembered how to do it, having been raised in DOS (I'm old),.....Everything is great Thank you,
......

John

[Kirill Kryukov]

Great! Please post some updates on your progress with generation, how many pieces you could reach, and how long time it took.

[jshriver]

Amazing work Kirill keep up the hard work and happy holidays.

[Kirill Kryukov]

Thanks Josh! Happy holidays to you too!