Page 2 of 2
Re: 3x4 chess is solved
Posted: Thu Mar 18, 2010 9:31 am
by Lutz Nebe
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
Re: 3x4 chess is solved
Posted: Thu Mar 18, 2010 1:33 pm
by Kirill Kryukov
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
Re: 3x4 chess is solved
Posted: Mon Mar 22, 2010 2:53 pm
by Lutz Nebe
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.
Re: 3x4 chess is solved
Posted: Tue Mar 23, 2010 12:49 am
by Kirill Kryukov
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!
Re: 3x4 chess is solved
Posted: Thu Mar 25, 2010 2:04 pm
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Tue May 25, 2010 12:00 pm
by Lutz Nebe
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.
Re: 3x4 chess is solved
Posted: Tue May 25, 2010 1:18 pm
by Kirill Kryukov
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!
Re: 3x4 chess is solved
Posted: Fri Sep 03, 2010 2:36 pm
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Thu Sep 16, 2010 7:35 am
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Mon Oct 11, 2010 2:17 pm
by Elmika
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...
Re: 3x4 chess is solved
Posted: Mon Oct 11, 2010 2:40 pm
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Tue Nov 09, 2010 4:07 pm
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Tue Nov 09, 2010 7:39 pm
by Ed Trice
What that page needs is some diagrams
Re: 3x4 chess is solved
Posted: Wed Nov 10, 2010 5:50 am
by Kirill Kryukov
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).
Re: 3x4 chess is solved
Posted: Tue Nov 23, 2010 2:23 am
by Kirill Kryukov
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).
Re: 3x4 chess is solved
Posted: Tue Nov 30, 2010 9:55 am
by Kirill Kryukov
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%).
Re: 3x4 chess is solved
Posted: Mon Mar 21, 2011 1:02 pm
by Kirill Kryukov
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.
Re: 3x4 chess is solved
Posted: Mon Mar 21, 2011 11:45 pm
by ernest
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.
Re: 3x4 chess is solved
Posted: Tue Mar 22, 2011 1:43 am
by Kirill Kryukov
Hi Ernest. Thanks. Mishima (where I live normally) is in the middle Japan, but now I am on vacation in Osaka.
Re: 3x4 chess is solved
Posted: Sat Apr 09, 2011 3:49 am
by Kirill Kryukov
I added a selection of "mate in 2" problems to the 3x4 chess web-site. Please enjoy!