LMP in PV nodes

[lucasart]

Completing the picture with newer tests:

Razoring at PV nodes
http://tests.stockfishchess.org/tests/v ... 5c4de1c0b9
http://tests.stockfishchess.org/tests/v ... 763e075658

Futility + LMP + SEE pruning at PV nodes in search()
http://tests.stockfishchess.org/tests/v ... 28c6bc66fd
http://tests.stockfishchess.org/tests/v ... 26a5666bc6

Futility pruning + SEE pruning at PV nodes in qsearch()
http://tests.stockfishchess.org/tests/v ... 17fe3fc6db
http://tests.stockfishchess.org/tests/v ... 28c6bc6704

Probcut at PV nodes
http://tests.stockfishchess.org/tests/v ... 6d8243c853
http://tests.stockfishchess.org/tests/v ... 5c4de1c0be

Null move pruning at PV nodes
http://tests.stockfishchess.org/tests/v ... 64db6b6d6f
http://tests.stockfishchess.org/tests/v ... 763e07564f

Child node Futility pruning at Root (aka. reverse futility pruning, beta pruning, static null move pruning)
http://tests.stockfishchess.org/tests/v ... 64db6b6d6d
http://tests.stockfishchess.org/tests/v ... 7a947a50bb

In the end the result wasn't that great, it seems?
http://tests.stockfishchess.org/tests/v ... 047028beb6

Even with the odds considerably favouring the "simplification", it seems to have failed.

Each patch was within the error bar. There is currently a bug with razoring PV nodes, which needs fixing. I will reschedule a test with fixed razoring.

Also, the test you're looking at does not have Futility/SEE/LMP. So far, no test has been scheduled with the whole lot at once.

[bob]

I do razoring before null move. Did you try it?

How would that work? Null move is done BEFORE anything is searched. Razoring applies to moves. I am not sure I understand your idea...

Maybe he means reverse razoring. Razoring for the opponent. Razoring after opponent has moved. Possible if you get last move from the stack. Don't know what's the use of it. But I also encountered "reverse futility pruning" in historic posts somewhere. I don't know.

Also stockfish does razoring before null move:

...
// Step 6. Razoring (skipped when in check)
// Step 7. Futility pruning: child node (skipped when in check)
// Step 8. Null move search with verification search (is omitted in PV nodes)
...

May be I'm not using the correct name in some concepts.

It is sort of an odd implementation, after looking at search.cpp. Most do the razoring stuff at the point where the move was made, rather than recursing to the next ply and then doing it before iterating through the move list. IE make move, made decision, and drop into q-search or do a normal search. Here the razoring decision is delayed one ply. I would think it worthwhile to avoid the recursive call and do it in the search loop, from an efficiency perspective. SF also seems to do futility pruning stuff 2x. Once at the normal place, then at the top of search on the next iteration. I've not thought about the "why" however. Perhaps it makes sense.

[Michel]

// Step 6. Razoring (skipped when in check)
// Step 7. Futility pruning: child node (skipped when in check)
// Step 8. Null move search with verification search (is omitted in PV nodes)

Well razoring is done when the static eval is low and reverse futility pruning+null move search are done when the static eval is high. So one would guess that it does not matter where you put razoring in the code. But of course one never really knows without testing.

[lucasart]

// Step 6. Razoring (skipped when in check)
// Step 7. Futility pruning: child node (skipped when in check)
// Step 8. Null move search with verification search (is omitted in PV nodes)

Well razoring is done when the static eval is low and reverse futility pruning+null move search are done when the static eval is high. So one would guess that it does not matter where you put razoring in the code. But of course one never really knows without testing.

Perhaps we could test swapping Step 6 and Step 7. The point is that Step 7 is cheap, while Step 6 is potentially expensive (it calls qsearch). Seems a logical test.

[lucasart]

SF also seems to do futility pruning stuff 2x. Once at the normal place, then at the top of search on the next iteration. I've not thought about the "why" however. Perhaps it makes sense.

At the parent node, you do futility pruning by looking at:

Code: Select all

optimistic_score = current_score + material_gain(move) + margin

In other words, you make the assumption that the eval after playing the move will not move by more than:

Code: Select all

delta_eval = material_gain(move) + margin

Instead, when you're in the child node, you know the exact eval. In fact, you even know the TT refined eval, which is better.

Morality: child node futility pruning is more accurate, but doing it in the parent node saves time, and especially saves an eval() call. So it's a speed tradeoff. But if you look at accuracy only (and neutralize speed by doing fixed nodes testing, or "node is time" testing), the child node version is the correct one.

[cdani]

I was just adding "eval pruning - parent node" to Andscacs, just before doing the move.

The idea that gives more elo here at least for Andscacs, is to minimize the false positives, i.e. the prunes that where not to be pruned in the child node. If instead of this you try to statistically mirror the most prunes of the child node in the parent node, you win less elo or you lose.

Just to give an idea, if the child where to prune 1.000.000 of moves and in the parent you achieve to prune 900.000 but you prune 80.000 that where not to be pruned, you win less elo that if in the parent you prune only 500.000 good ones and 10.000 false ones.

May be someone gives this a try if not already doing it.

[Michel]

Well after more testing it turns out that it is LMP that is responsible for GNU Chess's 5.60 huge drop in elo when enabling futility pruning in PV nodes.

The theoretical correctness of LMP in (predicted) ALL/PV nodes depends on correct move ordering, in the sense that it makes the gamble that if such a node will fail high then it will do so in the first few moves.

So probably GNU Chess 5.60 just has bad move ordering. In any case this gives me something to think about.