Transposition table bug - Points to incorrect alpha-beta?

[hgm]

Others use "ply" for mate scoring as well, of course ...

Oh yes, that kludge. I of course never do. But you have to think about how to interpret your mate scores anyway (e.g. whether you assign +INF to mate or to King capture).

[bob]

But we were not talking about 'depth', but about 'ply'. The chance for confusion with the latter is very small, as it isn't used for anything other than identifying the node where to print debug info. This will not be shared with other programs, and in fact changes all the time in my own programs depending on what I am debugging. And whether MAXPLY is 99 or 100 ply removed from the root doesn't really matter.

With 'depth' it is of course a quite different matter. Many search decisions discussed in the literature depend on it, so uniformity of the meaning is very desirable. Yet, for practical reasons, many of my engines use non-standard encoding for it. In micro-Max, for instance, the last full-width node has d=3. d=2 is QS, and d=1 is an intermediate iteration of the IID, where beta is replaced by +INF (the king-capture score), and the MVV/LVA sort key is used in lieu of move score (so that the QS iteration starts with the MVV/LVA-wise best move, like any iteration starts with the best move of the previous iteration).

In HaChu QS, (the first non-full-width depth) starts at depth=4, because there are still several different levels within QS which prune captures with different eagerness, and I don't like to waste half the encoding space on negative values by making depth a signed int. To avoid confusion (and allow easy change) I #defined a symbol QSDEPTH there, and testing depth for values outside QS is always done by clauses like if(depth == QSDEPTH + 1).

Let's define things carefully so I can show where MY confusion came in.

ply=1 is the root position that we start a search on. Making a move from the ply=1 position takes us to ply=2, making a move from ply=2 position takes us to ply=3, etc. Regardless of the type of move (including a null-move).

depth = remaining plies before calling Quiesce(). In Ken's original post of the negamax algorithm, he did this:

if (depth > 0)
v = -Search(..., ply+1, depth-1)
else
v = -Quiesce(..., ply+1, depth-1)

And most have written their code that way.

But Heinz did this:

if (depth >= 0)
v = -Search(..., ply+1, depth-1)
else
v = -Quiesce(..., ply+1, depth-1)

There are things to quibble about. For example, I don't use depth-1 to call quiesce(), I don't pass it a depth at all in fact. But the biggie is that depth > 0 vs depth >= 0. What that does is (a) cause you to search one ply deeper at depth D than anyone else; and (b) if you do things like futility pruning, something like "if (depth >= 2)" means something different in his program compared to mine. Mine would need to be depth >= 3, for example.

I simply considered it a non-standard implementation from the point that I finally realized what he was doing, and had no further trouble reading his dissertation. But it initially caused some confusion on my part and my tests produced unexpected results.

I don't see a thing wrong with your depth >= 4 or whatever. And once YOU settle in to that thinking, it would work flawlessly. But another person might have to stop and think a bit here and there.

Cray Blitz had a 3-tiered search. first N plies were normal full-width plies. Next M (M=4 typically but could go up to 6) were selective plies that included checks, captures, and a very few "tactical" moves. The remainder was pure q-search (captures, but also including uninterrupted sequences of check/escape-check moves.)

[rob]

What "kludge" is this?

Rob

[Sven]

What "kludge" is this?

I think he means the way of mate scoring that is used by most engine programmers (return -(INF - distanceToRoot)) ...

[Sven]

Others use "ply" for mate scoring as well, of course ...

Oh yes, that kludge. I of course never do. But you have to think about how to interpret your mate scores anyway (e.g. whether you assign +INF to mate or to King capture).

There is one obvious and simple interpretation: King capture occurs one ply beyond the mate since the mated side made an illegal move, so if I ever were in the situation to implement mate detection based on king capture I would assign +(INF+1) to the position where the moving side can capture the king. That would still allow to express DTM as the distance of a mate score to +INF resp. -INF (depending on the side to move).

[rob]

It turns out that using the ply counter method, with ply starting at zero (in my case) and incrementing with each recursive call to negamax(+alphabeta+transposition tables) solves all my problems.

