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.
Move ordering by PST
Moderators: hgm, Rebel, chrisw
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering by PST
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 wrote: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.
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Move ordering by PST
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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering by PST
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...Onno Garms wrote: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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering by PST
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...Onno Garms wrote: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.
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".
-
- Posts: 2684
- Joined: Sat Jun 14, 2008 9:17 pm
Re: Move ordering by PST
bob wrote: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.
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering by PST
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...mcostalba wrote:bob wrote: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.
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Move ordering by PST
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 wrote: 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...
-
- Posts: 20943
- Joined: Mon Feb 27, 2006 7:30 pm
- Location: Birmingham, AL
Re: Move ordering by PST
Just for fun, there are other ideas to try (I already have).Onno Garms wrote: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 wrote: 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...
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.
-
- Posts: 224
- Joined: Mon Mar 12, 2007 7:31 pm
- Location: Bonn, Germany
Re: Move ordering by PST
Seems that history tables are a relict of the history of chess engines when they searched 7 plies