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/
