Author |
Topic: Changing your mind and managing your time (Read 2791 times) |
|
Oystein
Forum Full Member
Arimaa player #3272
Gender: 
Posts: 21
|
 |
Re: Changing your mind and managing your time
« Reply #15 on: Jan 6th, 2009, 4:06am » |
 Quote  Modify
|
on Jan 6th, 2009, 1:25am, 99of9 wrote:| That's not quite true, Jeff is right that even incomplete iterations can be very useful. Unfortunately Gnobot can only make use of complete iterations, hence the time control. If it were able to use incomplete ones, then I agree with Jeff it would probably just be better to use the whole time. |
|
If you already has spent time on an incomplete search, it is of course best to use that information. What I mean is that it is better to save the time until you have enough to do a complete iteration. I assume that 5 seconds used on a complete iteration is worth more than 5 seconds on an incomplete. If anyone has made a test to show otherwise, I would be pleased to know. Hopefully I would be able to test things like this myself, but currently my engine is not good enough to make any test worth the work.
In an incomplete iteration, we only know what the best move among the finished moves are. If this is the best move from previous iteration, we havent gained anything. If not, it is quite likely we havent got to the best move yet. This is why I think time spent on an incomplete search is worth less. Perhaps a hybrid depth would work: When it becomes clear that the current iteration cant be finished on time, reduce the search depth for the remaining moves.
|
|
 IP Logged |
|
|
|
jdb
Forum Guru
Arimaa player #214
Gender:
Posts: 682
|
|
Re: Changing your mind and managing your time
« Reply #16 on: Jan 6th, 2009, 10:16am » |
Quote Modify
|
Assumptions:
1) the first move searched on an iteration is the best move from the previous iteration.
2) there is a nominal time to search per move and a reserve time that is available for use in special situations.
In an incomplete iteration, in addition to knowing what the best move is for the iteration, we also know the score of that move. If the score has dropped a large amount, when compared to the score of the previous iteration, we already have enough information to know we are in big trouble and should use up some reserve time to try and find a better move.
|
| « Last Edit: Jan 6th, 2009, 10:18am by jdb » |
IP Logged |
|
|
|
Fritzlein
Forum Guru
Arimaa player #706
Gender:
Posts: 5928
|
|
Re: Changing your mind and managing your time
« Reply #17 on: Jan 6th, 2009, 4:07pm » |
Quote Modify
|
I just re-read the link from my first post in this thread. According to Newborn's hypothesis, the increase in playing strength that accrues from searching an additional ply is proportional the probability that the bot will change its mind at that ply.
To apply Newborn's hypothesis to time management, it would be convenient to know (A) how long the next iteration will take to complete, and (B) how likely is the bot to change its mind on the iteration. Then B/A is the value of doing that iteration.
One application of this is the one I had in mind starting the thread, i.e. that perhaps B is very high for depths 4, 8, 12, etc., so those should be searched if possible.
A second application is jdb's insight that B is very high if searching the best move from the previous iteration produces a lower value.
A third application might be to have some measure of how sharp/volatile the position is, and suppose that B is higher in such positions, thus they should be searched more deeply.
Looking at it now, though, it strikes me that A, the time to search another iteration, seems to increase by a factor of two or three per step of depth. Another iteration won't be worth it unless B is two or three times higher than normal, and two more iterations won't be worth it unless B is four or nine times higher than normal.
Looking at the bottom half of the ratio, namely the time invested, makes it seem like the best policy is essentially going to be using the same amount of time on every move.
|
| « Last Edit: Jan 6th, 2009, 4:09pm by Fritzlein » |
IP Logged |
|
|
|
99of9
Forum Guru
Gnobby's creator (player #314)
 
Gender:
Posts: 1413
|
|
Re: Changing your mind and managing your time
« Reply #18 on: Jan 6th, 2009, 9:03pm » |
Quote Modify
|
on Jan 6th, 2009, 12:29am, Oystein wrote:Just a little observation:
Same first move, but different order of the steps. Normally this would not happen because of the transposition table. |
|
Thanks to your little observation, I have found numerous bugs that I introduced when I originally wrote the move ordering code. On this position I now get to 12 ply in 173 sec (45% saving), and on my overall test database I get a 26% time saving. Pleasingly I now have to renew my test database, because it is now running too quickly to give tournament-relevant results!!
Thanks again for spotting it.
|
|
IP Logged |
|
|
|
|
Home
Help
Search
Members
Login
Register
Reply
Notify of replies
Send Topic
Print