Negative Plausibility Move Ordering

Discussion of chess software programming and technical issues.

Moderators: bob, hgm, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Alessandro Damiani
Posts: 24
Joined: Fri Mar 10, 2006 2:29 pm
Location: Zurich, Switzerland

Negative Plausibility Move Ordering

Post by Alessandro Damiani » Thu Jul 09, 2009 7:05 pm

Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Negative Plausibility Move Ordering

Post by Gerd Isenberg » Thu Jul 09, 2009 7:57 pm

Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.

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

Re: Negative Plausibility Move Ordering

Post by bob » Sat Jul 11, 2009 6:35 pm

Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Negative Plausibility Move Ordering

Post by Don » Sun Jul 12, 2009 12:43 am

bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
It's truly bizarre that this is true in your program. In my program it definitely helps to use the history heuristic for move ordering. I don't use the classic version of HH but the version that considers how often it's chosen when the move is possible.

I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.

It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Negative Plausibility Move Ordering

Post by Don » Sun Jul 12, 2009 12:04 pm

bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
What do you do about the "other" moves in the list? When I say "other" or "rest" I mean the moves that are not normally put at the top of the list, such as killers, captures, hash table moves and promotions.

I did an experiment last night at 9 ply searches - where I could at least get a few thousand games per player. If I don't sort the "rest" of the moves at all it is 43 ELO weaker +/- 12 ELO.

Here is what I tested and the ELO ratings generated +/- about 12 ELO.

2000 - version that does history heuristic
1990 - version that evaluates each move fully (but not with quies)
1989 - version that sorts by piece square table.
1978 - moves are shuffled.
1957 - moves are retained in moveGen() order

All these versions put losing moves (according to see()) at the end of the list except the shuffled version and the one that does nothing.

The version that evaluate the moves using see() are slower - so this is a no-brainer. They are slower AND weaker. Perhaps at greater depths these would start winning?

I will add one more version, that shuffles the moves but applies see() to put losing moves at end of list. Maybe that is where 90% of the benefit is.

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

Re: Negative Plausibility Move Ordering

Post by bob » Sun Jul 12, 2009 5:20 pm

Don wrote:
bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
It's truly bizarre that this is true in your program. In my program it definitely helps to use the history heuristic for move ordering. I don't use the classic version of HH but the version that considers how often it's chosen when the move is possible.
You didn't read my post carefully enough. I didn't just test it in my program. I disabled it in the other programs that use it that I run on my cluster. It made zero difference... Note I am not talking about ordering either. I am talking about pruning/reduction decisions only...


I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.

It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don

User avatar
Don
Posts: 5106
Joined: Tue Apr 29, 2008 2:27 pm

Re: Negative Plausibility Move Ordering

Post by Don » Sun Jul 12, 2009 8:56 pm

bob wrote:
Don wrote:
bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
It's truly bizarre that this is true in your program. In my program it definitely helps to use the history heuristic for move ordering. I don't use the classic version of HH but the version that considers how often it's chosen when the move is possible.
You didn't read my post carefully enough. I didn't just test it in my program. I disabled it in the other programs that use it that I run on my cluster. It made zero difference... Note I am not talking about ordering either. I am talking about pruning/reduction decisions only...
Where in your post did you say that? You didn't.

There is nothing in your post that would lead any reader to conclude that you meant something different, especially when the whole thread is about move ordering.

I think that any reasonable interpretation is that you don't use the history heuristic (because you said it doesn't work for you.) There is nothing in your post that would lead any reader to conclude that you meant something different that what you actually said. Just because YOU know what you meant doesn't mean you wrote it down clearly and so you accuse the reader of being sloppy when it was really the writer who was sloppy.

I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.

It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don

MattieShoes
Posts: 718
Joined: Fri Mar 20, 2009 7:59 pm

Re: Negative Plausibility Move Ordering

Post by MattieShoes » Sun Jul 12, 2009 9:10 pm

Don wrote:
bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
It's truly bizarre that this is true in your program. In my program it definitely helps to use the history heuristic for move ordering. I don't use the classic version of HH but the version that considers how often it's chosen when the move is possible.

