Possible search improvment

[Suji]

I'm wondering if there is a way to improve searching by somehow excluding moves that are calculated to be bad. Maybe at some point, say depth 10-12 we take only our top ten moves, and we search them for our remaining depths until our time allotted for the move runs out.

You could then search the top moves deeper, most likely out searching your opponent.

I'm wondering if this would work at all.

[Ryan Benitez]

You mean like history leaf pruning or more like many shallow searches to exclude moves like probcut? Both ideas that are used by engines today with good results.

[hgm]

The problem is that it hardly takes any time to search moves that really are bad. And sometimes a move that looks really bad at 12 ply turns out to be a brilliant sacrifice at 13 ply...

[MattieShoes]

I'm wondering if there is a way to improve searching by somehow excluding moves that are calculated to be bad. Maybe at some point, say depth 10-12 we take only our top ten moves, and we search them for our remaining depths until our time allotted for the move runs out.

You could then search the top moves deeper, most likely out searching your opponent.

I'm wondering if this would work at all.

It'd work, just not as well as one would hope. What you're talking about is a form of forward pruning, and a fairly aggressive one. What's more typically done is to do a less comprehensive search of moves likely to be bad rather than pruning them entirely. This is done via Null Move pruning and LMR.

The other reason this doesn't work as well as one would hope is because the majority of the time spent is searching the first (hopefully best) root move at a given depth. Once it's done this, it simply has to prove the others are worse rather than finding an exact score for them. This takes much less time. So pruning away 3/4 of the root moves doesn't save you 3/4 of the time, and it hurts your chances for finding tactics on moves you never bothered to search.

[hgm]

So in practice it doesn't work at all, unless you consider a severe drop in Elo "working". Skipping the moves does not save you enough time to decide between the remaining moves significantly better, and now and then your engine will bungle a game because it fails to find a good sacrifice, or a miraculous escape.

[MattieShoes]

Right, sorry. When I said works, I meant forward pruning in general can be a winner. This particular incarnation of it would be a net loser in chess

[Suji]

The problem is that it hardly takes any time to search moves that really are bad. And sometimes a move that looks really bad at 12 ply turns out to be a brilliant sacrifice at 13 ply...

Yes, I could see that happening. What if we optimized the depth so that this couldn't happen? Is it possible to do such a thing?

[Suji]

If you have good move ordering, wouldn't the tactics all be near the top end of the search anyway?

[jwes]

If you have good move ordering, wouldn't the tactics all be near the top end of the search anyway?

How would your move ordering algorithm distinguish between apparently bad moves and really bad moves without searching deep enough to see the point?

[Edmund]

If you have good move ordering, wouldn't the tactics all be near the top end of the search anyway?

The standard move ordering applied in most engines works fine for the average positions, but you can't expect it to find all tactics. These are usually left to the search.

And as hgm already pointed out, it takes hardly any time to refute a bad move. Alpha Beta Search already works in a way that it concentrates only on good lines and just refutes bad ones. Eg. If one side looses the queen, move ordering is very easy because almost any move will be good enough to prove that the opponent won't be able to reach the score possible without loosing the queen.