The branching factor of two is the branching factor of a canonical subgame tree used for summing the subgames (the canonical subgame tree is built by backtracking from terminal nodes), not the branching factor of exploration to reach terminal nodes. So I think the complexity of summing subgames would be the O(sum of 2^n(k)) where n(k) is the number of vertices involved in subgame k. I understand that ko creates dependencies between subgames which is a problem, because subgames have to be independent. But then I don't understand how approximating the sum of subgames helps in solving this problem. So are approximating strategies aiming to mitigate the ko problem or are they aiming at some different problem (leaving the ko problem unsolved)? Dave de Vos
________________________________ Van: terry mcintyre [mailto:terrymcint...@yahoo.com] Verzonden: wo 18-2-2009 20:43 Aan: dave.de...@planet.nl Onderwerp: Re: [computer-go] CGT approximating the sum of subgames Why a branching factor of two? If ko is involved, one may pick one of n ko threats ( which usually alters a sub-game); the option is then to either connect the ko, or make one of m replies to the threat -- and sometimes the threat involves another ko. The main problem, as I see it, ( I can't even begin to play an "expert" even on the internet, lol ) is that ko allows otherwise independent sub-games to be linked closely together. "You keep this, I get that in recompense." Terry McIntyre <terrymcint...@yahoo.com> -- Libertarians Do It With Consent! ________________________________ From: "dave.de...@planet.nl" <dave.de...@planet.nl> To: computer-go <computer-go@computer-go.org> Sent: Wednesday, February 18, 2009 11:30:43 AM Subject: RE: [computer-go] CGT approximating the sum of subgames Or is it it a problem to extract the best move when the sum of subgames is known but not equal to a number (which will often be the case)? ________________________________ Van: computer-go-boun...@computer-go.org namens dave.de...@planet.nl Verzonden: wo 18-2-2009 20:04 Aan: computer-go Onderwerp: RE: [computer-go] CGT approximating the sum of subgames Are you saying that - calculating the exact sum is too expensive? - calculating the exact sum does not give the the best move? - the existence of Ko in go makes it impossible to split the board in independent subgames? A subgame may not be a number in many cases, but using canonicalforms backtracked from terminal nodes, wouldn't we still be able to calculate the exact sum of subgames without ambiguity? (if implemented according to the definition 2.7 in http://arxiv.org/PS_cache/math/pdf/0410/0410026v2.pdf and pruning dominated and reversible options). Is this incorrect? A full canonical subgame tree would only have a branching factor of at most two (each subgame consists of only a left and right stop to represent the confusion interval recursively). That does not seem too bad to me, so I wonder why it is that expensive to calculate the sum of subgames. Dave ________________________________ Van: computer-go-boun...@computer-go.org namens Eric Boesch Verzonden: wo 18-2-2009 16:50 Aan: computer-go Onderwerp: Re: [computer-go] CGT approximating the sum of subgames On Tue, Feb 17, 2009 at 4:39 PM, <dave.de...@planet.nl> wrote: > 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? I'm sure someone else could give a better answer, but it does come down to slowness. Same thing as assuming the value of a gote move equals the position value if black moves first averaged with its value if white moves first, and the game score equals original score plus half the value of the largest move on the board -- these assumptions are wrong, and they estimates are not guaranteed to yield either the correct score or the biggest play on the board, but you have to do something if you can't perfectly read out the rest of the game. If CGT values were all nice real numbers that summed normally when combining subgames, then CGT would be a lot simpler. The possibility of wanting to play a ko threat in another part of the board prevents the two areas from being separate subgames in the technical sense -- the information sets are shared. _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
_______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
