Game complexity: Difference between revisions

Revision as of 17:40, 20 May 2023

Revision as of 19:25, 20 May 2023

Line 1:

{{Short description|Notion in combinatorial game theory}}

{{Use mdy dates|cs1-dates=ly|date=May 2023}}

[[Combinatorial game theory]] has several ways of [[Computational complexity theory|measuring]] '''game [[complexity]]'''. This article describes five of them: state-space complexity, game tree size, decision complexity, game-tree complexity, and computational complexity.

Line 82 ⟶ 83:

|style="text-align:right;"|3.7

|style="text-align:right;"|

|[[PSPACE-complete]]<ref>{{cite conference

|[[PSPACE-complete]]<ref>{{cite book|url=http://dl.acm.org/citation.cfm?id=647481.728124|title=The Complexity of Graph Ramsey Games|first=Wolfgang|last=Slany|date=26 October 2000|publisher=Springer-Verlag|pages=186–203|access-date=12 April 2018|via=dl.acm.org|isbn=9783540430803}}</ref>

| last = Slany | first = Wolfgang

| editor1-last = Marsland | editor1-first = T. Anthony

| editor2-last = Frank | editor2-first = Ian

| contribution = The complexity of graph Ramsey games

| doi = 10.1007/3-540-45579-5_12

| pages = 186–203

| publisher = Springer

| series = Lecture Notes in Computer Science

| title = Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers

| volume = 2063

| year = 2000}}</ref>

|-

|[[Pentomino]]es

Line 160 ⟶ 172:

|style="text-align:right;"|70

|style="text-align:right;"|2.8

|style="text-align:right;"|<ref name="Allis1994"/><ref>{{cite journal | author = Jonathan Schaeffer| title = Checkers is Solved | journal = Science | date = July 6, 2007 | doi=10.1126/science.1144079 | volume=317 |issue= 5844 |pages= 1518–1522 | pmid=17641166 |display-authors=etal|bibcode=2007Sci...317.1518S | s2cid = 10274228 }}</ref><ref>Schaeffer,{{cite Jonathanjournal
| (2007).last "Game= over:Schaeffer Black| tofirst play= and draw in checkers". ''[[ICGA Journal]]''. '''30''' (4): 187–197. [[CiteSeerX (identifier)Jonathan
|CiteSeerX]] 10.1.1.154.255.doi [[Doi= (identifier)|doi]]:10.3233/ICG-2007-30402.</ref>

| issue = 4

| journal = [[ICGA Journal]]

| pages = 187–197

| title = Game over: Black to play and draw in checkers

| url = https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf

| archive-url = https://web.archive.org/web/20160403093928/https://ticc.uvt.nl/icga/journal/contents/Schaeffer07-01-08.pdf

| archive-date = 2016-04-03

| url-status = dead

| volume = 30

| year = 2007}}</ref>

|[[EXPTIME-complete]]<ref name="robson1984">{{cite journal | author = J. M. Robson | title = N by N checkers is Exptime complete | journal = [[SIAM Journal on Computing]] | volume = 13 | issue = 2 | pages = 252–267 | year = 1984 | doi = 10.1137/0213018}}</ref>

|-