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/
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/
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/
Re: [computer-go] CGT approximating the sum of subgames
From: Jason House jason.james.ho...@gmail.com On 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.) Link? http://www.cs.rice.edu/~cra1/Home/Publications_files/icga_vol29_4.pdf looks promising. ( just something I googled up ) ___ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
