3x4 chess is solved

Endgame analysis using tablebases, EGTB generation, exchange, sharing, discussions, etc..

3x4 chess is solved

Postby Kirill Kryukov » Sun Sep 27, 2009 5:37 pm

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
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby ernest » Sun Sep 27, 2009 7:38 pm

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

Can you give us a quick definition of your 3x4 chess?
And what is the result: value of the game (1, 1/2, 0?)
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: 3x4 chess is solved

Postby mbourzut » Sun Sep 27, 2009 8:19 pm

Kirill Kryukov wrote: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
Attachments
3x4_6tbs.zip
(79.41 KiB) Downloaded 181 times
mbourzut
 
Posts: 30
Joined: Fri Mar 03, 2006 7:48 pm

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Sep 28, 2009 2:43 am

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

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. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Sep 28, 2009 2:52 am

mbourzut wrote: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).
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Sep 28, 2009 5:26 am

Here is my statistics for up to 6 pieces, including pawns and 5-vs-1 combinations (exactly 1000 tables).
Attachments
Kirr-3x4-chess-statistics-up-to-6-pieces.zip
(96.86 KiB) Downloaded 186 times
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Sep 29, 2009 4:19 pm

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.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Oct 01, 2009 4:34 am

Kirill Kryukov wrote: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.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby George Tsavdaris » Thu Oct 01, 2009 10:35 am

Kirill Kryukov wrote: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!! :shock: I wonder how this is possible, i will thin about it later.
George Tsavdaris
 
Posts: 3
Joined: Thu Nov 16, 2006 4:02 pm

Re: 3x4 chess is solved

Postby George Tsavdaris » Thu Oct 01, 2009 10:38 am

Kirill Kryukov wrote:
Kirill Kryukov wrote: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. :D

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?
George Tsavdaris
 
Posts: 3
Joined: Thu Nov 16, 2006 4:02 pm

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Oct 01, 2009 1:36 pm

George Tsavdaris wrote:
Kirill Kryukov wrote: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.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Oct 01, 2009 1:40 pm

George Tsavdaris wrote: 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. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Fri Oct 02, 2009 3:05 pm

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. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Fri Oct 02, 2009 5:57 pm

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.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Mark » Sat Oct 03, 2009 8:22 pm

This is very interesting! Thanks for posting.

What position has the mate in 85 ply?
Mark
 
Posts: 13
Joined: Tue Jun 24, 2008 11:15 am

Re: 3x4 chess is solved

Postby Kirill Kryukov » Sun Oct 04, 2009 3:58 am

Mark wrote: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). :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Mark » Sun Oct 04, 2009 2:52 pm

Kirill Kryukov wrote:
Mark wrote: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)?
Mark
 
Posts: 13
Joined: Tue Jun 24, 2008 11:15 am

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Oct 05, 2009 3:06 am

Mark wrote: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. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Sun Dec 20, 2009 12:25 pm

I added 3x4 chess solver binary to the project page. If anyone is curious to construct your own 3x4 chess database, now you can. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby rivenburg » Mon Dec 21, 2009 5:15 pm

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 :-)
rivenburg
 
Posts: 10
Joined: Sun Nov 26, 2006 11:06 pm
Location: Little Falls NY USA

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Dec 22, 2009 2:55 am

rivenburg wrote: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
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby rivenburg » Tue Dec 22, 2009 7:16 pm

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
rivenburg
 
Posts: 10
Joined: Sun Nov 26, 2006 11:06 pm
Location: Little Falls NY USA

Re: 3x4 chess is solved

Postby Kirill Kryukov » Wed Dec 23, 2009 4:50 am

Great! Please post some updates on your progress with generation, how many pieces you could reach, and how long time it took. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby jshriver » Wed Dec 23, 2009 2:50 pm

Amazing work Kirill :) keep up the hard work and happy holidays.
User avatar
jshriver
 
Posts: 286
Joined: Tue Jan 31, 2006 5:59 am
Location: Toledo, OH, USA

Re: 3x4 chess is solved

Postby Kirill Kryukov » Wed Dec 23, 2009 4:10 pm

Thanks Josh! Happy holidays to you too!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7336
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Next

Return to Endgame Tablebases

Who is online

Users browsing this forum: Baidu [Spider] and 2 guests