게임 복잡도

3. 게임별 복잡성

3. 1. 틱택토

3. 2. 차이니즈 체커

참조

_[1] 웹사이트 combinatorics - TicTacToe State Space Choose Calculation https://math.stackex[...] 2020-04-08
_[2] 웹사이트 Btsan/generate_tictactoe https://github.com/B[...] 2018-10-20
_[3] 논문 Gobang ist PSPACE-vollständig (Gobang is PSPACE-complete)
_[4] 간행물 Computers and Games, Second International Conference, CG 2000, Hamamatsu, Japan, October 26-28, 2000, Revised Papers Springer
_[5] 간행물 Games of No Chance: Papers from the Combinatorial Games Workshop held in Berkeley, CA, July 11–21, 1994 Cambridge University Press
_[6] 문서 See van den Herik et al for rules.
_[7] 웹사이트 John's Connect Four Playground https://tromp.github[...]
_[8] 간행물 More Games of No Chance: Proceedings of the 2nd Combinatorial Games Theory Workshop held in Berkeley, CA, July 24–28, 2000 Cambridge University Press
_[9] 논문 Games solved: Now and in the future
_[10] 논문 Checkers is Solved 2007-07-06
_[11] 논문 Game over: Black to play and draw in checkers https://ticc.uvt.nl/[...]
_[12] 논문 N by N checkers is Exptime complete
_[13] 문서 See Allis 1994 for rules
_[14] 간행물 IJCAI 2013, Proceedings of the 23rd International Joint Conference on Artificial Intelligence, Beijing, China, August 3-9, 2013 IJCAI/AAAI
_[15] 논문 Best Play in Fanorona leads to Draw https://dke.maastric[...]
_[16] 웹사이트 An Upper Bound on the Complexity of Tablut http://ai.unibo.it/b[...] 2018
_[17] 논문 The Shortest Game of Chinese Checkers and Related Problems
_[18] 논문 Classes of pebble games and complete problems
_[19] 논문 The Othello game on an $n\backslash times\; n$ board is PSPACE-complete
_[20] 학위논문 Analysis and Implementation of the Game OnTop https://project.dke.[...] Maastricht University, Dept of Knowledge Engineering
_[21] 학위논문 Informed Search in Complex Games https://dke.maastric[...] Maastricht University, Maastricht, The Netherlands
_[22] 논문 Hex ist PSPACE-vollständig (Hex is PSPACE-complete)
_[23] 논문 Programming a Computer for Playing Chess http://archive.compu[...]
_[24] 논문 Computing a perfect strategy for $n\backslash times\; n$ chess requires time exponential in $n$
_[25] 간행물 2014 IEEE Conference on Computational Intelligence and Games, CIG 2014, Dortmund, Germany, August 26-29, 2014 IEEE
_[26] 학위논문 Analysis and Implementation of the game Gipf https://project.dke.[...] Maastricht University
_[27] 서적 2009 Chinese Control and Decision Conference
_[28] 논문 On the fairness and complexity of generalized k -in-a-row games http://dl.acm.org/ci[...] 2018-04-12
_[29] 논문 Practical issues in temporal difference learning 1992-05-01
_[30] 학위논문 Searching for Solutions in Games and Artificial Intelligence https://project.dke.[...] University of Limburg, Maastricht, The Netherlands
_[31] 논문 Computer Chinese Chess http://www.csie.ndhu[...] 2004-03
_[32] arXiv Space-state complexity of Korean chess and Chinese chess
_[33] 웹사이트 Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search https://project.dke.[...] Dept of Knowledge Engineering, Maastricht University 2012-03-29
_[34] 학위논문 Pushy Computing: Complexity Theory and the Game Abalone Reed College
_[35] 웹사이트 Creating a Havannah Playing Agent https://project.dke.[...] 2012-03-29
_[36] arXiv Havannah and TwixT are PSPACE-complete 2014-03-25
_[37] 학위논문 Txixt: Theory, Analysis, and Implementation https://project.dke.[...] Faculty of Humanities and Sciences of Maastricht University
_[38] 학위논문 Mastering Quoridor http://hyperion.cs.w[...] University of New Mexico 2005-05
_[39] 학위논문 Implementing a Computer Player for Carcassonne https://project.dke.[...] Maastricht University, Dept of Knowledge Engineering
_[41] conference Computer Games Workshop, Amsterdam, the Netherlands, 15-17 June 2007
_[42] 웹사이트 A Knowledge-Based Approach of the Game of Amazons https://project.dke.[...] Universiteit Maastricht, Institute for Knowledge and Agent Technology
_[43] arXiv Amazons is PSPACE-complete 2005-02-02
_[44] 저널 Computer shogi 2002-01
_[45] 저널 Shogi on n × n board is complete in exponential time
_[46] 학위논문 Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis https://project.dke.[...] Maastricht University
_[47] 웹사이트 Combinatorics of Go https://tromp.github[...]
_[48] 웹사이트 Number of legal Go positions https://tromp.github[...]
_[49] 웹사이트 Statistics on the length of a go game https://homepages.cw[...]
_[50] 서적 Information Processing; Proceedings of IFIP Congress
_[51] 웹사이트 Analysis and Implementation of the Game Arimaa https://project.dke.[...]
_[52] 웹사이트 Move Ranking and Evaluation in the Game of Arimaa http://icosahedral.n[...]
_[53] 웹사이트 A Look at the Arimaa Branching Factor http://arimaa.janzer[...]
_[54] 학위논문 Competitive Play in Stratego https://project.dke.[...] Maastricht
_[55] arXiv Transfinite game values in infinite chess
_[56] 저널 The mate-in-n problem of infinite chess is decidable
_[57] arXiv Magic: the Gathering is Turing Complete
_[58] arXiv Magic: the Gathering is as Hard as Arithmetic
_[59] arXiv Wordle is NP-hard 2022-05-14
_[60] 저널 Games solved: Now and in the future
_[61] 문서 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].
_[63] 학위논문 Searching for Solutions in Games and Artificial Intelligence https://project.dke.[...] University of Limburg, Maastricht, The Netherlands
_[64] 웹인용 John's Connect Four Playground https://tromp.github[...]
_[65] 저널 Checkers is Solved 2007-07-06
_[66] 간행물 Game over: Black to play and draw in checkers
_[68] 저널 Best Play in Fanorona leads to Draw https://dke.maastric[...]
_[69] 웹인용 An Upper Bound on the Complexity of Tablut http://ai.unibo.it/b[...] 2018
_[70] 저널 The Shortest Game of Chinese Checkers and Related Problems http://emis.ams.org 2021-06-26
_[71] 학위논문 Analysis and Implementation of the Game OnTop https://project.dke.[...] Maastricht University, Dept of Knowledge Engineering
_[72] 학위논문 Informed Search in Complex Games https://dke.maastric[...] Maastricht University, Maastricht, The Netherlands
_[73] 저널 Programming a Computer for Playing Chess http://archive.compu[...]
_[74] ArXiv Bejeweled, Candy Crush and other Match-Three Games are (NP-)Hard
_[75] 학위논문 Analysis and Implementation of the game Gipf https://project.dke.[...] Maastricht University
_[76] 서적 2009 Chinese Control and Decision Conference
_[77] 저널 Practical issues in temporal difference learning 1992-05-01
_[78] 저널 Computer Chinese Chess http://www.csie.ndhu[...] 2004-03
_[79] ArXiv Space-state complexity of Korean chess and Chinese chess
_[80] 웹인용 Implementing a Computer Player for Abalone Using Alpha-Beta and Monte-Carlo Search https://project.dke.[...] Dept of Knowledge Engineering, Maastricht University 2012-03-29
_[81] 학위논문 Pushy Computing: Complexity Theory and the Game Abalone Reed College
_[82] 웹인용 Creating a Havannah Playing Agent https://project.dke.[...] 2012-03-29
_[83] 학위논문 TWIXT: THEORY, ANALYSIS AND IMPLEMENTATION https://project.dke.[...] Maastricht University, Faculty of Humanities and Sciences of Maastricht University
_[84] 학위논문 Mastering Quoridor http://hyperion.cs.w[...] University of New Mexico 2005-05
_[85] 학위논문 Implementing a Computer Player for Carcassonne https://project.dke.[...] Maastricht University, Dept of Knowledge Engineering
_[86] 문서 The lower branching factor is for the second player.
_[87] 인용 The Monte-Carlo Approach in Amazons
_[88] 웹인용 A Knowledge-Based Approach of the Game of Amazons https://project.dke.[...] Universiteit Maastricht, Institute for Knowledge and Agent Technology
_[89] 저널 Computer shogi 2002-01
_[90] 학위논문 Monte-Carlo Search Techniques in the Modern Board Game Thurn and Taxis https://project.dke.[...] Maastricht University
_[91] 웹인용 Combinatorics of Go https://tromp.github[...]
_[92] 웹인용 Number of legal Go positions https://tromp.github[...]
_[93] 웹인용 Statistics on the length of a go game https://homepages.cw[...]
_[94] 웹인용 Analysis and Implementation of the Game Arimaa https://project.dke.[...]
_[95] 웹인용 Move Ranking and Evaluation in the Game of Arimaa http://icosahedral.n[...]
_[96] 웹인용 A Look at the Arimaa Branching Factor http://arimaa.janzer[...]
_[97] 학위논문 Competitive Play in Stratego https://project.dke.[...] Maastricht
_[98] 웹사이트 Chess on an Infinite Plane http://www.chessvari[...]
_[99] 웹사이트 Trappist-1 http://www.chessvari[...]
_[100] ArXiv Transfinite game values in infinite chess
_[101] 저널 Magic: the Gathering is Turing Complete https://arxiv.org/pd[...]