Move ordering by PST

[Onno Garms]

The common scheme for move ordering is history based. The Stockfish authors tried PST as a fallback solution when no history is available. They told me that there was no improvement by that, so they reverted to history alone.

Has anybody tried PST alone? (The Stockfish authors don't remember if they did.) Or a combination of PST and piece type? (Pawn moves tend to be bad.)

I always disliked history based move ordering. The heuristic doesn't look plausible for me, moreover it sometimes leads to reproducability problems in debugging, when the move ordering depends on some obscure history. But for lack of an alternative that is known to work, I have history based move ordering in Onno.

Also note that there was a severe bug in the history in Toga 1.2.1, but this but did not cost any Elo:
http://talkchess.com/forum/viewtopic.php?t=38406
This might indicate that the whole concept is messy.

[bob]

The common scheme for move ordering is history based. The Stockfish authors tried PST as a fallback solution when no history is available. They told me that there was no improvement by that, so they reverted to history alone.

Has anybody tried PST alone? (The Stockfish authors don't remember if they did.) Or a combination of PST and piece type? (Pawn moves tend to be bad.)

I always disliked history based move ordering. The heuristic doesn't look plausible for me, moreover it sometimes leads to reproducability problems in debugging, when the move ordering depends on some obscure history. But for lack of an alternative that is known to work, I have history based move ordering in Onno.

Also note that there was a severe bug in the history in Toga 1.2.1, but this but did not cost any Elo:
http://talkchess.com/forum/viewtopic.php?t=38406
This might indicate that the whole concept is messy.

I gave up on history-based ordering several years ago. I tested the fool out of it and decided it didn't work very well. And for LMR, it _really_ was random as I reported several years ago when Fruit showed up. I added LMR to Crafty, and tested the fruit history idea. No good. I tried a dozen different ways of measuring history, some even use my last attempt today. But nothing worked worth a flip. I then took the history stuff out of fruit (but left LMR in) and found the _same_ result. History just didn't work very well when tested with real games...

[Onno Garms]

So you say that even random move ordering works as well as history based move ordering? Intersting. Marco might have had different results with Stockfish:

We made the tests very long ago and resulted that history was given us
an increase, I don't remember if we have tested PST alone vs history
alone.

[bob]

So you say that even random move ordering works as well as history based move ordering? Intersting. Marco might have had different results with Stockfish:

We made the tests very long ago and resulted that history was given us
an increase, I don't remember if we have tested PST alone vs history
alone.

I didn't say _random_. I even try to generate moves in a sane order in that I do advances before retreats, etc... And I still have killers, a hash move, SEE >= 0 captures first, etc...

[bob]

So you say that even random move ordering works as well as history based move ordering? Intersting. Marco might have had different results with Stockfish:

We made the tests very long ago and resulted that history was given us
an increase, I don't remember if we have tested PST alone vs history
alone.

I didn't say _random_. I even try to generate moves in a sane order in that I do advances before retreats, etc... And I still have killers, a hash move, SEE >= 0 captures first, etc...

My speculation is that killers may well be more than good enough to replace history ordering. And history based reductions really seem to be "not good".

[mcostalba]

And history based reductions really seem to be "not good".

Did someone talk about history based reductions ?

For what I have understood Onno is talking about move ordering with the aim of increasing the average probability to find a cut-off move sooner than later, this is what move ordering stands for...at least this is what I have always assumed.

[bob]

And history based reductions really seem to be "not good".

Did someone talk about history based reductions ?

For what I have understood Onno is talking about move ordering with the aim of increasing the average probability to find a cut-off move sooner than later, this is what move ordering stands for...at least this is what I have always assumed.

I was talking about "history information". Which can be applied to ordering, reductions, pruning, extensions, etc. Used to work until depths swiftly passed 20 plies and beyond... Then the numbers began to look more like random garbage...

[Onno Garms]

I was talking about "history information". Which can be applied to ordering, reductions, pruning, extensions, etc. Used to work until depths swiftly passed 20 plies and beyond... Then the numbers began to look more like random garbage...

ACK. On inspection of the history values they looked like random garbage for me too. However, this "random garbage" might still contain information such as "advancing moves are better than withdrawals", which Bob has added to his move generation but I have not. So I am not sure if I could have removed history as easily.

[bob]

I was talking about "history information". Which can be applied to ordering, reductions, pruning, extensions, etc. Used to work until depths swiftly passed 20 plies and beyond... Then the numbers began to look more like random garbage...

ACK. On inspection of the history values they looked like random garbage for me too. However, this "random garbage" might still contain information such as "advancing moves are better than withdrawals", which Bob has added to his move generation but I have not. So I am not sure if I could have removed history as easily.

Just for fun, there are other ideas to try (I already have).

1. use a 17 bit index <piece><to><from> which provides more detailed information.

2. When a move fails high, update it's history. And also reduce the history counters for any move(s) you tried before that fail high move, since they failed to produce a cutoff.

However, none of those helped at all for me.

[Onno Garms]

Seems that history tables are a relict of the history of chess engines when they searched 7 plies