Alpha-beta in simple end-games

[hgm]

Funny observation:

I was wondering why a certain engine could not find the win in Suicide Chess for the following position:

[d]8/8/8/4k3/8/8/8/R7 w

So I reprogrammed micro-Max to consider being stalemated as a win and make capture mandatory. When I then search the position above I get:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        189 a1b1
 3    444        0        533 a1b1
 4    444        1       2023 a1b1
 5    444        1       2999 a1b1
 6    444        1       5594 a1b1
 7    444        2       8738 a1b1
 8    444        3      14070 a1b1
 9    444        3      18461 a1b1
10    447        7      34337 a1a3
11    447        9      43772 a1a3
12    448       12      60731 a1a3
13    447       16      78285 a1a3
14    447       24     119637 a1a3
15    448       41     206322 a1a3
16    448       49     240797 a1a3
17    452       79     385022 a1a3
18    453      101     497728 a1a3
19    886      122     595590 a1a3
20    883      171     810926 a1a3
21    885      210     990987 a1a3
22    885      239    1135530 a1a3
23   7977      346    1662536 a1a3
24   7984      518    2461896 a1a3
25   7984      821    3878180 a1a3

So far nothing unusual. It needs 3.46 sec to find the first 'mating score'. But now I retry the same thing with alpha-beta pruning switched off, i.e. using plain minimax:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        483 a1b1
 3    444        1       2323 a1b1
 4    444        2       7782 a1b1
 5    444        5      15195 a1b1
 6    444        7      26118 a1b1
 7    446       12      40298 a1a3
 8    446       17      56358 a1a3
 9    447       22      74622 a1a3
10    448       27      92542 a1a3
11    448       35     110892 a1a3
12    449       42     129605 a1a3
13    449       48     148731 a1a3
14    449       55     168394 a1a3
15    450       61     188416 a1a3
16    451       69     208553 a1a3
17    453       76     229350 a1a3
18    453       84     250515 a1a3
19   7981       91     272045 a1a3
20   7982      100     293931 a1a3
21   7982      108     316182 a1a3
22   7982      116     338798 a1a3
23   7982      125     361779 a1a3
24   7982      132     385125 a1a3
25   7982      142     408836 a1a3
26   7982      151     432912 a1a3
27   7982      161     457353 a1a3
28   7982      168     482159 a1a3

Now the first mating score is already found after 0.91 sec. That is 4 times faster than with alpha-beta! To search to 28 ply takes only 482k nodes now. With alpha-beta it took 3.8M nodes to reach 25 ply.

If the entire game tree fits within the hash, apha-beta can be very counter-productive!

[Gerd Isenberg]

Funny observation:

If the entire game tree fits within the hash, apha-beta can be very counter-productive!

Impressive, reminds me on fine70! With TT switched off alpha-beta is the winner again (unless you have a bug), but will take too long to solve.

[hgm]

Now what I wonder is if there would be an algorithm that gives you 'the best of both worlds'. I guess the given position could even be solved more efficiently than in the minimax case above, by cranking up the draft of mate scores: if a position after N-ply search is found to have a lower-bound of mate-in-N-ply, it has this lower bound for searches of any depth, and can be stored in the hash with infinite draft.

In minimax, where every score is exact, this gives quite an additional speedup:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        480 a1b1
 3    444        0       2368 a1b1
 4    444        1       8049 a1b1
 5    444        3      14985 a1b1
 6    444        5      23940 a1b1
 7    445       10      34879 a1a3
 8    446       14      46382 a1a3
 9    446       18      58273 a1a3
10    447       22      68650 a1a3
11    448       24      77564 a1a3
12    448       27      86163 a1a3
13    449       30      94273 a1a3
14    450       34     102220 a1a3
15    452       36     109671 a1a3
16   7982       40     117136 a1c1
17   7982       42     123911 a1c1
18   7982       44     130511 a1c1
19   7982       46     135999 a1c1
20   7982       48     141456 a1c1
21   7982       50     145943 a1c1
22   7982       52     150078 a1c1
23   7982       54     153637 a1c1
24   7982       55     157073 a1c1
25   7982       56     159471 a1c1
26   7982       57     161680 a1c1
27   7982       58     163334 a1c1
28   7982       58     164869 a1c1
29   7982       59     166025 a1c1
30   7982       60     167096 a1c1
31   7982       60     167678 a1c1
32   7982       60     168176 a1c1
33   7982       60     168703 a1c1
34   7982       60     168708 a1c1
35   7982       60     168709 a1c1
36   7982       61     168710 a1c1
37   7982       61     168711 a1c1
38   7982       61     168712 a1c1

