3x4 chess is solved

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

Re: 3x4 chess is solved

Postby Lutz Nebe » Thu Mar 18, 2010 9:31 am

Hi Kirill,
that's really a fantastic work and 43 moves a longest mate are incredible.
I downloaded your program and started it on my normal machine ( Intel Duo 3,16 GHz ).

Generating all 9-piece endings took 20,5 hours. Now it's on the way for all 10-piece endings.

Is it possible to modifie the program for 4x3 chess and ( more important ) 4x4 chess.
I know this one needs much more disk space and RAM too but the first n-pice endings
should be solvable.

Lutz
User avatar
Lutz Nebe
 
Posts: 18
Joined: Tue Jun 27, 2006 9:47 am
Location: Koblenz, Germany

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Mar 18, 2010 1:33 pm

Lutz Nebe wrote:Hi Kirill,
that's really a fantastic work and 43 moves a longest mate are incredible.

Hi Lutz! Thanks! Yes, 43 moves is incredible. It's more than 3 times the number of squares (almost 4). Although I'd be even happier with 42. :)

Lutz Nebe wrote:I downloaded your program and started it on my normal machine ( Intel Duo 3,16 GHz ).

Generating all 9-piece endings took 20,5 hours. Now it's on the way for all 10-piece endings.

Great! Let me know how far you will progress. By the way, I think that v.1.0 of the solver can't build 12-piece DTM. I'm afraid I hard-coded it to DTC at that time. I will upload a fixed version in a few days. (Although you don't need 12 piece tables for querying, they are not used even when you query a 12-piece position).

Lutz Nebe wrote:Is it possible to modifie the program for 4x3 chess and ( more important ) 4x4 chess.
I know this one needs much more disk space and RAM too but the first n-pice endings
should be solvable.

Lutz

4x3 is certainly possible, because it's a bit smaller than 3x4 (due to more squares where pawns can't be placed). My current program is hard-coded for 3x4 right now, but with some effort it's possible to convert it to 4x3. However personally I am not too much interested in 4x3.

4x4 is a very different story. Well I can convert my program to solve some subset of 4x4, like 7 or may be 8 pieces. But targeting a complete solution will require a lot of changes. My current data structures and algorithms are optimized specifically for 3x4 and current day hardware. Since 4x4 is so much larger, it will require a very different approach.

I guess we now can't even begin to imagine the longest line in 4x4. I hope DTM will still fit in one byte. :-)

All the best,
Kirill
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Lutz Nebe » Mon Mar 22, 2010 2:53 pm

I just finished all 10-piece endgames, It took 89 hours to calculate.
Next week I will start 11-piece endgames.

If I can help you in any way, e.g. calculating some endgame groups, just let me know.
I'm thinking about the possibility to create a interface for 3x4 chess and other variants.
User avatar
Lutz Nebe
 
Posts: 18
Joined: Tue Jun 27, 2006 9:47 am
Location: Koblenz, Germany

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Mar 23, 2010 12:49 am

Lutz Nebe wrote:I just finished all 10-piece endgames, It took 89 hours to calculate.
Next week I will start 11-piece endgames.

