哲球棋
哲球棋(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(页面存档备份,存于互联网档案馆))
策略
移动时,仅跨过一只棋子毫无意义,因为对手可以在下一步放棋到你刚跨过的棋子的位置,再下一步“复原”刚才的棋势。