哲球棋
哲球棋(Phutball),原文是Philosopher's football的縮寫,意思是哲學家的足球,第一次於康威、埃爾溫·伯利坎普和蓋伊的《Winning Ways for your Mathematical Plays》(ISBN 1568811306)裏出類的雙人棋類。
規則
編輯哲球棋使用圍棋棋盤(有人則採用19×15的棋盤;其實所有邊界為單數的棋盤都可以使用),亦如圍棋般,棋子要放在線的交叉點;棋盤可以視為「球場」。它的目標是將「球」(某隻棋子)推進對方的「球門」(對方的邊線,可以是上下,或左右,若兩邊長度不同,通常是短邊)。開始時,將「球」放在棋盤中央。雙方輪流下,每次可以放置「人」(和「球」顏色不同的棋子)到球場上的任何未佔據的地方,或移動「球」。移動「球」的方法是讓「球」跨過附近八格的「人」,可以不停地跨直至附近無「人」為止,亦可中途停止。若這些「人」連成一直線,「球」須一次過跨過它們。被跨過的「人」要即時移離棋盤。
複雜性
編輯決定棋手是否存在一條即時取勝的路線,看似很簡單,其實這是NP完備的問題。
參見:Erik D. Demaine, Martin L. Demaine 和 David Eppstein. Phutball Endgames are Hard(pdf(頁面存檔備份,存於網際網路檔案館))
策略
編輯移動時,僅跨過一隻棋子毫無意義,因為對手可以在下一步放棋到你剛跨過的棋子的位置,再下一步「復原」剛才的棋勢。