六貫棋

六貫棋（英語：）是在六邊形格的棋盤上玩的圖版遊戲，亦是數學遊戲，通常使用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的六貫棋都可以人手找到先行一方的必勝路線。棋盤大小為6的六貫棋由Queenbee找到了必勝路線，棋盤大小為7的解答可在楊靖的網站找到。

相關遊戲
  • 六貫棋是Y的子集
  • Shannon switching game與六貫棋不同，它並非PSPACE困難。

六貫棋必勝的核心概念就是雙活,而不同大小棋盤之間的關係就是堆疊,所以對任意大小的n層棋盤,皆可視為(n-1)層棋盤外再加一層,所以依照這個概念,我們只要有任意一種棋盤的必勝走法,就能利用六邊形方格的特性向外擴張,立用這樣的想法,省略中間的推導過程,那麼設現在有一n×n的拿許棋盤，而我們有k×k拿許棋盤的必勝法，k≦n，現在在n×n的棋盤中任意下一點，則這一子所佔有的「領域」，就是以這一子為一角，所畫出來的k×k拿許棋盤，但是這一角需是k×k拿許棋盤的必是點之一，如此就能確保上下兩端貫通，如果將這一塊棋盤旋轉，取剛好完全重疊的部份，能到一個六邊形的方格，可想成以一個方格為基礎所做出來的大方格，而這個方格，即是這一點所具有的”完整領域”，而先手接下來只要確保領域和領域了貫通，就能做出必勝策略，至於要如何貫通，就是要預測貫通點，只要預測出的貫通點或貫通方式有兩種或兩種以上，就能得到必勝策略。

外部連結

程式
This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. Additional terms may apply for the media files.