组合游戏-定义
一个组合游戏是满足下列条件的二人游戏:
- 这个游戏是确定性:这里不存在像抛硬币或掷骰子那样的随机机制。
- 有完美的信息在游戏中:每个玩家都知道关于游戏状态的所有信息,没有什么是隐藏的。
求解这些博弈的方法分析在组合游戏——获胜的位置.
著名的例子
组合游戏的著名例子有三字棋、跳棋、国际象棋、围棋、圆点和盒子以及尼姆。
一个有限的组合游戏总会结束;不存在导致无限博弈的一系列动作。这意味着国际象棋的基本形式不是有限的,而井字游戏是有限的。
组合博弈正常的游戏惯例是一种游戏,第一个无法移动的玩家输了。(如果双方玩家都能继续移动,就被认为是平局;当然,这只有在游戏不是有限的情况下才会发生。)国际象棋,在某种意义上,是正常的游戏,但许多游戏,如一字棋,围棋,或点和盒子,不正常。
组合博弈使用misère play convention是一种反转结果的游戏;如果一个玩家在一场正常的游戏中会输,他们就会赢。也许最常见的misère游戏是misère Nim(在正常的Nim中,不能移动的玩家输了;在misère Nim中,不能移动的玩家获胜)。
公正的游戏
公正的游戏是组合游戏,两个玩家之间没有区别(游戏是公正的),除了一个人开始游戏。从形式上讲,要让游戏具有公正性,它必须满足两个附加条件。
1)可用的招式仅取决于游戏的位置,而不取决于哪个玩家的回合。
2)任何特定移动对双方玩家的价值是相同的。
条件1排除了许多常见的游戏,如一字棋、跳棋、国际象棋和围棋。在所有游戏中,一名玩家只能移动/放置一种棋子(白棋),而另一名玩家只能移动/放置另一种棋子(黑棋)。
最著名的公正游戏是尼姆.尼姆的游戏是由两个玩家玩和使用 成堆的石头,大小不一 .在一个回合中,玩家可以从一堆石头中移除任意数量的石头。当没有剩下的石头时游戏结束,轮到谁移动的人将输掉游戏。