六贯棋
六贯棋（英语：Hex）是在六边形格的棋盘上玩的图版游戏，亦是数学游戏，通常使用10乘10或11乘11的菱形棋盘（约翰·纳什则采用14×14的棋盘）。
在计算复杂性理论，六贯棋的复杂性已证明了是PSPACE完全的。(注意不少抽象策略游戏如国际跳棋、象棋和围棋都是EXPTIME完全。)
历史
[编辑]六贯棋最初在丹麦数学家海恩于1942年12月26日在丹麦报纸Politiken发表的一篇文章里出现，当时称为Polygon。1948年，约翰·福布斯·纳什重新独立发明了它。追随纳希的玩家最初称这个游戏为Nash。后来1952年Parker Brothers发行了一个版本，将它称为Hex，从此这个名字就定了下来。
规则
[编辑].jpg){kind=spacer}
六贯棋由两个人一起玩，有两种颜色，通常是红、蓝或黑、白。四个边平行填上两方的颜色。双方轮流下，每次占领一处空白格，在空白格放上自己颜色的棋子（或填上自己的颜色）。最先将棋盘属于自己的颜色的边连成一线的一方为胜。
由于先行的一方有极大的优势，所以有人发明了交换(Swap，或Pie rule)这个规矩。
必胜策略
[编辑]约翰·纳什证明了六贯棋不可能有和局：让对方无法取胜的充分必要条件就是己方形成了一条连接对边的通路。可以说，六贯棋是一种确定的游戏。
六贯棋的棋盘通常是n×n，虽然两边不相等的棋盘是可行的，但两边之间距离较小的一方必胜。
在n×n的棋盘，先手有必胜策略。证明：
- 1.因为这个游戏满足
- 在有限次数内结束
- 只有两种结果（先手胜或后手胜）
- 棋手移动时有有限的选择，且为完美信息博弈
- 根据博弈论的策梅洛定理，其中一个棋手必有必胜路线。
- 2.若后手有必胜策略，先手可以随便走一步，然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋，则再随便走一步，以此类推。考虑后手的最后一步，由于先手使用的是后手必胜策略，那么最后一步必定只有一种走法，此即为先前任意走的那步棋。这将使先手获胜导致矛盾，因此必存在先手必胜策略。
棋盘大小为3至5的六贯棋都可以人手找到先行一方的必胜路线。
相关游戏
[编辑]- 六贯棋是Y的子集
- Shannon switching game与六贯棋不同，它并非PSPACE困难。
外部链接
[编辑]- HexWiki （页面存档备份，存于互联网档案馆）
- Jack van Rijswijck's Hex page
- Hex game information center
- OHex （页面存档备份，存于互联网档案馆），在线的资料库
- MazeWorks - Hex-7
- Thesis on Hex （页面存档备份，存于互联网档案馆） history, classification and complexity
- Game of Hex （页面存档备份，存于互联网档案馆） at MathWorld with links to related mathematical papers
- 1×1 to 6×6 opening strategy by Jack van Rijswijck of the University of Alberta
- BoardGameGeek上的Hex
- Printable Hex boards on A4 or A3 paper, for use with standard Go stones
- Game of Hex mathematic analysis and solution by Edouard Rodrigues
- HexWiki a wiki dedicated to Hex