博弈复杂度
博弈复杂度（）可以用许多方法加以衡量。本条目讲述其中的5種方法：状态空间复杂度（）、博弈树的大小（）、策略复杂度（）、博弈树复杂度（）與计算复杂度（）。 博弈复杂度的衡量 状态空间复杂度 状态空间复杂度指的是从博弈最开始的状态可以变化出的符合规则的状态的数量。 一些知名博弈的复杂度 由于博弈复杂度非常巨大，下面表中一些数据只显示了以10为底数的指数部分。下面的表中的数值都需要小心对待：在博弈中，一个看起来很微小的规则变换会引起结果的巨大…
标签：#组合博弈论
共 9 篇文章
組合博弈論
組合博弈論是博弈論的一個分支，但跟主流博弈論不同的是，組合博弈論學者的研究對象絕大部份是資訊全知的且不帶機率成份的。 組合博弈論的主要研究對象是資訊完全、輪流行步的二人博弈。（此條目以下提及「博弈」或「遊戲」一詞，如非特別聲明，均指的都是組合博弈論的資訊完全且不帶機率成份的二人博弈。）其中一個重要的研究對象是尼姆。根據斯普莱格–格隆第定理，所有無偏博弈都可對應一局尼姆博弈。 組合博弈論較早的一篇論文是查理斯·雷納德·包頓的《拈及其相關的…
蒙特卡洛树搜索
蒙特卡洛树搜索（；简称：MCTS）是一种用于某些决策过程的启发式搜索算法，最引人注目的是在游戏中的使用。一个主要例子是电脑围棋程序，它也用于其他棋盘游戏、即时电子游戏以及不确定性游戏。 历史 基于随机抽样的蒙特卡洛方法可以追溯到20世纪40年代。布鲁斯·艾布拉姆森（Bruce Abramson）在他1987年的博士论文中探索了这一想法，称它“展示出了准确、精密、易估、有效可计算以及域独立的特性。”他深入试验了井字棋，然后试验了黑白棋和国…
尼姆游戏
尼姆游戏（），又譯為拈，是一种两个人玩的回合制数学战略游戏。游戏者轮流从幾排棋子（或者任何道具）中選擇一排，再由這一排中取走一个或者多个，依規則不同，拿走最後一個的可能是输家，也有可能是贏家。当指定相应数量时，一堆这样的棋子称作一个尼姆堆。古代就有許多尼姆游戏的變體。最早歐洲有關尼姆游戏的參考資料是在16世紀，目前使用的名稱是由哈佛大学的Charles L. Bouton命名，他也在1901年提出了此遊戲的完整理論，不過沒有說明名稱的由…
分支因子
]] 在电脑运算、树数据结构、賽局理論领域中，分支因子（）是每个下的子结点数，即出度。如果各个结点分支因子不同，则可以计算平均分支因子。 例如，在国际象棋中，如把一步合法走法算作一个“结点”，那么平均分支因子据信约为35。这表示，棋手每一步走棋平均有大约35种合法走法。相比之下，围棋的分支因子为250。 }}
围棋与数学
围棋是世界上最流行的游戏之一。由于其规则优美而简单，围棋一直是数学研究的灵感来源。11世纪的中国学者沈括在《梦溪笔谈》中估计，围棋所有可能的局面数量为 10172 左右。近年来，約翰·H·康威在对围棋的研究中发明了超現實數，并促进了组合博弈论的发展（“围棋微数字”就是它在围棋中使用的一个具体示例）。 计算复杂性 广义围棋是在 n x n 的棋盘上进行的，在广义围棋的给定位置确定赢家的计算复杂性主要取决于打劫规则。 围棋的复杂性“几乎”是…
尼姆数
组合博弈论引入了一类数学对象，称为尼姆数，它们被定义为尼姆堆的值。但是由于斯普莱格–格隆第定理，它们可以用于一大类游戏的研究。事实上，尼姆数是在序数的真类上赋予尼姆加法和尼姆乘法的运算之后形成的概念。这些运算和通常施行于序数类上的加法和乘法并不相同。 尼姆数的特点 斯普莱格–格隆第定理指出：每个无偏博弈等价于一个特定大小的尼姆堆。尼姆数的加法运算（叫做尼姆加法）可以用于计算等价于多个堆的单一尼姆堆大小。这被定义为 :\alpha + \…
天使问题
天使问题是由英国数学家约翰·何顿·康威提出的一个博弈论问题，在2006年已獲解答。 陳述 天使问题是關於一個叫*天使與惡魔的雙人遊戲，其規則如下： 兩名玩家分別扮演天使和惡魔 遊戲開始前，指定一個正整數 K，稱之為天使的力量 游戏在一个无限大的方格棋盘上进行；开始时棋盘是空的，天使停留在棋盘上的某一个方格（称为天使的起始点），恶魔并不存在于棋盘上 每一轮中，恶魔可以在棋盘上放置一个路障，路障不可以放置在天使停留处 每一轮中，天使可以向相…
斯普莱格–格隆第定理
在组合博弈论中，斯普莱格–格隆第定理证明， 所有的一般胜利条件下的无偏博弈都能转换成尼姆数表达的尼姆堆博弈。 一个无偏博弈的尼姆值定义为这个博弈的等价尼姆数。