게임 복잡도 문서 원본 보기

{{위키데이터 속성 추적}}
'''게임 복잡도 이론'''은 '''게임'''의 '''복잡성'''을 측정하는 몇 가지 방법을 가지고 있다. 이 문서에서는 그 중 주 공간 복잡성, 게임 트리 크기, 의사결정 복잡성, 게임 트리 복잡성, 계산 복잡성이라는 5가지에 분야에 대해 설명한다.

== 게임 복잡성 측정 ==

=== 주 공간 복잡성 ===
게임의 '''주 공간 복잡성'''은 게임을 처음 위치에서 시작했을 때 도달할 수 있는 합법적인 게임 위치의 경우이다. 게임을 계산하기 너무 어려울 때 가끔 일부 속임수도 세어서 상한을 계산할 수 있는데, 이는 게임 과정에서 절대 일어날 수 없는 포지션을 의미한다.

=== 게임 트리 크기 ===
'''게임 트리 크기'''는 게임을 시작할 수 있는 총 게임 수이다. 게임 트리의 리프 노드 수는 게임 초기 위치에 뿌리를 두고 있다.

게임 트리는 많은 게임에서 서로 다른 순서로 움직여서 같은 위치가 발생할 수 있기 때문에 일반적으로 주 공간보다 훨씬 크다.(예를 들어, 보드에 두 개의 X와 한 개의 O가 있는 틱택토 게임에서, 이 위치는 첫 번째 X가 어디에 놓였는지에 따라 두 가지 다른 방법으로 도달할 수 있었다). 게임 나무의 크기에 대한 상한선은 트랙터블이 될 때까지 게임 나무의 크기만을 증가시키는 방식으로(예를 들어 불법적인 움직임을 허용함으로써) 게임을 단순화함으로써 계산될 수 있다.

이동 횟수가 제한되지 않는 게임(예: 보드 크기 또는 위치 반복에 대한 규칙)의 경우 게임 트리는 일반적으로 무한하다.

=== 의사결정 나무 ===
다음 두 가지 척도는 "A 선수 승리", "B 선수 승리" 또는 "끌어짐"으로 표시된 각 포지션과 함께 게임 트리의 하위 트리인 의사결정 ''트리''의 아이디어를 사용한다. 만약 그 포지션이 그래프에서 다른 포지션만을 검토하여 (양쪽에 의한 최상의 플레이를 가정) 그 가치를 가질 수 있다면 말이다. (단자 위치는 직접 라벨을 붙일 수 있다. A선수가 이동할 수 있는 자리는 A선수가 승리할 경우 "A선수가 승리한다"고 표시하거나, 모든 후임자가 B선수가 승리할 경우 "B선수가 승리한다"고 표시하거나, 모든 후임자가 추첨되거나 B선수가 승리할 경우 "추첨"이라고 표시할 수 있다. 그리고 그에 상응하여 B가 있는 위치가 이동한다.)

==== 의사 결정 복잡성 ====
게임의 '''결정 복잡성'''은 초기 위치의 가치를 설정하는 가장 작은 의사결정 나무의 리프 노드 수이다.

==== 게임 트리의 복잡성 ====
게임의 게임 '''트리 복잡성'''은 초기 위치의 가치를 설정하는 가장 작은 ''전체'' 너비 의사결정 트리의 리프 노드 수이다. 전체 너비 트리는 각 깊이에 있는 모든 노드를 포함한다.

이것은 초기 위치의 값을 결정하기 위해 미니맥스 검색에서 평가해야 할 위치의 수에 대한 추정치다.

게임 트리의 복잡성을 추정하기는 어렵지만, 일부 게임의 경우 게임의 평균 분기 ''요소'' b를 평균 게임에서 플라이 ''수'' d의 힘으로 높여서 근사치를 산출할 수 있다.

<math>GTC \geq b^d</math>

