Problems with this position

[bob]

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?

You should be able to see a queen very quickly. A simple piece of chess knowledge can help, but it is not necessary.

The simple rule for king and pawn vs king, pawn not a rookpawn, is that if the winning king is 2 squares in front of the pawn, and the pawn can't be taken by the opponent, then the position is won. If the king is one square in front of the pawn, the pawn can't be captured, and the winning king has the opposition, then the position is won.

If any of the above fail, the position is a draw. This position is trivially won since the king can reach a position that meets the above very quickly.

This is nowhere near being correct. I would guess that you are even misremembering what you have in crafty on this. For example, with the pawn on the 5th and your king one square in front of your pawn, it is a win with or without the opposition unless the pawn is a rook pawn. Another example, W: Kc5, Pf5; B: Kc7 wins with White to move. There are also all the square of the pawn winning positions, etc. There are many more examples.

I simply left out the case for pawn on the 5th, so you are correct. This is a variation of the "if the pawn reaches the 7th without giving check" case of winning.

[ffao]

I have problems with this position too. Seeing as I take 45 MN to search to depth 17, while Crafty reports 180 KN to search to depth 21, I'm doing something pretty wrong.

I'm thinking this is too much to be a result of bad move ordering. If I turn off the evaluation, I get one more ply, but it's still terrible.

Now, looking at your statistics, you have 0.1% of the hash table filled. My stats are as follows:

Code: Select all

Total: 16277216
Filled: 2526061 (15.0%)

Exact: 10538 (0.4%)
Alpha: 935811 (37.0%)
Beta: 1579712 (62.5%)

Perhaps equal positions are getting different hash keys (and that's turning off en-passant, because it shouldn't be considered in this position anyway).

Maybe I should just play random transpositions and check if the keys match?

P.S: yes, that was a great idea. I not only found one, but two bugs in the hash! (I didn't expect that, as I stress-tested it for a whole day when I wrote it the first time...)

1) The hash for a black queen and king was the same;
2) The moving piece was always considered to be a pawn when advancing.

Of course, bug 2 was the one apparent here. My node count falls to 300 KN in depth 21, while my hash cutoff rate is now nearly 50%. I still have 15% of the table filled, though.

Fermin, you definitely have a hidden bug there.

[hgm]

Some stats taken from micro-Max, for comparison:

Code: Select all

4M entries
-1     -1        8          1 e2e3
probes=        1 hits=        0 cuts=        0      used=     1 exact=   1
 0     74       16          2 e2e3
probes=        0 hits=        0 cuts=        0      used=     1 exact=   1
 1     81       23          9 e2e4
probes=        3 hits=        0 cuts=        0      used=     4 exact=   3
 2     75       30         56 e2e4
probes=       23 hits=        3 cuts=        1      used=    24 exact=   9
 3     81       37        137 e2e4
probes=       56 hits=       28 cuts=       12      used=    52 exact=  12
 4     77       45        510 e2e4
probes=      267 hits=      141 cuts=       77      used=   178 exact=  31
 5     81       52       1049 e2e4
probes=      493 hits=      344 cuts=      204      used=   327 exact=  39
 6     79       60       1924 e2e4
probes=     1015 hits=      817 cuts=      535      used=   525 exact=  71
 7     79       70       2935 e2e3
probes=     1235 hits=      979 cuts=      640      used=   780 exact=  94
 8     79       77       4664 e2e3
probes=     2333 hits=     1909 cuts=     1324      used=  1203 exact= 121
 9     81       86       8928 e2e4
