Move filters: how engines decide which plays to search

#Why engines prune

A typical roll has around twenty legal plays, and most of them are obviously bad. Searching every one of them at depth wastes nearly all of the work, since each extra ply multiplies the cost by about twenty. So engines rank every play with the quick network evaluation first and spend the deep search only on the plays that might be best. The rule that decides which plays survive is called a move filter.

A filter never makes the engine play better. Its only question is how often it throws away the play the full search would have chosen, and what that costs. Every number in this article is measured that way: the filtered choice against a search of every play, on thousands of decisions from engine self-play, with the cost given in equity per decision. Only the filter on the plays at the root of the decision changes; the search below each play keeps HedgeHog's usual pruning, described at the end.

#What the reference engines do

Both reference engines publish their filters.

GNU Backgammon's move filters set one filter for each search depth, with one step for each ply on the way down. In its current development version, the Normal filter at its 1-ply (HedgeHog's 2-ply) keeps up to 12 plays within 0.24 of the best. At its 3-ply it keeps 16 plays within 0.32 after the network evaluation, then 8 within 0.16 after 1-ply, then 4 within 0.06 after 2-ply, and searches those 4 at the full depth. The 1.08 release, which most players run, is narrower: it keeps 8 plays within 0.16 after the network evaluation at every depth, and at its 3-ply only 2 within 0.04 after 2-ply. Where this article says GNU Backgammon's filter, it means the development version's.

eXtreme Gammon's search interval works the same way. At 3-ply on its Normal setting, all plays are evaluated by the network, up to 8 within 0.160 of the best are searched at 2-ply, and up to 4 within 0.080 of the new best are searched at 3-ply. The Large, Huge and Gigantic settings multiply every count and threshold by 1.5, 2 and 4. eXtreme Gammon's own study puts the cost of the Normal setting at under one Elo point against searching all of the top 32 plays at full depth.

Each step has three settings: how many plays to keep at most, how far behind the best a play may be and still be kept, and, in GNU Backgammon's version, how many plays to keep unconditionally whatever their distance.

#Ladders

The important word is ladder. Each step ranks the survivors at its own depth, so a strong play the network ranks too low can move up at a shallower search before the deepest one is spent.

We measured what that buys at 3-ply with Fox (version 0.34, the one used throughout this article), one of HedgeHog's networks, over 1200 decisions against a search of every play:

The ladder is about nine times faster than searching everything. Skipping its middle step saves no time and gives up nearly twice as much; matching the ladder's quality without the middle step costs about twice the time. The middle step is cheap because a 2-ply search costs about a hundred-and-fiftieth of a 3-ply one, so ranking a dozen plays at 2-ply is nearly free next to searching even one of them at 3-ply.

#A filter is only as good as the network

