Twisted Logic bug

[metax]

Edsel, I know you are no longer working on Twisted Logic, so I just want to inform you about a bug in the latest Twisted Logic (20100131x) without any expectations of fixing it.

In this position:

[d]8/8/8/2K2k2/2P1p3/8/8/8 w - - 0 1

Twisted Logic wants to play Kd4 with a draw score. It reaches iteration 21 after 10 seconds on my machine but does not get to depth 22 after 8 minutes.

(The right move is 1.Kb6!= by the way, but that is difficult to see for most engines which don't know the KQKP endgame.)

8/8/8/2K2k2/2P1p3/8/8/8 w - -

Engine: Twisted Logic 20100131x (128 MB)
by Edsel Apostol, Philippines

19/34 0:05 0.00 1.Kd4 Kf4 2.c5 e3 3.Kd3 Ke5 4.c6 Kd6
5.c7 Kxc7 6.Kxe3 Kd6 7.Kd4 Ke6 8.Ke4 Kf6
9.Kd4 Ke6 (4.577.403) 905

20/34 0:08 0.00 1.Kd4 Kf4 2.c5 e3 3.Kd3 Ke5 4.c6 Kd6
5.c7 Kxc7 6.Kxe3 Kd6 7.Kd4 Ke6 8.Ke4 Kd6
9.Kd4 (7.884.812) 939

21/36 0:10 0.00 1.Kd4 Kf4 2.c5 e3 3.Kd3 Ke5 4.c6 Kd6
5.c7 Kxc7 6.Kxe3 Kd6 7.Kd4 Ke6 8.Ke4 Kd6
9.Kd4 (9.539.693) 946

best move: Kc5-d4 time: 8:01.294 min n/s: 892.531 nodes: 429.317.652

However, after playing Kd4 on the board, it sees that white is lost immediately (ply 11!):

8/8/8/5k2/2PKp3/8/8/8 b - -

Engine: Twisted Logic 20100131x (128 MB)
by Edsel Apostol, Philippines

17/30 0:01 -10.89 1...Kf4 2.Kc3 e3 3.c5 Kf3 4.c6 e2
5.Kd2 Kf2 6.Kd3 e1Q 7.Kc4 Qe5 8.Kb4 Qd5
9.c7 Qb7+ 10.Kc4 Ke3 11.c8Q Qxc8+
12.Kd5 (1.493.605) 957

18/30 0:01 -10.91 1...Kf4 2.Kc3 e3 3.c5 Kf3 4.Kd3 e2
5.Kd2 Kf2 6.Kd3 e1Q 7.Kd4 Qe6 8.Kc3 Qe4
9.Kb3 Qd4 10.c6 Qb6+ 11.Kc4 Qxc6+
12.Kd4 (1.901.456) 999

19/32 0:02 -10.94 1...Kf4 2.Kc3 e3 3.c5 Kf3 4.Kd3 e2
5.Kd2 Kf2 6.Kd3 e1Q 7.Kd4 Qe6 8.Kc3 Qe4
9.Kb3 Qd4 10.c6 Qb6+ 11.Kc4 Qxc6+
12.Kd4 Qd6+ 13.Ke4 (2.246.644) 1021

20/36 0:08 -11.31 1...Kf4 2.Kc3 e3 3.c5 Kf3 4.c6 e2
5.Kd2 Kf2 6.Kd3 e1Q 7.Kd4 Qa5 8.Ke4 Qc5
9.Kf4 Qxc6 10.Kg5 Kf3 11.Kh5 Qe8+
12.Kh6 (10.213.328) 1177

21/37 0:10 -11.32 1...Kf4 2.Kc3 e3 3.c5 Kf3 4.c6 e2
5.Kd2 Kf2 6.Kd3 e1Q 7.Kd4 Qa5 8.Ke4 Qc5
9.Kf4 Qxc6 10.Kg5 Kf3 11.Kf5 Qe4+
12.Kg5 Qe5+ 13.Kg6 (12.838.944) 1194

best move: Kf5-f4 time: 0:11.871 min n/s: 1.203.449 nodes: 13.967.240

[Edsel Apostol]

Hi Luca,

Thanks for pointing out the bug. It is due to the very aggressive prunings (my futility pruning in this version has no depth limit) and reductions.

Even Hannibal with a similar search but with good endgame knowledge sees it as a draw in the first 19 plies. It might be a problem with my search.

[hgm]

How can you ever prune pushing a passer that will promote first, when you don't have a winning score yet? That makes absolutely no sense. It might make more sense if it was the only move you searched, and pruned all others...

[hgm]

My new engine sees that kd5 is losing after 0.22 sec at 15 ply. It takes 22 ply and 0.84 sec before it switches to Kb6, though. It cannot see that that draws, because it does not know about KQKP. But of course it will always prefer an end leaf with a pawn on the 7th above one where the Pawn is already lost, or where it is checkmated.

Code: Select all

 1     -64      0         0 eval, dif=-20, Pawns=5
 1     -59     11         3 c5d5
 2     -59     16        15 c5d4 f5f4
 3     -45     17        28 c5d4 f5f4 c4c5
 4     -59     17        38 c5d4 f5f4 c4c5 e4e3
 5     -50     17        62 c5d4 f5f4 c4c5 e4e3 c5c6
 6     -59     17       117 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3
 7     -51     17       168 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3 c5c6
 8       1     17       320 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 c7c8
 9       1     17       340 c5d4 f5f4 c4c5 e4e3 c5c6 e2e1 c7c8
10       1     18       458 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 c7c8 e1f2
11       1     18       588 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 c7c8 e1f2 d4d5
12      -8     19       848 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 c7c8 e1d2 d4c4 f4e4
13      -8     19      1055 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 c7c8 e1d2 d4c4 f4e4 c8b7
14      -5     20      3039 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3 c5c6 e3e2 c6c7 e2e1 c7c8 f3f4 d3c4
15    -710     22      6397 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3 c5c6 e3e2 d3d2 f3f2 c6c7 e2e1 d2d3 f2f3
16    -710     23      7844 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3 c5c6 e3e2 d3d2 f3f2 c6c7 e2e1 d2c2 e1e6 c2d3 f2f3
17    -706     23      9188 c5d4 f5f4 c4c5 e4e3 d4d3 f4f3 c5c6 e3e2 d3d2 f3f2 c6c7 e2e1 d2c2 e1e6 c2d3 f2f3 d3d4
18    -737     30     25458 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 d4d5 e1e5 d5c6 e5e6 c6b5 e6d7 b5b6 f4e4 b6b7 d7b5
19    -746     39     48828 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 d4d5 e1e5 d5c6 e5e6 c6b5 e6d7 b5b6 f4e4 b6b7 d7b5 b7c8
20    -746     40     54100 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 d4d5 e1e5 d5c6 e5e6 c6b5 e6d7 b5b6 f4e4 b6b7 d7b5 b7c8 b5c6
21    -744     43     63935 c5d4 f5f4 c4c5 e4e3 c5c6 e3e2 c6c7 e2e1 d4d5 e1e5 d5c6 e5e6 c6b7 e6d7 b7b8 d7b5 b8c8 f4e4 c8d8 b5d3
22    -751     84    207070 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e8 b6b7 e8b5 b7a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6b5 d7c8 d4c5
23    -751     99    247858 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e8 b6b7 e8b5 b7a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6d5 b7b8 d5b3
24    -751    118    294955 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1c3 b6b7 c3f3 b7b8 f3b3 b8a7 b3c4 a7b7 c4d5 b7a7 d5d7 a7b7 d7b5 b7a7 b5c5 a7b7
25    -751    133    335241 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6f7 b7b8 f7b3 b8a7 b3c4 a7b7 c4b5 b7a7 b5c6 a7b8 c6b6 b8a8 b6a5 a8b7 a5d5 b7b8
26    -751    157    393559 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6
27    -751    185    455113 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6
28    -751    277    737243 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6e7 b7b8 e7b4
29    -751    357    946102 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6
30    -751    406   1052079 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6d5
31    -751    520   1319837 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6e7 b7b8 e7b4 b8a7 b4a5 a7b7 a5d5 b7b8 d5b3
32    -751   1534   3702078 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6e7 b7b8 e7b4 b8a7 b4c4 a7b7 c4e4
33    -751   1620   3864932 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6 b8b7 d6e7 b7b8 e7b4 b8a7 b4c5 a7b7 c5d5 b7a7
34    -751   1803   4267906 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1c1 b6b7 c1h1 b7b8 h1b1 b8a7 b1a2 a7b7 a2d5 b7a7 d5c6 a7b8 c6b5 b8a7 b5d7 a7b8 d7d6 b8b7 d6e7 b7b8 e7b4 b8a7 b4a3 a7b7 a3f3 b7a7
35    -751   3047   4512203 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6e4 b7b8 e4b1 b8a7 b1c2 a7b7 c2g2 b7b8 g2b2 b8a7 b2g7 a7b8 g7e5 b8b7 e5b5 b7a7 b5c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6d6
36    -751   3328   5155749 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6e4 b7b8 e4b1 b8a7 b1c2 a7b7 c2g2 b7b8 g2b2 b8a7 b2d4 a7b7 d4d5 b7a7 d5c6
37    -751   3585   5676857 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1e6 b6b7 e6d7 b7b8 d7b5 b8a7 b5c6 a7b8
38    -751   3783   6090971 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1c1 b6b7 c1h1 b7b8 h1b1 b8a7 b1c2 a7b7 c2e4 b7b8 e4b4 b8a8 b4c5
39    -751   6138  11196294 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1c1 b6b7 c1h1 b7b8 h1b1 b8a7 b1c2 a7b7 c2e4 b7b8 e4b4 b8a8 b4a5
40    -751   6427  11784398 c5b6 e4e3 c4c5 e3e2 c5c6 e2e1 c6c7 e1c1 b6b7 c1h1 b7a7 h1c6 a7b8 c6b6 b8a8 b6a6 a8b8 a6b5 b8a7 b5d7 a7b8 d7d6 b8b7 d6e7 b7b8 e7b4 b8a7 b4c5 a7b7

[metax]

OK, so I haven't experienced a bug but only a heavlily pruning search, as TL has always had.
The test position hasn't any practical relevance anyway, because I noticed Twisted Logic to solve other tactics problems much faster than before.

My engine also finds that Kd4 is losing relatively fast, then switching to Kb6 at ply 12 with a draw score at ply 13 after one second:

8/8/8/2K2k2/2P1p3/8/8/8 w - - 0 1

Analysis by ChessMind 0.72:

1.Kd4 Kf4 2.c5 e3 3.c6 e2
= (-0.20) Tiefe: 6/8 00:00:00
1.Kd4 e3 2.Kxe3 Ke5 3.Kf2 Kd4 4.Kg1
= (0.00) Tiefe: 7/14 00:00:00 2kN
1.Kd4 e3 2.Kxe3 Ke5 3.Kf2 Kd4 4.Kg1 Kxc4
= (0.00) Tiefe: 8/14 00:00:00 6kN
1.Kd4 e3 2.Kxe3 Ke5 3.Kf2 Kd4 4.Kg1 Kxc4
= (0.00) Tiefe: 9/16 00:00:00 8kN
1.Kd4 e3 2.Kxe3 Ke5 3.Kf2 Kd4 4.Kg1 Kxc4
= (0.00) Tiefe: 10/18 00:00:00 17kN
1.Kd4 e3 2.Kxe3 Ke5 3.Kf2 Kd4 4.Kg1 Kxc4
= (0.00) Tiefe: 11/20 00:00:00 24kN
1.Kd4 Kf4 2.c5 e3 3.Kc3 Kf3 4.Kb4 e2 5.c6 e1Q+ 6.Kb5 Ke2 7.Ka4
-+ (-9.31) Tiefe: 12/24 00:00:00 135kN
1.Kb6
-+ (-8.30 ++) Tiefe: 12/26 00:00:00 275kN
1.Kb6
-+ (-6.64 ++) Tiefe: 12/26 00:00:01 307kN
1.Kb6
-+ (-4.07) Tiefe: 12/26 00:00:01 357kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2
= (0.00) Tiefe: 13/28 00:00:01 565kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7
= (0.00) Tiefe: 14/30 00:00:02 845kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 15/31 00:00:03 1341kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 16/33 00:00:05 2324kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 17/37 00:00:08 4112kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 18/38 00:00:15 7251kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 19/45 00:00:30 14557kN
1.Kb6 e3 2.c5 Kg4 3.c6 e2 4.c7 e1Q 5.c8Q+ Kf3 6.Ka7 Ke2 7.Kb6 Qd2 8.Ka7 Qe1
= (0.00) Tiefe: 20/47 00:01:09 33492kN


One question may be allowed: I have seen the latest Twisted Logic perform much better in tactical test positions than the previous version and you also wrote that you switched to a more conservative pruning method. Why doesn't that help in this position?

[hgm]

ChessMind sees that draw score pretty fast. How does it do that? Do you have some sort of recognizer for KQKP?

How do you see that Kd4 does not work already at 12 ply, btw? Do you have a promotion extension? Or is it just grafting because of lucky hash hit? I am a bit worried that my new engine does not see it at 14 ply. I guess it is because the check extension is off in this game phase.

[Alibaba]

Hi,

M-Chess 8.0 plays Kb6 after 1 s.....


Regards
Andi

[hgm]

Well, there could be programs that play Kb6 from the very start, after 0 sec. What matters is the score & PV they assign to it. If they do it and assign a draw score because they see it will end up in a drawn KQKP position, then they are brilliant. If they do it and assign a draw score because they do not realize that the Pawns can promote, and count wood in KPKP, it doesn't mean a thing. White has only 7 moves, so even a random mover would 'solve' this position in zero time 14% of the cases...

[metax]

ChessMind sees that draw score pretty fast. How does it do that? Do you have some sort of recognizer for KQKP?

Simple - ChessMind's got an evaluation function for KQKP which is around 50 lines long, so really nothing brilliant.

How do you see that Kd4 does not work already at 12 ply, btw? Do you have a promotion extension? Or is it just grafting because of lucky hash hit? I am a bit worried that my new engine does not see it at 14 ply. I guess it is because the check extension is off in this game phase.

The refutation of 1.Kd4 is 14 plies deep:

1.Kd4 Kf4 2.c5 e3 3.c6 e2 4.c7 e1Q 5.c8Q Qd2+ 6.Kc5 Qc1+ 7.Kd5 Qxc8. Given that the last move is a capture and could be seen in the quiescence search, any engine without pruning or reductions should it see at 13 ply without any extensions, at 11 ply with check extension and at 9 ply with check and passed-pawn extension. And engines like Spike 1.2 do find it at iteration 9. It's rather surprising that ChessMind sees it _only_ at ply 12, but that's probably due to some pruning even in pawn endgames.

Well, there could be programs that play Kb6 from the very start, after 0 sec. What matters is the score & PV they assign to it. If they do it and assign a draw score because they see it will end up in a drawn KQKP position, then they are brilliant.

Really not. Took me about 30 min and a bit of testing time to implement a KQKP evaluation function for both sides and it does practically not reduce the speed of normal evaluation. It does probably not really raise the strength because the endgame occurs very infrequently and other engines also play Kb6 because it's the only move which does not lose the pawn within the horizon.

If you want I can post some pseudo code but it's really easy to implement. No big deal.

[hgm]

Simple - ChessMind's got an evaluation function for KQKP which is around 50 lines long, so really nothing brilliant.

OK, that explains it.

The refutation of 1.Kd4 is 14 plies deep:
1.Kd4 Kf4 2.c5 e3 3.c6 e2 4.c7 e1Q 5.c8Q Qd2+ 6.Kc5 Qc1+ 7.Kd5 Qxc8.

It is a bit deeper, actually. White can stall some more by chasng the black Pawn:
1.Kd4 Kf4 2.c5 e3 3.Kd3 Kf3 4.c6 e2 5.c7 e1Q 6.c8Q Qd2+ 7.Kc5 Qc1+ 8.Kd5 Qxc8.
Doing it once more does not help, because then black promotes with check. But this is 16 ply, where the 16th ply can be QS. So a plain search would need 15 ply to see it, and indeed, my engine does not see it at 14 ply.

The last remark was directed towards Andreas; from the scores you posted it ws obvious that ChessMind did see a draw despite the black promotion. The recognizer explains that. I have no recognizers at all yet, note even KBK.