六贯棋(英语:Hex)是在六边形格的棋盘上玩的图版游戏,亦是数学游戏,通常使用10乘10或11乘11的菱形棋盘(约翰·纳什则采用14×14的棋盘)。

Hex - The Zig-Zag Game - Parker Brothers - 1950
六贯棋的常见摆法,除了横摆(见下图)和这种摆法、外,六贯棋亦可 摆成矩形页面存档备份,存于互联网档案馆)。

计算复杂性理论,六贯棋的复杂性已证明了是PSPACE完全的。(注意不少抽象策略游戏国际跳棋象棋围棋都是EXPTIME完全。)

11×11的六贯棋棋盘

历史

六贯棋最初在丹麦数学家海恩于1942年12月26日在丹麦报纸Politiken发表的一篇文章里出现,当时称为Polygon。1948年,约翰·福布斯·纳什重新独立发明了它。追随纳希的玩家最初称这个游戏为Nash。后来1952年Parker Brothers发行了一个版本,将它称为Hex,从此这个名字就定了下来。

规则

 
一种蓝方获胜的情况

六贯棋由两个人一起玩,有两种颜色,通常是红、蓝或黑、白。四个边平行填上两方的颜色。双方轮流下,每次占领一处空白格,在空白格放上自己颜色的棋子(或填上自己的颜色)。最先将棋盘属于自己的颜色的边连成一线的一方为胜。

由于先行的一方有极大的优势,所以有人发明了交换(Swap,或Pie rule)这个规矩。

必胜策略

约翰·纳什证明了六贯棋不可能有和局:让对方无法取胜的充分必要条件就是己方形成了一条连接对边的通路。可以说,六贯棋是一种确定的游戏。

六贯棋的棋盘通常是n×n,虽然两边不相等的棋盘是可行的,但两边之间距离较小的一方必胜。

在n×n的棋盘,先手有必胜策略。证明:

1.因为这个游戏满足
  • 在有限次数内结束
  • 只有两种结果(先手胜或后手胜)
  • 棋手移动时有有限的选择,且为完美信息博弈
根据博弈论策梅洛定理,其中一个棋手必有必胜路线。
2.若后手有必胜策略,先手可以随便走一步,然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋,则再随便走一步,以此类推。考虑后手的最后一步,由于先手使用的是后手必胜策略,那么最后一步必定只有一种走法,此即为先前任意走的那步棋。这将使先手获胜导致矛盾,因此必存在先手必胜策略。

棋盘大小为3至5的六贯棋都可以人手找到先行一方的必胜路线。

相关游戏

外部链接

程式