probes=     6830 hits=     5925 cuts=     4304      used=  2104 exact= 173
10     81       94      15322 e2e4
probes=    11500 hits=    10378 cuts=     7638      used=  3214 exact= 246
11     81      102      24144 e2e4
probes=    17096 hits=    15800 cuts=    11665      used=  4479 exact= 335
12     81      111      37970 e2e4
probes=    31092 hits=    29544 cuts=    22424      used=  5995 exact= 539
13     82      125      79283 e1d2
probes=    96777 hits=    93130 cuts=    70901      used=  9500 exact= 813
14    139      140     128812 e1d2
probes=   131763 hits=   129061 cuts=   100944      used= 11973 exact= 994
15    139      162     217943 e1d2
probes=   259553 hits=   255838 cuts=   202216      used= 15181 exact= 953
16    138      187     301861 e1d2
probes=   247748 hits=   244959 cuts=   195048      used= 17448 exact=1060
17    138      216     430681 e1d2
probes=   420099 hits=   415518 cuts=   338109      used= 20961 exact=1206
18    148      308     875488 e1d2
probes=  1352820 hits=  1347481 cuts=  1088533      used= 24380 exact=1131
19    152      394    1289744 e1f2
probes=  1375482 hits=  1367835 cuts=  1122490      used= 28998 exact=1232
20    197      760    3286683 e1f2
probes=  5901840 hits=  5890746 cuts=  4745241      used= 32494 exact=1088
21    194      950    4256651 e1f2
probes=  3330215 hits=  3321055 cuts=  2720798      used= 35709 exact=1290
22    193     1237    5663711 e1f2
probes=  4468374 hits=  4462614 cuts=  3653893      used= 37364 exact=1410
23    193     1742    8176642 e1f2
probes=  8577663 hits=  8572705 cuts=  7250154      used= 38917 exact=1335
24    216     2329   11077372 e1d2
probes= 10380787 hits= 10365213 cuts=  8578433      used= 42324 exact=1531
25    214     2488   11789436 e1d2
probes=  2667681 hits=  2660082 cuts=  2210816      used= 44139 exact=1600
26    212     3978   19888158 e1d2
probes= 24808628 hits= 24791147 cuts= 20020289      used= 45669 exact=1585
27    804     4549   23028167 e1d2
probes= 10744118 hits= 10729447 cuts=  8843451      used= 47953 exact=1700

16M entries
-1     -1       38          1 e2e3
probes=        1 hits=        0 cuts=        0      used=     1 exact=   1
 0     74       71          2 e2e3
probes=        0 hits=        0 cuts=        0      used=     1 exact=   1
 1     81      100          9 e2e4
probes=        3 hits=        0 cuts=        0      used=     4 exact=   3
 2     75      128         56 e2e4
probes=       23 hits=        3 cuts=        1      used=    24 exact=   9
 3     81      157        137 e2e4
probes=       56 hits=       28 cuts=       12      used=    52 exact=  12
 4     77      187        510 e2e4
probes=      267 hits=      141 cuts=       77      used=   178 exact=  31
 5     81      218       1049 e2e4
probes=      493 hits=      344 cuts=      204      used=   327 exact=  39
 6     79      249       1924 e2e4
probes=     1015 hits=      817 cuts=      535      used=   525 exact=  71
 7     79      281       2935 e2e3
probes=     1235 hits=      979 cuts=      640      used=   781 exact=  94
 8     79      312       4662 e2e3
probes=     2333 hits=     1910 cuts=     1324      used=  1204 exact= 121
 9     81      342       8922 e2e4
probes=     6815 hits=     5911 cuts=     4289      used=  2106 exact= 173
10     81      377      15298 e2e4
probes=    11453 hits=    10336 cuts=     7599      used=  3219 exact= 246
11     81      407      24090 e2e4
probes=    17060 hits=    15775 cuts=    11639      used=  4495 exact= 337
12     81      438      37851 e2e4
probes=    30971 hits=    29438 cuts=    22324      used=  6013 exact= 541
13     82      476      78987 e1d2
probes=    96500 hits=    92904 cuts=    70697      used=  9521 exact= 810
14    139      513     127746 e1d2
probes=   129598 hits=   127080 cuts=    99241      used= 11931 exact= 978
15    140      564     216192 e1d2
probes=   270259 hits=   266900 cuts=   213004      used= 15009 exact= 931
16    139      617     311341 e1d2
probes=   286660 hits=   283613 cuts=   227345      used= 17720 exact= 978
17    148      715     665291 e1d2
probes=   923347 hits=   919495 cuts=   720636      used= 20896 exact= 966
18    153      777     827118 e1d2
probes=   580753 hits=   575657 cuts=   473781      used= 25044 exact= 965
19    183      838     993999 e1d2
probes=   612465 hits=   608469 cuts=   503238      used= 27971 exact=1141
20    196      967    1465897 e1f2
probes=  1707657 hits=  1701669 cuts=  1416723      used= 31992 exact= 934
21    196     1110    2027235 e1d2
probes=  2032459 hits=  2028798 cuts=  1681015      used= 33455 exact= 873
22    194     1662    4645882 e1d2
probes=  8837520 hits=  8826205 cuts=  7211413      used= 38601 exact=1157
23    213     2332    7890272 e1f2
probes= 10898546 hits= 10890794 cuts=  8996580      used= 42187 exact=1186
24    823     3650   14472865 e1f2
probes= 20677543 hits= 20668782 cuts= 16797405      used= 45042 exact=1367