=== 계산 복잡성 ===
게임의 '''계산적 복잡성'''은 게임이 임의적으로 커져서 큰 O 표기법이나 복잡성 등급의 멤버십으로 표현될 때 나타나는 점증적 난이도를 설명한다. 이 개념은 특정 게임에 적용되는 것이 아니라, 일반적으로 n-by-n 보드에서 게임을 함으로써 임의적으로 크게 만들 수 있도록 일반화된 게임들에 적용된다.(계산 복잡성의 관점에서, 고정된 크기의 보드 위에서 게임은 O(1)에서 해결할 수 있는 유한한 문제로서, 예를 들어, p의 조회표에 의해 해결된다. 각 포지션에서 가장 잘 움직일 수 있도록 한다.)

점증적 복잡성은 게임을 해결하기 위해 가장 효율적인(어떤 계산적 자원에 관해서든)알고리즘에 의해 정의된다. 가장 일반적인 복잡성 측정(컴퓨팅 시간)은 가능한 모든 경우에 솔루션 알고리즘이 작동해야 하기 때문에 점증적 상태-공간 복잡성의 로그에 의해 항상 경계를 낮춘다. 게임의 테이트 그것은 게임 패밀리에 작용하는 어떤 특정한 알고리즘의 복잡성에 의해 상한선이 될 것이다. 유사한 언급이 두 번째로 일반적으로 사용되는 복잡성 측정치, 즉 계산에 사용되는 공간이나 컴퓨터 메모리의 양에도 적용된다. 알고리즘이 게임 상태를 저장할 필요가 없기 때문에 일반적인 게임의 공간 복잡성에 하한선이 있다는 것은 명백하지 않다; 그러나 관심 있는 많은 게임들은 PSPACE-hard로 알려져 있고, 그들의 공간 복잡성은 점증적 상태-공간 복잡성의 로그에 의해 하한선이 될 것이다(기술적으로 더 낮다). 바운드(bound)는 이 수량에서 다항식일 뿐이지만, 일반적으로 선형이라고 알려져 있다.

* 깊이-최초 미니맥스 전략은 전체 트리를 탐구해야 하기 때문에 게임의 트리-복잡성에 비례하는 계산 시간과 알고리즘이 가능한 각 이동 깊이에 트리의 한 노드를 항상 저장해야 하기 때문에 트리-복잡성의 로그에 메모리 다항식의 양이 사용되며, 그리고 가장 높은 이동 깊이에서 노드 수를 항상 저장해야 하기 때문이다. 바로 그 나무 조각이다.
* 후진 유도는 각 가능한 위치에 대해 정확한 이동을 계산하고 기록해야 하므로 상태-공간 복잡성에 비례하는 메모리와 시간을 모두 사용한다.

== 교차점 ==
틱택토(tic-tac-toe)의 경우, 주공간의 크기에 대한 단순한 상한은<sup>9</sup> 3 = 19,683이다. (각 셀마다 3개의 상태와 9개의 셀이 있다.) 이 카운트에는 5개의 크로스를 올리고 무득점 포지션이나 두 선수 모두 3열로 된 포지션 등 많은 불법 포지션이 포함된다. 이런 불법적인 자리를 없애면서 더 세심한 카운트를 하면 5,478개가 나온다. 그리고 회전과 위치의 반사가 동일하다고 여겨질 때, 근본적으로 다른 위치는 765개밖에 없다.

게임 트리를 묶기 위해서는 9개의 초기 동작, 8개의 응답 등이 가능하기 때문에 최대 9개의 게임이나 362,880개의 게임이 있다. 그러나, 게임은 해결하는데 9회 미만이 걸릴 수 있으며, 정확한 집계 결과는 255,168개의 가능한 게임을 제공한다. 로테이션과 포지션 반사가 동일하다고 판단되면 26,830경기만 가능하다.

