Relationship between move ordering and pruning

[lucasart]

Have you tried the Glaurung history method ?

No, please elaborate.

You can have a look at what Stockfish does, as this part hasn't changed since Glaurung: github.com/mcostalba/stockfish.
It is surprisingly simple, yet very good
- a history table, indexed by piece type (6 piece types, P, N, B, R, Q, K) and target square
- when a move fails high, you add depth*depth
- for all other moves that *have been* searched at this node, you substract depth*depth
- whenever an history vbalue exceeds, in absolute value, HistoryMax = 2000, you divide all the elements of the array by 2

Thanks for sharing. Yes I have tried this and various other variations on this theme during the last 32 years It works great for starters but if you already have a good move-ordering there hardly is any gain. I seldom look at code of others but does Stockfish limit the history values to a certain ply? During my experiments I noticed that there is something to gain if you limit the history table update to 8-10-12 ply (will depend per engine of course) since after that you only collect rubbish.

Not updating after a certain depth is probably too blunt, but I see your point. Perhaps an intermediate approach like
bonus = +/- depth * min(12, depth)
instead of
bonus = +/- depth*depth
I'm currently testing that in DiscoCheck. It shouldn't change much, but at least it prevents bogus overflows at very high depth -- the kinds of depth that are easily reached in late endgames.

[Rebel]

Have you tried the Glaurung history method ?

No, please elaborate.

You can have a look at what Stockfish does, as this part hasn't changed since Glaurung: github.com/mcostalba/stockfish.
It is surprisingly simple, yet very good
- a history table, indexed by piece type (6 piece types, P, N, B, R, Q, K) and target square
- when a move fails high, you add depth*depth
- for all other moves that *have been* searched at this node, you substract depth*depth
- whenever an history vbalue exceeds, in absolute value, HistoryMax = 2000, you divide all the elements of the array by 2

Thanks for sharing. Yes I have tried this and various other variations on this theme during the last 32 years It works great for starters but if you already have a good move-ordering there hardly is any gain. I seldom look at code of others but does Stockfish limit the history values to a certain ply? During my experiments I noticed that there is something to gain if you limit the history table update to 8-10-12 ply (will depend per engine of course) since after that you only collect rubbish.

Not updating after a certain depth is probably too blunt, but I see your point. Perhaps an intermediate approach like
bonus = +/- depth * min(12, depth)
instead of
bonus = +/- depth*depth
I'm currently testing that in DiscoCheck. It shouldn't change much, but at least it prevents bogus overflows at very high depth -- the kinds of depth that are easily reached in late endgames.

Perhaps it's an idea to limit the history at 8-10-12 ply and PST ordering thereafter. I will try SF exact "HistoryMax = 2000" anyway some day, who knows? and it's a kind of sport to get the last drop out of move-ordering.

Something related, funny and very theoretic, since the introduction of LMR it's not guaranteed any longer that a speed-up of (say) 5% in move-ordering automatically means an elo improvement. Using a move-count of "3" for LMR a faster search could shift the best-move from place 3 at place 4 and a wrong reduction is made. Nah.... I don't believe it myself.

[lucasart]

Perhaps it's an idea to limit the history at 8-10-12 ply and PST ordering thereafter. I will try SF exact "HistoryMax = 2000" anyway some day, who knows? and it's a kind of sport to get the last drop out of move-ordering.

I've recently found that having a history table by color is slightly more efficient.

Something related, funny and very theoretic, since the introduction of LMR it's not guaranteed any longer that a speed-up of (say) 5% in move-ordering automatically means an elo improvement. Using a move-count of "3" for LMR a faster search could shift the best-move from place 3 at place 4 and a wrong reduction is made. Nah.... I don't believe it myself.

You are absolutely right. I can assure you that I have noticed that pernicious effect myself. And I even use *double* reductions of late moves in certain conditions. In an engine that does aggressive search reductions (or other move count dependant pruning/reductions) the effect of move ordering is amplified.
Any modification that affects functionality should be tested! You can't just say: well on a small sample of positions the new move ordering seems to produce less nodes, so it must be better, let's commit the code patch and be done with it...

[Rebel]

Perhaps it's an idea to limit the history at 8-10-12 ply and PST ordering thereafter. I will try SF exact "HistoryMax = 2000" anyway some day, who knows? and it's a kind of sport to get the last drop out of move-ordering.

I've recently found that having a history table by color is slightly more efficient.

Looks logical to me.

I have tried my own suggestion using Tord's formula in the following way:

Code: Select all

static int history [ply] [piece_type] [to_square]

First 8 plies only, thereafter PST ordering.

Code: Select all

TEST  7:59:14 (46.037M nodes) NPS = 1.601K
MAIN  8:30:44 (50.125M nodes) NPS = 1.636K

Meaning, 7% faster in time, 9% in nodes.

Trying 10 plies as a limit (instead of 8) it goes down rapidly but needs more games for a conclusion.

[lucasart]

Perhaps it's an idea to limit the history at 8-10-12 ply and PST ordering thereafter. I will try SF exact "HistoryMax = 2000" anyway some day, who knows? and it's a kind of sport to get the last drop out of move-ordering.

I've recently found that having a history table by color is slightly more efficient.

Looks logical to me.

I have tried my own suggestion using Tord's formula in the following way:

Code: Select all

static int history [ply] [piece_type] [to_square]

First 8 plies only, thereafter PST ordering.

Code: Select all

TEST  7:59:14 (46.037M nodes) NPS = 1.601K
MAIN  8:30:44 (50.125M nodes) NPS = 1.636K

Meaning, 7% faster in time, 9% in nodes.

Trying 10 plies as a limit (instead of 8) it goes down rapidly but needs more games for a conclusion.

I suppose you mean:

Code: Select all

static int history [color] [piece_type] [to_square]

Switching from a history table autocalibrated by the search, to a hardcoded PST, suddenly at a fixed depth, is a bit brutal
I doubt your PST bit is going to outperform Tord's formula. Surely when you have no search information, your PST is better than random ordering, but I suggest you throw away the PST completely, and only use Tord's formula and see how it performs. Perhaps you can initialize the history table based on your PST values, so that they get used for the first iteration (ordering at depth 1, quiet checks at depth 0, quiet check evasions in the qsearch), and gradually overwritten by the search thereafter.

[Rebel]

Code: Select all

static int history [ply] [piece_type] [to_square]

is what I use, the color is included this way (odd | even)

[lucasart]

Code: Select all

static int history [ply] [piece_type] [to_square]

is what I use, the color is included this way (odd | even)

I think you misunderstood. For a given color, there's no ply dependancy. It's all handled by the +/- depth*depth bonus (fail high/previously searched moves)