Alpha-beta in simple end-games

[adams161]

One thing i was trying to point out yesterday in email, ( and this is based on my knowledge of how little non material evaluate information there is in teh pulsar suicide engine) was there was in the postion you ran into ( the one posted) nothing to score except the end result, i.e the only moves it would score yesterday was this move results in a loss. otherewise it had 0 endgame knoweledge that it was scoring. so with 15 rook moves and 8 king moves at max per turn, searching deep would blow up, as the only lines alpha beta can prune are those that result in an early mate. If you put the same position into a regular chess program, it will typically have some endgame code to encourage the program to force it to the side. When i added that code, active in endgames, this became trivial. Pulsar no longer even needs to search much beyond depth 2 or 3. It knows the optimal move in a fraction of a second, and only needs depth 3 because that is how deep it needs to go to find the last score or the mated result.


ps in my earlier post i said you want to force the king to the side to capture the king, not correct. in suicide you want to be captured, but forcing the king to the side means that once its in a corner it has to step back to the center and you can move along side it and be captured.

Mike

[Jan Brouwer]

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.

My program stores two bounds.
Every time I try to reduce that to one, the search trees get larger (if I remember correctly by something like 10% or so) and I have often wondered if this indicates a bug somewhere.
Anyone else using two bounds (in a non-MDTf program)?

[hgm]

I tried to get the best of both world now. This works pretty well. With alpha-beta the first mate score is now seen after 1.30 sec, only 50% slower than with pure minimax and about 2 times faster than normal alpha-beta with hashing.

The trick is to relabel in IID (or ID) the depth of an iteration to infinity (88 here) as soon as it reveals a mate bound that could not be improved by deeper search. This aborts the deepening, and causes the hash entry to be stored with infinite depth. In addition, such entries will be stored with dual bounds, and on probing, the applicable bound will be tested to decide on a hash cutoff.

Code: Select all

 0    444        0          3 a1b1
 1    444        0         46 a1b1
 2    444        0        141 a1b1
 3    444        0        636 a1b1
 4    444        0       1294 a1b1
 5    445        0       3448 a1a3
 6    444        1       5286 a1a3
 7    446        2       9429 a1a3
 8    446        2      12415 a1a3
 9    446        3      16399 a1a3
10    446        5      20976 a1a3
11    448        8      35364 a1a3
12    448        9      43880 a1a3
13    448       12      59306 a1a3
14    448       18      88665 a1a3
15    449       23     119032 a1a3
16    449       38     177652 a1a3
17    450       50     242303 a1a3
18    450       62     307330 a1a3
19    450       71     351147 a1a3
20    453       98     487698 a1a3
21   7982      130     643153 a1c1
22   7982      135     667038 a1c1
23   7982      152     745253 a1c1
24   7982      165     806212 a1c1
25   7982      186     906703 a1c1
26   7982      213    1039177 a1c1
27   7982      236    1143929 a1c1
28   7982      255    1232496 a1c1
29   7982      268    1292958 a1c1
30   7982      281    1362301 a1c1
31   7982      289    1397112 a1c1
32   7982      293    1414955 a1c1
33   7982      310    1499156 a1c1
88   7982      315    1524036 a1c1

Note that the 7982 score corresponds to 'mate' in 17. (A stalemate, actually, as this is Suicide Chess, which is won by being stalemated. having no moves ends the game with a score of 7999.) A search of 34 ply is enough to see this, so in the root iteration 34 is relabeled as 88=INF.

For comparison, standard alpha-beta (not increasing the depth of iterations to infinity, and thus also never storing hash entries with dal bounds) produces this:

Code: Select all

 0    444        0          3 a1b1
 1    444        0         46 a1b1
 2    444        0        141 a1b1
 3    444        0        643 a1b1
 4    444        1       1327 a1b1
 5    445        1       3594 a1a3
 6    444        1       5700 a1a3
 7    446        2      10366 a1a3
 8    446        3      13957 a1a3
 9    446        4      19123 a1a3
10    446        6      25171 a1a3
11    448        9      42280 a1a3
12    448       11      54062 a1a3
13    448       15      72672 a1a3
14    448       23     119839 a1a3
15    449       30     158265 a1a3
16    448       44     227086 a1a3
17    450       53     280981 a1a3
18    449       73     380395 a1a3
19    450       84     438747 a1a3
20    450      103     532808 a1a3
21    453      148     758054 a1a3
22    455      187     956826 a1a3
23   7982      286    1472671 a1c1
24   7982      319    1645102 a1c1
25   7982      360    1865972 a1c1
26   7982      428    2224429 a1c1
27   7982      461    2398701 a1c1
28   7982      509    2653651 a1c1
29   7982      559    2922978 a1c1
30   7982      610    3216278 a1c1
31   7982      659    3482696 a1c1

