Move ordering

Discussion of chess software programming and technical issues.

Moderators: hgm, Dann Corbit, Harvey Williamson

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
hgm
Posts: 25941
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering

Post by hgm » Fri Aug 31, 2007 9:27 am

You mean in nodes with CurEval < Beta? Just try your best capture in stead of a null move, and look if the refutation was something different from the recapture.

I guess a problem is that even at d=1, when CurEval >= Beta you definitely want to do a null move as a first try anyway (saving you the trouble of move generation if it works). But when CurEval < Beta, you are pretty much dead anyway if there is a threat against you. The opponent would simply stand pat on your evasion, even in the face of a counter-threat. (Unless you have a non-standard QS that forbids such stand pats.) If you are too much below Alpha, all non-captures might even be futile.

So when CurEval < Beta you would only have to worry about move ordering for d >= 2. Starting IID at d=1 will tell you nothing, it will predictably fail low unless you have a capture worth more than the worst threat against you. But at d=2 you might have a chance to recover, if you had a good capture that was just not good enough compared to the threat, but you can evade the threat by creating a new threat of your own. The opponent will then be faced with two threats at d=1, solve one, and get refuted by the cashing in on the other in QS. But you would like to search evasions first at d=2, rather than start d=2 with the doomed captures, as the recovery, if it exists, should be among those evasions.

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Move ordering

Post by Michael Sherwin » Fri Aug 31, 2007 12:06 pm

In RomiChess I do not ever do a null move at d=1. When I tried it, it helped only against a very few programs while Romi did worse against most programs. I do not have a clue why that is. I am not the only one that has reported that.

If null_move is normally done only if cur_eval >= beta then at d=1 it may be a good idea to do null_move if cur_eval >= alpha inorder to detect PxQ threats.
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

User avatar
hgm
Posts: 25941
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering

Post by hgm » Fri Aug 31, 2007 12:26 pm

I prefer the null move even at d=1 because it saves you generating moves, and in Joker the result goes into the hash table as a d=3 search if it works (and consequently d=2 parents in which the side that is behind can make no threat go into the hash as d=4, and their parents as d=5), which saves a lot of work on the next iteration.

Michael Sherwin
Posts: 3196
Joined: Fri May 26, 2006 1:00 am
Location: WY, USA
Full name: Michael Sherwin

Re: Move ordering

Post by Michael Sherwin » Fri Aug 31, 2007 12:32 pm

Thanks! I will give that a try. :D
If you are on a sidewalk and the covid goes beep beep
Just step aside or you might have a bit of heat
Covid covid runs through the town all day
Can the people ever change their ways
Sherwin the covid's after you
Sherwin if it catches you you're through

User avatar
hgm
Posts: 25941
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering

Post by hgm » Fri Aug 31, 2007 12:52 pm

To maximally profit from this, the best way is to make Search() not only return a score, but also the depth to which this score is valid (as it will often be larger than the requested depth). For a cut-node this will be the depth of the cut-move, for a PV or all-node the worst depth of any of the moves searched (after correcting for the extensions/reductions).

You will then also automatically upgrade QS cut-nodes to d=1.

FrancoisK
Posts: 80
Joined: Tue Jul 18, 2006 8:46 pm

Re: Move ordering

Post by FrancoisK » Fri Aug 31, 2007 2:44 pm

So you are storing hash move fail high results in the hash table ?
I don't in BugChess2 because of an experiment i did long ago, i have not tried to discover why the version that did not store has move cuts seemed to be more successful in actual play.
Have someone done the same experiment ?

FrancoisK
Posts: 80
Joined: Tue Jul 18, 2006 8:46 pm

Re: Move ordering

Post by FrancoisK » Fri Aug 31, 2007 4:29 pm

FrancoisK wrote:So you are storing hash move fail high results in the hash table ?
I don't in BugChess2 because of an experiment i did long ago, i have not tried to discover why the version that did not store has move cuts seemed to be more successful in actual play.
Have someone done the same experiment ?
Oops, I mean null move, not hash move :oops:

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

Re: Move ordering

Post by bob » Fri Aug 31, 2007 4:47 pm

FrancoisK wrote:So you are storing hash move fail high results in the hash table ?
I don't in BugChess2 because of an experiment i did long ago, i have not tried to discover why the version that did not store has move cuts seemed to be more successful in actual play.
Have someone done the same experiment ?
I can't imagine why you would not store _every_ search result in the hash table. The reason? If you do it right, then you do the same search from the same position again, why would you get a different result? If you don't, then why would you not use the hash result instead. Same result. Zero work.

I don't (and never have) understood this idea of not storing some types of positions in the hash table. Mate scores are one oft-discussed topic. I've been storing them since I did my first program, I've been adjusting the mate scores or bounds in the logical way since then. I've never had a moment's trouble with them unless I simply introduced some sort of bug.

So why would you not want to store fail highs?

I could easily run a 10,000 game match to compare my program with and without storing fail highs. But I am certain that the result would be that the one that does not store them would play somewhat worse. How much worse would depend on how much this would slow the search down, something I am not sure about exactly. But it would definitely be slower and slower is bad.

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

Re: Move ordering

Post by bob » Fri Aug 31, 2007 4:50 pm

FrancoisK wrote:
FrancoisK wrote:So you are storing hash move fail high results in the hash table ?
I don't in BugChess2 because of an experiment i did long ago, i have not tried to discover why the version that did not store has move cuts seemed to be more successful in actual play.
Have someone done the same experiment ?
Oops, I mean null move, not hash move :oops:
same answer, second verse.

If a null move fails high here at some depth, why would it suddenly not fail high given the same position and depth, in another part of the tree? This is the very basis of hashing in the first place. If it is bad for some things, it would be bad for all. Or vice-versa...

User avatar
hgm
Posts: 25941
Joined: Fri Mar 10, 2006 9:06 am
Location: Amsterdam
Full name: H G Muller
Contact:

Re: Move ordering

Post by hgm » Fri Aug 31, 2007 4:59 pm

Ah, then it makes more sense. Yes, Joker stores them. In Joker it is actually the parent responsible for the hash probe and later storing of a position (so that Make/Unmake can be skipped on a hash hit). At that point I have no direct information on what happened inside the node, although I guess it could be deduced from the returned information (Score, to determine if it was a fail high, and the hash move and depth: if no hash move was returned it can be a fail low (ruled out by the score), a stand-pat (d=0) or a null-move (d>=R+1)).

I also considered not storing the null-move fail highs, but then you would have to do another hash probe for the null-move search, and it might no longer be around: because of the reduction it is more susceptible to replacement. So I decided against it without really trying. I guess the fact that the null-move fail highs are stored with extra depth helps to tip the balance towards storing them: they are more likely to survive.

Post Reply