Identical positions in tree

[evert823]

Very nice, the more I hit my TT the more nodes I get, which is the opposite of why one implemets a TT. And sometimes, a position which was stored with forced mate, later gives a weaker value upon checking. All elementary steps seem to go fine upon inspection (store a position, compare a position, check depth, alpha beta etc).
3fold repetition must be spoiling it somewhere. A node that is draw because of this, was forced mate earlier.
Maybe that's why I got this remark:

Next question might be about the "Graph History Interaction Problem"....

https://www.chessprogramming.org/Graph_ ... nteraction

--
Srdja

[shawn]

Testing whether there are bugs in your TT implementation by playing games is about the worst you can do.

Why? Would a bug in TT cutoffs not translate in a significant decrease in strength? Testing this via SPRT would take you 10 minutes anyway.

[shawn]

Very nice, the more I hit my TT the more nodes I get, which is the opposite of why one implemets a TT. And sometimes, a position which was stored with forced mate, later gives a weaker value upon checking. All elementary steps seem to go fine upon inspection (store a position, compare a position, check depth, alpha beta etc).
3fold repetition must be spoiling it somewhere. A node that is draw because of this, was forced mate earlier.

How are you storing/using your TT entries? Providing some actual code could be helpful in debugging this issue.

[evert823]

And sometimes, a position which was stored with forced mate, later gives a weaker value upon checking.

Ah, but that was because the stored depth was high enough for resolving a forced mate, and the current depth was not. That makes sense, but then it will cause the engine to find forced mates at a depth, at which it would not be able to see it without the TT. I don't know if that's good or bad...

[evert823]

How are you storing/using your TT entries? Providing some actual code could be helpful in debugging this issue.

The part I am still doubting is this:

Code: Select all

                    if (TransTable[p].used_alpha < TransTable[p].calculated_value &
                        current_alpha < TransTable[p].calculated_value &
                        TransTable[p].used_beta > TransTable[p].calculated_value &
                        current_beta > TransTable[p].calculated_value)
                    {
                        //if position also equal then accept the stored score
                    }

[hgm]

Testing whether there are bugs in your TT implementation by playing games is about the worst you can do.

Why? Would a bug in TT cutoffs not translate in a significant decrease in strength? Testing this via SPRT would take you 10 minutes anyway.

And then what? You already know thereIf there is virtually no decrease in the number of nodes searched. And if it confirms what you already knew it still doesn't give you a clue what is wrong. And if it confirms 100 Elo improvement, you would not know whether it should have been 150 Elo if everything worked correctly, and would have missed the opportunity for a 50 Elo improvement due to a false sense of security.

[hgm]

And sometimes, a position which was stored with forced mate, later gives a weaker value upon checking.

Ah, but that was because the stored depth was high enough for resolving a forced mate, and the current depth was not. That makes sense, but then it will cause the engine to find forced mates at a depth, at which it would not be able to see it without the TT. I don't know if that's good or bad...

Indeed, this is known as 'grafting'. It is especially common in simple end-games, like KRK, where Fairy-Max sometimes reports mates in more than 80 moves, at 10 ply. This is then quickly improved upon when the search deepens.

It happens when the defending side tries moves that poorly defends first (e.g. running voluntarily into the corner with the bare King). These then get checkmated before the horizon even at low depth, and will get stored in the TT as such. When after that moves are tried that defend better, and would have pushed the mate beyond the horizon, the stored position might still be within the horizon.

You could prevent this by only allowing exact-depth hits. Which might be useful for testing, but otherwise just makes the engine weaker.

[hgm]

How are you storing/using your TT entries? Providing some actual code could be helpful in debugging this issue.

The part I am still doubting is this:

Code: Select all

                    if (TransTable[p].used_alpha < TransTable[p].calculated_value &
                        current_alpha < TransTable[p].calculated_value &
                        TransTable[p].used_beta > TransTable[p].calculated_value &
                        current_beta > TransTable[p].calculated_value)
                    {
                        //if position also equal then accept the stored score
                    }

This is no good. The used and current alpha and beta must ly on the same side of the score. But this code now also requires on which side they must ly. So you only accept exact scores now (i.e. between alpha and beta). While it would be perfectly OK to have the score lower than both used and current alpha. Only very few scores areexact in alpha-beta search, which explains your low hit rate. The whole idea is that in most nodes you get a beta cutoff (preferably with the first move you try) with a score above beta, and then a score below alpha in the parent 'all node'.

In an ideal alpha-beta tree you have one PV, and only the nodes along it get exact score. All other notes have scores that are upper or lower bounds.

[shawn]

The part I am still doubting is this:

Code: Select all

                    if (TransTable[p].used_alpha < TransTable[p].calculated_value &
                        current_alpha < TransTable[p].calculated_value &
                        TransTable[p].used_beta > TransTable[p].calculated_value &
                        current_beta > TransTable[p].calculated_value)
                    {
                        //if position also equal then accept the stored score
                    }

