I've been looking into CGT lately and I stumbled on some articles
about approximating strategies for determining the sum of subgames
(Thermostrat, MixedStrat, HotStrat etc.)
It is not clear to me why approximating strategies are needed. What
is the problem? Is Ko the problem? Is an exact computation too slow?
Can anyone shed some light on this?
The classical theory is only for loopfree games (no ko). Then you get
independent subgames and can talk about sums. Even so, the sum of
simple games can quickly become very complex.
A great tool for exploring CGT is Aaron Siegel's CGSuite
http://cgsuite.sourceforge.net/
For example, consider a game where Black can either capture n white
stones, or White can save them. It can be represented as a
'switch' { 2n | 0 }. Now let's add up several such games with
different numbers of stones. CGSuite computes the 'canonical form',
the simplest single game tree representing such a sum.
> {2|0}
{2|0}
> {2|0} + {4|0}
{6|4||2|0}
> {2|0} + {4|0} + {6|0}
{12|10||8|6|||6|4||2|0}
> {2|0} + {4|0} + {6|0} + {8|0}
{20|18||16|14|||14|12||10|8||||12|10||8|6|||6|4||2|0}
> {2|0} + {4|0} + {6|0} + {8|0} + {10|0}
{{30|28||26|24|||24|22||20|18||||22|20||18|16|||16|14||12|10}|{20|18||
16|14|||14|12||10|8||||12|10||8|6|||6|4||2|0}}
> {2|0} + {4|0} + {6|0} + {8|0} + {10|0} + {12|0}
{{42|40||38|36|||36|34||32|30||||34|32||30|28|||28|26||24|22}|{32|30||
28|26|||26|24||22|20||||24|22||20|18|||18|16||14|12}||{30|28||26|24|||
24|22||20|18||||22|20||18|16|||16|14||12|10}|{20|18||16|14|||14|12||10|
8||||12|10||8|6|||6|4||2|0}}
All these represent very basic Go positions, but the canonical forms
blow up quickly as we add more subgames.
Now in many cases in Go, you can play optimally without computing the
sum explicitly. This is explored in the Berlekamp/Wolfe book.
http://www.akpeters.com/product.asp?ProdCode=0326
I implemented a Go program that can solve such puzzles in my PhD thesis.
http://www.cs.ualberta.ca/~mmueller/cgo/thesis.html
In the best case, you can find one move with an "incentive" that
dominates all other moves, and you can do that with mostly local
computations. However, in the worst case, there will be "incomparable"
moves and you have to compute the messy sum.
Approximate methods can hugely reduce the complexity of all this. For
example, computie only a single number, the temperature, of each
subgame. But even that can be hard when the local games themselves are
complicated. In that case, you want approximate methods such as
Temperature Discovery Search
M. Müller, M. Enzenberger, and J. Schaeffer. Temperature discovery
search. In Nineteenth National Conference on Artificial Intelligence
(AAAI 2004), pages 658-663, San Jose, CA, 2004
http://www.cs.ualberta.ca/~mmueller/publications.html#2004
Now ko is a whole other story :)
Martin
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
