[Computer-go] Scoring a go board.

Don Dailey dailey.don at gmail.com
Fri Feb 8 14:51:59 PST 2013


On Fri, Feb 8, 2013 at 5:08 PM, Woody Folsom <woody.folsom at gmail.com> wrote:

> I wrote an AI agent which plays go using a pure Java implementation of
> UCT-RAVE for my MS project at Georgia Tech.  With better data structure
> optimization I'm relatively sure 10,000s of roll-outs per second, per core,
> is not an unreasonable goal.
>
> Chinese scoring is easier than Japanese but I wouldn't go so far as to say
> trivial - my initial implementation erroneously counted surrounded dead
> groups as points!
>

Chinese scoring is trivial if the game is fully played out.    In Chinese
scoring there are no dead groups.    If the group is on the board it is
counted as alive - that is the whole point of Chinese scoring.

You are really doing playouts the hard way if you don't have the eye fill
rule.    The way it works is like this:

  1.  Never fill a 1 point eye (a properly defined one.)
  2.  Never allow a pass in the playouts unless there are no other moves
(subject to rule 1)
  3.  Otherwise pass.

The zobrist hash rule you use is a very good idea too.

Note that at Chinese scoring time there will be NO dead groups on the board
to score incorrectly.    There is nothing to get wrong at all,   you
basically add up all the points on the board,  white stones belong to
white,  black stones belong to black and the single empty points belong to
whoever completely surrounds them.

Here is probably the best definition of a single point eye:

definition of eye:

       an empty point whose orthogonal neighbors are all of the
       same color AND whose diagonal neighbors contain no more
       than 1 stone of the opposite color unless it's a border
       in which case no diagonal enemies are allowed.

This is excellent to get started and your suggestion to start with uniform
random playouts is a good one.    Later on he can explore some more
advanced issues such as dealing with seki and other things.



> I used no heuristics whatsoever in the roll-out policy, and would
> recommend getting your MCTS algorithm working with purely random roll-outs
> first.  I also did not explicitly code for avoiding filling the player's
> own eye, but used Zobrist hashing for super-ko detection and in practice
> never observed games run into hundreds of moves.
>
> I suspect that with Zobrist you avoid the most serious cases, but I'll bet
you are still going far more moves than necessary.    The one point eye
rules is very powerful and is probably the most important piece of
knowledge you could add.   It's almost always the worst move on the board
to fill a one point eye so this brings a great deal of sanity to the
playouts.

Don


> I would recommend using a board state data structure which encodes groups
> (or strings) of stones.  Counting liberties recursively consumed 40% of my
> first agent's total run-time, for negligible memory gains.  I did not deal
> with culling the state tree at all.
>
> Finally, (3) above is quite difficult.  I am currently attempting to train
> a neural network which usefully estimates this value by means of temporal
> difference learning.
>
> For more details, feel free to check out my project write-up at
> http://woodyfolsom.net/blog/?page_id=43.  I did not manage much original
> research since the whole project was done start to finish in one semester,
> but it covers the basics of MCTS and computer go.
>
>
> On Fri, Feb 8, 2013 at 4:41 PM, Don Dailey <dailey.don at gmail.com> wrote:
>
>> Score a go board using Chinese rules - it is trivial.
>>
>> The basic concept is that you play random moves and (usually) allow no
>> passes until there is nothing else to be done.  To prevent eye filling
>> there is a fairly simply but very effective rule that prohibits filling a
>> one point eye - otherwise the game can last for hundreds of moves.
>>
>> That is the "basic" concept.   These "playouts" can be greatly improved
>> on with some simple rules and patterns.  But there must sitll be some
>> element of randomness and getting this right is subject to a lot of
>> research and is considered a bit of a black art.
>>
>> Even a pretty trivial (uniformly random) playout strategy with the rule
>> not to fill properly constructed one point eyes can give a reasonable
>> evaluation, especially  near the end of the game if you view it
>> statistically.   For example if you play 1000 of these "random" playouts
>> and black wins 950 of them,  black probably really does have a won game.
>>  With a little bit of intelligence added to the playout strategy it can
>> become quite good.   MCTS  basically integrates a best first search with
>> this concept.
>>
>> Don
>>
>>
>>
>>
>> On Fri, Feb 8, 2013 at 4:33 PM, Rémi <remi.de.z at gmail.com> wrote:
>>
>>> surely at any time during a game of go, three passes can be made and the
>>> game can be scored...
>>>
>>> On 8 February 2013 22:31, Rémi <remi.de.z at gmail.com> wrote:
>>>
>>>> If there really is a difference between (1) and (2) then I have always
>>>> been completely oblivious to it. For your third (3) case I again see not
>>>> what the difference is.
>>>>
>>>>
>>>> On 8 February 2013 22:02, Nick Wedd <nick at maproom.co.uk> wrote:
>>>>
>>>>> On 08/02/2013 20:34, Rémi wrote:
>>>>>
>>>>>> Hy,
>>>>>>
>>>>>> There are a lot of interesting papers on UCT and selection strategies
>>>>>> ... But it's harder to find information about the more 'pragmatic'
>>>>>> side
>>>>>> of computer-go.
>>>>>>
>>>>>> How do you score a go board?
>>>>>>
>>>>>
>>>>> What do you mean by "score a go board"?  I can think of three
>>>>> reasonable possibilities.
>>>>>
>>>>> (1.) Count the score in a game that is over.
>>>>>
>>>>> (2.) Count the score in a game that is not over, but both players have
>>>>> passed because they think it is.
>>>>>
>>>>> (3.) Count the score in a game that is still being played.
>>>>>
>>>>> (1) is difficult but practicable. (2) is similar to (1), so long as
>>>>> you are not bothered about the result being meaningful, but just want to
>>>>> calculate the score as a referee might if asked to score a game in which
>>>>> both players have passed prematurely. (3) is as difficult as playing Go
>>>>> perfectly.
>>>>>
>>>>> Nick
>>>>>
>>>>>
>>>>>  What would be a faster algorithm to score a go-board?
>>>>>> Could you pre-calculate and accumulate some information early in the
>>>>>> game (on every move), knowing you're going to evaluate the board many
>>>>>> times?
>>>>>> When do you decide to finish/score the game?
>>>>>>
>>>>>> Also, what are some of the languages used besides C(++)? Does anyone
>>>>>> work in something like java or a functional language?
>>>>>>
>>>>>> Rémi de Zoeten.
>>>>>>
>>>>>>
>>>>>> ______________________________**_________________
>>>>>> Computer-go mailing list
>>>>>> Computer-go at dvandva.org
>>>>>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go>
>>>>>>
>>>>>>
>>>>>
>>>>> --
>>>>> Nick Wedd
>>>>> nick at maproom.co.uk
>>>>> ______________________________**_________________
>>>>> Computer-go mailing list
>>>>> Computer-go at dvandva.org
>>>>> http://dvandva.org/cgi-bin/**mailman/listinfo/computer-go<http://dvandva.org/cgi-bin/mailman/listinfo/computer-go>
>>>>>
>>>>
>>>>
>>>
>>> _______________________________________________
>>> Computer-go mailing list
>>> Computer-go at dvandva.org
>>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>>
>>
>>
>> _______________________________________________
>> Computer-go mailing list
>> Computer-go at dvandva.org
>> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>>
>
>
> _______________________________________________
> Computer-go mailing list
> Computer-go at dvandva.org
> http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://computer-go.org/pipermail/computer-go/attachments/20130208/a2875e27/attachment.html>


More information about the Computer-go mailing list