Move ordering by PST

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Move ordering by PST

Post by Onno Garms » Sat Apr 16, 2011 12:46 pm

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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering by PST

Post by bob » Sat Apr 16, 2011 1:18 pm

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.
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...

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Move ordering by PST

Post by Onno Garms » Sat Apr 16, 2011 1:38 pm

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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering by PST

Post by bob » Sat Apr 16, 2011 3:45 pm

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.
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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering by PST

Post by bob » Sat Apr 16, 2011 3:46 pm

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.
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
Posts: 2679
Joined: Sat Jun 14, 2008 7:17 pm

Re: Move ordering by PST

Post by mcostalba » Sat Apr 16, 2011 7:09 pm

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.

bob
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering by PST

Post by bob » Mon Apr 18, 2011 12:07 am

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.
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...

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Move ordering by PST

Post by Onno Garms » Mon Apr 18, 2011 6:09 am

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...
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
Posts: 20340
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Move ordering by PST

Post by bob » Mon Apr 18, 2011 5:31 pm

Onno Garms wrote:
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...
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.

User avatar
Onno Garms
Posts: 224
Joined: Mon Mar 12, 2007 6:31 pm
Location: Bonn, Germany

Re: Move ordering by PST

Post by Onno Garms » Mon Apr 18, 2011 6:55 pm

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

Post Reply