六貫棋：修订间差异
删除的内容 添加的内容
小 →歷史： 修正筆誤（刪除多餘的換行） |
|||
| （未显示3个用户的4个中间版本） | |||
| 第2行： | 第2行： | ||
[[File:hex six.png|right|thumb|250px|六貫棋的常見擺法，除了橫擺(見下圖)和這種擺法、外，六貫棋亦可 [http://hex.kosmanor.com/hex-bin/board/10/Q/_/ 擺成矩形] {{Wayback|url=http://hex.kosmanor.com/hex-bin/board/10/Q/_/ |date=20170729094826 }}。]] |
[[File:hex six.png|right|thumb|250px|六貫棋的常見擺法，除了橫擺(見下圖)和這種擺法、外，六貫棋亦可 [http://hex.kosmanor.com/hex-bin/board/10/Q/_/ 擺成矩形] {{Wayback|url=http://hex.kosmanor.com/hex-bin/board/10/Q/_/ |date=20170729094826 }}。]] |
||
'''六 |
'''六貫棋'''（{{lang-en|Hex}}）是在[[六邊形]]格的棋盤上玩的[[圖版遊戲]]，亦是[[數學遊戲]]，通常使用10乘10或11乘11的[[菱形]]棋盤（[[约翰·福布斯·纳什|約翰·納什]]則採用14×14的棋盤）。 |
||
在[[計算複雜性理論]]，六貫棋的複雜性已證明了是[[PSPACE|PSPACE完全]]的。(注意不少[[抽象策略遊戲]]如[[國際跳棋]]、[[象棋]]和[[圍棋]]都是[[EXPTIME|EXPTIME完全]]。) |
在[[計算複雜性理論]]，六貫棋的複雜性已證明了是[[PSPACE|PSPACE完全]]的。(注意不少[[抽象策略遊戲]]如[[國際跳棋]]、[[象棋]]和[[圍棋]]都是[[EXPTIME|EXPTIME完全]]。) |
||
| 第9行： | 第9行： | ||
== 歷史 == |
== 歷史 == |
||
六貫棋最初在[[丹麥]][[數學家]][[皮亞特·海恩 (數學家)|海恩]]於1942年12月26日在丹麥報紙[[Politiken]]發表的一篇文章裏出現，當時稱為'''Polygon'''。1948年，[[约翰·福布斯·纳什]]重新獨立發明了它。追隨納希的玩家最初稱這個遊戲為'''Nash'''。後來1952年[[Parker Brothers]]發行了一個版本，將它稱為'''Hex''' |
六貫棋最初在[[丹麥]][[數學家]][[皮亞特·海恩 (數學家)|海恩]]於1942年12月26日在丹麥報紙[[Politiken]]發表的一篇文章裏出現，當時稱為'''Polygon'''。1948年，[[约翰·福布斯·纳什]]重新獨立發明了它。追隨納希的玩家最初稱這個遊戲為'''Nash'''。後來1952年[[Parker Brothers]]發行了一個版本，將它稱為'''Hex'''，從此這個名字就定了下來。 |
||
，從此這個名字就定了下來。 |
|||
== 規則 == |
== 規則 == |
||
| 第32行： | 第30行： | ||
:* 只有兩種結果（先手勝或後手勝） |
:* 只有兩種結果（先手勝或後手勝） |
||
:* 棋手移動時有有限的選擇，且爲完美信息博弈 |
:* 棋手移動時有有限的選擇，且爲完美信息博弈 |
||
:根據[[博弈論]]的 |
:根據[[博弈論]]的[[策梅洛定理 (博弈論)|策梅洛定理]]，其中一個棋手必有必勝路線。 |
||
:2.若後手有必勝策略，先手可以隨便走一步，然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋，则再随便走一步，以此类推。考虑后手的最后一步，由于先手使用的是后手必胜策略，那么最后一步必定只有一种走法，此即为先前任意走的那步棋。这将使先手获胜导致矛盾，因此必存在先手必胜策略。 |
:2.若後手有必勝策略，先手可以隨便走一步，然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋，则再随便走一步，以此类推。考虑后手的最后一步，由于先手使用的是后手必胜策略，那么最后一步必定只有一种走法，此即为先前任意走的那步棋。这将使先手获胜导致矛盾，因此必存在先手必胜策略。 |
||
棋盤大小為3至5的六貫棋都可以人手找到先行一方的必勝路線。 |
棋盤大小為3至5的六貫棋都可以人手找到先行一方的必勝路線。 |
||
2024年9月4日 (三) 10:00的最新版本
六貫棋（英語：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