Hi, you might want to have a look at our paper on time management for MCTS: https://dke.maastrichtuniversity.nl/m.winands/documents/time_management_for_monte_carlo_tree_search.pdf We used Go in the beginning and then also generalized to some other games; the most successful strategy was quite a lot more effective than only looking at the expected remaining number of moves. Byo-yomi is not taken into account yet though.
Hope it helps, Hendrik 2016-11-04 13:00 GMT+01:00 <[email protected]>: > Send Computer-go mailing list submissions to > [email protected] > > To subscribe or unsubscribe via the World Wide Web, visit > http://computer-go.org/mailman/listinfo/computer-go > or, via email, send a message with subject or body 'help' to > [email protected] > > You can reach the person managing the list at > [email protected] > > When replying, please edit your Subject line so it is more specific > than "Re: Contents of Computer-go digest..." > > > Today's Topics: > > 1. Time policy (Billy White) > 2. Re: Time policy (Gian-Carlo Pascutto) > 3. Re: Time policy (Urban Hafner) > 4. Re: Time policy (Gonçalo Mendes Ferreira) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Fri, 4 Nov 2016 11:45:56 +0800 > From: Billy White <[email protected]> > To: [email protected] > Subject: [Computer-go] Time policy > Message-ID: <[email protected]> > Content-Type: text/plain; charset=us-ascii > > Hi, > > Our team is working on a computer go system mainly followed alphago. We try > to add time policy to our system but cannot find something useful. > > I am wondering whether there are some useful material? > > Thanks (: > > > > ------------------------------ > > Message: 2 > Date: Fri, 4 Nov 2016 09:00:58 +0100 > From: Gian-Carlo Pascutto <[email protected]> > To: [email protected] > Subject: Re: [Computer-go] Time policy > Message-ID: <[email protected]> > Content-Type: text/plain; charset=utf-8 > > On 04-11-16 04:45, Billy White wrote: >> Hi, >> >> Our team is working on a computer go system mainly followed alphago. >> We try to add time policy to our system but cannot find something >> useful. >> >> I am wondering whether there are some useful material? > > Take a large games database, and construct a table of expected number of > moves remaining based on the current move of the game. > > Divide total amount of time left by the output of that table. > > Test if biasing it to think slightly longer early on helps playing strength. > > If there is byo-yomi time. the required extra thinking time generally > flows logically from the byo-yomi timecontrol and the above. > > -- > GCP > > > ------------------------------ > > Message: 3 > Date: Fri, 4 Nov 2016 09:40:41 +0100 > From: Urban Hafner <[email protected]> > To: "[email protected]" <[email protected]> > Subject: Re: [Computer-go] Time policy > Message-ID: > <CAHmXpNnzFeTofTo=+asg3qlpbomtw+lkuayk3ntum+6bhbu...@mail.gmail.com> > Content-Type: text/plain; charset="utf-8" > > I think there are some short papers about it out there. But I would suggest > looking at the source code of existing bots like michi or pachi. What I use > in my bot is really simple. I use the following formula: > > time for next move = remaining time / (C * max(vacant points, M)) > > Where C is some constant you need to figure out (I use 0.5 right now), > “vacant points” is the number of empty intersections on the board and M is > a lower limit (I currently use 24) so that you don’t use up too much time > that you might need when a capture happens. > > It has worked well enough so far that I haven’t looked at more intricate > algorithms. Oh, and once I hit byo-yomi time I just divide the time into > equal parts by the number of stones for the byo-yomi period. > > Urban > > On Fri, Nov 4, 2016 at 9:00 AM, Gian-Carlo Pascutto <[email protected]> wrote: > >> On 04-11-16 04:45, Billy White wrote: >> > Hi, >> > >> > Our team is working on a computer go system mainly followed alphago. >> > We try to add time policy to our system but cannot find something >> > useful. >> > >> > I am wondering whether there are some useful material? >> >> Take a large games database, and construct a table of expected number of >> moves remaining based on the current move of the game. >> >> Divide total amount of time left by the output of that table. >> >> Test if biasing it to think slightly longer early on helps playing >> strength. >> >> If there is byo-yomi time. the required extra thinking time generally >> flows logically from the byo-yomi timecontrol and the above. >> >> -- >> GCP >> _______________________________________________ >> Computer-go mailing list >> [email protected] >> http://computer-go.org/mailman/listinfo/computer-go >> > > > > -- > Blog: http://bettong.net/ > Twitter: https://twitter.com/ujh > Homepage: http://www.urbanhafner.com/ > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: > <http://computer-go.org/pipermail/computer-go/attachments/20161104/ecc4cfc8/attachment-0001.html> > > ------------------------------ > > Message: 4 > Date: Fri, 04 Nov 2016 09:02:18 +0000 > From: Gonçalo Mendes Ferreira <[email protected]> > To: "[mailing" <[email protected]> > Subject: Re: [Computer-go] Time policy > Message-ID: <[email protected]> > Content-Type: text/plain; charset="utf-8" > > I similarly use C x (T / E) in matilda, with > C = 1.24 > T = time left on current period (absolute or byo yomi) > E = argmax(estimate of game length divided by two ; 19) or byo yomi stones > remaining > > The length estimate ir around 2/3 of the board points. > > It lacks the decision to expend a byo yomi period in more difficult positions. > > > Gonçalo FerreiraEm 04/11/2016 08:40, Urban Hafner <[email protected]> > escreveu: >> >> I think there are some short papers about it out there. But I would suggest >> looking at the source code of existing bots like michi or pachi. What I use >> in my bot is really simple. I use the following formula: >> >> time for next move = remaining time / (C * max(vacant points, M)) >> >> Where C is some constant you need to figure out (I use 0.5 right now), >> “vacant points” is the number of empty intersections on the board and M is a >> lower limit (I currently use 24) so that you don’t use up too much time that >> you might need when a capture happens. >> >> It has worked well enough so far that I haven’t looked at more intricate >> algorithms. Oh, and once I hit byo-yomi time I just divide the time into >> equal parts by the number of stones for the byo-yomi period. >> >> Urban >> >> On Fri, Nov 4, 2016 at 9:00 AM, Gian-Carlo Pascutto <[email protected]> wrote: >>> >>> On 04-11-16 04:45, Billy White wrote: >>> > Hi, >>> > >>> > Our team is working on a computer go system mainly followed alphago. >>> > We try to add time policy to our system but cannot find something >>> > useful. >>> > >>> > I am wondering whether there are some useful material? >>> >>> Take a large games database, and construct a table of expected number of >>> moves remaining based on the current move of the game. >>> >>> Divide total amount of time left by the output of that table. >>> >>> Test if biasing it to think slightly longer early on helps playing strength. >>> >>> If there is byo-yomi time. the required extra thinking time generally >>> flows logically from the byo-yomi timecontrol and the above. >>> >>> -- >>> GCP >>> _______________________________________________ >>> Computer-go mailing list >>> [email protected] >>> http://computer-go.org/mailman/listinfo/computer-go >> >> >> >> >> -- >> Blog: http://bettong.net/ >> Twitter: https://twitter.com/ujh >> Homepage: http://www.urbanhafner.com/ > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: > <http://computer-go.org/pipermail/computer-go/attachments/20161104/1da9af4d/attachment-0001.html> > > ------------------------------ > > Subject: Digest Footer > > _______________________________________________ > Computer-go mailing list > [email protected] > http://computer-go.org/mailman/listinfo/computer-go > > ------------------------------ > > End of Computer-go Digest, Vol 82, Issue 1 > ****************************************** _______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go
