豆芽遊戲
豆芽遊戲（Sprouts），是種屬於抽象策略遊戲並且為無偏博弈的紙筆遊戲，由數學家約翰·何頓·康威、Michael S. Paterson於1970年代在劍橋大學發表。
規則
[編輯]- 開始前，畫上指定數量的點。
- 每方回合在兩點（可以是同一點）間畫上連接線，然後於此線畫上一點。
- 每個點最多連接其他三個點。
- 線可以彎線或直線，不可跨越自己線或其他線。[1]
必勝策略
[編輯]豆芽遊戲有兩個版本：普通版本（畫最後一條線者贏）和悲慘版本（畫最後一條線者輸）。由於豆芽遊戲是有限遊戲且必有勝者，故必有必勝策略，區別只在於勝者是先手還是後手。
關於普通版本，丹尼斯·莫里森（Denis Mollison）在1982年證明，若開局時有6個點，則後下者有必勝策略。截至2011年，開局為44個點及以下的所有情況都有證明。關於悲慘版本，目前已證明至開局為20個點及以下的所有情況。