[Computer-go] Time Policy

Hendrik Baier hendrik.baier at gmail.com
Fri Nov 4 06:30:40 PDT 2016


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  <computer-go-request at computer-go.org>:
> Send Computer-go mailing list submissions to
>         computer-go at computer-go.org
>
> 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
>         computer-go-request at computer-go.org
>
> You can reach the person managing the list at
>         computer-go-owner at computer-go.org
>
> 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 <bywbilly at gmail.com>
> To: computer-go at computer-go.org
> Subject: [Computer-go] Time policy
> Message-ID: <50DC71C0-311E-4967-B97F-2980E5366C48 at gmail.com>
> 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 <gcp at sjeng.org>
> To: computer-go at computer-go.org
> Subject: Re: [Computer-go] Time policy
> Message-ID: <ef84c1ca-a6c7-03d1-ba53-f151796d3683 at sjeng.org>
> 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 <contact at urbanhafner.com>
> To: "computer-go at computer-go.org" <computer-go at computer-go.org>
> Subject: Re: [Computer-go] Time policy
> Message-ID:
>         <CAHmXpNnzFeTofTo=+ASg3QLPBomtw+LkUAYk3NtUM+6BHbUyxw at 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 <gcp at sjeng.org> 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
>> Computer-go at computer-go.org
>> 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 <gonmf at sapo.pt>
> To: "[mailing" <computer-go at computer-go.org>
> Subject: Re: [Computer-go] Time policy
> Message-ID: <66qylsywmiiciuvopopwb61c.1478250138260 at email.android.com>
> 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 <contact at urbanhafner.com> 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 <gcp at sjeng.org> 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
>>> Computer-go at computer-go.org
>>> 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
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go
>
> ------------------------------
>
> End of Computer-go Digest, Vol 82, Issue 1
> ******************************************



More information about the Computer-go mailing list