틱택토(tic-tac-toe)의 계산적 복잡성은 그것이 어떻게 일반화되는지에 따라 달라진다. 자연적인 ''일반화''는 m,''n'',k게임에 대한 것이다: 승자는 ''k''를 연속해서 얻은 첫 번째 선수인 m ''by'' n board에서 경기를 한다. 게임트리 전체를 검색하면 이 게임이 DSPACE(''mn'')에서 풀릴 수 있다는 것은 바로 알 수 있다. 이것은 그것을 중요한 복잡성 등급인 PSPACE에 둔다. 더 많은 작업을 통해 PSPACE-완전함을 보여줄 수 있다.

== 게임의 복잡성 ==
이 표는 게임 복잡성이 크기 때문에 로그의 밑을 베이스 10으로 한다. 다음 숫자들은 모두 주의해서 고려해야 한다: 겉보기에는 게임의 규칙을 조금만 바꾸면 (어쨌든 대략적인 추정치인) 숫자가 엄청난 요인에 의해 바뀔 수 있는데, 이것은 표시된 숫자보다 훨씬 더 많을 수 있다.

참고: 게임 트리 크기로 정렬
{| class="wikitable sortable"
!게임
!보드
사이즈

(positions)
!상태 공간 복잡성
(as [[:en:Logarithm|log]] to base 10)
!게임트리의 복잡성
(as [[:en:Logarithm|log]] to base 10)
!평균 게임 길이
([[:en:Ply_(game_theory)|plies]])
!분기계수
!참조
|-
|[[틱택토]]
|  |9
|  |3
|  |5
|  |9
|  |4
|  |
|-
|[[:en:Sim_(pencil_game)|심]]
|  |15
|  |3
|  |8
|  |14
|  |3.7
|  |
|-
|[[:en:Pentomino|펜토미노스목]]
|  |64
|  |12
|  |18
|  |10
| } |75
|  |<ref name="GamesSolved">{{저널 인용|title=Games solved: Now and in the future|journal=Artificial Intelligence|author=H. J. van den Herik|author2=J. W. H. M. Uiterwijk|year=2002|volume=134|issue=1–2|pages=277–311|doi=10.1016/S0004-3702(01)00152-7|author3=J. van Rijswijck|doi-access=free}}</ref><ref>Hilarie K. Orman: ''Pentominoes: A First Player Win'' in ''[http://www.msri.org/publications/books/Book29/contents.html Games of no chance]'', MSRI Publications – Volume 29, 1996, pages 339-344. Online: [http://www.msri.org/publications/books/Book29/files/orman.pdf pdf].</ref>
|-
|[[:en:Kalah|칼라]]<ref>See van den Herik et al for rules.</ref>
|  |14
|  |13
|  |18
|  |
|  |50
|  |<ref name="GamesSolved" />
|-
|[[커넥트포]]
|  |42
|  |13
|  |21
|  |36
|  |4
|  |<ref name="Allis1994">{{학위논문 인용|author=Victor Allis|author-link=Victor Allis|year=1994|title=Searching for Solutions in Games and Artificial Intelligence|degree=Ph.D.|publisher=University of Limburg, Maastricht, The Netherlands|isbn=90-900748-8-0|url=https://project.dke.maastrichtuniversity.nl/games/files/phd/SearchingForSolutions.pdf}}</ref><ref>{{웹 인용|url=https://tromp.github.io/c4/c4.html|title=John's Connect Four Playground|author=John Tromp|year=2010}}</ref>
|-
|[[:en:Domineering|도미니어링]] (8 × 8)
|  |64
|  |15
|  |27
|  |30
|  |8
|  |<ref name="GamesSolved" />
|-
|[[:en:Congkak|콩카크]]
|  |14
|  |15
|  |33
|  |
|  |
|  |<ref name="GamesSolved" />
|-
|[[영미식 체커]]
|  |32
|  |20 or 18
|  |40
|  |70
|  |2.8
|  |<ref name="Allis1994" /><ref>{{저널 인용|title=Checkers is Solved|journal=Science|author=Jonathan Schaeffer|date=July 6, 2007|volume=317|issue=5844|pages=1518–1522|bibcode=2007Sci...317.1518S|doi=10.1126/science.1144079|pmid=17641166|display-authors=etal|s2cid=10274228}}</ref><ref>Schaeffer, Jonathan (2007). "Game over: Black to play and draw in checkers". ''[[ICGA Journal]]''. '''30''' (4): 187–197. [[CiteSeerX (identifier)|CiteSeerX]] 10.1.1.154.255. [[Doi (identifier)|doi]]:10.3233/ICG-2007-30402.</ref>
|-
|[[오와레]]<ref>See Allis 1994 for rules</ref>
|  |12
|  |12
|  |32
|  |60
|  |3.5
|  |<ref name="Allis1994" />
|-
|[[큐빅 (보드 게임)|큐빅]]
|  |64
|  |30
|  |34
|  |20
|  |54.2
|  |<ref name="Allis1994" />
|-
|[[:en:Computer_bridge|더블 더미 브리지]]{{refn|'''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 the last 4 plies are always forced moves with branching factor 1.|group=nb}}
|  |(52)
|  |<17
|  |<40
|  |52
|  |5.6
|
|-
|[[:en:Fanorona|파노로나]]
|  |45
|  |21
|  |46
|  |44
|  |11
|  |<ref name="Schadd2008">{{저널 인용|title=Best Play in Fanorona leads to Draw|journal=[[New Mathematics and Natural Computation]]|author1=M.P.D. Schadd|author2=M.H.M. Winands|url=https://dke.maastrichtuniversity.nl/m.winands/documents/Fanorona.pdf|year=2008|volume=4|issue=3|pages=369–387|doi=10.1142/S1793005708001124|author3=J.W.H.M. Uiterwijk|author4=H.J. van den Herik|author5=M.H.J. Bergsma}}</ref>
|-
|[[나인 멘스 모리스]]
|  |24
|  |10
|  |50
|  |50
|  |10
|  |<ref name="Allis1994" />
|-
|[[:en:Tablut|타블루트]]
|  |81
|  |27
|  |
|  |
|  |
|  |<ref name="Galassi2018">{{웹 인용|url=http://ai.unibo.it/biblio/galassiTablutComplexity|title=An Upper Bound on the Complexity of Tablut|author=Andrea Galassi|date=2018}}</ref>
|-
|[[국제식 체커]](10x10)
|  |50
|  |30
|  |54
|  |90
|  |4
|  |<ref name="Allis1994" />
|-
|[[차이니즈 체커]] (2인용)
|  |121
|  |23
|  |
|  |
|  |180
|  |<ref name="Bell_Halma">{{저널 인용|title=The Shortest Game of Chinese Checkers and Related Problems|journal=Integers|author=G.I. Bell|url=http://emis.ams.org|year=2009|volume=9|arxiv=0803.1245|bibcode=2008arXiv0803.1245B|doi=10.1515/INTEG.2009.003|archive-url=https://web.archive.org/web/20190902211912/http://www.emis.ams.org/|archive-date=2019-09-02|url-status=dead|access-date=2021-06-26|s2cid=17141575}}</ref>
|-
|[[차이니즈 체커]] (6인용)
|  |121
|  |78
|  |
|  |
|  |600
|  |<ref name="Bell_Halma" />
|-
|[[오델로]](리버시)
|  |64
|  |28
|  |58
|  |58
|  |10
|  |<ref name="Allis1994" />
|-
|OnTop (2p base game)
|  |72
|  |88
|  |62
|  |31
|  |23.77
|  |<ref name="OnTopComputer">{{학위논문 인용|title=Analysis and Implementation of the Game OnTop|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Briesemeister_Thesis.pdf|author=Robert Briesemeister|year=2009|publisher=Maastricht University, Dept of Knowledge Engineering}}</ref>
|-
|[[:en:Lines_of_Action|라인스 오브 액션]]
|  |64
|  |23
|  |64
|  |44
|  |29
|  |<ref name="Winands2004">{{학위논문 인용|author=Mark H.M. Winands|year=2004|title=Informed Search in Complex Games|degree=Ph.D.|publisher=Maastricht University, Maastricht, The Netherlands|isbn=90-5278-429-9|url=https://dke.maastrichtuniversity.nl/m.winands/documents/informed_search.pdf}}</ref>
|-
|[[오목]] (15x15, 자유형)
|  |225
|  |105
|  |70
|  |30
|  |210
|  |<ref name="Allis1994" />
|-
|[[헥스]](11x11)
|  |121
|  |57
|  |98
|  |50
|  |96
|  |<ref name="GamesSolved" />
|-
|[[:en:Chess|체스]]
|  |64
|  |44
|  |123
|  |70
|  |35
|  |<ref name="Shannon1950">The size of the state space and game tree for chess were first estimated in {{저널 인용|title=Programming a Computer for Playing Chess|journal=Philosophical Magazine|author=Claude Shannon|author-link=Claude Shannon|url=http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|year=1950|volume=41|issue=314|archive-url=https://web.archive.org/web/20100706211229/http://archive.computerhistory.org/projects/chess/related_materials/text/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon/2-0%20and%202-1.Programming_a_computer_for_playing_chess.shannon.062303002.pdf|archive-date=2010-07-06|url-status=dead}} Shannon gave estimates of 10<sup>43</sup> and 10<sup>120</sup> respectively, smaller than the upper bound in the table, which is detailed in [[Shannon number]].</ref>
|-
|[[비주얼드]] (8x8)
|  |64
|  |<50
|  |
|  |
|  |70
|  |<ref name="Gual14">{{ArXiv 인용|author1=L. Gualà|author2=S. Leucci|author3=E. Natale|title=Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard|eprint=1403.5830|year=2014|class=cs.CC}}</ref>
|-
|[[:en:GIPF_(game)|GIPF]]
|  |37
|  |25
|  |132
|  |90
|  |29.3
|  |<ref name="Wentink_thesis">{{학위논문 인용|title=Analysis and Implementation of the game Gipf|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Wentink_thesis.pdf|author=Diederik Wentink|year=2001|publisher=Maastricht University}}</ref>
|-
|[[육목]]
|  |361
|  |172
|  |140
|  |30
|  |46000
|  |<ref name="EnhancePNConn6">{{서적 인용|title=2009 Chinese Control and Decision Conference|last1=Chang-Ming Xu|last2=Ma|first2=Z.M.|year=2009|pages=4525|chapter=Enhancements of proof number search in connect6|doi=10.1109/CCDC.2009.5191963|isbn=978-1-4244-2722-2|last3=Jun-Jie Tao|last4=Xin-He Xu|s2cid=20960281}}</ref>
|-
|[[백개먼]]
|  |28
|  |20
|  |144
|  |55
|  |250
|  |<ref>{{저널 인용|title=Practical issues in temporal difference learning|journal=Machine Learning|last=Tesauro|first=Gerald|date=1 May 1992|volume=8|issue=3–4|pages=257–277|doi=10.1007/BF00992697|doi-access=free}}</ref>
|-
|[[샹치]]
|  |90
|  |40
|  |150
|  |95
|  |38
|  |<ref name="Allis1994" /><ref name="Hsu2004">{{저널 인용|title=Computer Chinese Chess|journal=International Computer Games Association Journal|author1=Shi-Jim Yen, Jr-Chang Chen|author2=Tai-Ning Yang|url=http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf|date=March 2004|volume=27|issue=1|pages=3–18|doi=10.3233/ICG-2004-27102|archive-url=https://web.archive.org/web/20070614111609/http://www.csie.ndhu.edu.tw/~sjyen/Papers/2004CCC.pdf|archive-date=2007-06-14|url-status=dead|author3=Shun-Chin Hsu}}</ref><ref name="Donghwi">{{ArXiv 인용|author=Donghwi Park|title=Space-state complexity of Korean chess and Chinese chess|eprint=1507.06401|year=2015|class=math.GM}}</ref>
|-
|[[아발론 (보드 게임)|아발론]]
|  |61
|  |25
|  |154
|  |87
|  |60
|  |<ref name="PasChor">{{웹 인용|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/pcreport.pdf|title=Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search|last=Chorus|first=Pascal|publisher=Dept of Knowledge Engineering, Maastricht University|access-date=29 March 2012}}</ref><ref name="Kopczynski">{{학위논문 인용|first=Jacob S|last=Kopczynski|title=Pushy Computing: Complexity Theory and the Game Abalone|publisher=Reed College|year=2014}}</ref>
|-
|[[:en:Havannah|하바나]]
|  |271
|  |127
|  |157
|  |66
|  |240
|  |<ref name="GamesSolved" /><ref>{{웹 인용|url=https://project.dke.maastrichtuniversity.nl/games/files/bsc/bscHavannah.pdf|title=Creating a Havannah Playing Agent|last=Joosten|first=B|access-date=29 March 2012}}</ref>
|-
|[[:en:TwixT|트윅스트]]
|  |572
|  |140
|  |159
|  |60
|  |452
|  |<ref name="Thesis_Moesker">{{학위논문 인용|title=TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION|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>
|-
|[[장기]]
|  |90
|  |44
|  |160
|  |100
|  |40
|  |<ref name="Donghwi" />
|-
|[[쿼리도]]
|  |81
|  |42
|  |162
|  |91
|  |60
|  |<ref name="MasterQuor">{{학위논문 인용|author=Lisa Glendenning|title=Mastering Quoridor|date=May 2005|department=Computer Science|degree=B.Sc.|publisher=[[University of New Mexico]]|url=http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf|url-status=dead|archive-url=https://web.archive.org/web/20120315192840/http://hyperion.cs.washington.edu/attachments/15/glendenning_ugrad_thesis.pdf|archive-date=2012-03-15}}</ref>
|-
|[[카르카손 (보드 게임)|카르카손]]
|  |72
|  |>40
|  |195
|  |71
|  |55
|  |<ref name="CarcassoneComputer">{{학위논문 인용|title=Implementing a Computer Player for Carcassonne|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/MasterThesisCarcassonne.pdf|author=Cathleen Heyden|year=2009|publisher=Maastricht University, Dept of Knowledge Engineering}}</ref>
|-
|[[:en:Game_of_the_Amazons|아마존(10x10)]]
|  |100
|  |40
|  |212
|  |84
|  |374 or 299<ref>The lower branching factor is for the second player.</ref>
|  |<ref name="Kloetzer_themonte-carlo">{{인용|author=Julien Kloetzer|author2=Hiroyuki Iida|author3=Bruno Bouzy|title=The Monte-Carlo Approach in Amazons|year=2007|citeseerx=10.1.1.79.7640}}</ref><ref name="Hengens_thesis">{{웹 인용|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Hensgens_thesis.pdf|title=A Knowledge-Based Approach of the Game of Amazons|author=P. P. L. M. Hensgens|year=2001|publisher=Universiteit Maastricht, Institute for Knowledge and Agent Technology}}</ref>
|-
|[[쇼기]]
|  |81
|  |71
|  |226
|  |115
|  |92
|  |<ref name="Hsu2004" /><ref>{{저널 인용|title=Computer shogi|journal=Artificial Intelligence|author=Hiroyuki Iida|author2=Makoto Sakuta|date=January 2002|volume=134|issue=1–2|pages=121–144|doi=10.1016/S0004-3702(01)00157-6|author3=Jeff Rollason|doi-access=free}}</ref>
|-
|[[:en:Thurn_and_Taxis_(board_game)|Thurn_and_Taxis]] (2 player)
|  |33
|  |66
|  |240
|  |56
|  |879
|  |<ref name="Schadd2010">{{학위논문 인용|author=F.C. Schadd|title=Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis|year=2009|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf|publisher=Maastricht University|archive-url=https://web.archive.org/web/20210114164554/https://project.dke.maastrichtuniversity.nl/games/files/msc/Fschadd_thesis.pdf|archive-date=2021-01-14}}</ref>
|-
|[[바둑]] (19x19)
|  |361
|  |170
|  |505
|  |211
|  |250
|  |<ref name="Allis1994" /><ref name="cwi">{{웹 인용|url=https://tromp.github.io/go/gostate.ps|title=Combinatorics of Go|author1=John Tromp|author2=Gunnar Farnebäck|year=2007}} This paper derives the bounds 48&#x3C;log(log(''N''))&#x3C;171 on the number of possible games ''N''.</ref><ref name="Tromp2016">{{웹 인용|url=https://tromp.github.io/go/legal.html|title=Number of legal Go positions|author=John Tromp|year=2016}}</ref><ref>{{웹 인용|url=https://homepages.cwi.nl/~aeb/go/misc/gostat.html|title=Statistics on the length of a go game}}</ref>
|-
|[[아리마]]
|  |64
|  |43
|  |402
|  |92
|  |17281
|  |<ref name="Cox2006">{{웹 인용|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Cox_thesis1.pdf|title=Analysis and Implementation of the Game Arimaa|author=Christ-Jan Cox|year=2006}}</ref><ref name="Wu2011">{{웹 인용|url=http://icosahedral.net/downloads/djwuthesis.pdf|title=Move Ranking and Evaluation in the Game of Arimaa|author=David Jian Wu|year=2011}}</ref><ref name="Haskin2006">{{웹 인용|url=http://arimaa.janzert.com/bf_study/|title=A Look at the Arimaa Branching Factor|author=Brian Haskin|year=2006}}</ref>
|-
|[[스트라테고]]
|  |92
|  |115
|  |535
|  |381
|  |21.739
|  |<ref name="ArtsStratego">{{학위논문 인용|author=A.F.C. Arts|title=Competitive Play in Stratego|year=2010|url=https://project.dke.maastrichtuniversity.nl/games/files/msc/Arts_thesis.pdf|publisher=Maastricht}}</ref>
|-
|[[:en:Infinite_chess|무한 체스]]{{refn|'''Infinite chess''' is a class of games, which includes [[Infinite chess#Variations|'''Chess on an Infinite Plane''']] and [[Infinite chess#Variations|'''Trappist-1''']] as examples.<ref>[http://www.chessvariants.com/invention/chess-on-an-infinite-plane Chess on an Infinite Plane] game rules</ref><ref>[http://www.chessvariants.com/invention/trappist-1 Trappist-1] game rules</ref>|group=nb}}
|  |무한
|  |무한
|  |무한
|  |무한
|  |무한
|  |<ref>{{ArXiv 인용|author=CDA Evans and Joel David Hamkins|title=Transfinite game values in infinite chess|year=2014|class=math.LO|eprint=1302.4377}}</ref>
|-
|[[매직 더 개더링]]
|  |무한
|  |언바운드됨
|  |언바운드됨
|  |무한
|  |무한
|  |<ref name="Churchill2020">{{저널 인용|title=Magic: the Gathering is Turing Complete|journal=Fun with Algorithms|author=Alex Churchill, Stella Biderman, and Austin Herrick|url=https://arxiv.org/pdf/1904.09828.pdf|year=2020|arxiv=1904.09828}}</ref>
|}

== 같이 보기 ==
* [[풀린 게임]]
== 각주 ==
{{각주}}
; 내용주
<references group="nb" />

[[분류:조합론적 게임 이론]]
[[분류:게임 이론]]