Loading AI tools
来自维基百科,自由的百科全书
六貫棋(英語:Hex)是在六邊形格的棋盤上玩的圖版遊戲,亦是數學遊戲,通常使用10乘10或11乘11的菱形棋盤(約翰·納什則採用14×14的棋盤)。
在計算複雜性理論,六貫棋的複雜性已證明了是PSPACE完全的。(注意不少抽象策略遊戲如國際跳棋、象棋和圍棋都是EXPTIME完全。)
六貫棋最初在丹麥數學家海恩於1942年12月26日在丹麥報紙Politiken發表的一篇文章裏出現,當時稱為Polygon。1948年,約翰·福布斯·納什重新獨立發明了它。追隨納希的玩家最初稱這個遊戲為Nash。後來1952年Parker Brothers發行了一個版本,將它稱為Hex,從此這個名字就定了下來。
六貫棋由兩個人一起玩,有兩種顏色,通常是紅、藍或黑、白。四個邊平行填上兩方的顏色。雙方輪流下,每次佔領一處空白格,在空白格放上自己顏色的棋子(或填上自己的顏色)。最先將棋盤屬於自己的顏色的邊連成一線的一方為勝。
由於先行的一方有極大的優勢,所以有人發明了交換(Swap,或Pie rule)這個規矩。
約翰·納什證明了六貫棋不可能有和局:讓對方無法取勝的充分必要條件就是己方形成了一條連接對邊的通路。可以說,六貫棋是一種確定的遊戲。
六貫棋的棋盤通常是n×n,雖然兩邊不相等的棋盤是可行的,但兩邊之間距離較小的一方必勝。
在n×n的棋盤,先手有必勝策略。證明:
棋盤大小為3至5的六貫棋都可以人手找到先行一方的必勝路線。
Seamless Wikipedia browsing. On steroids.
Every time you click a link to Wikipedia, Wiktionary or Wikiquote in your browser's search results, it will show the modern Wikiwand interface.
Wikiwand extension is a five stars, simple, with minimum permission required to keep your browsing private, safe and transparent.