[computer-go] 10k UCT bots

[Don Dailey]

Norbert Gábor Papp wrote:
> Thanks for your fast reply,but sorry, I don't really understand this...
>
> The situation -> both player pass, end of the game, I need the score.
>
> I want to remove dead-stones which means :
>   
There is no known perfect algorithm for doing this in every case and 
it's a function of how good your program is.   So if you figure out how 
to do it,  please let us know.

Typically, some kind of local search is done and the details of how to 
do that vary from program to program.   Some do it better than 
others.    It's not trivial.    Search the web,  there are papers and 
articles about it.

If you use tromp/taylor scoring you don't worry about it.   After 2 
passes EVERY stone is considered alive.   If there are dead stones then 
the opponent should not have passed.  

If you are asking because you want to implement monte carlo,  you just 
play until there are no legal eye filling moves, then you pass.   Then 
you score the board as is with no consideration of dead stones.     It's 
very simple.    Sometimes one side has no moves that fit this criteria 
but the other side does,  so you just play until both players run out of 
non-eye filling moves,  which gives 2 consecutive passes.

A reasonable but slow algorithm for identifying dead stones is to play a 
few hundred random games (without filling eyes) and if existing stones 
rarely or never survive they are dead with a high probability.     This 
covers most of the simple and visually intuitive cases.


- Don


> if (IsGameEnded) {
> for (int i=0, int ,j=0; i<table.sizeX,y<table.sizeZ;i++,j++){
> if dead(i,j)
>   {
>
>     table.remove(i,j);
>   }
> }
> countterritories();
> .
> .
> .
>
> }
> I'm interested in the function dead(), which is true when a stone is dead
> after both player pass,and the game is ended.
>
>
> 2008/5/14 Jason House <jason.james.house at gmail.com>:
>
>   
>> That's a function of how smart your bot is. If you play until you only have
>> eye-filling moves, you can safely assume all of your opponent's stones are
>> alive, all your groups with two eyes are alive, and everything else is dead.
>> Note the asymetry - your opponent may use a different strategy.
>>
>> If you use random playouts, you could compute the probability of specific
>> points being owned by each player, and use that for both passing and marking
>> dead stones.
>>
>> There are many other variants that use life and death modules, but I'll
>> assume you don't have them yet
>>
>> Sent from my iPhone
>>
>>
>> On May 14, 2008, at 9:10 AM, "Norbert Gábor Papp" <
>> papp.norbert.gabor at gmail.com> wrote:
>>
>>  Thanks! How can I identify dead stones?
>>     
>>> I haven't seen algorithm for this, and it is a very important part of
>>> a go program
>>> 2008/5/14, Don Dailey <drdailey at cox.net>:
>>>
>>>       
>>>> This probably explains it better than I could:
>>>>
>>>>  http://senseis.xmp.net/?TrompTaylorRules
>>>>
>>>> - Don
>>>>
>>>>
>>>>
>>>> Norbert Gábor Papp wrote:
>>>>
>>>>         
>>>>> Hi!
>>>>>
>>>>> Can you tell me some algorithm to compute the score ? (Both players
>>>>> pass,
>>>>> and who is the winner...)
>>>>>
>>>>> Thanks, Norbert
>>>>>
>>>>>
>>>>> ------------------------------------------------------------------------
>>>>>
>>>>> _______________________________________________
>>>>> computer-go mailing list
>>>>> computer-go at computer-go.org
>>>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>>>
>>>>>           
>>>> _______________________________________________
>>>> computer-go mailing list
>>>> computer-go at computer-go.org
>>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>>
>>>>  _______________________________________________
>>>>         
>>> computer-go mailing list
>>> computer-go at computer-go.org
>>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>>
>>>       
>> _______________________________________________
>> computer-go mailing list
>> computer-go at computer-go.org
>> http://www.computer-go.org/mailman/listinfo/computer-go/
>>
>>     
>
>   
> ------------------------------------------------------------------------
>
> _______________________________________________
> computer-go mailing list
> computer-go at computer-go.org
> http://www.computer-go.org/mailman/listinfo/computer-go/