As you can see, the number of used hash entries in your case is suspiciously small in comparison. In fact, it is suspiciously close to 4096. Are you sure you take more than 12 bits from the hash key to derive the index? Could it be that your Zobrist keys consist largely of zeros, because the random does not return enough bits?

[bob]

I have problems with this position too. Seeing as I take 45 MN to search to depth 17, while Crafty reports 180 KN to search to depth 21, I'm doing something pretty wrong.

I'm thinking this is too much to be a result of bad move ordering. If I turn off the evaluation, I get one more ply, but it's still terrible.

Now, looking at your statistics, you have 0.1% of the hash table filled. My stats are as follows:

Code: Select all

Total: 16277216
Filled: 2526061 (15.0%)

Exact: 10538 (0.4%)
Alpha: 935811 (37.0%)
Beta: 1579712 (62.5%)

Perhaps equal positions are getting different hash keys (and that's turning off en-passant, because it shouldn't be considered in this position anyway).

Maybe I should just play random transpositions and check if the keys match?

P.S: yes, that was a great idea. I not only found one, but two bugs in the hash! (I didn't expect that, as I stress-tested it for a whole day when I wrote it the first time...)

1) The hash for a black queen and king was the same;
2) The moving piece was always considered to be a pawn when advancing.

Of course, bug 2 was the one apparent here. My node count falls to 300 KN in depth 21, while my hash cutoff rate is now nearly 50%. I still have 15% of the table filled, though.

Fermin, you definitely have a hidden bug there.

This is one of the reasons I made Crafty available. If I am searching a much smaller tree than you are, then you can figure out why/how by looking at the trace output and/or the source code. Which makes it possible to fix. This ought to be the first step for any author. Compare your trees to a stable program (such as Crafty). Run WAC and have your program stop on the first iteration where it finds the correct move. Crafty can be told to do this on the test command (test wac.epd 1) where the 1 says terminate after one iteration that produces the right answer. Now you can compare depths for each position. Look for the ones where you need much more depth and then figure out why. You are then on your way to developing a stronger engine. Crafty's far from perfect. But it is rock-solid (it has only played a couple of billion games in my testing so far) and reliable. If you can beat it in terms of depth or time, you are doing pretty good already.

[ffao]

Sounds reasonable, but isn't the first iteration criterion a bit too light? A lot of engines get the move by chance on depth 7, for example, but switch moves on depth 8 because they don't really know what's going on...

Also, isn't there sort of a tendency to make the engine stronger on tactical shots, but weaker on overall positional play? I can see some moves two depths earlier than Crafty, for example, but it obviously doesn't translate into better game play.

Nitpick note: Change line 483 in Crafty's search.c to read

depth - 1 - LMR_depth >= LMR_min_depth

Felipe

[bob]

Sounds reasonable, but isn't the first iteration criterion a bit too light? A lot of engines get the move by chance on depth 7, for example, but switch moves on depth 8 because they don't really know what's going on...

Also, isn't there sort of a tendency to make the engine stronger on tactical shots, but weaker on overall positional play? I can see some moves two depths earlier than Crafty, for example, but it obviously doesn't translate into better game play.

Nitpick note: Change line 483 in Crafty's search.c to read

depth - 1 - LMR_depth >= LMR_min_depth

Felipe

I didn't say it was a perfect scheme. You still have to actually look at the program output to see what is going on. But by doing it this way, you have a chance of finding very shallow search positions and those are far easier to test and analyze than something that takes billions of nodes...

For your second question, there are two parts to the game. The search, and the evaluation. I chose WAC because those are all tactical, and pretty easy tactics as well. You at least want a reasonable search before you spend a ton of time on the evaluation, so I suggest starting there. I can't imagine there being many WAC positions where evaluation is that important.

[hgm]

To judge if the engine solved the problem, I look at the score rather than the move. As you can see, micro-Max switches from a drawing move (e2e4) to a winning move (e1d2) already at 13 ply, but the score there is only still about +1 (meaning it does not even see it can force the Pawn to 6th rank). Only at 24 ply (with 96MB hash) does it see it can force a promotion.

Without a +8 score, there really is no solution. Even after a move that immediately draws (like 1. e2e4) it is still possible to force the Pawn to 7th rank in a leave node in almost any deep search. (The fact that you either have to give up the Pawn or stalemate the opponent nicel pushed just beyond the horizon by stalling the final Pawn push.) If it prefers a winning King move over a drawing Pawn move when the score is only +2.2, it is for totally irrelevant reasons that accidentally help n this particular position. (e.g. excluding the opponent King from the center by being there first, or discovering that an aggressive advance of the Pawn will lead to its early deise.)

