Game complexity: Difference between revisions

Revision as of 17:05, 20 May 2023

Revision as of 17:37, 20 May 2023

Line 181:

|[[PSPACE-complete]]<ref name="Reisch1980"/>

|-

|[[Computer bridge|Double dummy bridge]]{{refn|group=nb|'''Double dummy bridge''' (i.e., double dummy problems in the context of [[contract bridge]]) is not a proper board game but has a similar game tree, and is studied in [[computer bridge]]. The bridge table can be regarded as having one slot for each player and trick to play a card in, which corresponds to board size 52. Game-tree complexity is a very weak upper bound: 13! to the power of 4 players regardless of legality. State-space complexity is for one given deal; likewise regardless of legality but with many transpositions eliminated. Note that theThe last 4 plies are always forced moves with branching factor 1.}}

|style="text-align:right;"|(52)

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

Line 320:

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

|style="text-align:right;"|<ref name="GamesSolved"/>

|[[PSPACE-complete]]<ref name="Reisch1980">{{cite journal | author = Stefan Reisch | title = Hex ist PSPACE-vollständig (Hex is PSPACE-complete) | journal = Acta Inform. | issue = 15 | year = 1981 | pages = 167–191}}</ref>

|-

|[[Chess]]

Line 435:

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

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

|style="text-align:right;"|<ref name="Thesis_Moesker">{{cite thesis | title=TWIXTTxixt: THEORYTheory, ANALYSISAnalysis, ANDand IMPLEMENTATIONImplementation |

url = https://project.dke.maastrichtuniversity.nl/games/files/msc/Thesis_Moesker.pdf |

author = Kevin Moesker | year=2009 | publisher = Maastricht University, Faculty of Humanities and Sciences of Maastricht University }}</ref>

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

|-