Move ordering based on stored values of child nodes

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
Post Reply
Morten Lohne
Posts: 6
Joined: Wed Jul 19, 2017 10:18 pm

Move ordering based on stored values of child nodes

Post by Morten Lohne » Thu May 31, 2018 11:29 am

So I've been trying to read up on move ordering for my chess engine. Checking the position in the hash table, and searching the "hash move" first, seems to be a universal technique. Is it possible to also look up every child node in the table, get their values from shallower searches, and then sort the entire move vector based on that? It seems like a natural next step, but for some reason I can't find anyone else who has tried it. Is it just a bad idea for some reason I don't understand? How else are top engines able to check the best move first 90% of the time?

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

Re: Move ordering based on stored values of child nodes

Post by hgm » Thu May 31, 2018 12:03 pm

The problem is that for >99% of all nodes the score is not known at all, not even from a shallower search. All that is known is an upper or lower bound on the score. So what you would get when you retrieve all scores for the daughter nodes from the previous iteration, is something like this:

hash move: +0.76 (exact)
10 other moves +0.76 (upper bound)
8 other moves: +0.75 (upper bound)
6 other moves +0.73 (upper bounds)
remaining moves +0.70, +0.53, 0.0, -2.13, -200.0 (all upper bounds)

The second-best move could easily be the one with upper bound +0.70. How would you know?

Engines get the best move first >90% of the time because the hash move happens to be best move >90% of the time.

User avatar
Evert
Posts: 2900
Joined: Fri Jan 21, 2011 11:42 pm
Location: NL
Contact:

Re: Move ordering based on stored values of child nodes

Post by Evert » Thu May 31, 2018 12:30 pm

With current move ordering heuristics, you get a cut-off from the first three moves in 95-99% of cases. That's the statistic you have to beat.
Any effort spent on move ordering in ALL-nodes is wasted.
Any effort in improving move ordering in a CUT-node is wasted in 95-99% of cases, so whatever you propose needs to be fast. Getting statistics for all moves is not cheap (especially not in horizon nodes).
Not to forget: move ordering doesn't need to be perfect. It needs to be good enough.

Daniel Shawul
Posts: 3498
Joined: Tue Mar 14, 2006 10:34 am
Location: Ethiopia
Contact:

Re: Move ordering based on stored values of child nodes

Post by Daniel Shawul » Thu May 31, 2018 12:54 pm

Morten Lohne wrote:
Thu May 31, 2018 11:29 am
So I've been trying to read up on move ordering for my chess engine. Checking the position in the hash table, and searching the "hash move" first, seems to be a universal technique. Is it possible to also look up every child node in the table, get their values from shallower searches, and then sort the entire move vector based on that? It seems like a natural next step, but for some reason I can't find anyone else who has tried it. Is it just a bad idea for some reason I don't understand? How else are top engines able to check the best move first 90% of the time?
I do this in alpha-beta rollouts since I have the tree stored in memory. You can do things like sorting by size of subtree similar do what alpha-beta engines do at the root. I belive it gives better move ordering overall.

Cardoso
Posts: 276
Joined: Thu Mar 16, 2006 6:39 pm

Re: Move ordering based on stored values of child nodes

Post by Cardoso » Thu May 31, 2018 2:18 pm

Evert wrote:
Thu May 31, 2018 12:30 pm
With current move ordering heuristics, you get a cut-off from the first three moves in 95-99% of cases. That's the statistic you have to beat.
Do you get that consistently throughout the entire game?
Do you get that for example from the starting position or after the first say 10 moves?
And what about when your engine is behind or even loosing?
And what happens when the engine changes it's mind often?

Post Reply