After 34 ply every position in the tree is to infinite depth in the hash, and each iteration takes only a sigle node, namely the root (hash cutoffs are not counted as nodes in uMax, only looping through all moves is).

I guess the trick would be to fill up the hash somehow with exact scores of infinite depth. With alpha-beta most of the hash entries are filled with bounds, but at some search depth the bounds become valid to infinite depth. These bounds can then only be adjusted in the direction of shorter mates. At some point a bound is not satisfactory, you search, and you get a better bound. Or the bound type flips.

I guess alpha-beta is so inefficient in this cases compared to minima because the bound typeflips all the time, requiring a node to be searched time after time. With an mtd(f)-type table, recording both upper and lower bound, you should be able to approach the minimax performance.

Storing two bounds in general is expensive, but in the case of mate scores of infinite depth there might be a (space-wise) free kludge: you can use the depth field by reserving a few depth codes (all encoding infinite draft) to encode the difference betweenupper and lower bound.

[bob]

Funny observation:

I was wondering why a certain engine could not find the win in Suicide Chess for the following position:

[d]8/8/8/4k3/8/8/8/R7 w

So I reprogrammed micro-Max to consider being stalemated as a win and make capture mandatory. When I then search the position above I get:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        189 a1b1
 3    444        0        533 a1b1
 4    444        1       2023 a1b1
 5    444        1       2999 a1b1
 6    444        1       5594 a1b1
 7    444        2       8738 a1b1
 8    444        3      14070 a1b1
 9    444        3      18461 a1b1
10    447        7      34337 a1a3
11    447        9      43772 a1a3
12    448       12      60731 a1a3
13    447       16      78285 a1a3
14    447       24     119637 a1a3
15    448       41     206322 a1a3
16    448       49     240797 a1a3
17    452       79     385022 a1a3
18    453      101     497728 a1a3
19    886      122     595590 a1a3
20    883      171     810926 a1a3
21    885      210     990987 a1a3
22    885      239    1135530 a1a3
23   7977      346    1662536 a1a3
24   7984      518    2461896 a1a3
25   7984      821    3878180 a1a3

So far nothing unusual. It needs 3.46 sec to find the first 'mating score'. But now I retry the same thing with alpha-beta pruning switched off, i.e. using plain minimax:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        483 a1b1
 3    444        1       2323 a1b1
 4    444        2       7782 a1b1
 5    444        5      15195 a1b1
 6    444        7      26118 a1b1
 7    446       12      40298 a1a3
 8    446       17      56358 a1a3
 9    447       22      74622 a1a3
10    448       27      92542 a1a3
11    448       35     110892 a1a3
12    449       42     129605 a1a3
13    449       48     148731 a1a3
14    449       55     168394 a1a3
15    450       61     188416 a1a3
16    451       69     208553 a1a3
17    453       76     229350 a1a3
18    453       84     250515 a1a3
19   7981       91     272045 a1a3
20   7982      100     293931 a1a3
21   7982      108     316182 a1a3
22   7982      116     338798 a1a3
23   7982      125     361779 a1a3
24   7982      132     385125 a1a3
25   7982      142     408836 a1a3
26   7982      151     432912 a1a3
27   7982      161     457353 a1a3
28   7982      168     482159 a1a3

Now the first mating score is already found after 0.91 sec. That is 4 times faster than with alpha-beta! To search to 28 ply takes only 482k nodes now. With alpha-beta it took 3.8M nodes to reach 25 ply.

If the entire game tree fits within the hash, apha-beta can be very counter-productive!

My first thought is a bug. There is no way that minimax can find the correct answer several plies earlier than alpha/beta. Alpha/Beta provably searches the same path as minimax. Whether this is a hash problem, or some sort of pruning problem I couldn't guess. But this is not a valid result, ever, unless there is some sort of bug present.

[hgm]

I am pretty sure that it is a true result.

The provability of your claim that alpha-beta searches the same tree as minimax is doubtfull, in the presence of hashing. The key is grafting:

