Many faces does most of what has been mentioned. In addition, rather than stop search when it is impossible for another move to be chosen, I stop earlier, when it is unlikely for another move to become best. When far ahead, I stop a little earlier. That preserves some time in case there is a reversal later, and makes customers happier.
I don’t stop early when pondering on opponent’s time. Sometimes this means that when Many Faces gets to move, it moves instantly, because the criteria for early stopping is already met after pondering. It’s more difficult to decide when to take extra time to think, and I don’t have a good solution. I just set the target time very generously and depend on time saving in other moves to give enough cushion. David From: Computer-go [mailto:[email protected]] On Behalf Of Pawel Koziol Sent: Saturday, November 05, 2016 8:15 AM To: [email protected] Subject: Re: [Computer-go] Computer-go Digest, Vol 82, Issue 2 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-...@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_9zefokyztukdqn12n6...@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+6bhbu...@mail.gmail.com > <mailto:asg3qlpbomtw%2blkuayk3ntum%[email protected]> > > 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
