Voting techniques in move ordering

[sje]

Voting techniques in move ordering

Consider that there are a half dozen or more traditional techniques for ordering selections in an A/B search. Some of these techniques only produce a single move, and some aren't available in all situations. But usually there are several selection techniques that can contribute to that good ordering desperately needed for an efficient A/B search.

Instead of applying these techniques in a particular order, think about the alternative of trying all of them simultaneously and taking a vote based on the results. Some techniques may be more reliable than others and perhaps these could be given extra weighting. The idea here is that the added time expense of running multiple ordering heuristics when less may be needed could provide an overall savings due to a higher quality consensus first choice.

Also, consider the case where all or nearly all of the techniques vote for the same move. In these cases, the strength of the consensus could be used to invoke forward pruning of the alternative moves at that node.

[michiguel]

Voting techniques in move ordering

Consider that there are a half dozen or more traditional techniques for ordering selections in an A/B search. Some of these techniques only produce a single move, and some aren't available in all situations. But usually there are several selection techniques that can contribute to that good ordering desperately needed for an efficient A/B search.

Instead of applying these techniques in a particular order, think about the alternative of trying all of them simultaneously and taking a vote based on the results. Some techniques may be more reliable than others and perhaps these could be given extra weighting. The idea here is that the added time expense of running multiple ordering heuristics when less may be needed could provide an overall savings due to a higher quality consensus first choice.

Also, consider the case where all or nearly all of the techniques vote for the same move. In these cases, the strength of the consensus could be used to invoke forward pruning of the alternative moves at that node.

I think this is worth trying at the root. Particulary because there you have many "strategies". In other part of the tree people are doing similar things, right? hash table, many flavor of captures etc.

Miguel

[Bill Rogers]

I generate all moves at the root and each move is given positional point as well as capture points is a piece is captured. Then depending on the piece other points are given. After all moves are generated at the root I just sort them all and start with the one with the highest point score.
Basically this is the same way that Rebel works as I discovered later and it works very well.
Bill

[bob]

Voting techniques in move ordering

Consider that there are a half dozen or more traditional techniques for ordering selections in an A/B search. Some of these techniques only produce a single move, and some aren't available in all situations. But usually there are several selection techniques that can contribute to that good ordering desperately needed for an efficient A/B search.

Instead of applying these techniques in a particular order, think about the alternative of trying all of them simultaneously and taking a vote based on the results. Some techniques may be more reliable than others and perhaps these could be given extra weighting. The idea here is that the added time expense of running multiple ordering heuristics when less may be needed could provide an overall savings due to a higher quality consensus first choice.

Also, consider the case where all or nearly all of the techniques vote for the same move. In these cases, the strength of the consensus could be used to invoke forward pruning of the alternative moves at that node.

I'm not quite sure how you pull that off, but the idea sounds like modern branch prediction where the processor uses what is called "tournament branch prediction". The idea is that you use a global predictor which uses global branch history for all branches to predict any single branch, which detects branches that have a "correlated" behavior. And you use a local branch history to predict a branch based on its local history of being taken or not taken. And finally, you use a tournament predictor that tells you for each branch which predictor works overall for this particular execution of this program.

I suppose you could try that by counting cutoffs that result from each approach to move ordering, and dynamically adjust the order you apply the various selection ideas. However, I'd have a hard time imagining a reasonable case where one would find a better ordering than the tradtional hash move, non-losing captures, killers, and then the rest of the moves, although "the rest of the moves" might be open for some sort of improvement (try pawn pushes first, or moves closer to the king, or checks, or whatever one might want to try).

[sje]

Let's see what predictors we might have:

1) PV Move when following the PV
2) Transposition table move
3) Best non-losing capture
4) Most popular killer
5) Most popular reply to last move
6) Attack/capture of last piece moved
7) Best history scored move
8) Best continuation move (follows popular refutation variation)
9) Best centralizing move
10) Best king safety gain or opponent safety loss move

There's plenty more, just think of old MacHack's plausible move generator. So,

Step 1: Instrument a traditional A/B searcher to use all of these selectors and keep track of relative merit.

Step 2: Use the results to assign confidence weights to the selectors.

Step 3: Rerun with voting; consider a sufficiently high vote score as a basis for a forward prune or at least a depth reduction for any remaining moves.