无偏博弈

在组合博弈论裡,无偏博弈是一类任意局势对于游戏双方都是平等的回合制双人游戏。这里平等的意思是所有可行的走法仅仅依赖于当前的局势,而与现在正要行动的是哪一方无关。换句话说,两个游戏者除了先后手之外毫无区别。此外,它们还要满足一些组合游戏的基本条件:

*完全信息,所有游戏者都能看到整个局势。这排除了桥牌一类的游戏。
*无随机行动。所有行动都确定性地将目前局势转变到下一个局势。
*在有限步行动之后按照规则游戏必将终止,此时有唯一的一方成为赢家。

即使常见的棋類如象棋、围棋、五子棋等抽象策略遊戲等能符合以上三条规定(可能需要附加一些防止无限循环的规则),但都不是无偏博弈,因为它们不是共用棋子,双方走法因而要造成局势的不同变化。但是如果定义五子棋的一个变种:双方都共用棋子,先连成5子一线算胜利,那么这个变种是无偏博弈。冰山棋雖共用棋子,但因為採用計分的勝利規則,不是无偏博弈。

大同棋、塞磚棋、巧克力棋、豆芽棋、尼姆遊戲都是无偏博弈。

根据斯普莱格–格隆第定理,每个无偏博弈的特定局势都对应着一个尼姆数。这一定理是对无偏博弈进行分析的主要工具。

參考文献
*

相关链接
以下网站上有在线的无偏博弈可以试玩。
*[http://www.cut-the-knot.org Cut the knot]
*[http://quarto.freehostia.com/en Quarto]
*[https://web.archive.org/web/20100611064632/http://lpcs.math.msu.su/~pentus/abacus.htm Chomp]

评论 (0)

  • 还没有评论,来抢沙发吧。