Fastest first search

[MikeG]

I was wondering if anyone has tried the "fastest first" search trick, which has been used in othello, with computer chess.

The idea has been used to significantly speed up othello endgame solvers. For example see:

http://radagast.se/othello/ also http://ijcai.org/papers09/Papers/IJCAI09-089.pdf

The idea is simple - if we are at an expected cut node, but there is *also* a high probability that *more* than one move that will fail high, we should chose the move which minimizes the opponents mobility. Under the right circumstances maybe this could also speed up chess search (?)

I implemented this in my othjello endgame solver by doing the usual pre-sort with shallow evals, and re-ordering by mobility only the moves which were above some standard threshold - but the eval was re-ordered primarily by mobility. Something like: if (mv.eval > thresh) mv.eval_with_mob = mv.eval + opponent.mob*1000; // now re-sort on mv.eval_with_mob

I think speedups were on the order of 10 to 30% depending on position.

It does seem risky to not always search thehighest eval move from pre-sort, or possibly even the hash move first for example - but think this might be worth the risk in the right situation, such as when the opponent has already played a "desparate" move and we have multiplemvs that fail high.

Although it works with othello endgames, it could be that mobility differences are more of a factor there than in chess. But I still wonder if anyone has already tried this, or maybe would like to try it .

(Edited for typos)

[hgm]

In Chess mobility and eval are much more correlated than in Othello. The best way to reduce the opponent's mobility is to capture his most powerful piece. Which is also what you would do from the eval perspective.

[MikeG]

Maybe, but I still would be interested to see if this has been tested already. I would guess that if there is any improverment in chess would be much lower than for othello. But I wonder how often material is traded down with advantage - perhaps always?

Another more subtle way to reduce mobility might be to close the position for ex. with pawn pushes.

Any other opinions on this?

[hgm]

The way most engines work now is first go for null move (because of the depth reduction associated with it, this seems to be always cheaper, even if the alternative is capturing a hanging Queen), and then for the captures. If the null move does not do it, either you are already too much behind, so that a capture is necessary (and there usually isn't a whole lot of choice there), or there is a specific threat (where again, there are not too many moves that solve it).

[Uri Blass]

In Chess mobility and eval are much more correlated than in Othello. The best way to reduce the opponent's mobility is to capture his most powerful piece. Which is also what you would do from the eval perspective.

I think that threating the opponent king is the best way to reduce the opponent's mobility but I think that searching checks first is not a good idea because programs extend checks and it means that they will need to search bigger trees.

In other words if you want to search smaller trees then trying to reduce the opponent mobility is not a good idea even if you fail high

I think that starting from the best move is better because later programs use reductions and pruning based on evaluation so they can search smaller trees.

Uri

[MikeG]

"...In Chess mobility and eval are much more correlated than in Othello"

Thiking about this, I'm not certain that this is true. Mobility is very important in othello and most evals tend to key on it. Yet, the fastest first trick produces significant gains anyway.


"...In other words if you want to search smaller trees then trying to reduce the opponent mobility is not a good idea even if you fail high "

? This statement seems opposite common sense for a generic search tree (although, in the examples for checks or NULL move I could see how things get messy). But not all moves that produce cuts are captures, checks or NULL moves are they? Maybe someone knows %?

Suppose black has just sacked his queen on e6. White has two ways to fail high, each is a pawn capture (from d5 or f5).

The capture with the f5 pawn opens up the f file for blacks f8 rook. The other caputure results in less mobility for oppoent (or even both sides). If both resulting positions are "quiet" it is possible it is worth doing the work to find smaller branch.

Regarding the eval - I'm not sure that a good eval is going to always drive the opponents mobility down. I would think it might drive the mobility *difference* down, which is not quite the same thing. If in the example above, if the extra mobility of a rook on f8 is counterbalanced with a white rook on f1, an eval might not see a reason not to capture with the f pawn. Result is a somewhat larger tree to search.