That doesn't seem quite right. This is how TT cutoffs work, assuming a fail-soft negamax search:

Failing High

First, we need to ask the following question: When a search fails high, what information can we extract from it?

Well, in order to fail high, our search must find a move that is good enough to beat beta. Since we end the search as soon as such a move is found, it is easy to see that the rest of the possible legal moves that would've been searched later were not being searched at all. That is, when a search fails high, only a portion of the moves are explored.

This results in a degree of uncertainty to the "true value" of our node -- there is no way to know if any of our discarded moves are better than the move that caused the fail high. Therefore, the "true value" of our node is likely higher or equal to the best value we have gotten. We call our best value a lower bound.

To illustrate this, here is an example:
our alpha is -inf, our beta is 30, and below are the best values of each of our nodes, had we done search on all of them:

Code: Select all

[0, 20, 40, 30, 100]

The true value of this node is 100, the best possible outcome we can achieve. But take a look on how alpha/beta pruning resolves it.

We search the first two moves, and they do not trigger a fail high. Therefore for each of them, we raise alpha as necessary.
Now on the third move, we get 40, which exceeds beta. Therefore, we return best value of 40. Note that had we kept searching, we'll find a move that is worth 100. But since we failed high on 40, we stop early without searching the later moves. So 40 is not the truth score of the position, but rather a lower bound on what that true score actually is.


Failing Low

Now we explore the opposite question: When a search fails low, then what information can we extract from that?

(Failing low, in this case, means that none of the moves we searched beat the original alpha. Which means our best value is smaller than alpha.)

Since every move must not beat alpha, and since you negate the score from child in Negamax. We infer that all of the child nodes beat their beta (-alpha from the parent's perspective). This means that our children failed high, and therefore returns a lowerbound. After the negation, those lowerbounds become upperbounds. And therefore every score we have received are upperbounds. Now since we still only select a "best" score in negamax. The best score we have found will also be an upperbound. That is, the true score of a fail-low node is lower than or equal to the best score we have found.


Exact Nodes

What if we neither failed high nor failed low. In this case the evaluation says within our window, meaning everything down to qsearch would not be affected by fail high upperbounds. Thus our score is exactly the true score we would get.


Putting Everything Together

To summarize, we discussed the following results:

• When failing high, the score we have is a lowerbound of the true score

• When failing low, the score we have is an upperbound of the true score

• When neither happens, the score we have is exactly the true score

Now suppose we searched a node in our search tree. The results were a lowerbound score of value V.
Suppose then we encounter the same position some time later, with possibly a different beta. What happens when beta <= V?

Well, we know from the discussion above that the true score S >= V. So beta <= V <= S. Our true score will always fail high.

This means that if we were to continue our search, it would certainly fail high. So we skip the search altogether and return V as our score.

In code, this means something like this:

Code: Select all

if (TransTable[p].score_type == LOWERBOUND &&
    TransTable[p].score >= beta )
    return TransTable[p].score;

By the same logic, if we have an UPPERBOUND node, and our TT score V <= alpha. Then we have our true value S <= V <= alpha. Meaning that we already know that the search will fail low. So we return V as a fail low score.

Code: Select all

if (TransTable[p].score_type == UPPERBOUND &&
    TransTable[p].score <= alpha )
    return TransTable[p].score;

Now if the score is exact, we can just return that score, since it will be the true value anyway

Code: Select all

if (TransTable[p].score_type == EXACT)
    return TransTable[p].score;

But here's a problem: If we have a lower depth entry, but we are on some higher depth, then it is not safe to perform those cutoffs, as the true score found on a higher depth will likely be different and much more accurate. So we add an extra guard.

Code: Select all

if (TransTable[p].entry_depth >= depth)
{
    // Perform above logic
}

The final code would look something like this:

Code: Select all

if (TransTable[p].entry_depth >= depth)
{
    if (TransTable[p].score_type == EXACT)
        return TransTable[p].score;
        
    if (TransTable[p].score_type == UPPERBOUND &&
        TransTable[p].score <= alpha )
        return TransTable[p].score;
        
    if (TransTable[p].score_type == LOWERBOUND &&
        TransTable[p].score >= beta )
        return TransTable[p].score;
}

If you have any further questions, feel free to ask me or in one of those discord servers, where most top engine devs are active in nowadays: https://www.chessprogramming.org/Discord_Channels

[evert823]

Thank you very much everybody!! This helps!! Before TT the mate in 6 from #8 took my engine above 30 minutes, now 6 minutes.

One last(?) question:
At what depth do we decide to not at all use the transposition table?
At very low depth I see two reasons for not doing so:
- the number of positions that we would WANT to store grows exponentially
- doing the evaluation without TT becomes fast enough if not much faster
I am currently doing from depth 5 on but that is also a bit arbitrarily chosen.