Page 1 of 2

easy move?

Posted: Fri Oct 19, 2018 9:32 am
by flok
Hi,

I vaguely remember something about "easy moves". During iterative deepening it is decided that a move is easy and search time is shortened.
Googled it, could not find anything about it so does anyone know anything about this?

regards

Re: easy move?

Posted: Fri Oct 19, 2018 1:05 pm
by Robert Pope
I think it's something like, if the gain>X and the move has remained best for Y iterations, then stop early. I've never tried it, but I recall others saying it didn't really help. If it is an easy move, your advantage just grew, so saving a little time probably won't change the outcome. But it could be that the move can actually be refuted if you searched one ply deeper, and by stopping early, you are going with an inferior move.

I don't think it's possible to really know that a move is easy, even PxQ undefended, since it could just be the start of a deep sacrifice.

Re: easy move?

Posted: Fri Oct 19, 2018 1:43 pm
by elcabesa
Sometimes it happens that you use few time for an easy move, and this time give you very few additional time to every following move.
You can miss deep sacrifice giving few extra time to sequent moves. It's not clear if it's an advantage.

Re: easy move?

Posted: Fri Oct 19, 2018 3:41 pm
by flok
thanks everybody!

Re: easy move?

Posted: Fri Oct 19, 2018 4:59 pm
by Ras
I have an easy move detection that works as follows:

If the 1 ply pre-search with QS gives the top move at least +200 centipawns over the second best,
AND
if the top move is within a +/-50 centipawn window of the previous move turn,
AND
if the top move stays top until depth 6,

then it's an easy move. It usually comes in when the opponent takes a piece and there is only one way of recapturing.

If the opponent makes a sacrifice, it will fail the +/- 50 centipawns condition and trigger a full search.

The other "easy move" situation is of course when there is only one legal move.

Re: easy move?

Posted: Fri Oct 19, 2018 6:20 pm
by hgm
I guess one of the reasons people think that easy move is not worth it is that they only test in ponder-off games. Spending a lot of time on an easy move in a ponder-on game is giving the opponent free thinking time on a guaranteed ponder hit. Of course some variants have more easy moves than others.

In Shokidoki I consider a move easy if there is at least a 300cP gap between its score and that of the second-best move, in all iterations.

Re: easy move?

Posted: Fri Oct 19, 2018 6:34 pm
by Ras
hgm wrote:
Fri Oct 19, 2018 6:20 pm
I guess one of the reasons people think that easy move is not worth it is that they only test in ponder-off games.
For me, it was because it's simply annoying in actual human play when a trivial recapture doesn't happen promptly.
In Shokidoki I consider a move easy if there is at least a 300cP gap between its score and that of the second-best move, in all iterations.
How do you get the score for second best in ID? Do you always perform multi variant analysis? I think the second best (and all others) will just fail low after alpha has been established by the first move.

Re: easy move?

Posted: Fri Oct 19, 2018 7:06 pm
by flok
Ras wrote:
Fri Oct 19, 2018 6:34 pm
In Shokidoki I consider a move easy if there is at least a 300cP gap between its score and that of the second-best move, in all iterations.
How do you get the score for second best in ID? Do you always perform multi variant analysis? I think the second best (and all others) will just fail low after alpha has been established by the first move.
What about looking up all the other moves (besides the best move) in the transposition table?

Re: easy move?

Posted: Fri Oct 19, 2018 7:27 pm
by AlvaroBegue
flok wrote:
Fri Oct 19, 2018 7:06 pm
Ras wrote:
Fri Oct 19, 2018 6:34 pm
In Shokidoki I consider a move easy if there is at least a 300cP gap between its score and that of the second-best move, in all iterations.
How do you get the score for second best in ID? Do you always perform multi variant analysis? I think the second best (and all others) will just fail low after alpha has been established by the first move.
What about looking up all the other moves (besides the best move) in the transposition table?
No, that won't help. What Ras is pointing out is by the nature of alpha-beta search (and even more so NegaScout or PVS), the only thing we learn about other moves is that their scores are not better than the score of the best move, but we don't know by how much. Of course one could do additional null-window searches to establish the 50cp difference. At depth 6 this isn't very costly at all.

My old program Ruy-López had an easy-move heuristic, where I established the difference in score was large at depth 1, and then I would remove the easy-move flag if another move became best at any time. The effect of the flag was allowing only a small fraction of the usual time per move to be spent (1/20th, I believe). In some versions I think I also required that some large fraction of the search time was being used in the first move (meaning that it's easy to prove the other moves are inferior).

However, in my newer program RuyDos I don't do this. That's because Ruy-López would clear the hash tables between moves, and then the checks I described above make sense. In RuyDos the hash table is not cleared between moves, which means I don't gain any information about how consistent the results of the searches at different depths are, because all the low depth searches get short-circuited by hash-table data.

Re: easy move?

Posted: Fri Oct 19, 2018 8:20 pm
by D Sceviour
Rather than looking for easy moves to reduce time, instead try adding more time for difficult positions. For each root PV change per iteration, add an incremental time step.