豆芽遊戲
豆芽遊戲(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個點及以下的所有情況。