A search can see over-the-horizon mates through hash hits on deeper entries. There is no guarantee that alpha-beta will visit the positions that could produce useful grafts before it probes them, or even at all. Minimax with iterative deepenng, OTOH, will always search every branch to only one ply less deep in the previous iteration than alpha-beta would search it in the current iteration. (If alpha-beta would search it at all, and search it in time to produce the hit.) But even one ply less deep is often deep enough to produce useful grafts. Especially since in minimax all scores are exact, and depth is the only criterion that could spoil a hash cutoff. So effectively, minimax + IID + hashing will search a tree that is very different (and much larger) than alpha-beta.

[adams161]

Pulsar has since solved this and solves it in what to me appears to be the most effecient manor. the issus was i didnt think i needed a king endgame table in suicide/giveaway, as the king could not be checkmated, there was no check, and you can capture the king like any other piece.

thats apparently not true. when people promote to a king at the end , the best way to force it to be captured is to drive it to the side of the board. I am not using very small vallues that only turn on in endgame to encourage the king to be in teh center, and will have to see how this works in other positions.

Mike

[wgarvin]

Storing two bounds in general is expensive, but in the case of mate scores of infinite depth there might be a (space-wise) free kludge: you can use the depth field by reserving a few depth codes (all encoding infinite draft) to encode the difference betweenupper and lower bound.

I've often wondered why most engines only store one bound. A score needs something like 14 to 16 bits. Some engines already waste more bits than this in every hash entry (storing redundant bits of the zobrist key, for example). Also, if you have slots for both upper and lower bound, then you don't need the 2 bits to describe the bound type.

[bob]

I am pretty sure that it is a true result.

The provability of your claim that alpha-beta searches the same tree as minimax is doubtfull, in the presence of hashing. The key is grafting:

A search can see over-the-horizon mates through hash hits on deeper entries. There is no guarantee that alpha-beta will visit the positions that could produce useful grafts before it probes them, or even at all. Minimax with iterative deepenng, OTOH, will always search every branch to only one ply less deep in the previous iteration than alpha-beta would search it in the current iteration. (If alpha-beta would search it at all, and search it in time to produce the hit.) But even one ply less deep is often deep enough to produce useful grafts. Especially since in minimax all scores are exact, and depth is the only criterion that could spoil a hash cutoff. So effectively, minimax + IID + hashing will search a tree that is very different (and much larger) than alpha-beta.

Grafting is a problem, as I had previously mentioned. But if minimax is faster than alpha/beta over several positions, something has to be wrong. Minimax and alpha/beta should produce the same result for the same depth, in almost all cases. If you disable hashing, does this still happen?

[hgm]

As you can see below, without hashing minimax and alpha-beta produce the same scores. Of course it will take several times the life-time of the universe to find a win-in-18 without hashing, using minimax. So only comparison of the early itertions is possible.

Alpha-beta:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        191 a1b1
 3    444        1       1449 a1b1
 4    444        1       5401 a1b1
 5    445        5      32853 a1a3
 6    444       16     109896 a1a3
 7    446      103     678676 a1a3
 8    445      343    2332315 a1a3
 9    446     1235    8403514 a1a3
10    445     6409   43778424 a1a3

Minimax:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         49 a1b1
 2    444        0        623 a1b1
 3    444        2       7541 a1b1
 4    444       13      64253 a1b1
 5    445      126     657011 a1a3
 6    444     1119    5484467 a1a3
 7    446    10164   51043241 a1a3

[hgm]

I've often wondered why most engines only store one bound. A score needs something like 14 to 16 bits. Some engines already waste more bits than this in every hash entry (storing redundant bits of the zobrist key, for example). Also, if you have slots for both upper and lower bound, then you don't need the 2 bits to describe the bound type.

In general you would also need to store a depth for each bound.

My hash entries are only 9 byte, so I haven't too many bits to spare. But for the mate scores, I could fit it in the existing schema as follows:

I use 2 bits for bound type, which means one bound-type code is unused. This code could now be taken to indicate that the depth is infinite, the score field contains a lower bound, and the upper bound can be obtained by adding the depth field to the lower bound. Even with a depth field of ony 6 bit, this would allow a range of 64 moves between the upper and lower bound. As we are unlikely to uncover mates more distant than 64 moves in the first place, this rage seems large enough to encode all 'absolute scores'.