Author: Heiner Marxen
Date: 19:30:53 11/28/01
Go up one level in this thread
On November 28, 2001 at 04:26:04, Uri Blass wrote:
>On November 27, 2001 at 21:21:08, Heiner Marxen wrote:
>
>>In reply to: http://www.icdchess.com/forums/1/message.shtml?196199
>>Posted by Mike Hood on November 08, 2001 at 06:12:44:
>>
>>[The original message is not accessible anymore]
>>
>>[D]2k5/3P4/8/8/8/8/1r5p/R3K3 b Q -
>>
>>This is a KRPKRP position, suspected to be a mate in 18.
>>I have downloaded some 5-piece Nalimov tables for this, namely:
>>krpkr
>>krnkr
>>krbkr
>>krrkr
>>kqrkr
>>i.e. krkr plus an arbitrary further piece.
>>I had already all the 4-piece tables.
>>The total amount of my EGTB files now is around 296 MB.
>>
>>Then I have asked Chest (current development version 3.23) to solve the
>>mate in 18. It was intended as a stress test for EGTBs.
>>It turned out to be a quite massive computation: more than 15 days.
>>This happened on my K7/600 with 350 MB hash, and additional 40 MB cache
>>for the EGTBs (I have 512 MB real memory, and run Linux).
>>
>>Chest confirms that 1.Kd8 is a mate in 18, and there is no other way to
>>achieve that:
>>
>>PV: Kd8 Ra8+ Kxd7 Ra7+ Kd6 Ra6+ Kd5 Ra5+ Ke4 Rh5 h1=Q+ Rxh1 Rb1+ Kd2 Rxh1 Kc3
>>Rc1+ Kb4 Kd5 Kb3 Rc4 Ka3 Kc5 Kb3 Kb5 Ka3 Rb4 Ka2 Ka4 Ka1 Kb3 Kb1 Rc4 Ka1 Rc1#
[snip]
>>Total Time (user) = 1337207.05 sec (22286.8 min) (371.4 hrs) (15.5 days)
>>
>>From the refutation table...
>>
>>refu 1: Kd8 Ra8+ [ 16-]
>>solu 4: Ra8+ [ 17+]
>>solu 5: Rc1 [ 1+]
>>solu 6: Ra7 [ 1+]
>>solu 7: Rd1 [ 1+]
>>solu 8: Ra3 [ 1+]
>>solu 9: Ra4 [ 1+]
>>solu 10: Ra5 [ 1+]
>>solu 11: Ra6 [ 1+]
>>solu 12: Kf1 [ 1+]
>>solu 13: Kd1 [ 1+]
>>solu 14: O-O-O [ 12+]
>>solu 15: Rb1 [ 1+]
>>solu 16: Ra2 [ 1+]
>>refu 2: Kb8 d8=Q+ [ 17-]
>>refu 3: Kc7 d8=Q+ [ 17-]
>>refu 4: Kb7 d8=N+ [ 17-]
>>solu 1: d8=Q [ 1+]
>>refu 5: Kxd7 O-O-O+ [ 63-]
>>solu 2: Rd1+ [ 6+]
>>solu 3: Ra7+ [ 16+]
>>
>>... we see, that 1.Kxd7 does not succeed in 63 moves, i.e. does not win at all.
>>Well, that is a direct EGTB hit.
I have to correct myself: because of the remaining castling right
it is _not_ a direct table base hit. (Chest does this right.)
>>Quite interesting (and unexpected) is, what part of the analysis took most
>>of the time. 99.9961% of the time were spent on 1.Kb7 d8=N+ ... wow!
>
>bad order of moves
In this particular case: yes.
>I believe that it may be better to use some short search to find the best move
>based on only material evaluation.
>
>You are going to find that 0-0-0+ is better than d8N
O-O-O does not say check here, d8=N+ does.
That is the main reason why Chest prefered it.
>proving that white has a forced mate by 0-0-0(you do not need to find the
>shortest mate for this purpose) is doable in a few minutes and it means that
>chest can replace 99.9961% of the time by few minutes and solve the problem in
>few minutes after you improve the program.
You are a bit too optimistic, here.
I have just run a few tests.
After 1...Kb7 2.O-O-O:
[D]8/1k1P4/8/8/8/8/1r5p/2KR4 b - -
analysing (mate in 16 moves):
% EGTB found tables for max 5 pieces
% EGTB uses 3728.4K memory internally
# 1 0.10s 0kN 0.87 1- 0
# 2 0.10s [ 1.00] 0kN 0.99 1- 0
# 3 0.10s [ 1.00] 0kN [ 5.31] 0.92 23- 0
# 4 0.10s [ 1.00] 1kN [ 8.45] 1.07 136- 0
# 5 0.16s [ 1.60] 4kN [ 6.27] 1.33 709- 0
# 6 0.33s [ 2.06] 12kN [ 3.28] 2.07 2655- 0
# 7 0.66s [ 2.00] 24kN [ 2.04] 2.99 4953- 0
# 8 1.24s [ 1.88] 46kN [ 1.90] 4.06 8404- 0
# 9 2.24s [ 1.81] 88kN [ 1.91] 4.94 14318- 0
# 10 3.55s [ 1.58] 145kN [ 1.64] 6.27 21642- 0
# 11 5.76s [ 1.62] 240kN [ 1.65] 7.49 34402- 0
# 12 10.44s [ 1.81] 480kN [ 2.00] 7.76 67098- 0
# 13 22.97s [ 2.20] 1228kN [ 2.56] 7.31 166954- 0
# 14 48.15s [ 2.10] 2616kN [ 2.13] 8.33 366894- 0
# 15 159.26s [ 3.31] 9268kN [ 3.54] 7.21 1299752- 1
# 16 420.17s [ 2.64] 24868kN [ 2.68] 8.03 3246867- 1482
No solution in 16 moves.
Any serious bets on the time for depth=18?
After 1...Kb7 2.d8=N+
[D]3N4/1k6/8/8/8/8/1r5p/R3K3 b Q -
analysing (mate in 13 moves):
# 1 0.00s 0kN 0.87 1- 0
# 2 0.00s 0kN 0.98 1- 0
% EGTB found tables for max 5 pieces
% EGTB uses 3728.4K memory internally
# 3 0.08s 0kN [ 15.75] 0.98 13- 0
# 4 0.08s [ 1.00] 0kN [ 3.10] 1.12 40- 0
# 5 0.09s [ 1.12] 1kN [ 4.05] 1.38 151- 0
# 6 0.12s [ 1.33] 3kN [ 4.05] 1.80 545- 0
# 7 0.26s [ 2.17] 13kN [ 4.06] 2.43 1892- 0
# 8 0.93s [ 3.58] 69kN [ 5.33] 2.83 9431- 0
# 9 2.97s [ 3.19] 221kN [ 3.19] 3.65 30710- 0
# 10 11.12s [ 3.74] 952kN [ 4.30] 3.75 118577- 0
# 11 58.19s [ 5.23] 5702kN [ 5.99] 3.83 585321- 0
# 12 406.50s [ 6.99] 39331kN [ 6.90] 4.26 3664080- 3918
# 13 1711.39s [ 4.21] 157289kN [ 4.00] 5.42 13423657- 4743589
No solution in 13 moves.
In the end the difference is huge, but at depth 9 or 10 it is not yet really
clear, which variant will be cheaper in the end.
Now the anti-experiment: After 1...Kb7 2.O-O-O and one more black ply,
let white search for mate in, say, 11: (times cumulate, sorry)
After Rb2 - c2 ...
# 7 1.49s [ 11.46] 134kN [ 69.58] 1.79 7363- 0
PV: Kxc2 h1=Q Rxh1 Kc7 Rd1 Kb7 d8=Q Kc6 Qc8+ Kb6 Rb1+ Ka5 Qa8#
After Rb2 - b1 ...
# 8 7.20s [ 4.47] 755kN [ 5.21] 3.67 38241- 0
PV: Kxb1 h1=Q Rxh1 Kc7 Rd1 Kc6 d8=Q Kc5 Qc8+ Kb5 Rd2 Ka5 Qb8 Ka6 Ra2#
After Ph2 - h1Q ...
# 11 20.53s [ 1.48] 1780kN [ 1.38] 7.96 149318- 0
No solution in 11 moves.
After Ph2 - h1N ...
# 7 24.19s [ 1.13] 2137kN [ 1.15] 6.98 185209- 0
PV: d8=Q Rb6 Qd7+ Ka6 Qa4+ Kb7 Rd7+ Kc8 Re7 Rc6+ Qxc6+ Kd8 Qc7#
PV: Kxb2 Nf2 Rd4 Nd3+ Rxd3 Kc7 d8=Q+ Kb7 Qd6 Ka7 Qb4 Ka8 Ra3#
After Ph2 - h1R ...
# 11 24.36s [ 1.00] 2153kN [ 1.00] 7.05 185223- 0
No solution in 11 moves.
After Ph2 - h1B ...
# 7 27.29s [ 1.12] 2483kN [ 1.15] 6.38 200797- 0
PV: Kxb2 Bf3 Rc1 Bg4 d8=Q Be2 Qc8+ Ka7 Rc6 Bf1 Qd7+ Ka8 Rc8#
After Rb2 - d2 ...
# 11 40.28s [ 1.36] 3474kN [ 1.31] 8.43 297709- 0
No solution in 11 moves.
After Rb2 - e2 ...
# 8 46.70s [ 1.15] 4036kN [ 1.16] 7.57 352555- 0
PV: d8=Q h1=Q Rxh1 Re5 Qd7+ Kb6 Qd6+ Kb5 Qxe5+ Kb6 Rh6+ Kb7 Qe7+ Kb8 Rh8#
After Rb2 - f2 ...
# 8 49.70s [ 1.06] 4282kN [ 1.05] 7.46 372191- 0
PV: d8=Q h1=Q Rxh1 Rf7 Qd5+ Kc7 Qxf7+ Kc6 Qe6+ Kc5 Kb2 Kb5 Rh5+ Kb4 Qe4#
After Rb2 - g2 ...
# 11 494.88s [ 5.37] 36452kN [ 4.88] 6.97 3454779- 2615
No solution in 11 moves.
After Rb2 - a2 ...
# 11 514.99s [ 1.02] 38056kN [ 1.01] 7.15 3587168- 3366
No solution in 11 moves.
After Rb2 - b3 ...
# 8 524.61s [ 1.02] 38933kN [ 1.02] 7.09 3652607- 3804
PV: d8=Q Rc3+ Kd2 Rc2+ Kxc2 h1=Q Qd7+ Kb6 Rxh1 Kc5 Rh5+ Kb4 Qb7+ Kc4 Qe4#
After Rb2 - b4 ...
# 8 529.78s [ 1.01] 39361kN [ 1.01] 7.09 3692719- 4081
PV: d8=Q Rc4+ Kd2 Rc2+ Kxc2 h1=Q Qd7+ Kb6 Rxh1 Kc5 Rh5+ Kb4 Qb7+ Kc4 Qe4#
After Rb2 - b5 ...
# 9 565.21s [ 1.07] 42200kN [ 1.07] 6.93 3972575- 6621
PV: d8=Q Rc5+ Kb2 Rb5+ Ka3 h1=Q Rxh1 Re5 Qd7+ Kb6 Rb1+ Kc5 Rb5+ Kc4 Rxe5 Kc3
Rc5#
After Rb2 - b6 ...
# 9 575.53s [ 1.02] 42991kN [ 1.02] 6.96 4048100- 7491
PV: d8=Q h1=Q Qd7+ Ka6 Rxh1 Rf6 Kd2 Rf2+ Ke3 Re2+ Kxe2 Kb6 Rb1+ Kc5 Rb5+ Kc4
Qd3#
After Kb7 - c7 ...
# 6 575.92s [ 1.00] 43020kN [ 1.00] 6.98 4048272- 7492
PV: d8=Q+ Kb7 Rd7+ Ka6 Rd6+ Ka7 Qc7+ Rb7 Qa5+ Kb8 Rd8#
After Kb7 - a7 ...
# 6 575.94s [ 1.00] 43021kN [ 1.00] 6.98 4048410- 7493
PV: Kxb2 h1=Q Rxh1 Kb7 d8=Q Ka7 Qc7+ Ka6 Qb8 Ka5 Ra1#
After Kb7 - b8 ...
# 6 576.06s [ 1.00] 43030kN [ 1.00] 6.98 4048802- 7497
PV: d8=Q+ Kb7 Rd7+ Ka6 Rd6+ Ka7 Qc7+ Rb7 Qa5+ Kb8 Rd8#
PV: Kxb2 h1=Q d8=Q+ Kb7 Rxh1 Ka7 Qc7+ Ka6 Qb8 Ka5 Ra1#
After Kb7 - b6 ...
# 6 576.33s [ 1.00] 43047kN [ 1.00] 6.99 4050322- 7518
PV: d8=Q+ Kb7 Rd7+ Ka6 Rd6+ Ka7 Qc7+ Rb7 Qa5+ Kb8 Rd8#
PV: Kxb2 h1=Q d8=Q+ Ka6 Rd6+ Qc6 Rxc6+ Ka7 Qd7+ Ka8 Rc8#
After Kb7 - a6 ...
# 6 576.47s [ 1.00] 43057kN [ 1.00] 6.99 4050471- 7522
PV: Kxb2 h1=Q Rxh1 Kb6 d8=Q+ Kc6 Rh6+ Kc5 Kb3 Kb5 Qd5#
After Kb7 - c6 ...
# 8 581.03s [ 1.01] 43405kN [ 1.01] 6.98 4080820- 7905
PV: d8=Q h1=Q Qd6+ Kb5 Rxh1 Re2 Rh5+ Re5 Qxe5+ Kb6 Qc5+ Ka6 Qb4 Ka7 Ra5#
After Kb7 - a8 ...
# 6 581.26s [ 1.00] 43421kN [ 1.00] 6.98 4081060- 7909
PV: d8=Q+ Kb7 Rd7+ Ka6 Rd6+ Ka7 Qc7+ Rb7 Qa5+ Kb8 Rd8#
PV: Kxb2 h1=Q d8=Q+ Ka7 Rxh1 Kb7 Qd6 Ka7 Rh7+ Ka8 Qd8#
Time (user) = 581.29 sec (9.7 min)
581.300u 7.110s 12:07.41 80.8%
After some of the moves there is no mate in 11, and in 1 case (Rg2)
this appears to cost much more than in all the other cases,
namely 444 from 581 seconds (76.4%).
But the main problem with such proof techniques is to find out, under
what circumstances they are worth trying. Every search can explode,
and so it is a risky thing to do a search, which even if successful,
will just save another search, and if not successful will not save anything.
>Another possible test for chest may be to find the shortest mate for white after
>Kb7?? or to find mate for black after Kb7?? d8N+??
Sure. The anti-mate idea. To a limited extent I do this already.
The problem is, that in most cases it does not pay off, since it does
not find anything. It is not easy to find the correct balance between
cost and benefit, here.
I cannot run just every possible experiment, and after that pick the
quickest one and then say: "Look Ma, if I only let out all those useless
experiments, except this one... how quick I'm going to be!"
It won't work for the next job.
>I also suspect that using more tablebases like the kqrkn could help.
Hmm, about this I do not yet have any data. Need to extend my statistics,
again :-)
>Uri
Thanks for your comments (even where I happen to disagree).
Heiner
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.