PV-move ordering necessary if you have TT-move ordering?

[mvanthoor]

Hi,

I've had some discussion with Thomas (Lithander, from MinimalChess) recently, about PV-move vs. TT-move ordering.

If you have an engine that orders on moves it gets from the TT, does it give you any benefit to also order on moves from the (triangular) PV-table?

The CPW says this:

PV-move

A PV-Move is part of the principal variation and therefor a best move found in the previous iteration of an Iterative deepening framework. It is either a hash move of a stored PV-node inside the transposition table, or - if a triangular PV-Table is applied, a move from that array.

Hash / TT-move:

The Hash Move is a move probed from the transposition table, either a best move of a stored PV-node - a PV-move, or a good enough refutation move to cause a cutoff.

By reading this I am assuming that PV-move ordering is not necessary anymore as soon as you TT-move ordering, as the PV-move must be in the TT; you specifically put it there with an EXACT score if alpha is raised and bèta not beaten. When you probe the TT, the resulting move is either a PV-move, or a cut-move. So if it is there you should get it back out again, as long as it's not overwritten. This is the only reason I can see to also do PV-move ordering: because in the triangular TT, the PV-moves aren't overwritten, so you'll always have them.

When I added TT-move ordering, the engine gained about 100 Elo. My speedup was very similar to the speedup gained by VICE (BlueFever) and BBC (Maksim Korzh), who added PV-move ordering before they had a TT. Would it be beneficial if I _also_ implemented PV-move ordering? I have a feeling it won't be, except in the case to compensate for an overwritten PV-move in the TT, but I don't know if that would gain much playing strength.

[lithander]

Here's some context:

Code: Select all

  1. [X] f6f7 g8f7 e1e4 e8e4 f3g5 f7g7 g5e4 d7c6 f1g2 c8e6 f2c2 = +282.00, 6418K nodes, 5472.8442ms
    TT played: 8%, cuts: 94%, PV played 63%, cuts 85%, TT Index Collisions: 16%
   2. [X] c6f3 d1f3 h8h2 g2h2 e5f3 h2g2 f3d4 c3b5 e6e5 b5d4 e5d4 = -128.00, 2243K nodes, 1829.3286ms
    TT played: 9%, cuts: 95%, PV played 58%, cuts 79%, TT Index Collisions: 9%
   3. [X] b3b5 c6b5 c7c8Q e8f7 c8e6 f7e6 d5c7 e6e7 c7b5 a7a5 b5d4 = +177.00, 3499K nodes, 3346.4757ms
    TT played: 10%, cuts: 94%, PV played 58%, cuts 66%, TT Index Collisions: 15%
   4. [X] c8c5 b4c5 d5d3 d2d3 c4c5 g1h1 c5a7 d3d6 a7a4 f1c1 a4e4 = -292.00, 9687K nodes, 7862.2402ms
    TT played: 7%, cuts: 95%, PV played 66%, cuts 85%, TT Index Collisions: 24%
   5. [X] c5f2 g1f2 f6g4 f2f1 g4h2 f1g1 c7g3 e2e7 d7e6 e7e8 g8g7 = -154.00, 39248K nodes, 32108.7726ms
    TT played: 4%, cuts: 95%, PV played 68%, cuts 79%, TT Index Collisions: 55%
   6. [X] g5f6 d8f6 h6g4 f6f3 g2f3 e5g5 f3e4 g5g4 g1h1 g4e4 b2b4 = +30.00, 9722K nodes, 8134.752ms
    TT played: 6%, cuts: 95%, PV played 66%, cuts 85%, TT Index Collisions: 23%
    

These are some stats on a few example positions that I let MMC search to depth 11 with a hash size of 50MB (no buckets). Because all the leaf nodes are almost never in the TT only on 8% of the positions I search I really find best-move's for in the TT. But if there is one then it's always a good one and provides a Cut in 94% of the cases.

But usually I don't have one so the 2nd move I play is from the triangular PV table. It can provide a good move even if I have never encountered the position. I just take the current PV move on the same depth. And indeed in ~60% of all positions this move is available. And it's also usually a good one that provides a cut-off in about ~80% of the times I played it.

So the combined benefit of playing the TT move if available and the PV move if available is that I have a 50% chance to be done with a position before I even have to generate any moves for it. My move generation isn't super fast (8x8 board representation...) so if I get the opportunity to not run it I take it gladly.

I don't know if what *I* do in MinimalChess means that others would benefit from it too. But that's what I do and what I explained to Marcel in our discussion.

[hgm]

Normally the PV should still be in the TT, if there isn't too much replacement, or if the replacement scheme somewhat protects the larger depths.

To make absolutely sure it is, some engines stuff back the PV from the tri-angular array into the TT after each iteration. The search itself then only has to bother with the TT move.

[mvanthoor]

I don't know if what *I* do in MinimalChess means that others would benefit from it too. But that's what I do and what I explained to Marcel in our discussion.

