RE: computer-go: Board evaluation by counting...

[Petersen Kjeld-WFKP1396 <Kjeld.Petersen@xxxxxxxxxxxx>]

As I see the game Go, the counting of influence and territory
is NOT just a matter of the radiation of the stone alone, but
more a matter of the radiation of the stones and the connections between the stones.

So I tried to design a methode for radiation on connections.

Kjeld


-----Original Message-----
From: Antti Huima [mailto:huima@xxxxxxxxxxxxxxxxx]
Sent: 18. september 2001 15:58
To: computer-go@xxxxxxxxxxxxxxxxx
Subject: Re: computer-go: Board evaluation by counting...


On Tue, 18 Sep 2001, Petersen Kjeld-WFKP1396 wrote:

> Instead it is nessassary to make radiation of connection of stones.
> First use the previous methode, but when 2 radiation get in contact,
> then there is set up a connection between this stones.
> All the radiations are reset, and a new radiation i made.
> Ex:     1   1                          1   1
>        121 121                        1211121
>       123212321                      123222321
>      123X323X321  =>>  X---X   =>>  123X333X321
>       123212321                      123222321
>        121 121                        1211121
>         1   1                          1   1
>
> Also the edge makesa connection to stones.
> Radiation of the other color cancel out the radiation.
>
> This process has to be done several times, and each time
> there is made new connection and radiation.
> I think this will give a better way to calculate territory and
> influence ?
>
> What do you think ?

Sounds like an ad hoc method. Why do you think it will give a better way
to calculate territory? Why you think it will be more accurate? Why?
Asking these questions is definitely reasonable scientific practice.

I think that methods for estimating territory (i.e. methods for evaluating
a board position) must be derived more from the game itself and less from
the ease of implementing of or the smallness of an algorithm.

One possibility would be this: Choose a big set of dan-level games that
have played until end. Choose a game G. Guess where the territories were
at the end. This can be done heuristically with good precision. It doesn't
matter if the judgements go wrong at times as long as most of the time the
territories are guessed correctly.

Then walk backwards in the game G. Correlate by a computational learning
method the patterns of stones in the positions of G with the known sets of
final territories. In this way you can train a learning system to predict
where territories will appear, given a position that is not final. Of
course, the system will make errors because it doesn't understand the
full-board tactical aspects of go, but it should work better (and consume
more resources) than a basic influence-based method.

To illustrate, we `know' based on our experience that

  . . . . . .
  . X . . X .
  . . . . . .
  ._._._._._.

is a relative stable formation. This means that in `most' games where the
position above appears, the marked intersections will appear as territory
(there will be either a live stone or an empty intersection that counts as
area):

  . . . . . .
  . X a a X .
  . a a a a .
  ._a_a_a_a_.

To be more precise, there could be e.g. two games with the position above
and the final board position at the same point looking like (`b' denotes
black's area)

  X X O O O O
  b X X O X O
  X X b X X O
  b_b_X_X_O_O

and

  O X b b b b
  X X b b X b
  b b b b b b
  b_b_b_b_b_b

The pattern of `a's above would appear as an `average' of these, but the
definition of `average' of course depends on the computational learning
method used.

A computational learning method could learn this. For example, a neural
network whose inputs are an N x N subgrid of the go board and whose
outputs denote ownership of territory could do it, learning from examples.
Or so could do unsupervised vector quantization within a suitable context.

Regards,

-- 
Antti Huima