豆芽遊戲(Sprouts),是種屬於抽象策略遊戲並且為無偏博弈紙筆遊戲,由數學家約翰·何頓·康威、Michael S. Paterson於1970年代在劍橋大學發表。

兩點開局的豆芽棋對弈

規則

編輯
  • 開始前,畫上指定數量的點。
  • 每方回合在兩點(可以是同一點)間畫上連接線,然後於此線畫上一點。
    • 每個點最多連接其他三個點。
    • 線可以彎線或直線,不可跨越自己線或其他線。[1]

必勝策略

編輯

豆芽遊戲有兩個版本:普通版本(畫最後一條線者贏)和悲慘版本(畫最後一條線者輸)。由於豆芽遊戲是有限遊戲且必有勝者,故必有必勝策略,區別只在於勝者是先手還是後手。

關於普通版本,丹尼斯·莫里森(Denis Mollison)在1982年證明,若開局時有6個點,則後下者有必勝策略。截至2011年,開局為44個點及以下的所有情況都有證明。關於悲慘版本,目前已證明至開局為20個點及以下的所有情況。

參考

編輯
  1. ^ Sprouts. [2012-01-17]. (原始內容存檔於2016-01-30). 

對外鏈接

編輯