[Computer-go] Computer-go Digest, Vol 82, Issue 2

David Fotland fotland at smart-games.com
Sat Nov 5 10:12:26 PDT 2016


 

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:computer-go-bounces at computer-go.org] On Behalf Of Pawel Koziol
Sent: Saturday, November 05, 2016 8:15 AM
To: computer-go at computer-go.org
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 <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. Re: Time policy (Álvaro Begué)
   2. Re: Time Policy (Hendrik Baier)
   3. Re: Time policy (valkyria at phmp.se)


----------------------------------------------------------------------

Message: 1
Date: Fri, 4 Nov 2016 08:59:11 -0400
From: Álvaro Begué <alvaro.begue at gmail.com>
To: computer-go <computer-go at computer-go.org>
Subject: Re: [Computer-go] Time policy
Message-ID:
        <CAF8dVMUrBNnjEm=4ZkSTzLkSrx0fQ5LXAic4zgMPWWwrbG-i0g at 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 <gonmf at sapo.pt>
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 <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/
>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at computer-go.org
> 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 <hendrik.baier at gmail.com>
To: computer-go at computer-go.org
Subject: Re: [Computer-go] Time Policy
Message-ID:
        <CAEc=CNaUx0J9ZTZEn_ORVm5t6dLN_9ZEfOKYZTUKDqN12n6tow at 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  <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 <mailto:ASg3QLPBomtw%2BLkUAYk3NtUM%2B6BHbUyxw 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
> ******************************************


------------------------------

Message: 3
Date: Fri, 04 Nov 2016 15:25:15 +0100
From: valkyria at phmp.se
To: computer-go at computer-go.org
Subject: Re: [Computer-go] Time policy
Message-ID: <d15aa716a36f872a72eb4c6032468452 at phmp.se>
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
> Computer-go at computer-go.org
> http://computer-go.org/mailman/listinfo/computer-go


------------------------------

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 2
******************************************

 

-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20161105/9c985eb8/attachment.html>


More information about the Computer-go mailing list