Revision as of 18:15, 23 May 2023 edit Quantumly (talk \| contribs) 34 edits The EXP-completeness result only applies when moves are allowed to repeat indefinitely. However, adding the rule that moves cannot repeat, the Exponential time lower bound no longer holds and it is only known to be PSPACE-hard but in EXPSPACE. It is this possible that adding this rule makes the game more computationally difficult (i.e., being EXPSPACE-complete), but it could also be that it makes the game easier (i.e., PSPACE-complete). This rule is included in most rulebooks except in Japan. Tags: Visual edit Mobile edit Mobile web edit ← Previous edit		Revision as of 04:48, 24 May 2023 edit undo Quantumly (talk \| contribs) 34 edits →Complexities of some well-known games Next edit →
Line 535: \|style="text-align:right;"\|250 \|style="text-align:right;"\|<ref name="Allis1994"/><ref name="cwi">{{cite web \| title = Combinatorics of Go \|author1=John Tromp \|author2=Gunnar Farnebäck \| year = 2007 \| url = https://tromp.github.io/go/gostate.ps}} This paper derives the bounds 48<log(log(''N''))<171 on the number of possible games ''N''.</ref><ref name="Tromp2016">{{cite web \| title=Number of legal Go positions \| author=John Tromp \| year=2016 \| url=https://tromp.github.io/go/legal.html}}</ref> \|[[EXPTIME-complete]] (~~Without~~without the [[superko rule]], otherwise [[PSPACE-hard]], and in [[EXPSPACE]])<ref name="Robson1983">{{Cite book \| author = J. M. Robson \| chapter = The complexity of Go \| title = Information Processing; Proceedings of IFIP Congress \| year = 1983 \| pages = 413–417}}</ref> \|- \|[[Arimaa]]

Game complexity: Difference between revisions