Time Management and Move Selection

Discussion of chess software programming and technical issues.

Moderators: hgm, Harvey Williamson, bob

Forum rules
This textbox is used to restore diagrams posted with the [d] tag before the upgrade.
User avatar
Steve Maughan
Posts: 1056
Joined: Wed Mar 08, 2006 7:28 pm
Location: Florida, USA
Contact:

Re: Time Management and Move Selection

Post by Steve Maughan » Thu Jul 26, 2018 11:32 am

I believe Ed Schroeder did something similar in his engines. You might also look in the hash table to see if the candidate for a single move was an exact match with sufficient search depth.

Steve
http://www.chessprogramming.net - Maverick Chess Engine

odomobo
Posts: 59
Joined: Thu Jul 05, 2018 11:09 pm
Location: Chicago, IL
Full name: Josh Odom

Re: Time Management and Move Selection

Post by odomobo » Thu Jul 26, 2018 1:16 pm

bob wrote:
Wed Jul 25, 2018 3:01 am
... if you don't change your mind after an iteration ends, you can reduce the target time a bit. Every time you complete without a change, reduce further. Any change to a different move resets to original target time or even longer to make sure you are not making a mistake.
Steve Maughan wrote:
Thu Jul 26, 2018 11:32 am
You might also look in the hash table to see if the candidate for a single move was an exact match with sufficient search depth.
I think without Steve's suggestion, if you don't clear the transposition table between searches, you'd accidentally flag a lot of moves as being easy moves (false positives), just because the info is already in the transposition table. I think this would especially happen if the other strong candidate root moves were also in the transposition table (so there's no chance for one of them to raise alpha).

On the other hand, with this suggestion (and with a transposition table with a depth-preferred strategy), it should be very hard to ever find an easy move. Let's say for given game, your average search is to depth 20. That means that the only real searches are for depth 19 and 20 (since 1-18 would have used the prior TT entries, and not contribute any "easy move" confidence).

Does this sound right? Is there a workaround for this issue?

bob
Posts: 20369
Joined: Mon Feb 27, 2006 6:30 pm
Location: Birmingham, AL

Re: Time Management and Move Selection

Post by bob » Tue Aug 14, 2018 8:52 pm

My current "easy move" approach is really just a "easier/harder" approach. If things are stable, the situation looks "easier". If things are unstable, the situation looks "harder". That degree of stability can make the search move significantly faster, or significantly slower. Very "un-computer-like" in that there are not any sequences of moves where Crafty takes the same amount of time for all of them. Sort of changes the time usage to something that is more human-like although that was not the intent. The intent was to try to use the time where things are unclear and more time might lead to a better move...

It is reasonably complex in that multiple best move changes in a single iteration will make the move look much "harder" and therefore burn more time. I am also concerned with fail highs as while they are sometimes good, they are sometimes an indication you might be stumbling into something that is not really there. Anything unusual always ends the "easier" part of this at the very least, and can trickle over into the "harder" part depending on what happens and for how long it happens.

Pio
Posts: 116
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Time Management and Move Selection

Post by Pio » Tue Aug 14, 2018 10:24 pm

odomobo wrote:
Mon Jul 09, 2018 11:08 pm
I've been thinking about the following, and was wondering if there are some practices for them. My questions are specifically with regards to alpha-beta search.

What's the best approach to finding singular best moves -- that is, when there's only one good move? For example, when your opponent initiates a queen trade, and there are no good zwischenzugs. Obv. under a fail-hard system, you'll never know how much worse your alternatives lines are to the PV. My idea was to allocate a small fraction of the search time (maybe somewhere between 1 and 10%) to search for such a move, by setting alpha = PV score - margin (maybe 200 cp). If no alternative line is able to raise alpha by the end of the singular move search, then return PV as the best line.

Is it safe to use a move which raises alpha over the PV, but before the search at that depth is finished? That is, when a non-PV move raises alpha just before we run out of time. I understand that if the PV lost value vs the previous search depth, that it makes sense to allocate extra "panic" time to find a good move (since we have been working with incomplete information up to this point). But what about the case where the PV score stayed nearly the same? Logically, I think it should be safe to use the new move, since we are using the best information we have, but intuitively I feel like there might be some mistake in doing this.
Hi, if you save number of positions searched for every position next to root, I think you would get a quite good measurement of how easy the root PV-move is. If the node count of one of the positions next to root (that is not the PV root move) with the highest node count is significantly lower than the Node count of the PV root move it means that the refutation trees are small and the PV can be trusted. The ratio between PV root move node count and the other root moves should be depth dependent since a deeper search should normally increase the ratio since you would have a higher confidence in the PV, thus searching even deeper there. Another good thing about this method is that when the method fails it means that the alternative solution will take a lot of time to resolve and might not be able to finish.

Pio
Posts: 116
Joined: Sat Feb 25, 2012 9:42 pm
Location: Stockholm
Contact:

Re: Time Management and Move Selection

Post by Pio » Tue Aug 14, 2018 10:49 pm

odomobo wrote:
Mon Jul 09, 2018 11:08 pm
I've been thinking about the following, and was wondering if there are some practices for them. My questions are specifically with regards to alpha-beta search.

What's the best approach to finding singular best moves -- that is, when there's only one good move? For example, when your opponent initiates a queen trade, and there are no good zwischenzugs. Obv. under a fail-hard system, you'll never know how much worse your alternatives lines are to the PV. My idea was to allocate a small fraction of the search time (maybe somewhere between 1 and 10%) to search for such a move, by setting alpha = PV score - margin (maybe 200 cp). If no alternative line is able to raise alpha by the end of the singular move search, then return PV as the best line.

Is it safe to use a move which raises alpha over the PV, but before the search at that depth is finished? That is, when a non-PV move raises alpha just before we run out of time. I understand that if the PV lost value vs the previous search depth, that it makes sense to allocate extra "panic" time to find a good move (since we have been working with incomplete information up to this point). But what about the case where the PV score stayed nearly the same? Logically, I think it should be safe to use the new move, since we are using the best information we have, but intuitively I feel like there might be some mistake in doing this.
Hi, Maybe you can try to extend the time if the given PV move is irreversible like a pawn move or castling since the possible damage caused by such a move is also irreversible. If the PV move will lead to draw, there is no loss searching the alternative moves until the end. Of course if you find a slightly better move, you will have to consider if the time left compared to the opponents time left is enough to justify the risk. If you have found out that you lose one not so nice strategy could be to wait until the end of the game to move, hoping the opponent will crash or lose the connection, but I guess most people will not like you then. Another consideration of how much time you should allocate should be the time control and if you have table bases. The longer the time control the more time should be allocated for the beginning of the game. The same should be done if table bases are used. If the PV will lead to a big simplification, you should also spend more time here. Of course the PV moves closer to the root should be trusted more doing so.

Post Reply