Purely as a matter of accuracy, I also needed to revert two additional incorrect changes I had deliberately introduced into the code while tinkering with it. That was of course a simple matter.

I'm surprised that this method is referred to as a "kludge". I would think that it is not an "ill-assorted collection of parts assembled to fulfill a particular purpose" since it solves my bug rather neatly.

I have two other questions about this that are very straightforward:
- What do you do in your engine when the transposition table is full? Perhaps you dynamically allocate 2x or 1.3x the current number of entries that you have? I caught a problem with transposition tables returning an illegal move (a1 to a9) from the starting chess position, but that was because I had a fixed size transposition table of 400,000 entries which was perfectly fine for depth=6, but flooded the table with depth=7.
- How are you handling multiple evaluators? Usually there is a "simple" evaluator applied at the leaves of the search which calculates material plus some basic positional features (e.g., passed pawn which can outrun enemy king and other pieces nearby) vs. a "complex" evaluator with many, many more features considered. And how does this interact with a simple quiescence capability which tries to capture the last moved piece with the least valuable attacker?

Rob

[bob]

It turns out that using the ply counter method, with ply starting at zero (in my case) and incrementing with each recursive call to negamax(+alphabeta+transposition tables) solves all my problems.

Purely as a matter of accuracy, I also needed to revert two additional incorrect changes I had deliberately introduced into the code while tinkering with it. That was of course a simple matter.

I'm surprised that this method is referred to as a "kludge". I would think that it is not an "ill-assorted collection of parts assembled to fulfill a particular purpose" since it solves my bug rather neatly.

I have two other questions about this that are very straightforward:
- What do you do in your engine when the transposition table is full? Perhaps you dynamically allocate 2x or 1.3x the current number of entries that you have? I caught a problem with transposition tables returning an illegal move (a1 to a9) from the starting chess position, but that was because I had a fixed size transposition table of 400,000 entries which was perfectly fine for depth=6, but flooded the table with depth=7.
- How are you handling multiple evaluators? Usually there is a "simple" evaluator applied at the leaves of the search which calculates material plus some basic positional features (e.g., passed pawn which can outrun enemy king and other pieces nearby) vs. a "complex" evaluator with many, many more features considered. And how does this interact with a simple quiescence capability which tries to capture the last moved piece with the least valuable attacker?

Rob

Simply, I hash to a bucket of 4 entries. To store, I replace the most useless entry (you can look at crafty's source, hash.c, where the comments are very accurate in describing my replacement policy.

I don't have a "simple evaluator". I only have "the" evaluator which does everything.

[rob]

Thank you for your very kind help.

Rob

[op12no2]

Rob, I'm glad you got it working. This has been an interested thread for me as well.

[Gerd Isenberg]

depth = remaining plies before calling Quiesce(). In Ken's original post of the negamax algorithm, he did this:

if (depth > 0)
v = -Search(..., ply+1, depth-1)
else
v = -Quiesce(..., ply+1, depth-1)

And most have written their code that way.

But Heinz did this:

if (depth >= 0)
v = -Search(..., ply+1, depth-1)
else
v = -Quiesce(..., ply+1, depth-1)

I think you are wrong here, see Heinz' "Extended Futility Pruning" paper:
http://people.csail.mit.edu/heinz/dt/node18.html
http://people.csail.mit.edu/heinz/dt/node22.html

The well-known technique of futility pruning at frontier nodes (depth = 1) exploits the peculiarities of ``standing pat'' at horizon nodes (depth = 0). ``Standing pat'' means to compute the static evaluation score of a node in order to test it against the upper search bound for a possible fail-high beta cutoff without further lookahead. Thus, ``standing pat'' implements the null-move assumption during the quiescence search with static node evaluations serving as null-move scores of zero depth. The following two sections describe the theory and practice of futility pruning at frontier nodes in detail because they provide the foundations for our new pruning scheme.

As far as I remember, your problem with Heinz was calling depth=1 nodes frontier nodes ...
http://www.stmintz.com/ccc/index.php?id=387518