move ordering especially ordering&searching of root move

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.
MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

move ordering especially ordering&searching of root move

Post by MahmoudUthman » Wed Dec 21, 2016 11:58 am

1-what is the best ordering method for root moves ?
2-and when ordering by number of nodes searched does this mean main search nodes only or Qnodes included ?
3-and should the root moves be ordered by a different technique before the first iteration of the ID ?
4-in the first iteration after making the root move (I use a different function for the IDLoop&rootSearch separate from the Main AlphaBeta ) , should the search descend directly into Qsearch (Call alphabeta with depth=0) or should it call alphabeta with search = 1 ?
5-Who are Capture-Promotion moves scored according to the MVV-LVA ?
6-can the average effective branching factor during multiple games a good be used as indicative of the quality of move ordering ?

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: move ordering especially ordering&searching of root

Post by cdani » Wed Dec 21, 2016 7:44 pm

MahmoudUthman wrote:1-what is the best ordering method for root moves ?
2-and when ordering by number of nodes searched does this mean main search nodes only or Qnodes included ?
3-and should the root moves be ordered by a different technique before the first iteration of the ID ?
4-in the first iteration after making the root move (I use a different function for the IDLoop&rootSearch separate from the Main AlphaBeta ) , should the search descend directly into Qsearch (Call alphabeta with depth=0) or should it call alphabeta with search = 1 ?
5-Who are Capture-Promotion moves scored according to the MVV-LVA ?
6-can the average effective branching factor during multiple games a good be used as indicative of the quality of move ordering ?
1 - In Andscacs I order root moves by static evaluation on the first iteration. On other iteratoins are ordered by, first the latest best, and other moves by the number of nodes searched in the previous iteration.

2 - In Andscacs means all the nodes including QS ones.

4 - Technically probably the good one is go to QS, but I suppose the difference is minimal.

5 - I don't understand the question.

6 - I think no. Some patches worked (won elo) but lowered NPS and typical depth.

MahmoudUthman
Posts: 234
Joined: Sat Jan 17, 2015 10:54 pm

Re: move ordering especially ordering&searching of root

Post by MahmoudUthman » Wed Dec 21, 2016 8:32 pm

cdani wrote:
MahmoudUthman wrote:1-what is the best ordering method for root moves ?
2-and when ordering by number of nodes searched does this mean main search nodes only or Qnodes included ?
3-and should the root moves be ordered by a different technique before the first iteration of the ID ?
4-in the first iteration after making the root move (I use a different function for the IDLoop&rootSearch separate from the Main AlphaBeta ) , should the search descend directly into Qsearch (Call alphabeta with depth=0) or should it call alphabeta with search = 1 ?
5-Who are Capture-Promotion moves scored according to the MVV-LVA ?
6-can the average effective branching factor during multiple games a good be used as indicative of the quality of move ordering ?
1 - In Andscacs I order root moves by static evaluation on the first iteration. On other iteratoins are ordered by, first the latest best, and other moves by the number of nodes searched in the previous iteration.

2 - In Andscacs means all the nodes including QS ones.

4 - Technically probably the good one is go to QS, but I suppose the difference is minimal.

5 - I don't understand the question.

6 - I think no. Some patches worked (won elo) but lowered NPS and typical depth.
thank you ,as for 5 I was up for >24 hours somehow it seemed fine then :), what I wanted to ask is : how should Promotion that capture pieces be ordered , for example should a promotion to queen that captures a rook be scored as a pawn capturing a rook or a queen capturing the rook ? and since promotions in general are better than normal moves in a sense should a Pro-Cap be scored higher than an equivalent normal capture ? or maybe lower since promotion adds more material to the table and accordingly increases the number of available legal moves to be search ?

User avatar
cdani
Posts: 2104
Joined: Sat Jan 18, 2014 9:24 am
Location: Andorra
Contact:

Re: move ordering especially ordering&searching of root

Post by cdani » Wed Dec 21, 2016 10:25 pm

MahmoudUthman wrote: thank you ,as for 5 I was up for >24 hours somehow it seemed fine then :), what I wanted to ask is : how should Promotion that capture pieces be ordered , for example should a promotion to queen that captures a rook be scored as a pawn capturing a rook or a queen capturing the rook ? and since promotions in general are better than normal moves in a sense should a Pro-Cap be scored higher than an equivalent normal capture ? or maybe lower since promotion adds more material to the table and accordingly increases the number of available legal moves to be search ?
Now I'm ignoring if is a promotion when is a capture, but I don't remember if I have tried to take it into account. Sure someone can tell something more concrete.

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

Re: move ordering especially ordering&searching of root

Post by Evert » Wed Dec 21, 2016 10:47 pm

MahmoudUthman wrote: thank you ,as for 5 I was up for >24 hours somehow it seemed fine then :), what I wanted to ask is : how should Promotion that capture pieces be ordered , for example should a promotion to queen that captures a rook be scored as a pawn capturing a rook or a queen capturing the rook ? and since promotions in general are better than normal moves in a sense should a Pro-Cap be scored higher than an equivalent normal capture ? or maybe lower since promotion adds more material to the table and accordingly increases the number of available legal moves to be search ?
I suspect it doesn't really matter much, since chances are good that the move is sorted high up in the list anyway. Some considerations.

A promotion move that gets you a rook swings the evaluation to your advantage by +13 points (9+5-1), if the promotion square is undefended. Otherwise it's just +4. That is something to keep track of.

