Re: [computer-go] Allocating remaining time
It seems important to have some way of measuring how good / settled the current best move is, particularly if you're also going to think in your opponent's time. Otherwise, you could end up spending significant amounts of allocated time when, for example, a sequence of forced moves is being played out and little thinking time is actually required. I'm not sure of the technical details, but I would have thought that UCT would provide a good estimate of how confident it is that it has found the best move that it's ever going to find. Oliver On 1/6/07, Eduardo Sabbatella Riccardi [EMAIL PROTECTED] wrote: Hello, I was thinking about this a few days ago and I decided I will try the following: When the engine is searching for best moves there is a game path of 3, 4 or up to 10 moves that the engine have found to be the best moves so far. 0) Before start the search, based on total available time, and current move, engine will decide Tmin time and Tmax time based on some static function. 1) Engine will run for Tmin ms. 2) if game path have not changed in the last n ms, search is finished. (n = Tmax-Tmin / c ) 3) if game path changed, it will extend the search for n ms. 4) if total time exceeds Tmax ms. Search is finished. I think its usefull to avoid local maximums that can be hard to avoid, perhaps next move is easier to get a better move, so it worths to spend more time on next move as its value/time ratio is better. My 2 cents. Eduardo PS: Definitely I will spend more time on first moves as they decide the rest of the game. On Thursday 04 January 2007 06:04, Peter Drake wrote: How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Allocating remaining time
My program does this to an extent - it's time control is based on an aggressive percentage of the remaining time but it is modified by other factors. It has the interesting characteristic that it can get into time trouble! I think a really good time control must get into trouble once in a while (but only rarely) - if it's not getting into trouble it's not using all it's time.You have to play the odds a bit because you are dealing with uncertainty. - Don On Mon, 2007-01-08 at 13:55 +, Oliver Lewis wrote: It seems important to have some way of measuring how good / settled the current best move is, particularly if you're also going to think in your opponent's time. Otherwise, you could end up spending significant amounts of allocated time when, for example, a sequence of forced moves is being played out and little thinking time is actually required. I'm not sure of the technical details, but I would have thought that UCT would provide a good estimate of how confident it is that it has found the best move that it's ever going to find. Oliver On 1/6/07, Eduardo Sabbatella Riccardi [EMAIL PROTECTED] wrote: Hello, I was thinking about this a few days ago and I decided I will try the following: When the engine is searching for best moves there is a game path of 3, 4 or up to 10 moves that the engine have found to be the best moves so far. 0) Before start the search, based on total available time, and current move, engine will decide Tmin time and Tmax time based on some static function. 1) Engine will run for Tmin ms. 2) if game path have not changed in the last n ms, search is finished. (n = Tmax-Tmin / c ) 3) if game path changed, it will extend the search for n ms. 4) if total time exceeds Tmax ms. Search is finished. I think its usefull to avoid local maximums that can be hard to avoid, perhaps next move is easier to get a better move, so it worths to spend more time on next move as its value/time ratio is better. My 2 cents. Eduardo PS: Definitely I will spend more time on first moves as they decide the rest of the game. On Thursday 04 January 2007 06:04, Peter Drake wrote: How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Allocating remaining time
Hello, I was thinking about this a few days ago and I decided I will try the following: When the engine is searching for best moves there is a game path of 3, 4 or up to 10 moves that the engine have found to be the best moves so far. 0) Before start the search, based on total available time, and current move, engine will decide Tmin time and Tmax time based on some static function. 1) Engine will run for Tmin ms. 2) if game path have not changed in the last n ms, search is finished. (n = Tmax-Tmin / c ) 3) if game path changed, it will extend the search for n ms. 4) if total time exceeds Tmax ms. Search is finished. I think its usefull to avoid local maximums that can be hard to avoid, perhaps next move is easier to get a better move, so it worths to spend more time on next move as its value/time ratio is better. My 2 cents. Eduardo PS: Definitely I will spend more time on first moves as they decide the rest of the game. On Thursday 04 January 2007 06:04, Peter Drake wrote: How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ __ Preguntá. Respondé. Descubrí. Todo lo que querías saber, y lo que ni imaginabas, está en Yahoo! Respuestas (Beta). ¡Probalo ya! http://www.yahoo.com.ar/respuestas ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
[computer-go] Allocating remaining time
How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Allocating remaining time
On Wed, 2007-01-03 at 22:04 -0800, Peter Drake wrote: How much time should a program spend on each move? If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. Excellent question. I think this really is a reasonable choice. I did a LOT of tests to determine this and it makes sense to front load quite heavily. I used a constant, I did not try to estimate how many moves might be left. If you use t/m you really should make m much smaller than the number of vacant points left. It's not a waste to spend a lot of time on early moves. From casual observation, I noticed that most games were decided very quickly, after just a few moves in 9x9. Another reason to front load is that the game gets easier and easier to play correctly as more stones get placed. It's a matter of concentrating the most energy where it's needed. My program notices when the game is pretty much a forgone conclusion and when this happens it plays even faster - I do this so that I can be even more aggressive about earlier moves. In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) You should test all of this. That's what I do. I think self-testing of different formula's and constants is fine for this kind of thing. It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? Peter Drake Assistant Professor of Computer Science Lewis Clark College http://www.lclark.edu/~drake/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/ ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] Allocating remaining time
How much time should a program spend on each move? I think this is one of the most important and also difficult questions in game programming. Much effort is done to speed up the node-count by 10%, but a good time control is a much more effective speedup. If my program has t milliseconds left to use in a game, and there are an estimated m moves left on the board (e.g., this many vacant spaces), one reasonable choice is t / m. One should at least use t/(m+1). There is also a locial reason for this. If m is very small, especially m==1 one should have some extra time if the programm recognizes a problem. In this case it should search deeper. Generally this t/(m+k) should only be a target time. The final decision should be based on the results of the search. It is important to recognize trivial/forced moves and to stop in this cases search earlier. If the programm sees a problem than it should search longer. I have made recently a simple (but strong) UCT backgammon programm. UCT gives much better information for time-control than Alpha-Beta. E.g. if almost all search effort is concentrated on the best move, one can reasonable conclude that its a trivial/forced move. If the eval of the best moves decreases in the last period constantly and there are some chances that the second best becomes best, one should search on In practice, this seems to spend too much time on early moves, which (under UCT/MC) is largely wasted time. Would it be better to use something like t / m**k, for some constant k? (Looking at graphs of such functions, k = 1.5 seems reasonable.) Go-Programmers like it complicated. It would also be interesting to look at the graphs of how much time humans spend on each move; is it usually less for the opening moves than for middle / endgame moves? Is there a smooth curve, or is there a relatively abrupt shift from joseki to analysis? One should forget human behaviour. If I would have to make a Turing test - is the player human or a programm - I would not look at the moves but on the time behaviour. The fundamental difference is that (good) humans know when the position is difficult and when its easy. Programms have no understanding of this at all. Humans play Chess/Go, programm make chess/Go moves. Consequently humans think for a few moves very long, and play other moves rather fast. But I think that the time-control of humans is not at all optimal. Its very human to try to solve an urgent problem even at the risk that it makes solving a further problem more difficult. Humans tend therefore to get into Zeitnot. When playing against GM Adams I proposed 40 Moves in 2 hours. He proposed 40 Moves in 1 hour 40 minutes plus 30 sek/move. In the first moment I could not see the difference. In both cases one has 2 hours for 40 moves. But at move 30 its different. The flag is falling there already at 1h 55 minutes. Its a psychological trick to avoid extreme Zeitnot. But if the human would have a good time-control algorithm there is no need for this trick. He could save this 30 seks for himself. Chrilly Note: One should forget human behaviour generally. A programm is a programm is a programm. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
