> How do you know what [complexity] class go belongs in? Hi Robert, If these topics interest you, you probably want to start by reading the papers [1] about the complexity of go. Then if you still disagree take up a specific point with the paper authors.
Both minimax and UCT solve go simply because they eventually make an exhaustive tree. You are quite right in pointing out that these results are theoretical, not practical, as we are unlikely ever to have the computing power or memory to make an exhaustive tree even for 9x9 go. Don, the Mogo team, and others, have collected good evidence that MCTS (i.e. UCT) algorithms scale very nicely at more practical hardware levels. On the other hand if you remake Don's scaling graph [2] with absolute instead of logarithmic axes then it is no longer straightish, but instead (looks like) it is flattening out. I.e. the improvement is not linear with computing power; you have to try harder to get each additional rank of improvement. (I know Don understands this, and his point with that whole experiment was just to prove his claim that "more cpu cycles always help".) Darren [1]: Looks like this provides a starting point of papers to read: http://senseis.xmp.net/?ComplexityOfGo [2]: (Sorry, cannot find the URL at the moment.) -- Darren Cook, Software Researcher/Developer http://dcook.org/mlsn/ (English-Japanese-German-Chinese-Arabic open source dictionary/semantic network) http://dcook.org/work/ (About me and my work) http://darrendev.blogspot.com/ (blog on php, flash, i18n, linux, ...) _______________________________________________ computer-go mailing list computer-go@computer-go.org http://www.computer-go.org/mailman/listinfo/computer-go/
