Combinatorial Game Theory
조합게임이론은 바둑 (baduk) 과 같은 어려운 끝내기문제 (endgame problem) 을 풀 수 있는 수학이론이다. 그것은 정확한 집 계산과 돌의 움직임의 가치를 결정하는 것을 다룬다. 돌의 움직임의 가치는 생각보다 훨씬 복잡하다. 이 이론은 thermography (피부온도측정 으로 병의 유무를 판단 ? : 일부의 관찰로 전체를 예측한다는 의미 ?) 라는 파생분야를 가지는데 그것은 적당한 양의 분석만으로 끝내기를 잘 할 수 있도록 하는데 유용하다. 그것은 또한 sente 와 gote (바둑용어, 선수와 후수) 의 의미를 명확히 설명한다. .... Elwyn Berlekamp, John Conway, Richard Guy 등은 Winning Ways 를 공동 저술하여 조합게임 이론의 기초를 닦았다 ...... David Wolfe 는 Berkeley 에서 조합게임 이론으로 박사학위를 받았으며 조합게임과 최신 바둑의 수에 관한 C library 를 만들었다. 그 중의 subroutine 들을 내 프로그램에서 바둑 수를 풀기위해 사용하기도 하였고 David's combinatorial game theory page 는 좋은 페이지이다 ...... Mathematical Go .... David Moews 도 Berkeley에서 조합게임 이론으로 박사학위를 받았다. Publications 에서는 바둑에서 조합게임 이론을 응용한 것들을 다루고 있다. ....... (Martin Müller : The University of Alberta GAMES Group : 바둑 : Publications : 바둑용어 (영문) : Combinatorial Game Theory)
조합게임 이론은 체스나 바둑과 같이 완전한 지식 (perfect knowledge) 의 2 인용 게임에 대한 전략과 수학을 연구한다. 경제학의 한 분야인 전통의 게임이론 (게임이론 (Game Theory)) 와의 분명한 차이점은 게임 플레이어가 동시에 참여하는 것이 아니라 순서대로 한명씩 돌을 움직인다는 것이며, 따라서 정보를 숨기는 전략이나 무작위로 움직이는 것과는 상관이 없다. 조합게임 이론의 바이블은 Elwyn Berlekamp, John Conway, Richard Guy 공저 Winning Ways for your Mathematical Plays 이며 조합게임 이론의 수학적 기초는 Conway 의 On Numbers and Games 에서 볼 수 있다. 최근의 논문 모임은 Games of No Chance 와 More Games of No Chance 에서 온라인으로 이용할 수 있다. 이러한 책들을 읽지 않았다면 당장에 도서관에 가도록 하라! ..... (David Eppstein : Combinatorial Game Theory)
수학자들은 "game theory" 라는 말을 두가지 의미로 사용한다. 죄수의 딜레마 (Prisoner's dilemma), 포커, 주식 거래 에서와 같은 정보가 불완전한 상태의 게임 ("imperfect-information") 에서 사용되는 의미가 일반적이다. 이러한 류의 게임이론에 관한 연구는 여러사람을 부자로 만들 게 해주며 몇몇 노벨 수상자를 배출하기도 하였다. Drexel 대학의 introductory sketch 에서 그 예를 볼 수 있다 ..... 그러한 종류는 내가 좋아하지 않는 수학 게임이다. 조합게임 이론은 Nim, 틱택토 (Tic-tac-toe) 와 같은 "perfect-information" games 의 결과를 분석한다. 더 어려운 실예로는 Hex, Reversi, Mancala, Checkers, 체스 (chess), 장기, 바둑 (baduk) 등을 들 수 있다. Nancy Casey 가 page full of examples 에서 그 예들을 보여준다 (Nancy 는 "9 년간의 연구결과 내가 무엇을 하는지 설명할 수가 없을 경우에는 그것을 잘 이해하지 못했거나 처음부터 가능성이 없는 것이다" 라고 하여 손을 놓은 상태 ?? )...... 더 자세히 소개된 것으로는 On Numbers and Games (John Conway) 나 Winning Ways for your Mathematical Plays (Elwyn Berlekamp, John Conway, Richard Guy) 등을 들 수 있다. 전자의 책은 수학적인 기초와 탐구과정 위주로 구성되었으며, 후자의 책은 실제적인 게임에 초점을 두고 있다. ....... (Jeff Erickson : web page on combinatorial games)
term :
게임 (Game) 게임이론 (Game Theory) 바둑 (baduk) 체스 (chess) thermography
site :
Wikipedia : Combinatorial game theory
paper :
Elwyn Berlekamp. The Economist's View of Combinatorial Games, pages
365-405. Cambridge University Press, 1996.
[ http://www.msri.org/publications/books/Book29/files/ber.pdf
]
Elwyn Berlekamp and Yonghoan Kim. Where Is the Thousand-Dollar
Ko?, pages 203-226. Cambridge University Press, 1996.
[ http://www.msri.org/publications/books/Book29/files/kim.pdf
]
Elwyn Berlekamp. Idempotents Among Partisan Games, pages 1-23.
Cambridge University Press, 2001.
[ http://math.berkeley.edu/~berlek/papers/idem.ps
]
Joerg Bewersdorff. Go und Mathematik, 1998. In German.
[ http://home.t-online.de/home/joerg.bewersdorff/go.htm
]
Tristan Cazenave. Management of uncertainty in combinatorial game theory.
Technical Report 95-10, Laforia, Paris, 1995.
[ http://www.ai.univ-paris8.fr/~cazenave/cgtmu.ps.gz
]
Tristan Cazenave. Learning to forecast by explaining the consequences of
actions. International Workshop MALFO'96, 1996.
[ http://www.ai.univ-paris8.fr/~cazenave/malfo96.pdf
]
Tristan Cazenave. Système d'Apprentissage Par Auto-Observation.
Application au jeu de Go. PhD thesis, Universite Paris, 1997. In
French.
[ http://www.ai.univ-paris8.fr/~cazenave/these.pdf
]
Erik D. Demaine. Playing games with algorithms: Algorithmic combinatorial game
theory. In 26th Symposium on Mathematical Foundations in Computer Science
(MFCS 2001), volume 2136 of Lecture Notes in Computer Science,
pages 18-32, 2001.
[ http://theory.lcs.mit.edu/~edemaine/papers/AlgGameTheoryMFCS2001/
]
William Edward Fraser. Thermographic analysis of Go endgames using brute force.
Combinatorial Game Theory Workshop, July 2000.
[ http://www.msri.org/publications/ln/msri/2000/gametheory/fraser/1/banner/01.html
]
Howard Landman. Eyespace Values in Go, pages 227-257. Cambridge
University Press, 1996.
[ http://www.msri.org/publications/books/Book29/files/landman.pdf
]
David Moews. On Some Combinatorial Games Connected with Go. PhD thesis,
University of California, Berkeley, 1993.
[ http://xraysgi.ims.uconn.edu:8080/dmoews/thesis.ps
]
Martin Müller. Game theories and computer Go. Go and Computer Science
Workshop (GCSW'93), INRIA, Sophia-Antipolis, 1993.
[ http://www.cs.ualberta.ca/~mmueller/ps/mueller93.ps
]
Martin Müller. Computer Go as a Sum of Local Games: An Application of
Combinatorial Game Theory. PhD thesis, ETH Zürich, 1995.
[ ftp://ftp.inf.ethz.ch/pub/publications/dissertations/th11006.ps.gz
]
Martin Müller, Elwyn Berlekamp, and Bill Spight. Generalized thermography:
Algorithms, implementation, and application to Go endgames. Technical Report
96-030, ICSI, Berkeley, 1996.
[ http://www.cs.ualberta.ca/~mmueller/ps/tr-96-030a.ps.gz
]
Martin Müller. Decomposition search: A combinatorial games approach to game tree
search, with applications to solving Go endgames. In IJCAI-99,
volume 1, pages 578-583, 1999.
[ http://www.cs.ualberta.ca/~mmueller/ps/ijcai1999.ps.gz
]
Martin Müller. Global and local game tree search. Information Sciences,
135:187-206, 2001. The URL links to an older version of the article.
[ http://www.cs.ualberta.ca/~mmueller/ps/mueller-infsci2000.ps.gz
]
Teigo Nakamura. Combinatorial game theory and the game of Go - analyzing semeai.
CGF Journal, 5, 2003. In Japanese.
[ http://www.dumbo.ai.kyutech.ac.jp/htdocs/teigo-ken/teigo/GoResearch/article1.pdf
]
Bill Spight. Analysis of the 4/21/98 Jiang-Rui endgame. Combinatorial Game
Theory Workshop, July 2000.
[ http://www.msri.org/publications/ln/msri/2000/gametheory/spight/1/index.html
]