豆芽游戏
豆芽游戏(Sprouts),是种属于抽象策略游戏并且为无偏博弈的纸笔游戏,由数学家约翰·何顿·康威、Michael S. Paterson于1970年代在剑桥大学发表。
![](http://upload.wikimedia.org/wikipedia/commons/thumb/b/b6/Sprouts-2spot-game.png/220px-Sprouts-2spot-game.png)
规则
编辑- 开始前,画上指定数量的点。
- 每方回合在两点(可以是同一点)间画上连接线,然后于此线画上一点。
- 每个点最多连接其他三个点。
- 线可以弯线或直线,不可跨越自己线或其他线。[1]
必胜策略
编辑豆芽游戏有两个版本:普通版本(画最后一条线者赢)和悲惨版本(画最后一条线者输)。由于豆芽游戏是有限游戏且必有胜者,故必有必胜策略,区别只在于胜者是先手还是后手。
关于普通版本,丹尼斯·莫里森(Denis Mollison)在1982年证明,若开局时有6个点,则后下者有必胜策略。截至2011年,开局为44个点及以下的所有情况都有证明。关于悲惨版本,目前已证明至开局为20个点及以下的所有情况。