Authors of chess program Stockfish gathered massive statistics about probability that on reaching certain move number game is still undecided (meaning not too larhe score difference). From that data they derived a table of multipliers used to adjust time per move calculated by their usual formula. Later on, they approximated the table by using some other formula.
2016-11-05 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. Re: Time policy (Álvaro Begué) > 2. Re: Time Policy (Hendrik Baier) > 3. Re: Time policy ([email protected]) > > > ---------------------------------------------------------------------- > > Message: 1 > Date: Fri, 4 Nov 2016 08:59:11 -0400 > From: Álvaro Begué <[email protected]> > To: computer-go <[email protected]> > Subject: Re: [Computer-go] Time policy > Message-ID: > <CAF8dVMUrBNnjEm=4ZkSTzLkSrx0fQ5LXAic4zgMPWWwrbG-i0g@mail. > gmail.com> > Content-Type: text/plain; charset="utf-8" > > Start by computing a "normal" amount of time to spend, using the kinds of > rules described by others in this thread. > > Since you are using MCTS, you may want to experiment with spending more > time if the move with the best score is not the one that has been explored > the most, since that probably signals an unclear situation. > > You can save a bit of time in obvious moves once you realize that the other > moves cannot catch up in the normal time allocated for this move. > > Álvaro. > > > > On Fri, Nov 4, 2016 at 5:02 AM, Gonçalo Mendes Ferreira <[email protected]> > wrote: > > > 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 Ferreira > > Em 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/ > > > > > > _______________________________________________ > > Computer-go mailing list > > [email protected] > > http://computer-go.org/mailman/listinfo/computer-go > > > -------------- next part -------------- > An HTML attachment was scrubbed... > URL: <http://computer-go.org/pipermail/computer-go/ > attachments/20161104/5083abf1/attachment-0001.html> > > ------------------------------ > > Message: 2 > Date: Fri, 4 Nov 2016 14:30:40 +0100 > From: Hendrik Baier <[email protected]> > To: [email protected] > Subject: Re: [Computer-go] Time Policy > Message-ID: > <CAEc=CNaUx0J9ZTZEn_ORVm5t6dLN_9ZEfOKYZTUKDqN12n6tow@mail. > gmail.com> > Content-Type: text/plain; charset=UTF-8 > > 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+6BHbUyxw@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 > > ****************************************** > > > ------------------------------ > > Message: 3 > Date: Fri, 04 Nov 2016 15:25:15 +0100 > From: [email protected] > To: [email protected] > Subject: Re: [Computer-go] Time policy > Message-ID: <[email protected]> > Content-Type: text/plain; charset=US-ASCII; format=flowed > > Just one additional thing. If you plan to play online (CGOS) you need > have a buffer for lag. > > That is if the opponent plays on until the board is filled, you might > end up playing another 100 moves. Even if your program responds locally > in 0.0001 seconds the lag of systems out of your control might quickly > make you spend several seconds time extra. > > best > Magnus > > > On 2016-11-04 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? > > > > Thanks (: > > > > _______________________________________________ > > Computer-go mailing list > > [email protected] > > http://computer-go.org/mailman/listinfo/computer-go > > > ------------------------------ > > 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 2 > ****************************************** >
_______________________________________________ Computer-go mailing list [email protected] http://computer-go.org/mailman/listinfo/computer-go
