I have a question regarding the move ordering. How to define what move ordering is better than the other?
First I thought that the best KPI is the number of nodes parsed on the same search depth. But then I found out that if you change the piece values (PieceVal = [ 0, 100, 325, 325, 550, 1000, 50000, 100, 325, 325, 550, 1000, 50000 ]) in Bluefever's Javascript chess engine to all zeroes (PieceVal = PieceVal.map(value=>0)) then LESS nodes get parsed on the same depth on starting position. The same thing if you change other heuristics to zeroes.
I also realize that the amount of nodes could also be reduced by making more checks and other moves provoking less posible responses.
Bluefever himself has used the fh/fhf formula. But I don't understand the logic behind this. Yes, it is good that all beta cut-offs are made on the first move - but what about the situations when there were no beta cut-offs at all? Should they be ignored? What if the beta cut-off is invoked only one time and is done on the first move? Then you get 100% rate but the performance of the engine would be poor since the amount of the beta cut-offs is low.
Could you help me with this?
Thank you!
How to define the best move ordering?
Moderator: Ras
-
jaroslav.tavgen
- Posts: 15
- Joined: Fri Oct 25, 2019 2:51 pm
- Full name: Jaroslav Tavgen
-
Robert Pope
- Posts: 567
- Joined: Sat Mar 25, 2006 8:27 pm
- Location: USA
- Full name: Robert Pope
Re: How to define the best move ordering?
I think you are conflating two different ideas here.
The first is: how can we compare or rank the quality of a program's move ordering? I think your definition is fine, though arguably time to search a given depth is more important. If you spend too much time ordering, you'll be worse off than a faster, less perfect scheme.
The second is: how can I reduce nodes searched in a program (presumably to make it play better)?
The first question assumes a static program, where the only thing being changed is the move ordering routine. You are violating this concept in your thought experiment by changing material weights, not the ordering function. This is like trying to argue you are going to improve move ordering by making Quiescence search more restrictive -- you are now searching fewer nodes per depth, but that doesn't mean your move ordering has improved, nor does it mean your program is stronger. In both of these, you've changed the shape of the search tree, but that isn't really related to move ordering.
That said, there are non-move-ordering things you can do that affect the tree shape (as seen above) and will affect strength one way or another. The granularity of your evaluation function has an impact, for example. But the only way to test these is through playing games, not search metrics.
And of course, once you've changed other parts of the program, the original assessment of the best ordering algorithm may change, since the underlying assumption in #1 was that the rest of the program was being held static.
The first is: how can we compare or rank the quality of a program's move ordering? I think your definition is fine, though arguably time to search a given depth is more important. If you spend too much time ordering, you'll be worse off than a faster, less perfect scheme.
The second is: how can I reduce nodes searched in a program (presumably to make it play better)?
The first question assumes a static program, where the only thing being changed is the move ordering routine. You are violating this concept in your thought experiment by changing material weights, not the ordering function. This is like trying to argue you are going to improve move ordering by making Quiescence search more restrictive -- you are now searching fewer nodes per depth, but that doesn't mean your move ordering has improved, nor does it mean your program is stronger. In both of these, you've changed the shape of the search tree, but that isn't really related to move ordering.
That said, there are non-move-ordering things you can do that affect the tree shape (as seen above) and will affect strength one way or another. The granularity of your evaluation function has an impact, for example. But the only way to test these is through playing games, not search metrics.
And of course, once you've changed other parts of the program, the original assessment of the best ordering algorithm may change, since the underlying assumption in #1 was that the rest of the program was being held static.
-
jaroslav.tavgen
- Posts: 15
- Joined: Fri Oct 25, 2019 2:51 pm
- Full name: Jaroslav Tavgen
Re: How to define the best move ordering?
Robert, thank you very much!