Dear all, This email to comment some old discussions we had in this mailing list around phantom-go. I'm interested in this as I've spent time trying to extend MCTS towards partially observable games, and succeeded only for restricted sets of problems.
It was said that phantom-rengo (japanese rules) is a good candidate for being undecidable, as there's a known undecidability result (by Bob Hearn) stating that a game with - finite state - two teams (with no communication) - unbounded horizon can be undecidable. The undecidable question is "is there a strategy for winning with probability 1 in situation X". and an instance is a position X. However, answering the question above is useless for playing well in a partially observable game. Most partially observable game never or almost never have a strategy for winning whatever the opponent can do: at best, they have a good probability of winning. But with the question above, you can not distinguish between a position in which you have 3% of probability of winning in case of perfect play, and a position in which you have 97% of probability of winning in case of perfect play. A more usefull question is "is move A better than move B in situation X ?" or "is situation X leading to a win with probability at least z% ?" Or these questions are undecidable, as a consequence of the paper by Madani et al on randomized one player games (randomized one player games can simulate non-randomized two player games). This consequence is not written in their paper, but one can prove it mathematically. Therefore, my claim is that phantom-Go (and not only phantom-rengo) is a good candidate for undecidability. Maybe Kriegskiel also, if we remove the rule which limits the length of games. All comments welcome :-) Best regards, Olivier
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