It could be that you are seeing benefit from using the PV-move because you have set a smaller TT, and have no buckets. Possibly you're overwriting the PV-move in the TT, and then use the one from the triangular array as a backup.

Normally the PV should still be in the TT, if there isn't too much replacement, or if the replacement scheme somewhat protects the larger depths.

To make absolutely sure it is, some engines stuff back the PV from the tri-angular array into the TT after each iteration. The search itself then only has to bother with the TT move.

Maybe I'll try this and see if it provides any benefit. This is going to be only one line of code.

[lithander]

Now I'm confused. If you are in a leaf node (depth = 0) just before Q search you probably don't have that position in the TT yet, right? This is a position that never was played before. How do you retrieve a move from the TT to play in that case?

[mvanthoor]

Now I'm confused. If you are in a leaf node (depth = 0) just before Q search you probably don't have that position in the TT yet, right? This is a position that never was played before. How do you retrieve a move from the TT to play in that case?

You don't, because when depth <= 0, you start qsearch, and don't even get to probing the TT:

Code: Select all

pub fn alpha_beta( ... ) {
	// ...
	
        // If so, extend search depth by 1 to determine the best way to get
        // out of the check before we go into quiescence search.
        if is_check {
            depth += 1;
        }

        // We have arrived at the leaf node. Evaluate the position and
        // return the result.
        if depth <= 0 {
            return Search::quiescence(alpha, beta, pv, refs);
        }

        // Count this node, as it is not aborted or searched by QSearch.
        refs.search_info.nodes += 1;

        // Variables to hold TT value and move if any.
        let mut tt_value: Option<i16> = None;
        let mut tt_move: ShortMove = ShortMove::new(0);

        // Probe the TT for information.
        if refs.tt_enabled {
            if let Some(data) = refs
                .tt
                .lock()
                .expect(ErrFatal::LOCK)
                .probe(refs.board.game_state.zobrist_key)
            {
                let tt_result = data.get(depth, refs.search_info.ply, alpha, beta);
                tt_value = tt_result.0;
                tt_move = tt_result.1;
            }
        }

        // If we have a value from the TT, then return immediately.
        if let Some(v) = tt_value {
            if !is_root {
                return v;
            }
        }
        
	//...
}

That is another debate: should we use the TT in QSearch, or not? Some people say yes, other say no, because in some engines it seems to beneficial, and in others, it's not. I have not tested it myself yet.

[hgm]

Most engines do probe the TT in QS, and last time I saw this discussed, most authors claimed there is significant Elo loss from not doing it.

[mvanthoor]

Most engines do probe the TT in QS, and last time I saw this discussed, most authors claimed there is significant Elo loss from not doing it.

But if you probe the TT in the QSearch, you'll have to put stuff in it too. Then where do you stuff positions into the TT, if you don't do that in the QSearch? You won't reach the QSearch depths with a normal search.

(I'll have to try this QSearch TT probe thing as well then, if consensus has changed from "depends on the engine" to "gains a significant amount of playing strength.")

[hgm]

Maybe I'll try this and see if it provides any benefit. This is going to be only one line of code.

I think you under-estimate that a bit: you have to run through the entire PV, update the hash key for all moves in it (which, if you don't store the captured piece in the moves you have in your PV, probably requires you to update the board as well), probe the TT, decide which entry to overwrite if it wasn't there, and then create or update the entry.

But if you probe the TT in the QSearch, you'll have to put stuff in it too. Then where do you stuff positions into the TT, if you don't do that in the QSearch? You won't reach the QSearch depths with a normal search.

You store into the TT during QS as well, of course. Imagine a long exchange on a single square. If you transpose the first two captures of player A, you will reach the same node after 4 ply, and don't have to continue with the remaining part of the exchange.

Besides, you could hit upon a position from the full-width search (e.g. with d=2) in a QS at the end of a branch that took a longer path to the same position (or a true transposition that happened to be reduced more).

[mvanthoor]

Maybe I'll try this and see if it provides any benefit. This is going to be only one line of code.

I think you under-estimate that a bit: you have to run through the entire PV, update the hash key for all moves in it (which, if you don't store the captured piece in the moves you have in your PV, probably requires you to update the board as well), probe the TT, decide which entry to overwrite if it wasn't there, and then create or update the entry.

Why can't I just convert my PV vector entry from storing just moves to storing the things the TT needs? (I could even just store store a TT-entry in the PV vector...) Then I can just run through the PV, and re-store everything as if I'm storing an EXACT PV-move in the search, which is one line of code. At least, that was my plan. Am I missing something?

Edit: the one thing that could happen is that, if the PV-move is still in the TT, it will now be in there twice, if it overwrites a position with a lower depth. Maybe I'll just write an extra function "stuff_pv_move()" that takes the information from the PV entry, looks if an entry with the exact Zobrist and verification exists, and if not, replaces the one with the lowest depth.

I don't understand "update the hash key for all moves in it." A PV move doesn't have a hash key... the board does. Why would the hash key be different when re-stuffing the PV into the TT?

You store into the TT during QS as well, of course.

I thought so; I'll try it.