Problems with this position

[Kempelen]

thanks all for your contribution. I have solved the problems. Last one appears to be a instability, but I have been parameterizing windows, prunnings and so on and have minimized the impact. Last tests show a significant improvement.

[JensBNielsen]

I tried this position a few days ago to test my programs hashtable - and now I came across this post ;o)

The problem is not easy because of the depth.

My intention is to add this simple knowledge to my program:
If the pawn is blocked by the enemy king, and the king is not on the backrow, the position is a draw.
This ought to give a lot of cut-off's and a faster search...

Best, Jens

[JensBNielsen]

I tried to add some knowledge to my program Dabbaba. The knowledge is ”If the enemy king blocks the pawn, and the king is not on the backrow, the position is a draw”.

It only made the search ca 10% faster measured at depth 24.
See below.

The promotion is seen at depth 25 with the knowledge, at depth 26 without the knowledge… Don’t know why…

Hyatt wrote ”If you can't solve this one in a second or so, you still have some search/transposition table issues even though you think it is working correctly...”

Dabbaba takes more than a minute to see the promotion. The speed seems to slow down from depth 19…
Are my hash-tables too small... max=524287 used=231114 used-pct=44.1

Here are Dabbabas searches:


with kpk knowledge:


1 00:00 1 1 +2,03 e2e3 score: 203 v=203 pawn=103 mat=100 n=1 time=0.00
1 00:00 2 2 +2,27 e2e4 score: 227 v=227 pawn=127 mat=100 n=2 time=0.00
2 00:00 39 39 +2,17 e2e4 score: 217 v=227 pawn=127 mat=100 n=39 time=0.00
3 00:00 65 65 +2,46 e2e4 score: 246 v=227 pawn=127 mat=100 n=65 time=0.00
4 00:00 261 261 +2,17 e2e4 score: 217 v=227 pawn=127 mat=100 n=261 time=0.00
5 00:00 662 662 +2,34 e2e4 score: 234 v=227 pawn=127 mat=100 n=662 time=0.00
6 00:00 1.483 1.483 0,00 e2e4 score: 0 v=220 pawn=120 mat=100 n=1483 time=0.00
6 00:00 1.966 1.966 +1,91 e1f1 score: 191 v=167 pawn=73 king=-6 mat=100 n=1966 time=0.00
6 00:00 2.909 2.909 +1,97 e2e3 score: 197 v=209 pawn=109 mat=100 n=2909 time=0.00
7 00:00 4.340 4.340 +1,97 e2e3 score: 197 v=209 pawn=109 mat=100 n=4340 time=0.00
7 00:00 5.980 5.980 +2,23 e1d2 score: 223 v=181 pawn=75 king=6 mat=100 n=5980 time=0.00
8 00:00 9.177 9.177 +2,40 e1d2 score: 240 v=181 pawn=75 king=6 mat=100 n=9177 time=0.00
9 00:00 22.510 1.125.500 +2,34 e1d2 score: 234 v=181 pawn=75 king=6 mat=100 n=22510 time=0.02 N/S=1125500
10 00:00 39.735 993.375 +2,40 e1d2 score: 240 v=181 pawn=75 king=6 mat=100 n=39735 time=0.04 N/S=993375
11 00:00 65.851 940.728 +2,34 e1d2 score: 234 v=181 pawn=75 king=6 mat=100 n=65851 time=0.07 N/S=940729
12 00:00 96.437 964.370 +2,64 e1d2 score: 264 v=181 pawn=75 king=6 mat=100 n=96437 time=0.10 N/S=964370
13 00:00 114.589 1.041.718 +2,64 e1d2 score: 264 v=181 pawn=75 king=6 mat=100 n=114589 time=0.11 N/S=1041718
14 00:00 147.700 1.055.000 +2,64 e1d2 score: 264 v=181 pawn=75 king=6 mat=100 n=147700 time=0.14 N/S=1055000
15 00:00 184.149 1.023.050 +2,64 e1d2 score: 264 v=181 pawn=75 king=6 mat=100 n=184149 time=0.18 N/S=1023050
16 00:00 250.773 1.139.877 +2,64 e1d2 score: 264 v=181 pawn=75 king=6 mat=100 n=250773 time=0.22 N/S=1139877
17 00:00 427.483 1.042.641 +2,76 e1d2 score: 276 v=181 pawn=75 king=6 mat=100 n=427483 time=0.41 N/S=1042641
18 00:00 692.785 1.082.476 +2,87 e1d2 score: 287 v=181 pawn=75 king=6 mat=100 n=692785 time=0.64 N/S=1082477
19 00:00 1.045.172 976.796 +2,92 e1d2 score: 292 v=181 pawn=75 king=6 mat=100 n=1045172 time=1.07 N/S=976796
20 00:10 8.980.072 868.478 +2,92 e1d2 score: 292 v=181 pawn=75 king=6 mat=100 n=8980072 time=8.19 N/S=1096468
21 00:13 13.732.894 1.000.939 +3,34 e1d2 score: 334 v=186 pawn=80 king=6 mat=100 n=13732894 time=13.31 N/S=1031773
22 00:19 20.203.534 1.025.560 +3,74 e1d2 score: 374 v=181 pawn=75 king=6 mat=100 n=20203534 time=19.63 N/S=1029217
23 00:23 21.564.335 937.579 +3,74 e1d2 score: 374 v=181 pawn=75 king=6 mat=100 n=21564335 time=21.35 N/S=1010039
24 01:17 60.022.170 779.508 +3,74 e1d2 score: 374 v=186 pawn=80 king=6 mat=100 n=60022170 time=71.11 N/S=844075
25 02:31 85.974.561 569.367 +12,61 e1d2 score: 1261 v=186 pawn=80 king=6 mat=100 n=85974561 time=103.12 N/S=833733
26 06:12 181.059.285 486.718 +12,82 e1d2 score: 1282 v=186 pawn=80 king=6 mat=100 n=181059285 time=220.25 N/S=822063