Great! You may want to compare your statistics (output of "3x4c -stat <N>") with mine (downloadable at http://kirr.homeunix.org/chess/3x4-chess/#Statistics). If our statistics matches, then you'll know you have the same database with me.

Lutz Nebe wrote:If I can help you in any way, e.g. calculating some endgame groups, just let me know.

Thanks! I don't need help at the moment, but I appreciate the offer. 3x4 is done, but solving something bigger in the future may be too much for one person.

Lutz Nebe wrote:I'm thinking about the possibility to create a interface for 3x4 chess and other variants.

Interesting! I'll follow your progress!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Mar 25, 2010 2:04 pm

I uploaded version 1.1.0 of the solver to the 3x4 chess homepage. See the list of changes.

The main focus was on reducing the database size:

1. Added LZMA compression.

2. Added 'auto' compression method - it tries every supported codec (raw, zlib, bzip2, lzma) and selects the one that managed better ratio. Dumb but functional. It saves very little space compared to LZMA. zlib and bzip2 are much faster than lzma, and raw is free, so 'auto' is just slightly slower than lzma for compression. Decompression speed is not impacted. Theoretically I can add more codecs in the future, making 'auto' selection more useful.

3. Changed the file format, table blocks are sometimes combined, sometimes not.

4. Positions under check are saved in separate blocks from those not under check.

5. A simple forward search was added. Now it is possible to query a position even if the corresponding table is missing.

6. Added '-shrink' command, which deletes one table from every pair of tables. For example, krkp - kpkr is a pair of two tables. Only one of them will be left after '-shrink' command is used. This reduces the database to about 35%.

As a result the complete DTM database (3 to 12 pieces) takes 50.6 GB. After shrinking and throwing away the 12-piece tables (because after shrinking the database can only be used for querying, and querying never uses 12-piece tables) it only takes 11.8 GB. This shrunk database still allows to query all 167 billions unique legal positions. And DTC is even smaller.

File format is not compatible with 1.0.0, so the database has to be re-built with the new version.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Lutz Nebe » Tue May 25, 2010 12:00 pm

I have created all databases form 3 to 12 pieces.
The program run for 689 hours on a single processor. (3,16 GHz )
All stats are checked and identicly.
User avatar
Lutz Nebe
 
Posts: 18
Joined: Tue Jun 27, 2006 9:47 am
Location: Koblenz, Germany

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue May 25, 2010 1:18 pm

Lutz Nebe wrote:I have created all databases form 3 to 12 pieces.
The program run for 689 hours on a single processor. (3,16 GHz )
All stats are checked and identicly.

Terrific!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Fri Sep 03, 2010 2:36 pm

My server (kirr.homeunix.org) will be off for one week, so 3x3 and 3x4 chess sites will be unavailable. I'm going out of town and I can't leave it working for one week by itself in this heat. After coming back I'll post some new data, including the exact number of all zugzwangs. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Thu Sep 16, 2010 7:35 am

A friend asked me about KRBB-KBBN ending, so here are the numbers for 3x4 chess.

Statistics for KRBB-KBBN (only positions where KRBB side is to move):
Code: Select all
=========== krbbkbbn ===========

Win in   1:         27048
Win in   2:         14266
Win in   3:         13174
Win in   4:         10714
Win in   5:         17817
Win in   6:         24213
Win in   7:         22976
Win in   8:         16410
Win in   9:         10047
Win in  10:          6857
Win in  11:          4544
Win in  12:          3655
Win in  13:          2860
Win in  14:          2937
Win in  15:          2279
Win in  16:          1438
Win in  17:          1149
Win in  18:           548
Win in  19:           309
Win in  20:           164
Win in  21:            51
Win in  22:             2
Draw:              100854
Loss in  30:            1
Loss in  29:            0
Loss in  28:            0
Loss in  27:            0
Loss in  26:            2
Loss in  25:            6
Loss in  24:            3
Loss in  23:            6
Loss in  22:           12
Loss in  21:           25
Loss in  20:           26
Loss in  19:           40
Loss in  18:           44
Loss in  17:           38
Loss in  16:           45
Loss in  15:           36
Loss in  14:           31
Loss in  13:           32
Loss in  12:           32
Loss in  11:           31
Loss in  10:           39
Loss in   9:           43
Loss in   8:           51
Loss in   7:           50
Loss in   6:           60
Loss in   5:           78
Loss in   4:          186
Loss in   3:          523
Loss in   2:          688
Loss in   1:         3748
Checkmated:         13616


Statistics for KBBN-KRBB (KBBN side is to move):
Code: Select all
=========== kbbnkrbb ===========

Win in   1:         11017
Win in   2:          3934
Win in   3:          3161
Win in   4:          1517
Win in   5:          1070
Win in   6:           669
Win in   7:           786
Win in   8:           935
Win in   9:           802
Win in  10:           622
Win in  11:           473
Win in  12:           409
Win in  13:           355
Win in  14:           465
Win in  15:           462
Win in  16:           393
Win in  17:           329
Win in  18:           439
Win in  19:           531
Win in  20:           431
Win in  21:           327
Win in  22:           136
Win in  23:            74
Win in  24:            32
Win in  25:            48
Win in  26:            44
Win in  27:            25
Win in  28:            38
Win in  29:            14
Win in  30:            19
Draw:              236158
Loss in  23:            5
Loss in  22:            5
Loss in  21:           28
Loss in  20:          110
Loss in  19:          198
Loss in  18:          364
Loss in  17:          688
Loss in  16:         1154
Loss in  15:         1673
Loss in  14:         1971
Loss in  13:         1545
Loss in  12:         1986
Loss in  11:         2065
Loss in  10:         3145
Loss in   9:         4623
Loss in   8:         6104
Loss in   7:         6691
Loss in   6:         5801
Loss in   5:         3707
Loss in   4:         2080
Loss in   3:         2923
Loss in   2:         5211
Loss in   1:        11609
Checkmated:         26903


Let's ignore the checkmated positions, and sum up the rest: When KRBB is to move, there are 183,458 wins, 5,876 losses and 100,854 draws. When KBBN is to move, there are 29,557 wins, 63,686 losses and 236,158 draws.

When we count both sides to move together, we get 619,589 positions in total (excluding checkmated positions). 247,144 (39.89%) of them are won for the KRBB side. 35,433 (5.72%) are won for the KBBN. 337,012 (54.39%) are draws.

Note that stalemated positions are counted togehter with draws in the numbers above.

So, KRBB-KBBN is more often drawn than won on a 3x4 board. Is it similar in full size 8x8 chess? Your guess is as good as mine.

By the way, the longest checkmate line in KRBB-KBBN takes 30 moves. :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Elmika » Mon Oct 11, 2010 2:17 pm

Nice work, Kirill! I only want to suggest a new subject to you. Although it is very interesting to see this small chess with many pieces, I personally would be rather more interested in a topic that is related more to our standard chess: Some endgames on boards of other sizes than normal. E.g. Queen vs rook on 9x9, 10x10 and so on. Or B and N vs K on 13x13. Or as a goal some fundamental rook and pawn endgames on bigger or smaller boards. Would be nice if you woudl develop some interest...
Elmika
 
Posts: 9
Joined: Sun Jul 13, 2008 10:26 pm

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Oct 11, 2010 2:40 pm

Hi Elmika, and thanks! I agree it would be very interesting to have a generalized chess solver that could be used to study various endgames on unusual boards. I've no time at the moment, but let's hope that such solver gets created sooner or later by someone.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Nov 09, 2010 4:07 pm

I updated the 3x4 chess page with more data, particularly Zugzwangs and Value of the right to move may be interesting. Also the query interface is slightly improved.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Ed Trice » Tue Nov 09, 2010 7:39 pm

Kirill Kryukov wrote:I updated the 3x4 chess page with more data, particularly Zugzwangs and Value of the right to move may be interesting. Also the query interface is slightly improved.


What that page needs is some diagrams :)
5.0 Ghz Intel Gulftown Supercomputers
http://www.liquidnitrogenoverclocking.com
User avatar
Ed Trice
 