[adams161]

hi,

I was giving this some more thought about how a search with two possible scores would work. One score is a mate score. I guess there can be some variance as mate at different depths is found. the other score, and this would be the bulk of the tree, is a 0 score.

now if move 1 at the root returns 0 and it calls search on move 2 at the root, ply 2 has a beta of 0 and the way the search looks like its going to unravel, a good chance it will quickly get a zero score and return beta.

So what seems to happen is every node hashes a score, mostly 0, or a fail high beta cuttoff and the hash table rapidly fills up. In fact you have a racing condition.

Any way short of something really complicated to deal with this? Does this sort of thing happen in regular search a lot? Say a middle game search.

My condition to replace the hash in the hash table is simple. i call the true 64 bit number in the hash table hnumber.

so i do if(curenthash != hnumber || current hash is hnumber but depth is < on hash than current hash)
overwrite.


so if i'm hashing a different positon i always replace because i reason i dont have a way to tell what obsolete hash'es are versus what i need ( it could be from older search ) or if I realize i'm hashing the same postion once again i replace if i have more depth currently.

Also is this just unavoidable if evaluate is looking at a large number of moves say 8 for one side and 15 for the other, with most of them returning 0, does it just choke as it gets to deeper depths?

Mike

[hgm]

so if i'm hashing a different positon i always replace because i reason i dont have a way to tell what obsolete hash'es are versus what i need ( it could be from older search ) or if I realize i'm hashing the same postion once again i replace if i have more depth currently.

This is a poor way of doing it. In an alpha-beta or PVS search the hash table will be almost exclusively filled with bounds. In end-games there are usually many short paths (because of poor defense) to positions that eventually occur on the PV much later (with good defense). So they (and the sub-trees sprouting fom them) are searched with a much larger depth than they are eventually needed. But when they are first searched, they typically get very unrealistic bounds, because the very reason you search them through that path is that you have not found the good defense yet, and thus are way off with the score.

Then, in a later iteration, the root score has shifted, and you don't visit most of these positions again through the short path, because the early moves are now much easier to refute, (because of the shifted window), and the search has learned how. But for a long time, deeper in the PV, you will hit upon hash entries with useless bounds, but a depth far graeter than you need now, (and which you will get when you search them). This is very detrimental to performance.

Essentially the scheme you use poisons the hash tabe with deep entries with useless bounds. Because of the window shifting around, "more recent" is much more important than "more depth"". You should ignore the depth in replacement, and either do "always replace" (for equal key) or go for the best bound. Note that when on storing you find the same position as you have just searched with a higher depth, the reason that you searched it again must be that the stored bound was no good, as the depth apparently was. Despite its good depth, it was a useless hash entry, and you had to search the position anyway.

[MattieShoes]

Note that the 7982 score corresponds to 'mate' in 17. (A stalemate, actually, as this is Suicide Chess, which is won by being stalemated. having no moves ends the game with a score of 7999.) A search of 34 ply is enough to see this, so in the root iteration 34 is relabeled as 88=INF.

I believe in suicide chess, stalemate is won by the side with less pieces. In giveaway, the stalemated side wins. Yes?

[hgm]

Oh, I am not aware of those fine details. Perhaps I should still correct this in WinBoard, then, which now adjudicates every stalemate as a win for the stm. Anyway, in the given position this does not matter, as the stalemate occurs through having zero pieces, which is always the smallest as it can happen only to one side.

[MattieShoes]

Hmm, from the old winboard engine interface file

Code: Select all

suicide     Win by losing all pieces including king, or by having 
            fewer pieces when one player has no legal moves (FICS)

giveaway 	Win by losing all pieces including king, or by having 
            no legal moves (ICC)

losers      Win by losing all pieces or getting mated (ICC) 

[hgm]

Yes, but WinBoard never enforced those rules. It relied enirely on the iCS or engine to determine game end. so you could not play them with "verfy claims" switched on, or the engine result claims would all be flagged as false claims, since they would not be checkmates.

The aim was to make it possible to play these variants with claim detection. But the way I fixed it, this is apparently still not possible for Suicide. (Like it is not possible for 3check either, as WB doesn't count checks yet.)

[wgarvin]

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.

Ouch.. Yeah, I forgot about that part. Thanks.