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/
[computer-go] January KGS bot tournament results
My write-up of yesterday's KGS online computer Go tournament is now available, at http://www.weddslist.com/kgs/past/22/index.html Congratulations to MoGoBot, undefeated winner of both divisions! Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] January KGS bot tournament results
On Mon, 2007-01-08 at 16:29 +, Nick Wedd wrote: > My write-up of yesterday's KGS online computer Go tournament is now > available, at http://www.weddslist.com/kgs/past/22/index.html > > Congratulations to MoGoBot, undefeated winner of both divisions! > > Nick "HouseBot obtained a won position against IdiotBot. However it does not implement the kgsGtp clean-up instruction, so IdiotBot was able to claim that its dead stones were alive and win the game." IdiotBot seems OK in disputed position, from logfile: FINEST: Got successful response to command "final_status_list dead": = N1 M11 C3 H10 B1 M8 C9 N6 F13 A9 M2 A13 M4 Actually I think all stones are simply assumed alive after cleanup phase. I think this is done by kgsGtp and bot has no control over this. >From log file: INFO: Cleanup mode has ended by passes. It will be assumed that all dead stones have already been removed. -- Aloril <[EMAIL PROTECTED]> ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] January KGS bot tournament results
Let me get this straight. I think you are saying that IdiotBot actually knew the stones were dead and correctly said so. But HouseBot didn't speak up for itself nor did it bother to capture the dead stones and the only way for the server to resolve this is to assume everything is alive. I think this is correct and how it should be done if I'm understanding it correctly I like the protocol, because you don't have to implement it, but if you don't you should clean up opponents dead stones before passing. - Don On Mon, 2007-01-08 at 19:11 +0200, Aloril wrote: > On Mon, 2007-01-08 at 16:29 +, Nick Wedd wrote: > > My write-up of yesterday's KGS online computer Go tournament is now > > available, at http://www.weddslist.com/kgs/past/22/index.html > > > > Congratulations to MoGoBot, undefeated winner of both divisions! > > > > Nick > > "HouseBot obtained a won position against IdiotBot. However it does not > implement the kgsGtp clean-up instruction, so IdiotBot was able to claim > that its dead stones were alive and win the game." > > IdiotBot seems OK in disputed position, from logfile: FINEST: Got > successful response to command "final_status_list dead": = N1 M11 C3 H10 > B1 M8 C9 N6 F13 A9 M2 A13 M4 > > Actually I think all stones are simply assumed alive after cleanup > phase. I think this is done by kgsGtp and bot has no control over this. > > >From log file: INFO: Cleanup mode has ended by passes. It will be > assumed that all dead stones > have already been removed. > ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] January KGS bot tournament results
In message <[EMAIL PROTECTED]>, Don Dailey <[EMAIL PROTECTED]> writes Let me get this straight. I think you are saying that IdiotBot actually knew the stones were dead and correctly said so. But HouseBot didn't speak up for itself nor did it bother to capture the dead stones and the only way for the server to resolve this is to assume everything is alive. I think this is correct and how it should be done if I'm understanding it correctly I don't know what IdiotBot said, because I don't have access to the logs. From what Aloril says, his IdiotBot said "those black stones are dead", but HouseBot failed to respond "ok then"; and this triggered the clean-up phase, which again HouseBot did not understand. I like the protocol, because you don't have to implement it, but if you don't you should clean up opponents dead stones before passing. I like it too. But bots which fail to support it will continue to lose games as a consequence. I shall change the page, and avoid saying that IdiotBot claimed its dead stones were alive. Nick -- Nick Wedd[EMAIL PROTECTED] ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] January KGS bot tournament results
On Mon, 2007-01-08 at 17:43 +, Nick Wedd wrote: > >I like the protocol, because you don't have to implement it, > >but if you don't you should clean up opponents dead stones before > >passing. > > I like it too. But bots which fail to support it will continue to > lose > games as a consequence. But it's ok to NOT support it as long as your program cleans up after itself, right?That's how I understand it. If this is the case, it's win/win. I would support this on CGOS as long as no program was required to understand the protocol. - Don ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
Re: [computer-go] January KGS bot tournament results
What I meant to say is that it's ok to NOT support the protocol and you would NEVER lose a game you should have won AS LONG AS your program makes sure to eat all the opponents dead groups before passing. Am I correct in this understanding? - Don On Mon, 2007-01-08 at 12:59 -0500, Don Dailey wrote: > On Mon, 2007-01-08 at 17:43 +, Nick Wedd wrote: > > >I like the protocol, because you don't have to implement it, > > >but if you don't you should clean up opponents dead stones before > > >passing. > > > > I like it too. But bots which fail to support it will continue to > > lose > > games as a consequence. > > But it's ok to NOT support it as long as your program cleans up after > itself, right?That's how I understand it. > > If this is the case, it's win/win. I would support this on CGOS as > long > as no program was required to understand the protocol. > > - Don > > > > ___ > 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] January KGS bot tournament results
> > My write-up of yesterday's KGS online computer Go tournament is now > > available, at http://www.weddslist.com/kgs/past/22/index.html > > > > Congratulations to MoGoBot, undefeated winner of both divisions! > > > > Nick > > "HouseBot obtained a won position against IdiotBot. However > it does not > implement the kgsGtp clean-up instruction, so IdiotBot was > able to claim > that its dead stones were alive and win the game." > > IdiotBot seems OK in disputed position, from logfile: FINEST: Got > successful response to command "final_status_list dead": = N1 > M11 C3 H10 > B1 M8 C9 N6 F13 A9 M2 A13 M4 > > Actually I think all stones are simply assumed alive after cleanup > phase. I think this is done by kgsGtp and bot has no control > over this. > > >From log file: INFO: Cleanup mode has ended by passes. It will be > assumed that all dead stones > have already been removed. It's been a very long time since housebot got the final status list wrong at the end of a game. I'll check with "ujh" who was running the bots to see if we have a kgs log of what happened at the end of that game. By default, housebot 0.4 plays until all stones are decided by Benson's algorithm for unconditionally safe stones. Otherwise, housebot plays in the uncertain regions until it kills something or leaves itself in atari. That makes final status list very easy to answer. This is also why it filled its eye in the seki later on. There are a few scenarios where that method leads to a position it can't score correctly, but they're very rare and didn't come up in the idiotbot game. Going into cleanup (at all) seems rather strange to me since I have faith in both housebot 0.4 and IdiotBot's handling of the final status list dead. Alas, this is all speculation until I can see the logs. ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
RE: [computer-go] January KGS bot tournament results
On Mon, 2007-01-08 at 13:56 -0500, House, Jason J. wrote: > It's been a very long time since housebot got the final status list > wrong at the end of a game. I'll check with "ujh" who was running the > bots to see if we have a kgs log of what happened at the end of that > game. > By default, housebot 0.4 plays until all stones are decided by > Benson's algorithm for unconditionally safe stones. Otherwise, > housebot plays in the uncertain regions until it kills something or > leaves itself in atari. That makes final status list very easy to > answer. This is also why it filled its eye in the seki later on. > There are a few scenarios where that method leads to a position it > can't score correctly, but they're very rare and didn't come up in the > idiotbot game. Going into cleanup (at all) seems rather strange to me > since I have faith in both housebot 0.4 and IdiotBot's handling of the > final status list dead. > Alas, this is all speculation until I can see the logs. Based on kgsGtp docs if HouseBot doesn't implement kgs-genmove_cleanup it will claim all stones as alive. This is change from KGS2 tournaments. In short: 1) You must support both kgs-genmove_cleanup and final_status_list or 2) You must capture dead opponent stones by playing before you pass (like at CGOS). kgsGtp docs say this: KGS and Tournament Games Tournament games are similar to ranked games but even stricter. Tournament play with kgsGtp is designed with a goal of allowing GTP vs. GTP play with no human intervention and no scoring disputes. Because of this, it is required that engines prove the status of dead groups, either with the kgs-genmove_cleanup command or by playing until all dead stones are removed from the board. In tournament play, when the game ends, there are two possibilities: Engine Supports kgs-genmove_cleanup and final_status_list: The engine will be queried as normal at the end of the game. If the engine disagrees with the stones that the opponent marks dead, then play will continue with the genmove requests replaced by kgs-genmove_cleanup. After the engine passes, it will be assumed that all stones in play are alive. This is the same as normal ranked play. Engine is Missing Support for kgs-genmove_cleanup and/or final_status_list: In this case the engine is not capable of resolving disputes after scoring, so the engine must resolve all disputes during play. The engine will claim that all stones on the board (by either player) are alive. If the opponent disagrees, then kgsGtp will continue to insist all stones are alive. Thus, if two engines that both support the cleanup system play, any disagreements will be resolved by continuing play; after the cleanup phase, all stones will be considered alive by both engines. If one that supports cleanup plays one that does not, the engine that supports cleanup will be forced to play on until it also considers all stones alive. If neither engine supports cleanup, then disagreement is not possible, since both engines must play until all dead stones are removed. -- Aloril <[EMAIL PROTECTED]> ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
