Saving moves into the TT

[mvanthoor]

Hi,

Today I was reading in the chess programming wiki, about node types (All-nodes, PV-nodes, Cut-nodes). That got me thinking about the TT again.

The CPW states:

- If a move beats bèta, it is a cut-node. This move is written into the TT. OK.
- If a move beats alpha but not bèta, it is a PV-node; this move is the "best move". This move is written into the TT. OK.
- If a move does not beat alpha, it's an All-node, and you don't have a best move. I can understand that.

I can visualize all of that, but I still have two questions I can't get completely clear after some time of reading around.

=== Question 1 ===

If I run through a move list, how is it possible that NO move beats alpha? It would mean that there is no move to play in this move list; no move to add to the PV. I do not yet understand this completely. Even if all moves in the list are losing the game, one of them has to be the least bad.

How is it possible to NOT have a best move in a move list?

=== Question 2 ===

If a move's evaluation score beats bèta, I save it in the transposition table with the bèta score and bèta flag, and return the bèta score. Function done. (This is clear to me.) If a move beats alpha but not beta, it's a PV-move/best move, and it's saved into the TT with the alpha score and the Exact flag. (This is clear as well.) My engine does both.

From this it follows that if alpha is never raised, we have NO move to put in the hash table, and we should save the alpha score with alpha flag, and no move. (Even though I don't yet understand this situation clearly; see question 1.)

However: in Alpha 2 (and also my current development version), I keep a "best_move" variable, which is set as soon as the evaluation score is increased (eval > best_eval). This is a remnant of Alpha 1's a/b-function.

If the evaluation score beats bèta, this best move is saved in the TT with score bèta and flag bèta. If the evaluation score beats alpha but not bèta, this best_move is saved with score alpha and flag exact. Everything fine so far.

The difference: If the evaluation score does not beat alpha (and thus also doesn't beat bèta), best_move contains the move from the move list from the last time the evaluation score increased. Therefore it is saved with the alpha score, and the alpha flag into the TT, and I never have a "save no move" situation.

"Saving the move that caused the the last increase of the evaluation score, if alpha is never increased" is not mentioned anywhere. CPW states that a node where alpha is not raised is an All-node, and you have no best move there. But I have the move that last increased the evaluation score as best_move.

I suspected that I was saving a useless move to the TT. (So it would be incorrect to save it, but do no harm.)

So I made a tiny change. In the experimental version I don't set "best_move" as soon as the evaluation score increases (this was removed): I only set it when alpha increases. Thus, if alpha increases "best_move" holds the PV move, and it's saved with the alpha score and exact flag. If alpha never increases, best_move stays empty, and at the end of the move loop, the alpha score is saved with the alpha flag, and no move.

Because I was thinking that I was saving a useless move before, I expected the change to have no effect.

However, cute_chess has been running a test between this experimental version (which saves the alpha score with alpha flag, and no move, if alpha never increases) against current dev-version (which saves the alpha score with the alpha flag, and the move that last increased the eval score, if alpha never increases) The current dev-version has been very slowly creeping ahead. Now, after almost 5000 games, it is 114 points ahead of the experimental version (2.3.100 is experimental, 2.2.100 is current development):

"Score of Rustic Alpha 2.3.100 vs Rustic Alpha 2.2.100: 1608 - 1722 - 1306 [0.488] 4636"

I can't believe that this is suddenly going to turn around. I assume the current dev-version which "saves the last move that increased the eval score if alpha never increased" keeps creeping ahead slowly, and at some point, cute_chess will decide that the change to "save no move if alpha is never increased" is losing Elo.

So, it seems best that if alpha never increases, to save the alpha score with alpha flag (as normal), AND the last move that increased the evaluation, instead of saving the alpha score with alpha flag and no move. At least in my engine.

Does this make sense to anyone?

It's the final piece I need to _clearly_ understand before I feel that I can write a page about the transposition table in Rustic's documentation.

[mar]

1. If I run through a move list, how is it possible that NO move beats alpha? It would mean that there is no move to play in this move list; no move to add to the PV. I do not yet understand this completely. Even if all moves in the list are losing the game, one of them has to be the least bad.

How is it possible to NOT have a best move in a move list?

simply because you search within alpha-beta bounds, it's possible that no move can beat alpha
so it can be an all node, it can be a research, ... there should also be a relation to root aspiration window

I suspected that I was saving a useless move to the TT.

...

Does this make sense to anyone?

It's the final piece I need to _clearly_ understand before I feel that I can write a page about the transposition table in Rustic's documentation.

it does make sense to me, I do something else though, when I store a move and don't have one and get a TT hit (=find an entry with same hash signature), I simply keep the move already in the TT (if any)
so it's well possible that with bounds a,b a move did beat alpha at depth x, but when you reenter the node later with bounds c,d no move can beat c at depth y
so it's clearly better to keep that move instead of overwriting it with no move, because if all moves fail low it doesn't matter which one you try first.
and I'd rather try a move that worked before first

I'm sure people like hgm can give you a better/thorough explanation (or even correct me if I wrote some nonsense here)

[mvanthoor]

simply because you search within alpha-beta bounds, it's possible that no move can beat alpha
so it can be all node, it can be pv research after scout. there should also be a relation to root aspiration window

But if in a node, no move can beat alpha, you wouldn't have a PV-move. Then what is the point of searching further down that line if no move is ever a PV-move? So now these two statements from the CPW seem to make sense:

1. The first child of a Cut-node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-node

(It is useless to search beyond a cut-node, because that node is so good for your opponent that every move after it loses for you. You CAN'T search beyound the cut node, because the a/b-function returns bèta immediately. But, you can still end up in the all-nodes beyond the cut node through a different path in the tree.)

2. Children of All-nodes are Cut-nodes

(Because you're in an all-node and thus can't find a PV-move, every other node by the opponent would therefore beat you. You can't reach those nodes through this line, but you can reach them through a different path in the tree.)

If I'm not mistaken.

it does make sense to me, I do something else though, when I store a move and don't have one and get a TT hit (=find an entry with same hash signature), I simply keep the move already in the TT (if any)
so it's well possible that with bounds a,b a move did beat alpha at depth x, but when you reenter the node later with bounds c,d no move can beat c at depth y
so it's clearly better to keep that move instead of overwriting it with no move, because if all moves fail low it doesn't matter which one you try first.
and I'd rather try a move that worked before first

This does make sense to me. If you are about to overwrite a hash entry (with the same zobrist key) and you are overwriting without having a move, you could keep the move that is already in the TT and just see if it's in the move list and try it if you get this entry back from the TT.

This would be somewhat similar to what I'm doing: if I should have had "no move" because alpha never increased (and thus bèta also didn't), I just save the move that increased the evaluation last (= had the highest evaluation). Maybe it didn't beat alpha or bèta now, but it might beat one of them later, if the entry is returned from the TT...

And it seems it does, because the Rustic version that does this, is at least few Elo stronger than the version that doesn't and saves alpha with the alpha flag and no move.

[emadsen]

If I run through a move list, how is it possible that NO move beats alpha?

It means the engine is exploring a nonsensical continuation, a sequence of moves that does not represent best play by both sides.

It occurs at the engine's next move after it hung its queen. The opponent took the queen with a lower valued piece. Looking ahead many moves, the engine finds no continuation that recovers the queen- materially or positionally (e.g. promoting a pawn). It's simply lost material with no compensation. The engine searches all the way down to the horizon. Comes back up to the engine's move immediate after it hung its queen (two ply deeper). Sees the situation is hopeless. That's a fail low (AKA upper bound). No move saves the game. Your engine can store score = alpha in the TT with an indicator that it represents a fail low. I call this ScorePrecision, other engines call it BoundType.

Code: Select all

} while (true); // End of move loop.
    if (legalMoveNumber == 0)
    {
        // Checkmate or Stalemate
        bestScore = Board.CurrentPosition.KingInCheck ? Evaluation.GetMateScore(Depth) : 0;
    }
    if (bestScore <= originalAlpha) UpdateBestMoveCache(Board.CurrentPosition, Depth, Horizon, Move.Null, bestScore, originalAlpha, Beta); // Score fails low.
    return bestScore; // Fail hard.
}

Inside UpdateBestMoveCache for the case of a fail low:

Code: Select all

if (score <= Alpha)
{
    CachedPositionData.SetScorePrecision(ref cachedPosition.Data, ScorePrecision.UpperBound);
    CachedPositionData.SetScore(ref cachedPosition.Data, Alpha);
}

[mar]

But if in a node, no move can beat alpha, you wouldn't have a PV-move. Then what is the point of searching further down that line if no move is ever a PV-move? So now these two statements from the CPW seem to make sense:

1. The first child of a Cut-node, and other candidate cutoff moves (nullmove, killers, captures, checks, ...) is an All-node

(It is useless to search beyond a cut-node, because that node is so good for your opponent that every move after it loses for you. You CAN'T search beyound the cut node, because the a/b-function returns bèta immediately. But, you can still end up in the all-nodes beyond the cut node through a different path in the tree.)

2. Children of All-nodes are Cut-nodes

(Because you're in an all-node and thus can't find a PV-move, every other node by the opponent would therefore beat you. You can't reach those nodes through this line, but you can reach them through a different path in the tree.)

If I'm not mistaken.

well, assuming PVS, most nodes are done with "zero width". you don't have a pv move here, you either fail low or high.
so basically non-pv nodes can be classified further as being all/cut.
it's a bit unclear to me how to classify expected PV nodes that fail low/high though (and yes, this happens due to what I wrote before)

the tricky part is how to classify node types in advance, you can guess but you don't know if it's a true cut/all node until you acually search the node,
I believe bob once wrote that 90% of the cut nodes produce the cutoff on the first move

[mvanthoor]

It means the engine is exploring a nonsensical continuation, a sequence of moves that does not represent best play by both sides.

It occurs at the engine's next move after it hung its queen. The opponent took the queen with a lower valued piece. Looking ahead many moves, the engine finds no continuation that recovers the queen- materially or positionally (e.g. promoting a pawn). It's simply lost material with no compensation. The engine searches all the way down to the horizon. Comes back up to the engine's move immediate after it hung its queen (two ply deeper). Sees the situation is hopeless. That's a fail low (AKA upper bound). No move saves the game.

That actually makes perfect sense to me now. Thanks. I'm bookmarking this as an example.

While I could understand the definition of a killer move ("A quiet, non-capturing move which causes cut-offs in different branches at the same ply"), it only "clicked" when I actually explained it in my docs (and to myself) in chess terms:

https://rustic-chess.org/search/ordering/killers.html

I was unable to come up with a similar chess-like explanation for how the engine can fail to find any move that beats alpha/becomes a PV-move. Thanks.

Your engine can store score = alpha in the TT with an indicator that it represents a fail low. I call this ScorePrecision, other engines call it BoundType.

In my engine, it's called HashFlag.

[mvanthoor]

The SPRT-test has finished.

Score of Rustic Alpha 2.3.100 vs Rustic Alpha 2.2.100: 1911 - 2049 - 1516 [0.487] 5476
... Rustic Alpha 2.3.100 playing White: 1072 - 891 - 776 [0.533] 2739
... Rustic Alpha 2.3.100 playing Black: 839 - 1158 - 740 [0.442] 2737
... White vs Black: 2230 - 1730 - 1516 [0.546] 5476
Elo difference: -8.8 +/- 7.8, LOS: 1.4 %, DrawRatio: 27.7 %
SPRT: llr -2.95 (-100.2%), lbound -2.94, ubound 2.94 - H0 was accepted
Finished match

The experimental version lost the match by a margin of 138 points.

NOT saving the move that last increased the evaluation score alongside the alpha score and alpha flag (and thus saving "no move" because we haven't beaten alpha) decreased the engine strength with +/- 9 Elo. It's just outside the error margin. This change could thus have a negative effect of roughly 1-17 Elo. I'm therefore going to leave saving the move that last increased the eval score (if alpha is not raised) as it is.

Apparently having a move that at least increased the score a bit to order on is slightly better than to have no move at all.

[hgm]

I would not call 138 points 'slightly better'. But it is a strange result.

The point is that scores below alpha are not really scores at all, but upper bounds. So what you get as best_move isn't really the best move at all; it can actually be the worst move, the search not having bothered to figure out how poor it actually is. In a deep search all scores that fail low are typically alpha or just 1 or 2 score quanta below alpha, and there is no systematics in that. So basically you are singling out a random move, to later search that before any of the others. One would expect this to be a waste of time, and that the capture of the most valuable piece is a better bet.

But in the lare majority of cases it would not matter. Because what was an all-node before usually stays an all-node on re-visit, and move ordering doesn't matter in all nodes. This makes it all the more strange that you measure such a large effect.

BTW, micro-Max also doesn't bother to suppress storing a move in the TT for fail lows.

[niel5946]

=== Question 1 ===

If I run through a move list, how is it possible that NO move beats alpha? It would mean that there is no move to play in this move list; no move to add to the PV. I do not yet understand this completely. Even if all moves in the list are losing the game, one of them has to be the least bad.

How is it possible to NOT have a best move in a move list?

Because if all moves are bad, you are very likely to be at an ALL-node. Move ordering isn't important at such nodes because all moves are expected to fail low. Additionally, the only case where saving a best move at an ALL-node would be good, were if the engine were going to change its mind and saw the node was actually a CUT-node, at a higher depth. In that case, it would be very beneficial to have a best move saved.
I can't think of a reason not to save the "best worst" move. I always do this since it doesn't really take any time to update a best_score flag (see this) and it always gives the best move. Even at ALL-nodes.

CPW states that a node where alpha is not raised is an All-node, and you have no best move there. But I have the move that last increased the evaluation score as best_move.

That is weird... I don't think it is formulated correctly in CPW. I think what is meant by that is that you can have no sufficiently good move for either of the players, since (as you also mention) some moves in an ALL-node are clearly better than others. Just because losing a knight and losing a queen are both bad for the side to move, one is clearly worse than the other.

So, it seems best that if alpha never increases, to save the alpha score with alpha flag (as normal), AND the last move that increased the evaluation, instead of saving the alpha score with alpha flag and no move. At least in my engine.

Does this make sense to anyone?

I don't know if this is correct, but consider a node that has previously been searched to depth 3 and was determined to be an ALL-node. Now we're searching it again, but to depth 5, and we find out it is actually a CUT-node. If a best_move wasn't saved in the transposition table, there would be no TT-move ordering which would make the experimental version slower than the dev version.
I don't think not storing the moves in _real_ ALL-nodes would make a difference since move ordering isn't really important at that node-type. Therefore, it must be the engine changing its mind between ALL-node and CUT-node or ALL-node and PV-node, but not having any best move to try first, thus having worse move ordering and being slower.

[hgm]

Therefore, it must be the engine changing its mind between ALL-node and CUT-node or ALL-node and PV-node, but not having any best move to try first, thus having worse move ordering and being slower.

The point is that when you have no clue as to what is the best move, the most efficient order is the static one (i.e. starting with MVV/LVA capt). Because the static move ordering was designed to handle exactly that situation. If another ordering would be better, we would have chosen that as static move ordering.

Preceding the ordering by some random move just because it happened to have a high upper bound is not very likely to improve matters.

A more compelling reason to deviate from the static ordering would be an upper bound very much below alpha for moves early in the static ordering. So perhaps we should store as hash move the first move that did not fail low very badly, and then resort all moves that would normally be searched before it to the back. I am afraid, though, that this will almost always be the first move, as upper bounds much below alpha rarely occur.