Ok, I'll look into your temperature discovery article.
I noticed that Amazons is mentioned a lot in CGT, but I am not familiar with
the game.
I want to use montecarlo to discover subgames. Then I want to use CGT
techniques to evaluate and sum subgames to get a full board evaluation.
If this is possible, it could dramatically reduce the combinatorial explosion
on large boards (like you said, totally killing full board search)
This is the idea. I don't even know if it is possible, but I definitely want to
give it a try.
So far, I've built a GTP engine, a light playouts engine, a transposition table
and a CGT calculator, so I have some basic building blocks.
I'm about to start experimenting with subgame discovery now (but I have a
family and a day job, so progress is slow).
Dave de Vos
________________________________
Van: computer-go-boun...@computer-go.org namens Martin Mueller
Verzonden: do 19-2-2009 0:39
Aan: computer-go
Onderwerp: [computer-go] re-CGT approximating the sum of subgames
I can see in your examples here that the space complexity of the sum
itself grows like 2^terms if the terms are simple forms but not numbers.
(I also took the liberty of adding your examples to my unit tests :)
Does computation time grow much faster than this?
Not sure how bad the worst case is. But it does get worse than this, because of
incomparable options, which multiply in number if both players have lots of
incomparable options at their choice, etc. In my Go example, at least there was
always a unique best move, which keeps the complexity down somewhat.
In the game Amazons you get lots more incomparable options, e.g. try
Amazons(".l...","x...r") in CGSuite, and then Amazons("l....",".....","xxx.r").
Then add one more empty square and you can go for a long walk :)
In Go, we are often lucky since only one, or a small number, of incomparable
incentives exist. But I am sure you can construct examples that are almost as
bad as in Amazons.
I've also stumbled on some complicated articles about loopy games (ko)
so I realize that there is some ground to cover in that direction too :)
I'll read you article about temperature discovery search. Thanks for
pointing me to it.
Are the techniques in that article improvements over the techniques in
http://www.icsi.berkeley.edu/ftp/global/pub/techreports/1996/tr-96-030.pdf ?
The topics are a bit different. In the 1996 tech report, we compute
thermographs for small (but potentially already messy) ko fights. The game
graphs (the moves of the Go game and the results) were input by hand, and the
program just computed the thermographs.
In the TDS paper, we deal only with the loopfree case (no ko). We are doing a
forward search from the starting position, whereas all previous methods used
bottom-up analysis from end positions. We did the experiments in Amazons since
we already had the bottom-up data to compare with. In the second part of this
paper, we try the method on subgames that are too complicated to build the
whole local game tree. We do a time-limited forward search only, but can still
get pretty good approximations to the real temperature. At least it is good
enough to completely kill full-board alphabeta :)
Extending TDS for Go (with ko fights) has been on our to-do list for a long
time. We have an incomplete implementation for that case. But there are still
unresolved research questions, e.g. how to approximately model ko threats in a
way that makes the search computationally feasible yet informative. No progress
in recent years, since that Monte-Carlo business has sucked up all my spare
time :)
Martin
_______________________________________________
computer-go mailing list
computer-go@computer-go.org
http://www.computer-go.org/mailman/listinfo/computer-go/
