Transposition table bug - Points to incorrect alpha-beta?

[hgm]

I'm not sure how you could be sure the bug you just spotted is not part of the problem, unless you have carefully looked at this "unexpected bug" to be certain it is not.

I would first figure out the exact reason of the aberrant behavior that I observed. That would automatically reveal whether the detected bug is part of the problem. Especially if it is part of the problem, fixing it is very dangerous, because it might make the problem go away in the given position, while the other part of it remains to haunt you later, in some other position.

[bob]

I'm not sure how you could be sure the bug you just spotted is not part of the problem, unless you have carefully looked at this "unexpected bug" to be certain it is not.

I would first figure out the exact reason of the aberrant behavior that I observed. That would automatically reveal whether the detected bug is part of the problem. Especially if it is part of the problem, fixing it is very dangerous, because it might make the problem go away in the given position, while the other part of it remains to haunt you later, in some other position.

Or this bug might interact with THE bug in unknown ways. Which means you study this bug carefully to make sure that doesn't happen, and at that point you have probably solved it but not made the necessary changes to eliminate it.

I am reminded of a plane crash investigation I just watched on TV. Landing gear light would not lock on on an older DC-8 (crash many years ago). The pilot became so focused on finding that, that he ignored other potential problems including a "fuel low" warning. Ended up crashing and killing all on board, still trying to decide whether the gear not locked down indication was a faulty gear problem or a faulty sensor problem.

[rob]

Can you tell me more about how "ply" is calculated? I understand that with some types of search extensions, e.g., check extension, the depth to search might be increased by one or two additional moves if check is detected. Is ply set to a particular value at the root, where the root is the start of the tree? And is ply zero at the leaves of the tree?

Also, the comment about "Update of alpha and beta bound is NOT valid in selective search" is a comment Tony Marsland includes in Figure 7 of his paper.

That paper is online here

Rob

[hgm]

'ply' (or 'level') is zero (or one, whatever you like) in the root, and in each daughter node it is one higher than in its parent. In the leaves it can be anything, depending on what iteration you are in, and how many extensions and reductions there are along the branchthat leads to the leave.

[bob]

Can you tell me more about how "ply" is calculated? I understand that with some types of search extensions, e.g., check extension, the depth to search might be increased by one or two additional moves if check is detected. Is ply set to a particular value at the root, where the root is the start of the tree? And is ply zero at the leaves of the tree?

Also, the comment about "Update of alpha and beta bound is NOT valid in selective search" is a comment Tony Marsland includes in Figure 7 of his paper.

That paper is online here

Rob

For every program I have looked at, mine included, "ply" is depth from the root. The search starts at a root position, known as ply=1. You make one of the legal moves there, taking you to a position at ply=2. Etc. Each time you make a move and change sides, ply gets incremented by 1. Extensions or reductions do not change it at all, only making moves and advancing deeper into the tree does so.

[bob]

'ply' (or 'level') is zero (or one, whatever you like) in the root, and in each daughter node it is one higher than in its parent. In the leaves it can be anything, depending on what iteration you are in, and how many extensions and reductions there are along the branchthat leads to the leave.

Maybe we don't count plies exactly the same, not that it matters since your description will also work. But our depths will differ by one. I call the root position ply=1, and any move I make from that position takes me to ply=2, etc. Ply=1 = the position that follows from my opponent's last real OTB move.

On second thought maybe you are counting the moves rather than positions? Where any move made from the root position is ply=1? I've always numbered positions, not moves...

[hgm]

Well, I have several engines, and they don't all do it the same way. Some do just ply++ at the top of Search(), and when I have no separate SearchRoot(), it means ply=1 in the root. But in other engines I put path[ply++]=move near MakeMove, and then the root has ply=0. Like you say, it does not matter much. I never use it for anything other than debug printouts, and to exit with an emergency stack dump when it exceeds MAXPLY.

[Sven]

Well, I have several engines, and they don't all do it the same way. Some do just ply++ at the top of Search(), and when I have no separate SearchRoot(), it means ply=1 in the root. But in other engines I put path[ply++]=move near MakeMove, and then the root has ply=0. Like you say, it does not matter much. I never use it for anything other than debug printouts, and to exit with an emergency stack dump when it exceeds MAXPLY.

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

[bob]

Well, I have several engines, and they don't all do it the same way. Some do just ply++ at the top of Search(), and when I have no separate SearchRoot(), it means ply=1 in the root. But in other engines I put path[ply++]=move near MakeMove, and then the root has ply=0. Like you say, it does not matter much. I never use it for anything other than debug printouts, and to exit with an emergency stack dump when it exceeds MAXPLY.

The only thing I dislike about the inconsistency is that it CAN cause great confusion. I believe Heinz counts like you do. And even worse, for his old program, depth=0 was the final full-width ply (called the frontier). For me, depth=1 is the final full-width ply. That does make a difference when one is playing with futility pruning and such. In fact, this led me to discover that doing futility pruning in last 4 or 5 plies worked well today when it did not back in the middle 90's due to different search depths reached. I one day noticed I was doing that wrong and when I fixed it, I dropped about 10-15 Elo. Studying it carefully and a lot of testing led me to discover that the "bug" was actually a "feature". All caused by a different way of counting plies.

[hgm]

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).