[computer-go] CGT in computer go

["Persson, Magnus" <persson@xxxxxxxxxxxxxxxxxx>]

> -----Original Message-----
> From: Eric Boesch [mailto:ericboesch@xxxxxxxxxxxxxxxxx]
> It sounds like you are suggesting computational game theory (CGT)
> calculations.  Does anybody's program do that?  (I'm guessing that
most
> programs have some kind of code to deal with sente vs. gote issues,
but
> that's not the same as full-generality CGT.)

My program (viking4 on KGS) uses an extremely simplified form of CGT for
all move evaluation. For a local situation it will compute an
approximation of temperature using a small tree with both black and
white playing first up to 2 ply if any of the 1ply moves might be
forcing moves. It simply plays the move that has the local highest
approximate temperature. 

This was first considered a crude hack, to test my then new full board
evaluation function. It uses patterns to decide how to build these small
trees.

The program as consequence often evaluate gote and sente roughly
correctly (it even tells you for each move it evaluates if the move is
seen as gote, sente, reverse sente or double sente (although double
sente is computed as an crude approximation of two gote moves in a row
from both sides)).

The thing above is a simplification since it is really hard to decide
what the local moves are, and there are many situations where this
approach fails and only a full board search (or something other smart)
would get accurate evaluations of moves.

I think this approach is equivalent in strength to a 2-ply full board
alfabeta-search, but much faster. In a sense it also uses "nullmove"
since it compares moves with what would happen if a pass was played and
the opponent moved first, but only local comparisons are made. It could
also be seen as two 1-ply searches with a 1ply quiescence search.  I
made some sloppy (Vincent would not accept it) tests (mainly on 9x9)
testing that my approach is faster and as a good as 2-ply search but a
4-ply search would perhaps be stronger (but be too slow with my bloated
evaluation function). 1-ply and 3-ply search is very weak because there
is no proper quiescence search and thus empty and bad threats are given
too high values (at least for 9x9).

If anyone want to make a 10 kyu program with this approach it is doable
I think, but it will never reach dan-level play. 

One major problem for viking4 is how to convert life and death knowledge
into temperatures, such that tactical information can be used. My
tactical module is even slower than my full board evaluation function,
since it actually uses a lazy version of the full board evaluation for
move generation and evaluation of middle game fights. Both systems work
very nice as standalone products but unfortunately 1+1=1.05 in this
case. I might be able to make the integration better, but so far I have
not got any good idea that would not involve further time consuming
search.

The worst problem approximate local temperature is that locality cannot
be defined, since moves anywhere are rarely completely truly
independent.

--
Magnus Persson
Center for Adaptive Behavior and Cognition
Tel: +49-(30)-82406-350
Cell phone: +49 163 6639868


_______________________________________________
computer-go mailing list
computer-go@xxxxxxxxxxxxxxxxx
http://www.computer-go.org/mailman/listinfo/computer-go/