A filter trusts the quick evaluation to put the best play somewhere near the top. Whether it does depends on the network. At 2-ply, keeping up to 8 plays within 0.16 (eXtreme Gammon's first step), over 4000 to 8000 decisions per network:

Xerxes is the network HedgeHog's server analysis uses by default. It has the same shape as eXtreme Gammon's networks, four specialised networks with one hidden layer each, and it is close to eXtreme Gammon in how it plays and judges positions, so it shows how the search interval behaves on the kind of network it was designed for.

With the strongest networks, this filter is close to free. With the weakest one it throws away the 2-ply search's best play once in fifty decisions, sometimes by a blunder's worth. These are the plays the network ranks badly and a deeper search ranks first, which are exactly the plays the deeper search was paid for. If a network's quick ranking and its deeper ranking often disagree, the filter has to be wider.

Xerxes sits in between, and at 3-ply that shows. Over 480 decisions, each ladder against a search of every play:

Nearly all of the search interval's cost is one decision in 480: a play outside the network's top 8 that the 3-ply search rates best by 0.042. GNU Backgammon's wider first step keeps it. That is exactly the kind of miss a wider first step exists to prevent.

#How far pruning can be pushed

The search interval on Xerxes costs about 0.0001 per decision, the same order as eXtreme Gammon's own study reports for its networks. Taking that as a budget, we asked how hard each of HedgeHog's strongest networks can be pruned before it costs more. We recorded every play's value at every depth for 8000 decisions per network, then scored hundreds of filters against the same decisions.

At 2-ply, a single filter step after the network evaluation:

Both published settings are one and a half to three times more cautious than these networks need to stay inside the budget. A margin is worth keeping, since a budget-limit filter measured on 8000 decisions could be over it on the next 8000: with a filter one notch wider (6 plays within 0.06 for Fox, 5 within 0.05 for Aureus, 6 within 0.12 for e32ds3) the average stays inside the budget even at the top of its statistical range, and the speed is still 6 to 9 times a full search.

Three patterns held for every network:

• A count and a distance together beat either alone. Keeping only the top few plays, however close the rest are, was at best 5.5 times faster within the budget. Keeping only the plays within a fixed distance, however many there are, was at best 6 times faster. Combining the two gets 6.7 to 10.3 times: the distance throws out the plays that are clearly worse, and the count caps the cost when many plays are close.
• The better the network, the tighter the distance. Aureus and Fox are best served by keeping only plays within 0.04 to 0.06 of the best. e32ds3, whose quick ranking agrees with its 2-ply search less often, needs 0.12.
• The average hides a few large misses. Even inside the budget, the cheapest filters still lose 0.020 or more on 5 to 11 decisions in 8000.

At 3-ply the cheap 2-ply step does most of the work, because searching a play at 2-ply costs about a hundred-and-fiftieth of searching it at 3-ply. Over 900 to 2000 decisions per network, a two-step ladder:

The pattern is the same for all three: keep a generous set at 2-ply, where the search is almost free, then send only two to four plays to 3-ply. Going from the network straight to 3-ply, with no 2-ply step, was never better than 7 to 10 times faster within the budget.

These 3-ply samples are too small to promise the budget with statistical margin. A single miss of 0.03 moves the average of 1000 decisions by 0.00003, so a setting for real use should sit a notch wider than the cheapest one here.

#Keeping the top two no matter what

That last point has a cheap remedy. Keeping the network's top two plays unconditionally, and filtering only the rest, removes most of the large misses for a modest price. For Aureus, 5 plays within 0.05 with the top two always kept is 6.9 times faster than a full search, costs 0.000034 per decision, and lost 0.020 or more on a single decision in 8000, against four without it. For Fox, 8 plays within 0.06 with the top two kept is 5.8 times faster and lost 0.020 or more twice, against six. Whether that trade is worth it depends on whether the average or the worst case matters more, and for analysis that reports blunders the worst case usually does.

At 3-ply the same trick applied to the second step, always sending the top two plays at 2-ply on to 3-ply, costs a sixth to a third of the speed. It removed the large misses for e32ds3 (none of 0.020 or more in 2000 decisions, against three without it) but not for Fox or Aureus.

#Pruning inside the search

Everything above is about the plays at the root of a decision. Inside the search every engine prunes again, at each turn of lookahead, and that is where most of the work of a deep search goes.

• GNU Backgammon runs a two-step ladder at every node and is the most aggressive. For each roll it ranks every reply with a small, fast pruning network, keeps the best 5 plus a few more for a roll with many legal plays (about 9 of 20), re-scores those with its full network, and searches only the single best reply deeper.
• HedgeHog's engine keeps more. At the first turn of lookahead it searches up to 16 replies within 0.32 of the best, the top 4 always; one turn deeper, up to 6 within 0.12; deeper still, up to 4 within 0.06. In deep searches it also searches the later replies one ply shallower and, when such a shallow search says a reply beats the best found so far, searches it again at full depth, so a reply that turns out better than it looked gets its full search back.
• eXtreme Gammon applies its search interval at every level of the search, not only at the root. The appendix of its study gives the ladder for each level, from 3-ply up to its rollout levels: at 4-ply on Normal, 16 plays within 0.32 at 2-ply, then 8 within 0.16 at 3-ply, then 4 within 0.08 at 4-ply.

At 2-ply the three nearly agree, because the reply to each roll is judged by the quick evaluation anyway; GNU Backgammon differs only when its pruning network drops the reply its full network would have picked. From 3-ply on they diverge, and the pruning inside the search matters more than the filter at the root.

#What to take from it

• The published defaults are safe and slow for strong networks. With Fox or Aureus, a filter two to three times tighter still stays within what eXtreme Gammon's own Normal setting costs.
• Tune the filter to the network, not the other way round. The same filter costs five times as much on one network as on another.
• Keep the top two when blunders matter. Against the cheapest filter inside the budget it gives up about a third of the speed (10.3 to 6.9 times a full search for Aureus, 8.5 to 5.8 for Fox) and removes most of the large misses.

Move filters matter most in rollouts, where every move of every game is a decision: Rollout settings shows how they combine with deeper first moves and a first-move cache.