> In the genreral case of unbounded games, the question is undecidable. But > you wonder if it is still the case for phantom go ? >
For phantom-go with chinese rules, it is decidable by bounded horizon as you have guessed; and yes, for phantom-go with japanese rules, I have no idea. The key point in my email is that, contrarily to usually published results, I consider the question of the probability of winning >=c, and not the question of the probability 1. This makes the question much harder, and in particular it is, in the general case, undecidable, even with just 2 players. > What prevents a brute force approach is the fact that a strategy cannot be > described finitely because of the unboundedness ? > > Yes! The paper by Bob is impressive for that - it shows that a finite game (in the sense of a finite state space) can be undecidable (provided that the horizon is unbounded). But the model in Bob Hearn's results is the existence of a strategy for winning with proba 1, which is not, in my humble opinion, a good model - such a question is not useful for playing optimally, whereas estimating the winning probability is useful for playing (approximately) optimally. Strategies are answers to arbitrarily long sequences of observations. Therefore there are infinitely strategies, even if we consider only deterministic strategies; and no solving by writing the matrix of the game. Using Madani et al, we can show that without more assumptions on the game, this is indeed undecidable.
_______________________________________________ Computer-go mailing list [email protected] http://dvandva.org/cgi-bin/mailman/listinfo/computer-go
