六貫棋
六貫棋（英語：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