I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.

It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don
HH helped for me too. But my depths are less than crafty or the other very strong engines.

Gerd Isenberg
Posts: 2127
Joined: Wed Mar 08, 2006 7:47 pm
Location: Hattingen, Germany

Re: Negative Plausibility Move Ordering

Post by Gerd Isenberg » Mon Jul 13, 2009 4:25 am

Don wrote:
bob wrote: You didn't read my post carefully enough. I didn't just test it in my program. I disabled it in the other programs that use it that I run on my cluster. It made zero difference... Note I am not talking about ordering either. I am talking about pruning/reduction decisions only...
Where in your post did you say that? You didn't.

There is nothing in your post that would lead any reader to conclude that you meant something different, especially when the whole thread is about move ordering.

I think that any reasonable interpretation is that you don't use the history heuristic (because you said it doesn't work for you.) There is nothing in your post that would lead any reader to conclude that you meant something different that what you actually said. Just because YOU know what you meant doesn't mean you wrote it down clearly and so you accuse the reader of being sloppy when it was really the writer who was sloppy.

I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.
It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don
I quoted Bob's "late move reductions" post, where he proposed to "penalize" early moves while a later move failed high is similar to Jeff's Negative Plausibility. However, Bob was focused on LMR there, but later abandoned (relative) HH for LMR as well for move ordering.
http://www.talkchess.com/forum/viewtopi ... 24&t=18345

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

Re: Negative Plausibility Move Ordering

Post by bob » Mon Jul 13, 2009 4:33 am

Don wrote:
bob wrote:
Don wrote:
bob wrote:
Gerd Isenberg wrote:
Alessandro Damiani wrote:Has anyone tested the move ordering method described on http://www.aifactory.co.uk/newsletter/2 ... bility.htm?
Looks like an Alternative of Relative History Heuristic, as proposed by Bob in late move reductions, March 01, 2006.
I was going to say it looks like yahm, (yet another history methodology). :) So far, I have found absolutely no history approach that helps. I have turned it off in several programs on my cluster and it made absolutely no difference in the Elo at all. Probably is workable for very shallow search depths. But we aren't seeing very shallow search depths today.
It's truly bizarre that this is true in your program. In my program it definitely helps to use the history heuristic for move ordering. I don't use the classic version of HH but the version that considers how often it's chosen when the move is possible.
You didn't read my post carefully enough. I didn't just test it in my program. I disabled it in the other programs that use it that I run on my cluster. It made zero difference... Note I am not talking about ordering either. I am talking about pruning/reduction decisions only...
Where in your post did you say that? You didn't.
You are correct. Perhaps I had it confused with a different thread on the same topic, am not sure. But in any case, to make the point, history can be applied in three areas. ordering, reduction and pruning. I am explicitly talking about reduction and pruning. I removed history ordering a long while back after testing showed zero benefit (or loss) to using it. I have tried lots of ways to use history information of various sorts to limit reductions and pruning. And have found nothing that works. I have even turned off the history part of reductions and pruning for various programs and found that it made no difference in them either...


There is nothing in your post that would lead any reader to conclude that you meant something different, especially when the whole thread is about move ordering.

See above. My post looks to be incomplete, which might well have been a touchpad error that deleted something I wrote without my noticing. Or I could have just made a mistake. In either case, hopefully I corrected it above.

[quote\\]

I think that any reasonable interpretation is that you don't use the history heuristic (because you said it doesn't work for you.) There is nothing in your post that would lead any reader to conclude that you meant something different that what you actually said. Just because YOU know what you meant doesn't mean you wrote it down clearly and so you accuse the reader of being sloppy when it was really the writer who was sloppy.

I have found that it's difficult to improve on that for the "other" moves - the ones beyond captures, killers, etc.

It's crazy but different people report different things. For Rebel, Ed sorts by a piece square table and reports that it definitely helps. It doesn't for me!

- Don
[/quote]

The main issue is "how did he measure the 'it definitely helps'"??? Most likely with far too few games to draw a valid conclusion.

Post Reply