You want to search the move that is most likely to generate a cut-off cheaply first. Cheaply means it should have a small(er) number of child nodes, which is more likely for moves that reduce material (captures) than for moves that increase it (promotions), so it makes some sense to search captures ahead of promotions.

Lyudmil Tsvetkov
Posts: 6052
Joined: Tue Jun 12, 2012 10:41 am

Re: move ordering especially ordering&searching of root

Post by Lyudmil Tsvetkov » Thu Dec 22, 2016 6:59 am

cdani wrote:
MahmoudUthman wrote: thank you ,as for 5 I was up for >24 hours somehow it seemed fine then :), what I wanted to ask is : how should Promotion that capture pieces be ordered , for example should a promotion to queen that captures a rook be scored as a pawn capturing a rook or a queen capturing the rook ? and since promotions in general are better than normal moves in a sense should a Pro-Cap be scored higher than an equivalent normal capture ? or maybe lower since promotion adds more material to the table and accordingly increases the number of available legal moves to be search ?
Now I'm ignoring if is a promotion when is a capture, but I don't remember if I have tried to take it into account. Sure someone can tell something more concrete.
Daniel will not be angry that I am posting here as a non-programmer, but what I have observed from SF framework is that any duplication of functions in the code simply fails, for example, if you score queen threats on the enemy rook and knight, scoring also double threats will almost certainly fail.

similarly, if you extend promotions in the search, why also assign them bigger move-ordering bonus? this seems a duplication of functions that is bound to fail.

or capture and promotion: you already order captures higher, promotions higher, so the move gets bonus for both, why additionally increase its score?

Lyudmil Tsvetkov
Posts: 6052
Joined: Tue Jun 12, 2012 10:41 am

Re: move ordering especially ordering&searching of root

Post by Lyudmil Tsvetkov » Thu Dec 22, 2016 7:12 am

I guess a major flaw of standard move-ordering techniques as found in engines, is that they rely too much on previous performance of a move (history tables, etc.), and too little of the objective quality of the move in the new setting at a bigger depth. relying on previous performance means relying on eval scores throughout different depths, which migth not be the perfect approach taken into account engines' far from perfect eval.

as I see it currently, modern top engines use too few flags to order their moves, and there are, of course, much much more important patterns than whether a move is a capture, winning capture, simply quiet move, etc. for example, it matters very much if the move is close to the enemy king or far from it, whether it creates some threat, though not executing it, etc., etc. Top engines seem to not quite take this into account, at least that is what I see from SF's choice of moves.

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

Re: move ordering especially ordering&searching of root

Post by Evert » Thu Dec 22, 2016 10:53 am

Lyudmil Tsvetkov wrote:I guess a major flaw of standard move-ordering techniques as found in engines, is that they rely too much on previous performance of a move (history tables, etc.), and too little of the objective quality of the move in the new setting at a bigger depth. relying on previous performance means relying on eval scores throughout different depths, which migth not be the perfect approach taken into account engines' far from perfect eval.

as I see it currently, modern top engines use too few flags to order their moves, and there are, of course, much much more important patterns than whether a move is a capture, winning capture, simply quiet move, etc. for example, it matters very much if the move is close to the enemy king or far from it, whether it creates some threat, though not executing it, etc., etc. Top engines seem to not quite take this into account, at least that is what I see from SF's choice of moves.
What you have to remember is that most move sequences considered by engines are blunders. When they hang a queen, you want to capture it immediately. That's why you have to sort captures (especially winning captures) first.
Once you're past that, you need some way to sort moves that are not obviously good (because they win you a queen). There are two approaches:
1. Hard code all patterns that you can think of. This requires a lot of work, and a lot of testing for special cases (I mean the code needs to do a lot of tests, not that it needs to be heavily tuned, though that is also true).
2. Use general guidelines and allow the code to figure out what works and what doesn't during search.

The first approach is like you suggest. This is not scalable and a maintenance nightmare. It's also slow because it needs to do a lot of work. The second is what most (all?) programs do, using things like killer tables and history. Good programs are good not in spite of doing (2) instead of (1), but because they don't waste time doing (1) when (2) will do.

Now, you probably could write a neural network that aims to do (1). I think Giraffe might have that? The issue is setting up and training said network.

sasachess
Posts: 24
Joined: Wed Nov 05, 2014 10:28 am
Location: Italy
Contact:

Re: move ordering especially ordering&searching of root

Post by sasachess » Thu Dec 22, 2016 7:14 pm

cdani wrote: On other iteratoins are ordered by, first the latest best, and other moves by the number of nodes searched in the previous iteration.
which benefits brings sorting by nodes searched in the previous iteration?

Sven
Posts: 3829
Joined: Thu May 15, 2008 7:57 pm
Location: Berlin, Germany
Full name: Sven Schüle
Contact:

Re: move ordering especially ordering&searching of root

Post by Sven » Thu Dec 22, 2016 10:50 pm

sasachess wrote:
cdani wrote: On other iteratoins are ordered by, first the latest best, and other moves by the number of nodes searched in the previous iteration.
which benefits brings sorting by nodes searched in the previous iteration?
It is often better than using the score that was returned since the alpha-beta algorithm only assigns upper bounds to all moves that were refuted through a beta cutoff, so you can't tell which of the refuted moves was relatively the best one.

In contrast to that, a higher node count tells us that the move was considered as "important" somehow. Of course it is not "proven" that using the node count for move ordering at root is a good strategy but many people have reported that it helps their engines.

Post Reply