豆芽游戏

豆芽游戏(Sprouts),是种属于抽象策略游戏并且为无偏博弈纸笔游戏,由数学家约翰·何顿·康威、Michael S. Paterson于1970年代在剑桥大学发表。

两点开局的豆芽棋对弈

规则

  • 开始前,画上指定数量的点。
  • 每方回合在两点(可以是同一点)间画上连接线,然后于此线画上一点。
    • 每个点最多连接其他三个点。
    • 线可以弯线或直线,不可跨越自己线或其他线。[1]

必胜策略

豆芽游戏有两个版本:普通版本(画最后一条线者赢)和悲惨版本(画最后一条线者输)。由于豆芽游戏是有限游戏且必有胜者,故必有必胜策略,区别只在于胜者是先手还是后手。

关于普通版本,丹尼斯·莫里森(Denis Mollison)在1982年证明,若开局时有6个点,则后下者有必胜策略。截至2011年,开局为44个点及以下的所有情况都有证明。关于悲惨版本,目前已证明至开局为20个点及以下的所有情况。

参考

  1. ^ Sprouts. [2012-01-17]. (原始内容存档于2016-01-30). 

对外链接