組合博弈論博弈論的一個分支,但跟主流博弈論不同的是,組合博弈論學者的研究對象絕大部份是資訊全知的且不帶概率成份的。

《穩操勝券》裏介紹的其中一款遊戲:Hackenbush

組合博弈論的主要研究對象是資訊完全、輪流行步的二人博弈。(此條目以下提及「博弈」或「遊戲」一詞,如非特別聲明,均指的都是組合博弈論的資訊完全且不帶概率成份的二人博弈。)其中一個重要的研究對象是尼姆。根據斯普萊格–格隆第定理,所有無偏博弈都可對應一局尼姆博弈。

組合博弈論較早的一篇論文是查理斯·雷納德·包頓的《拈及其相關的完全數學理論》(Nim, A Game with a Complete Mathematical Theory)。 1982年, 埃爾溫·伯利坎普約翰·何頓·康威理查德·蓋伊出版《穩操勝券》(Winning Ways for your Mathematical Plays,此系列書第二版出版於2001–2004年),當中分析了大量資訊完全的兩人遊戲,此外也分析了一些單人遊戲及一種「零人遊戲」(zero-person game)細胞自動機。此著作裏,作者利用超現實數的概念來分析資訊完全的兩人遊戲。(超現實數的概念,後來高德納撰寫了幾本小書用以普及。)

近年,在組合博弈論的研究圈子裏,針對一些遊戲,結合電腦科學裏的計算複雜度演算法分析的研究也相當活躍。

參見

編輯

相關期刊

編輯

參考

編輯

外部連結

編輯