[Computer-go] Scoring a go board.

Woody Folsom woody.folsom at gmail.com
Fri Feb 8 15:37:25 PST 2013


Thanks for the clarification - I thought I had a bug in my scoring code,
although I had successfully tested numerous scoring scenarios.  Most
likely, I simply forgot to set KGS to Chinese scoring when I ran some games
against GnuGo then tricked myself into thinking that dead stones counted as
points for the opponent!


On Fri, Feb 8, 2013 at 5:51 PM, Don Dailey <dailey.don at gmail.com> wrote:

>
>
> 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
>>
>
>
> _______________________________________________
> 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/497541ca/attachment.html>


More information about the Computer-go mailing list