1 06:12 5 0 +0,02 (hash: write=903054 nowrite=207012830 pre-va=127151004 pre-va-hit=91480823
1 00:00 5 5 +0,02 (hash: error=0 nofinal(cut-off!)=65162897 read=304097789 read_ok=246988160 read_ok_final(same position met again)=32863787
1 00:00 5 5 +0,02 (hash-elementer: max=524287 used=231114 used-pct=44.1 - VERSION 2.01 JA-Pelle Date 10-07-2009
1 00:00 5 5 +0,02 e1d2 e8d8 d2d3 d8d7 d3e4 d7e6 e2e3 e6d6 e4f5 d6e7 f5e5 e7d7 e5f6 d7d6




without kpk knowledge:


1 00:00 1 1 +2,03 e2e3 score: 203 n=1 time=0.00
1 00:00 2 2 +2,27 e2e4 score: 227 n=2 time=0.00
2 00:00 39 39 +2,17 e2e4 score: 217 n=39 time=0.00
3 00:00 65 65 +2,46 e2e4 score: 246 n=65 time=0.00
4 00:00 291 291 +2,17 e2e4 score: 217 n=291 time=0.00
5 00:00 756 756 +2,34 e2e4 score: 234 n=756 time=0.00
6 00:00 1.667 1.667 +1,40 e2e4 score: 140 n=1667 time=0.00
6 00:00 2.145 2.145 +1,91 e1f1 score: 191 n=2145 time=0.00
6 00:00 3.096 3.096 +1,97 e2e3 score: 197 n=3096 time=0.00
7 00:00 4.485 4.485 +1,97 e2e3 score: 197 n=4485 time=0.00
7 00:00 6.257 6.257 +2,23 e1d2 score: 223 n=6257 time=0.00
8 00:00 9.831 9.831 +2,44 e1d2 score: 244 n=9831 time=0.00
9 00:00 22.300 1.115.000 +2,38 e1d2 score: 238 n=22300 time=0.02 N/S=1115000
10 00:00 47.988 959.760 +2,44 e1d2 score: 244 n=47988 time=0.05 N/S=959760
11 00:00 70.587 1.008.385 +2,71 e1d2 score: 271 n=70587 time=0.07 N/S=1008386
12 00:00 97.267 972.670 +2,87 e1d2 score: 287 n=97267 time=0.10 N/S=972670
13 00:00 132.621 1.020.161 +2,92 e1d2 score: 292 n=132621 time=0.13 N/S=1020162
14 00:00 316.663 1.055.543 +2,90 e1d2 score: 290 n=316663 time=0.30 N/S=1055543
15 00:00 393.257 1.034.886 +2,90 e1d2 score: 290 n=393257 time=0.38 N/S=1034887
16 00:00 641.854 1.069.756 +2,92 e1d2 score: 292 n=641854 time=0.60 N/S=1069757
17 00:00 783.183 1.103.074 +3,08 e1d2 score: 308 n=783183 time=0.71 N/S=1103075
18 00:00 1.053.316 1.097.204 +3,30 e1d2 score: 330 n=1053316 time=0.96 N/S=1097204
19 00:01 1.669.505 987.872 +3,30 e1d2 score: 330 n=1669505 time=1.69 N/S=987873
20 00:03 2.986.607 933.314 +3,50 e1d2 score: 350 n=2986607 time=3.20 N/S=933315
21 00:14 8.973.716 618.024 +3,50 e1d2 score: 350 n=8973716 time=10.75 N/S=834764
22 00:21 15.888.872 747.008 +3,50 e1d2 score: 350 n=15888872 time=17.96 N/S=884681
22 00:21 19.307.136 907.716 +4,08 e1f2 score: 408 n=19307136 time=21.28 N/S=907290
23 00:45 26.692.596 593.168 +4,08 e1f2 score: 408 n=26692596 time=29.94 N/S=891536
24 01:35 70.010.002 736.947 +4,08 e1f2 score: 408 n=70010002 time=79.99 N/S=875234
25 03:13 114.706.434 594.333 +4,08 e1f2 score: 408 n=114706434 time=133.09 N/S=861871
26 06:34 191.612.151 486.325 +12,69 e1f2 score: 1269 n=191612151 time=218.73 N/S=876021
27 22:59 505.334.569 366.450 +12,69 e1f2 score: 1269 n=505334569 time=614.96 N/S=821736

[rjgibert]

I tried to add some knowledge to my program Dabbaba. The knowledge is ”If the enemy king blocks the pawn, and the king is not on the backrow, the position is a draw”.

It only made the search ca 10% faster measured at depth 24.

You can make this heuristic a tiny bit more general: If the enemy king is on 1 of the 2 squares before the pawn, and the pawn is not on the 7th, the position is a draw. An example, if the White pawn is on e4, then the 2 draw squares are e5 and e6.

[rjgibert]

I tried to add some knowledge to my program Dabbaba. The knowledge is ”If the enemy king blocks the pawn, and the king is not on the backrow, the position is a draw”.

It only made the search ca 10% faster measured at depth 24.

You can make this heuristic a tiny bit more general: If the enemy king is on 1 of the 2 squares before the pawn, and the pawn is not on the 7th, the position is a draw. An example, if the White pawn is on e4, then the 2 draw squares are e5 and e6.

Change this to: If the enemy king is on 1 of the 2 squares before the pawn, and the pawn is not on the 6th nor on the 7th, the position is a draw. Now it works. It could be a bit more precise, but this keeps it simple. It's not an "if and only if" rule, anyways.

[Don]

I found this position searching in the forum.

[D]4k3/8/8/8/8/8/4P3/4K3 w

It was posted in a thread about testing transposition table. OK I said, let's test it. What I found is that my engine does not find the solution even TT working fine. Then I give the position to other engines which I know TT work apparently fine. The conclusion is that there were engines which dont found the solution even in 30 depth or even passes 2 minutes:

I.e, Buzz engine:

Code: Select all

31 169 2268 12551036 Kd2 Kd7 Kd3 Kd6 Kd4 Ke6 Ke4 Ke7 Ke5 Kf7 Kd6 Kf6 e4 Kg5 e5 K
f4 e6 Ke3 Kd5 Kd3 Ke5 Kc4 Ke4 Kb3 Kd4 Ka2 Kd3 Ka3 Ke4 Kb3
31 169 2270 12557132 Kd2 Kd7 Kd3 Kd6 Kd4 Ke6 Ke4 Ke7 Ke5 Kf7 Kd6 Kf6 e4 Kg5 e5 K
f4 e6 Ke3 Kd5 Kd3 Ke5 Kc4 Ke4 Kb3 Kd4 Ka2 Kd3 Ka3 Ke4 Kb3

i.e2, Mizar:

Code: Select all

19 238 176 1560515 e1d2 e8e7 d2e3 e7d7 e3f4 d7e7 f4f5 e7f7 e2e4 f7e7 e4e5 e7f7 e
5e6 f7e8 f5f4 e8f8 f4e4 f8e8 e4e5 e8f8
20 238 198 1771848 e1d2 e8e7 d2e3 e7d7 e3f4 d7e7 f4f5 e7f7 e2e4 f7e7 e4e5 e7f8 e
5e6 f8e7 f5e5 e7f8 e5f6 f8e8 f6e5 e8f8

As I see, my search tend to fill with king moves or premature pawn push:

Code: Select all

19    197   1425   8622288 1. Kd2 Kd7 2. e4 Ke6 3. Kd3 Ke7 4. Ke3 Ke8 5. e5 Kf8
6. Kd4 Ke7 7. Kd5 Kd7 8. e6+ Kc7 9. Ke5 Kd8 10. Kf6 Kc7
20    197   2571  15915625 1. Kd2 Kd7 2. e4 Ke6 3. Kd3 Ke7 4. Ke3 Ke8 5. e5 Kf8
6. Kd4 Ke7 7. Kd5 Kd7 8. e6+ Ke7 9. Ke5 Ke8 10. Ke4 Kf8 11. Kd5

Of course, I add pawn passed bonus, pawn position bonus and all those things...

What is exactly needed here to correctly find the solution, a part from a correct TT implementation?

I turned off my kpvsk boolean rulebase and tried it and it finds queening very quickly, in just a fraction of a second.

It finds checkmate in 20 seconds. But this is going to vary wildly from program to program and is more about extensions and selectivity and various gadgets that make a search faster or slower. I do half a ply check extensions and a lot of checks in quies.

The checkmate is found at depth 38 in my program. At depth 24 the promotion is found where the score jumps from 280 to 1103.

You cannot make too much of this. The mighty Rybka, which is far stronger than my program seems to take a long time to find the promotion, about 30 seconds on the same computer that mine finds it in a fraction of a second. However the score very quickly gets high, but not a queens worth until 30 seconds where there is a huge jump.

My theory is the Rybka is somehow super-focused on what is relevant because it always plays the right moves, even if the score doesn't reflect that it really see's what is going on. In other words it is as if it knows the path, but not what is at the end. I've seen this before with Rybka.

After 10 minutes Rybka still does not find this mate.

Maybe there is something wrong with any program that finds it too fast, an indication that it is not selective enough or something.

[Don]

I tried to add some knowledge to my program Dabbaba. The knowledge is ”If the enemy king blocks the pawn, and the king is not on the backrow, the position is a draw”.

It only made the search ca 10% faster measured at depth 24.

You can make this heuristic a tiny bit more general: If the enemy king is on 1 of the 2 squares before the pawn, and the pawn is not on the 7th, the position is a draw. An example, if the White pawn is on e4, then the 2 draw squares are e5 and e6.

For king and pawn vs king you might as well just compile the database into your program - it's very tiny and it gets it right even in leaf nodes. I consider this basic knowledge every beginner needs to learn right away - how to win with king and pawn against a king - so I put it directly in my program. I doubt that it adds more than 1 or 2 ELO, but it's still nice to have.