[Computer-go] Time settings for KGS bot tournaments
Last month, I planned to use a time setting for the monthly KGS bot tournament that had Canadian overtime of 10 moves in 30 seconds. It was actually set to 25 moves in 30 seconds, causing some entrants to lose on time. I assumed that I had set it incorrectly, and gave an apology. Now I find that it was not entirely my fault. I had used the tournament creation software to set 30/10, as I had intended. It had created an XML file specifying 30/10. But when I uploaded this to the server, the server had decided that I meant 30/25. I found this out by checking the time settings for next week's KGS bot tournament, which I have just created. I set the Canadian overtime to 30/10, but the server decided to use 30/25. So I deleted the tournament and created a new one with 1:00/20; and the server decided that I meant 1:00/25. 1:00/25 is not quite what I want, but it's close enough, and I don't know how to do any better, so that is what we will be using. Nick -- Nick Weddn...@maproom.co.uk ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
Hi! On Thu, Jul 22, 2010 at 09:53:53AM +0200, Marius Schneider wrote: are there any investigations how to use efficiently the time? Should the bot spend many time in the opening (because there are many possibilities?)? Or is the middle game more important? Are there any distribution assumptions known? This depends a lot, e.g. on 9x9 it is probably worth spending a lot of time in the opening while in 19x19 stashing it for middlegame likely makes a lot more sense. I was really surprised by the strength increase in Pachi caused by a non-trivial time management algorithm (though we have no idea how close to an optimal one, since I guess a lot of the conceptual design was based on gut feeling) - it is definitely worth spending some effort on this boring-looking stuff. -- Petr Pasky Baudis The true meaning of life is to plant a tree under whose shade you will never sit. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
are there any investigations how to use efficiently the time? Aya calculates available time by dividing left time by constant number; available_sec = left_sec / DIV; I set DIV=7; in 9x9, and DIV=60 - moves / 10; in 19x19. In 9x9, I got DIV=7 from some experiences It seems thinking deeply in opening is good in 9x9. Against MoGo, 3 minutes sudden death. Mogo does 5 playouts always. rate wins/ all 0.639 (103/ 161) DIV= 5 0.619 (119/ 192) DIV=10 0.577 (130/ 225) DIV=15 Against MoGo, 3 minutes sudden death. Mogo does 10 playouts always. rate wins/ all 0.444 ( 50/ 126) DIV=3 0.485 (152/ 313) DIV=4 0.485 (156/ 321) DIV=5 0.557 (255/ 457) DIV=7 0.517 (517/1000) DIV=8 Regards, Hiroshi Yamashita - Original Message - From: Marius Schneider marius@googlemail.com To: computer-go@dvandva.org Sent: Thursday, July 22, 2010 4:53 PM Subject: [Computer-go] time settings Hey, are there any investigations how to use efficiently the time? Should the bot spend many time in the opening (because there are many possibilities?)? Or is the middle game more important? Are there any distribution assumptions known? best regards, Marius ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
In 9x9 go I found that Lazarus improved significantly by front loading the time. The basic idea in the sudden death time controls is time left divided by some constant chosen in such a way that you spend significantly more time on the first move that you would say the 40th move.Having an opening book for 9x9 is important too because it enables you to spend more time on your moves so you can delay using time for as long as possible. Since I do not know how to play go I built my opening book by letting Lazarus deep search positions - which is equivalent to having much more thinking time and spending a lot of it early. I don't remember the exact constant I used but the ideal constant was surprisingly aggressive - it spend a LOT more time on the first move than it did just a few moves later. In 9x9 go the first few moves are extremely critical and if you start badly you cannot recover. Don On Thu, Jul 22, 2010 at 3:53 AM, Marius Schneider marius@googlemail.com wrote: Hey, are there any investigations how to use efficiently the time? Should the bot spend many time in the opening (because there are many possibilities?)? Or is the middle game more important? Are there any distribution assumptions known? best regards, Marius ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
Good base to start with. However, things become more complicated when the bot is pondering (thinking on the opponent's time). Ingo. Original-Nachricht Datum: Thu, 22 Jul 2010 19:37:01 +0900 Von: Hiroshi Yamashita y...@bd.mbn.or.jp An: computer-go@dvandva.org Betreff: Re: [Computer-go] time settings are there any investigations how to use efficiently the time? Aya calculates available time by dividing left time by constant number; available_sec = left_sec / DIV; I set DIV=7; in 9x9, and DIV=60 - moves / 10; in 19x19. In 9x9, I got DIV=7 from some experiences It seems thinking deeply in opening is good in 9x9. Against MoGo, 3 minutes sudden death. Mogo does 5 playouts always. rate wins/ all 0.639 (103/ 161) DIV= 5 0.619 (119/ 192) DIV=10 0.577 (130/ 225) DIV=15 Against MoGo, 3 minutes sudden death. Mogo does 10 playouts always. rate wins/ all 0.444 ( 50/ 126) DIV=3 0.485 (152/ 313) DIV=4 0.485 (156/ 321) DIV=5 0.557 (255/ 457) DIV=7 0.517 (517/1000) DIV=8 Regards, Hiroshi Yamashita -- GRATIS für alle GMX-Mitglieder: Die maxdome Movie-FLAT! Jetzt freischalten unter http://portal.gmx.net/de/go/maxdome01 ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
But I think dividing by constant is too simple. Selecting easy and difficult position is maybe more efficient. I have a good result (0.57) in my alpha beta shogi program. Thank you, Yamashita. I wonder what means good result (0.57)? 1. root best searched nodes is not so big against second best. 2. second best nodes is big. 3. root value is decreasing. In these case, program uses 2.5 times time. I think such a method will be also effective in MCTS. So, you haven't use these heuristics in Aya, right? Although they are useful in your alpha-beta-search based shogi program. Aja Hiroshi Yamashita ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
On Thu, Jul 22, 2010 at 8:26 AM, Hiroshi Yamashita y...@bd.mbn.or.jp wrote: Hi Aja, mine. I wonder if my understanding is correct? Yes. so this formula takes effect immediately in the opening stage. Yes. But I think dividing by constant is too simple. Selecting easy and difficult position is maybe more efficient. And also an even more difficult problem!But I think you are right - the most gain is to be had in determining which specific positions deserve more (or conversely, less) thinking time. I have a good result (0.57) in my alpha beta shogi program. 1. root best searched nodes is not so big against second best. 2. second best nodes is big. 3. root value is decreasing. In these case, program uses 2.5 times time. I think such a method will be also effective in MCTS. I don't know how much this applies to go because the iteration schedule is so much different, but there are some ideas borrowed from computer chess. Detect easy moves and spend less time on them - and if the best move changes a lot spend more time thinking.I think this is in line with what you are suggesting. Every idea has it's downsides, so one hopes to find the right balance. Most of the time when you spend more time because the score is dropping, the extra time doesn't change anything, you are in a losing position. Nevertheless, it's probably the right thing to do because if you are losing it doesn't matter much anyway and there is always a chance you will save the game or simply avoid playing a losing move and finding a more profound move that is good. Hiroshi Yamashita ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
Hi Don, Sorry that I can't quote your words correctly by Outlook Express. If I understand correctly, you use the simple formula (goalTime = timeLeft / K) for both without pondering and with pondering. So firstly, you tune K to the optimal value for your program without pondering. Then you choose a value on a reasonable range (usually a lower K) with pondering, since the results are too close to be measured with few games that you can't say which K is the best. That means you make your program think longer from the beginning. Aja Using automated play I first tuned the program assuming no thinking on the opponents time. I many different divisor constants K in the simple formula goalTime = timeLeft / K Once I found something close to the optimal value, I experimented with how much more aggressive I could get without the results declining much.I found there was a fairly broad range of values I could use that made little difference in playing strength.So for thinking on the opponents time I simply chose a value on the higher end of the reasonable range which of course means using a lower K. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
There was something wrong in the format of my post. I repost by Windows 7 Live Mail this time. Hi Don, Sorry that I can't quote your words correctly by Outlook Express. If I understand correctly, you use the simple formula (goalTime = timeLeft / K) for both without pondering and with pondering. So firstly, you tune K to the optimal value for your program without pondering. Then you choose a value on a reasonable range (usually a lower K) with pondering, since the results are too close to be measured with few games that you can't say which K is the best. That means you make your program think longer from the beginning. Aja ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
On Thu, Jul 22, 2010 at 9:16 AM, Aja ajahu...@gmail.com wrote: Hi Don, Sorry that I can't quote your words correctly by Outlook Express. If I understand correctly, you use the simple formula (goalTime = timeLeft / K) for both without pondering and with pondering. So firstly, you tune K to the optimal value for your program without pondering. Then you choose a value on a reasonable range (usually a lower K) with pondering, since the results are too close to be measured with few games that you can't say which K is the best. That means you make your program think longer from the beginning. Yes, your understanding is correct. The issue is that it's possible to rarely or never predict an opponents move early in the game, where it really matters and also some players play very quickly in which case you stand little to gain from pondering anyway. Fortunately, I believe the range of reasonable values (the sweet spot) for each case overlaps so you can have a value that works very well for both cases. Also, keep in mind that if you opponent is pondering, he is going to predict YOUR moves and take time from you - meaning he will play some moves very quickly - which makes the ideal value for the ponder case closer to the ideal value for the non-ponder case. Don Aja Using automated play I first tuned the program assuming no thinking on the opponents time. I many different divisor constants K in the simple formula goalTime = timeLeft / K Once I found something close to the optimal value, I experimented with how much more aggressive I could get without the results declining much.I found there was a fairly broad range of values I could use that made little difference in playing strength.So for thinking on the opponents time I simply chose a value on the higher end of the reasonable range which of course means using a lower K. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
Thank you, Don. I am convinced by your words that to evaluate a pondering policy, we should test against a program that also do pondering, because thinking faster so that the opponent cannot steal much time is also an important issue. Aja - Original Message - From: Don Dailey To: Aja ; computer-go@dvandva.org Sent: Thursday, July 22, 2010 9:42 PM Subject: Re: [Computer-go] time settings On Thu, Jul 22, 2010 at 9:16 AM, Aja ajahu...@gmail.com wrote: Hi Don,  Sorry that I can't quote your words correctly by Outlook Express. If I understand correctly, you use the simple formula (goalTime = timeLeft / K) for both without pondering and with pondering. So firstly, you tune K to the optimal value for your program without pondering. Then you choose a value on a reasonable range (usually a lower K) with pondering, since the results are too close to be measured with few games that you can't say which K is the best.  That means you make your program think longer from the beginning. Yes,  your understanding is correct.   The issue is that it's possible to rarely or never predict an opponents move early in the game,  where it really matters and also some players play very quickly in which case you stand little to gain from pondering anyway.   Fortunately,  I believe the range of reasonable values (the sweet spot) for each case overlaps so you can have a value that works very well for both cases. Also, keep in mind that if you opponent is pondering,  he is going to predict YOUR moves and take time from you - meaning he will play some moves very quickly - which makes the ideal value for the ponder case closer to the ideal value for the non-ponder case. Don   Aja  Using automated play I first tuned the program assuming no thinking on the opponents time.  I many different divisor constants K in the simple formula  goalTime = timeLeft / K Once I found something close to the optimal value, I experimented with how much more aggressive I could get without the results declining much.   I found there was a fairly broad range of values I could use that made little difference in playing strength.   So for thinking on the opponents time I simply chose a value on the higher end of the reasonable range which of course means using a lower K.  ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
Hi! On Thu, Jul 22, 2010 at 09:26:34PM +0900, Hiroshi Yamashita wrote: But I think dividing by constant is too simple. Selecting easy and difficult position is maybe more efficient. Yes, I'm sorry, I completely forgot mentioning this, but this is absolutely crucial. In Pachi, we have normal thinking time and max thinking time (3*normal). Pachi continues searching up to max thinking time if: * best value != most playouts * difference between value of best node and its best child is too large * ratio between number of playouts of two best-explored nodes is less than c - we use c=2.5, so this kicks in very often, but it seems to be very benificial; maybe with different basic time distribution, its effect would be smaller OTOH, if result cannot change anymore, search is stopped immediately (unless it is byoyomi). Also, we stop very early if winrate is extremely high. -- Petr Pasky Baudis The true meaning of life is to plant a tree under whose shade you will never sit. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
[Computer-go] time settings
About the previous question, in which phase should more time be given: Don Dailey wrote: In 9x9 go the first few moves are extremely critical and if you start badly you cannot recover. Petr Baudis wrote: This depends a lot, e.g. on 9x9 it is probably worth spending a lot of time in the opening while in 19x19 stashing it for middlegame likely makes a lot more sense. Looks contradictory but it is not. It is consistent with the fact that computers play near pro level in 9x9. At this level you simply cannot afford going wrong, you pay it with a loss. Human pros claim (In the Beginning, Ikuro Ishigure) that when games are 2 days long, you have to dedicate and entire day to the first 50 moves. I agree with Petr that investing in middlegame and endgame is more profitable at the current strength, but that is only (my guess) because 19x19 computer go is so far away from pro level, unlike 9x9 where investing in the first moves is more profitable as Don states. In 19x19, the moves between 10 and say 60 are still the most important moves, (assuming the first 10 moves are “canonical”). They decide if you gain a superior position and your opponent will have to play out of necessity for the rest of the game, or it is you who plays the rest of the game from behind. The problem is just current MCTS programs don’t have a clue what to do with this extra time in the opening. This happens because the tree does not reach endgame or near endgame positions, it is floating in nodes evaluated by naïve playouts. Their kankaku (Yamato used this word for “feeling” in the sense of the value to which playouts converge) is kyu level, no matter what playout policy you choose. Therefore, why give them time to solve a problem they cannot solve? Jacques. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
agreed. and disturbingly, all of the knowledge i gained from reading in the beginning (several stones almost immediately) is the kind of thing that i cannot see how to make a computer take advantage of. which feels very weird. worse still, even if you could program in most of the three basic dictionaries of joseki by the same publisher, it still wouldn't successfully match when to use which and where and why, because there is no global knowledge or global goal in mcts and the whole-board interaction between josekis is so poorly defined. s. On Thu, Jul 22, 2010 at 12:59 PM, Jacques Basaldúa jacq...@dybot.comwrote: About the previous question, in which phase should more time be given: Don Dailey wrote: In 9x9 go the first few moves are extremely critical and if you start badly you cannot recover. Petr Baudis wrote: This depends a lot, e.g. on 9x9 it is probably worth spending a lot of time in the opening while in 19x19 stashing it for middlegame likely makes a lot more sense. Looks contradictory but it is not. It is consistent with the fact that computers play near pro level in 9x9. At this level you simply cannot afford going wrong, you pay it with a loss. Human pros claim (In the Beginning, Ikuro Ishigure) that when games are 2 days long, you have to dedicate and entire day to the first 50 moves. I agree with Petr that investing in middlegame and endgame is more profitable at the current strength, but that is only (my guess) because 19x19 computer go is so far away from pro level, unlike 9x9 where investing in the first moves is more profitable as Don states. In 19x19, the moves between 10 and say 60 are still the most important moves, (assuming the first 10 moves are “canonical”). They decide if you gain a superior position and your opponent will have to play out of necessity for the rest of the game, or it is you who plays the rest of the game from behind. The problem is just current MCTS programs don’t have a clue what to do with this extra time in the opening. This happens because the tree does not reach endgame or near endgame positions, it is floating in nodes evaluated by naïve playouts. Their kankaku (Yamato used this word for “feeling” in the sense of the value to which playouts converge) is kyu level, no matter what playout policy you choose. Therefore, why give them time to solve a problem they cannot solve? Jacques. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
Re: [Computer-go] time settings
You are probably right, but do you have solid evidence to back it up or is this based on your intuition? I have found in all games programming that my own intuition is very often wrong or for whatever reason does not translate directly to an algorithm the way I thing it should. And I am not an amateur at this as I have one of the stronger chess programs. If you are right, then there are a some things that may be going on. Either the first few moves in 19x19 are just not that important, or it's difficult to misplay it, or extra computing time is of very little benefit in the first few moves. Not being a go player, I could believe any of these 3 things. My best guess, assuming that what you are saying is correct, is that extra thinking time is wasted because the computer cannot improve it's first few moves very much with additional thinking time. On Thu, Jul 22, 2010 at 12:59 PM, Jacques Basaldúa jacq...@dybot.comwrote: About the previous question, in which phase should more time be given: Don Dailey wrote: In 9x9 go the first few moves are extremely critical and if you start badly you cannot recover. Petr Baudis wrote: This depends a lot, e.g. on 9x9 it is probably worth spending a lot of time in the opening while in 19x19 stashing it for middlegame likely makes a lot more sense. Looks contradictory but it is not. It is consistent with the fact that computers play near pro level in 9x9. At this level you simply cannot afford going wrong, you pay it with a loss. Human pros claim (In the Beginning, Ikuro Ishigure) that when games are 2 days long, you have to dedicate and entire day to the first 50 moves. I agree with Petr that investing in middlegame and endgame is more profitable at the current strength, but that is only (my guess) because 19x19 computer go is so far away from pro level, unlike 9x9 where investing in the first moves is more profitable as Don states. In 19x19, the moves between 10 and say 60 are still the most important moves, (assuming the first 10 moves are “canonical”). They decide if you gain a superior position and your opponent will have to play out of necessity for the rest of the game, or it is you who plays the rest of the game from behind. The problem is just current MCTS programs don’t have a clue what to do with this extra time in the opening. This happens because the tree does not reach endgame or near endgame positions, it is floating in nodes evaluated by naïve playouts. Their kankaku (Yamato used this word for “feeling” in the sense of the value to which playouts converge) is kyu level, no matter what playout policy you choose. Therefore, why give them time to solve a problem they cannot solve? Jacques. ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go ___ Computer-go mailing list Computer-go@dvandva.org http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
