Author: Don Dailey
Date: 19:51:49 12/08/97
Go up one level in this thread
On December 08, 1997 at 21:27:11, Robert Hyatt wrote: >On December 08, 1997 at 18:15:37, Don Dailey wrote: > >>On December 08, 1997 at 15:33:50, Robert Hyatt wrote: >> >>>On December 08, 1997 at 13:23:51, John Bartkiw wrote: >>> >>>>Just a quick question on how to decide how long to search on a certain >>>>move in a game. Specifically in a sudden death time control. I can see >>>>if you have a 40/2 time control you can just simply see how much time is >>>>left till the control and divive it by how many moves left until the >>>>control. But what do you do in a G/x situation? >>> >>>easiest answer is to search for "remaining_time/N" where N is some >>>constant. I use something like 25 I believe... which gives a steadily >>>decreasing amount of time, but will *never* run out of course, although >>>it can decrease to a fraction of a second if the game is a couple of >>>hundred moves long... >> >>Yes, this is a generally acceptable way to do it. I believe there is >>probably a better algorithm though. At the Dutch championship our >>program in one game predicted the opponents move so often that even >>after 40 or 50 moves we had 45 minutes left and our opponent was in >>time pressure. I feel like we did not utilize our time wisely. In >>other games we were pushing it and had utilized almost all our time >>by the time the game ended. >> > >this can be a problem. IE I have fudged around with this number quite a >bit over time. At times you end up with too much time left. At other >times, you end up with too little time left. More on what I do later... > > >>Consider: >> >>If you are on move 10, how many more moves do you expect to play on >>average to complete the game? Is it the same if you are move 70? >>At move 10, >>we might expect the game (on average) to last about 30-40 more moves. >>But this is probably not a wise assumption at move 70. I believe a >>better algorithm (to squeeze the maximum strength from a chess program) >>is to change N in Bob's formula above as the game progresses. I >>use the same formula Bob suggested but he doesn't actually say he uses >>the algorithm in this form. > > >I do, although I also carefully watch the other person's time, and try >to >not get too far behind them, because if I do, I'm likely going to get >blitzed >out in the endgame and lose that way... > > > >> >>If you use 25 according to Bobs formula, you are saying (sort of) that >>you believe >>or estimate the game to last about 25 more moves. But not really, >>because >>you are also expecting to predict a few moves and play the first few >>moves from the opening book. So 25 is probably just about the right >>number (we happen to use 30 in Cilkchess which is probably on the >>conservative side.) > >interesting. :) I used 30 until about 3 months ago, but had too many >people pointing out that in sudden death games (which I play a >tremendous >number of on ICC) I was ending up with too much time. 25 doesn't seem >too bad either... and, in reality, it might could go a little lower, >since >I take pains to not get too far behind on time as well.. > > > >> >>So the idea I propose (and maybe others use something like it) is to >>start N at something like 30-35 and slowly decrease it to something >>between 15 and 20. I believe it's basically correct to have used >>the vast majority of your time at move 40-50. It's probably not wise >>to make N too small though since where the game actually ends is always >>in doubt. In the game I mentioned, we should have >>been using much more time at move 40 than we did. I might add that >>we did happen to win the game but this is beside the point, our program >>was playing 50 to 100 rating points weaker at move 40 than it should >>have simply because we were not utilizing our time. >> >>Now someone might argue that if the game ends up being long, you will >>be playing a weak endgame since you will have little time left. Of >>course this will happen but the real issue is how you distribute the >>time and where you want to maximize your strength. It's basically >>a gamble, and you should put your money where the action is! You could >>play very quickly early on and then play very strong endgames but I >>argue >>that your endgames BETTER be strong in this case since you will >>probably end up in a lot of bad ones due to hasty play early in the >>game! >> >>I'm interested in other ideas for better game/X time controls. >> >>Don > >I have some code we played with a year ago, primarily written by Mike >Byrne, >that is *very* cute. It monitors what the opponent is doing, and if the >opponent moves quickly, it tends to speed up. If the opponent takes a >long >think, it does too to find out what it was that probably made them fail >low. >It also understands "instant moves" by pondering that the opponent can >sometimes >play, and, in general, really was real cute... Sounds pretty interesting. I'm a little skeptical about trying to second guess what might be going on but perhpas it has merit. But anything that attempts to break the vicious cycle of being on the wrong end of the "toot" game might be worth looking at. Another idea I have, is simply to force the program to stay on the 1/30 or 1/25 schedule (or whatever you choose.) We assume no toot'ing and no book moves and lay out the "schedule" in advance at the beginning of the game based on the time control that is set. As we build up time from toot'ing and book moves, we aggressively adjust our schedule to eat this time up quickly, I propose adding something like 1/5 of our "extra" time to try to get back on schedule. If we go into overtime we also try to recover fairly quickly by subtracting from our search goal time. This will keep us close to what we think is a reasonable schedule. We of course can play with the 1/30 and 1/5 factors to find reasonable numbers. I suspect this algorithm is a decent improvement over the dumb one I use now since it makes an intelligent attempt to factor in the increasing expectancy of the game to end as the number of moves increase. The algorithm I now use randomly extends this expectancy depending on how many moves it happens to predict correctly for the toot search. An improvement to this might be if you could find a way to estimate the expected game length based on the nature of the position! This sounds speculative but perhaps there are things that can be done. -- Don
This page took 0 seconds to execute
Last modified: Thu, 15 Apr 21 08:11:13 -0700
Current Computer Chess Club Forums at Talkchess. This site by Sean Mintz.