[Kempelen]

As you can see, the number of used hash entries in your case is suspiciously small in comparison. In fact, it is suspiciously close to 4096. Are you sure you take more than 12 bits from the hash key to derive the index? Could it be that your Zobrist keys consist largely of zeros, because the random does not return enough bits?

Hi HG,
You put me on the track. I investigated why I stored so few entries. I suspected collisions, so I replaced my rand generator but no luck. So I passed a few hours debuging code line by line, and at the end I found what has been one of the most difficult bug I have ever had. The problem was in the initializacion of the structure:

Code: Select all

BITBOARD		hash_piezas[2][6][64];

I am using 0 for empty, 1 for pawn, ..... and 6 for King, so here was the error. Now I have initialiced correctly the structure as follow:

Code: Select all

BITBOARD		hash_piezas[2][7][64];

And magic!!!!!, the search with PVS and no aspiration reach the solution at depth 21 and only 0.65 secs. uouuuu!!

It has been funny that hash_rand for king was storing the 64 bitboards of king moves for each square. Compiler things.....

But The problem has not finished here for me . After seen this fast result I turned on aspiration window, and left the program thinking for 300 secs and it did not find the solution, what is very surprising for me, as I can not imagine what the problem. My AW code looks as follow:

Code: Select all

      beta = eval + VENTANA1;
      alpha = eval - VENTANA1;

     for &#40;profundidad_actual = 1; profundidad_actual < MAX_PROF; profundidad_actual++) &#123;

      int paso_alpha = 1;
      int paso_beta = 1;
      while &#40;TRUE&#41; &#123;
        printf&#40;"pa = %d, pb = %d, alpha = %d, beta = %d\n",paso_alpha,paso_beta,alpha,beta&#41;;
        eval = busqueda_raiz&#40; profundidad_actual, alpha, beta&#41;;
        if &#40;eval<=alpha&#41; &#123;
          paso_alpha++;
          if &#40;paso_alpha == 2&#41; &#123;
            alpha = eval - VENTANA2;
            continue;
          &#125;
          if &#40;paso_alpha == 3&#41; &#123;
            alpha = -INFINITO;
            continue;
          &#125;
        &#125;
        if &#40;eval>=beta&#41; &#123;
          paso_beta ++;
          if &#40;paso_beta == 2&#41; &#123;
            beta = eval + VENTANA2;
            continue;
          &#125;
          if &#40;paso_beta == 3&#41; &#123;
            beta = INFINITO;
            continue;
          &#125;
        &#125;
        break;
      &#125;

.....
.....
.....
      beta = eval + VENTANA1;
      alpha = eval - VENTANA1;
&#125;

I dont see why with AW the search does not find the solution. Does anybody intuit was could be causing the problem? Could TT be incompatible with AW in this case?.

Thanks,
Fermin

[Kempelen]

sorry, I can not edit the msg, I misstyped the source, the first two lineas of code are these:

alpha = -INFINITO;
beta = INFINITO;

[pedrox]

Hi Fermin, perhaps you have instability, try to increase the depth only after you're sure that the search is into the window.

Code: Select all

alpha = -INFINITO; 
beta = INFINITO;

     for &#40;profundidad_actual = 1; profundidad_actual < MAX_PROF;) &#123; 

      int paso_alpha = 1; 
      int paso_beta = 1; 
      while &#40;TRUE&#41; &#123; 
        printf&#40;"pa = %d, pb = %d, alpha = %d, beta = %d\n",paso_alpha,paso_beta,alpha,beta&#41;; 
        eval = busqueda_raiz&#40; profundidad_actual, alpha, beta&#41;; 
        if &#40;eval<=alpha&#41; &#123; 
          paso_alpha++; 
          if &#40;paso_alpha == 2&#41; &#123; 
            alpha = eval - VENTANA2; 
            continue; 
          &#125; 
          if &#40;paso_alpha == 3&#41; &#123; 
            alpha = -INFINITO; 
            continue; 
          &#125; 
        &#125; 
        if &#40;eval>=beta&#41; &#123; 
          paso_beta ++; 
          if &#40;paso_beta == 2&#41; &#123; 
            beta = eval + VENTANA2; 
            continue; 
          &#125; 
          if &#40;paso_beta == 3&#41; &#123; 
            beta = INFINITO; 
            continue; 
          &#125; 
        &#125; 
        break; 
      &#125; 

..... 
..... 
..... 
      beta = eval + VENTANA1; 
      alpha = eval - VENTANA1;
      profundidad_actual++;
&#125; 

Pedro