Revision as of 04:48, 24 May 2023 edit Quantumly (talk \| contribs) 34 edits →Complexities of some well-known games ← Previous edit		Revision as of 04:55, 24 May 2023 edit undo Quantumly (talk \| contribs) 34 edits The table for GO seemed too crowded and so I've decided that the extra information may be better to stay in the wiki page of "Go in mathematics". 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 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