Posts: 58
Joined: Thu Oct 28, 2010 1:13 am
Location: Henlopen Acres, Delaware

Re: 3x4 chess is solved

Postby Kirill Kryukov » Wed Nov 10, 2010 5:50 am

Ed Trice wrote:What that page needs is some diagrams :)

Yeah, you're right. Unfortunately my diagrams suck even in the web-interface. I need to find a better looking graphics, or perhaps render using fonts (like I did for 3x3).
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Nov 23, 2010 2:23 am

I finally managed to complete the verification of the DTM database, including 12-piece tables. No new errors were detected. Verification took almost 10 days on my Phenom II 905e, using 2 cores, which means it is about twice faster than solving. 591369032564 positions were probed in the process, with 591326232700 cache hits (99.9928%).

By verification I mean the standard procedure of performing 1-ply forward search from each position, and checking that the database value for that position is consistent with those 1 ply ahead.

Of course this is not a 100% guarantee of being error-free. Verification and solving parts are sharing some code, so theoretically they could share a bug or two. Also they are done by the same person, so even if the code was different, a logic flaw could easily result in the same bug re-implemented twice. Only comparison with another solution produced independently by some other person should guarantee being error-free.

Still, formal verification is another minichess milestone (at least for me). :-)
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Nov 30, 2010 9:55 am

Now I completed verification of the DTC database, no errors. It took one week, using three cores in parallel. 591363852855 positions probed, 591320292453 cache hits (99.9926%).
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Mon Mar 21, 2011 1:02 pm

Just posting to let you know that 3x3 and 3x4 chess web-sites are down because of the earthquake in Japan. I am safe and the database is safe, but my minichess projects will stay offline for some time, until the situation stabilizes.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby ernest » Mon Mar 21, 2011 11:45 pm

Kirill Kryukov wrote:earthquake in Japan

Didn't know you lived in Japan.
Amid all this disaster, it's fortunate and I am glad that you are in the southern part of the country.
ernest
 
Posts: 63
Joined: Tue Nov 21, 2006 6:31 pm
Location: Paris

Re: 3x4 chess is solved

Postby Kirill Kryukov » Tue Mar 22, 2011 1:43 am

Hi Ernest. Thanks. Mishima (where I live normally) is in the middle Japan, but now I am on vacation in Osaka.
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Re: 3x4 chess is solved

Postby Kirill Kryukov » Sat Apr 09, 2011 3:49 am

I added a selection of "mate in 2" problems to the 3x4 chess web-site. Please enjoy!
User avatar
Kirill Kryukov
Site Admin
 
Posts: 7380
Joined: Sun Dec 18, 2005 9:58 am
Location: Mishima, Japan

Previous

Return to Endgame Tablebases

Who is online

Users browsing this forum: Baidu [Spider] and 1 guest

cron