跳至內容

組合賽局理論

本頁使用了標題或全文手工轉換
維基百科,自由的百科全書
《穩操勝券》裏介紹的其中一款遊戲:Hackenbush

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

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

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

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

參見

相關期刊

參考

外部連結