跳转到内容

六貫棋：修订间差异

维基百科，自由的百科全书
以互动方式浏览历史
←上一版本
删除的内容 添加的内容
可视化wikitext
Hidvenod（留言 | 贡献）
5次编辑
小 →歷史：​ 修正筆誤（刪除多餘的換行）
 
（未显示19个用户的30个中间版本）
第1行： 第1行：
[[File:Hex zig-zag.jpg|300px|thumb|right|Hex - The Zig-Zag Game - Parker Brothers - 1950]]
[[File:Hex zig-zag.jpg|300px|thumb|right|Hex - The Zig-Zag Game - Parker Brothers - 1950]]
[[File:hex six.png|right|thumb|250px|六貫棋的常見擺法，除了橫擺(見下圖)和這種擺法之外，六貫棋亦可 [http://hex.kosmanor.com/hex-bin/board/10/Q/_/ 擺成矩形]。]]
[[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 }}。]]


'''六貫棋'''是在[[六邊形]]格的棋盤上玩的[[圖版遊戲]]，亦是[[數學遊戲]]，通常使用10乘10或11乘11的[[菱形]]棋盤（[[约翰·福布斯·纳什|約翰·納什]]則採用14×14的棋盤）。
'''六貫棋'''（{{lang-en|Hex}}）是在[[六邊形]]格的棋盤上玩的[[圖版遊戲]]，亦是[[數學遊戲]]，通常使用10乘10或11乘11的[[菱形]]棋盤（[[约翰·福布斯·纳什|約翰·納什]]則採用14×14的棋盤）。


在[[計算複雜性理論]]，六貫棋的複雜性已證明了是[[PSPACE|PSPACE完全]]的。(注意不少[[抽象策略遊戲]]如[[國際跳棋]]、[[象棋]]和[[圍棋]]都是[[EXPTIME|EXPTIME完全]]。)
在[[計算複雜性理論]]，六貫棋的複雜性已證明了是[[PSPACE|PSPACE完全]]的。(注意不少[[抽象策略遊戲]]如[[國際跳棋]]、[[象棋]]和[[圍棋]]都是[[EXPTIME|EXPTIME完全]]。)
第13行： 第13行：
== 規則 ==
== 規則 ==


[[File:Hex-board-11x11-(2).jpg|thumb|right|250|一種藍方獲勝的情況]]
[[File:Hex-board-11x11-(2).jpg|thumb|right|250px|一種藍方獲勝的情況]]


六貫棋由兩個人一起玩，有兩種顏色，通常是紅、藍或黑、白。四個邊平行填上兩方的顏色。雙方輪流下，每次佔領一處空白格，在空白格放上自己顏色的棋子（或填上自己的顏色）。最先將棋盤屬於自己的顏色的邊連成一線的一方為勝。
六貫棋由兩個人一起玩，有兩種顏色，通常是紅、藍或黑、白。四個邊平行填上兩方的顏色。雙方輪流下，每次佔領一處空白格，在空白格放上自己顏色的棋子（或填上自己的顏色）。最先將棋盤屬於自己的顏色的邊連成一線的一方為勝。
第28行： 第28行：
:1.因為這個遊戲滿足
:1.因為這個遊戲滿足
:* 在有限次數內結束
:* 在有限次數內結束
:* 只有兩種結果(先手勝或後手勝)
:* 只有兩種結果（先手勝或後手勝）
:* 棋手移動時有有限的選擇，且爲完美信息博弈
:* 棋手移動時有有限的選擇，且爲完美信息博弈
:根據[[博奕論]]的一個[[策梅洛定理 (博弈論)|定理]]，其中一個棋手必有必勝路線。
:根據[[博弈論]]的[[策梅洛定理 (博弈論)|策梅洛定理]]，其中一個棋手必有必勝路線。
:2.若後手有必勝策略，先手可以隨便走一步，然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋，则再随便走一步，以此类推。考虑后手的最后一步，由于先手使用的是后手必胜策略，那么最后一步必定只有一种走法，此即为先前任意走的那步棋。这将使先手获胜导致矛盾，因此必存在先手必胜策略。
:2.若後手有必勝策略，先手可以隨便走一步，然后对后手的每一步棋使用后手必胜策略。若在某一步时的必胜走法是之前任意走的那步棋，则再随便走一步，以此类推。考虑后手的最后一步，由于先手使用的是后手必胜策略，那么最后一步必定只有一种走法，此即为先前任意走的那步棋。这将使先手获胜导致矛盾，因此必存在先手必胜策略。
棋盤大小為3至5的六貫棋都可以人手找到先行一方的必勝路線。棋盤大小為6的六貫棋由[http://www.cs.ualberta.ca/~queenbee Queenbee]找到了必勝路線，棋盤大小為7的解答可在[http://www.ee.umanitoba.ca/~jingyang/ 楊靖的網站]找到。
棋盤大小為3至5的六貫棋都可以人手找到先行一方的必勝路線。


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


== 外部鏈結 ==
== 外部連結 ==
* [http://www.hexwiki.tk/ HexWiki]
* [http://www.hexwiki.tk/ HexWiki] {{Wayback|url=http://www.hexwiki.tk/ |date=20170923045303 }}
* [http://www.cs.ualberta.ca/~javhar/hex/ Jack van Rijswijck's Hex page]
* [https://web.archive.org/web/20041009193939/http://www.cs.ualberta.ca/~javhar/hex/ Jack van Rijswijck's Hex page]
* [http://www.microring.it/hex/ Hex game information center]
* [https://web.archive.org/web/20041009220201/http://www.microring.it/hex/ Hex game information center]
* [http://www.kosmanor.com/hex-bin/board OHex]，在線的資料庫
* [http://www.kosmanor.com/hex-bin/board OHex] {{Wayback|url=http://www.kosmanor.com/hex-bin/board |date=20190914225147 }}，在線的資料庫
* [http://www.mazeworks.com/hex7/ MazeWorks - Hex-7]
* [https://web.archive.org/web/20041009215016/http://www.mazeworks.com/hex7/ MazeWorks - Hex-7]
* [http://maarup.net/thomas/hex/ Thesis on Hex] history, classification and complexity
* [http://maarup.net/thomas/hex/ Thesis on Hex] {{Wayback|url=http://maarup.net/thomas/hex/ |date=20201106232456 }} history, classification and complexity
* [http://mathworld.wolfram.com/GameofHex.html Game of Hex] at [[MathWorld]] with links to related mathematical papers
* [http://mathworld.wolfram.com/GameofHex.html Game of Hex] {{Wayback|url=http://mathworld.wolfram.com/GameofHex.html |date=20191225020507 }} at [[MathWorld]] with links to related mathematical papers
* [http://www.cs.ualberta.ca/~queenbee/openings.html 1×1 to 6×6 opening strategy]{{Dead link|date=July 2010}} by Jack van Rijswijck of the [[University of Alberta]]
* [https://web.archive.org/web/20091013152809/http://www.cs.ualberta.ca/~queenbee/openings.html 1×1 to 6×6 opening strategy] by Jack van Rijswijck of the [[University of Alberta]]
* {{bgg|4112|Hex}}
* {{bgg|4112|Hex}}
* [http://quatramaran.ens.fr/~viger/hex/ Printable Hex boards] on A4 or A3 paper, for use with standard Go stones
* [https://web.archive.org/web/20140308080351/http://quatramaran.ens.fr/~viger/hex/ Printable Hex boards] on A4 or A3 paper, for use with standard Go stones
* [http://jeudhex.com/?page_id=17 Game of Hex] mathematic analysis and solution by Edouard Rodrigues
* [https://web.archive.org/web/20140226082225/http://jeudhex.com/?page_id=17 Game of Hex] mathematic analysis and solution by Edouard Rodrigues
* [http://www.hexwiki.org/ HexWiki] a [[wiki]] dedicated to Hex{{dead link|date=September 2013}}
* [https://web.archive.org/web/20160708152421/http://hexwiki.org/ HexWiki] a [[wiki]] dedicated to Hex


=== 程式 ===
=== 程式 ===
*[http://www.ee.umanitoba.ca/~jingyang/ 楊靖的網站(英文)]，8×8和7×7的必勝Java程式(程式先行)
*[https://web.archive.org/web/20040930214052/http://www.ee.umanitoba.ca/~jingyang/ 楊靖的網站(英文)]，8×8和7×7的必勝Java程式(程式先行)
*[http://www.cs.ualberta.ca/~queenbee/ Queenbee]
*[https://web.archive.org/web/20040930173230/http://www.cs.ualberta.ca/~queenbee/ Queenbee]
*[http://six.retes.hu/ Six]，Linux的程式
*[https://web.archive.org/web/20040925074251/http://six.retes.hu/ Six]，Linux的程式
*[http://home.earthlink.net/~vanshel/ Hexy]，Windows的程式
*[http://vanshel.com/Hexy/ Hexy] {{Wayback|url=http://vanshel.com/Hexy/ |date=20201111235824 }}，Windows的程式




2024年9月4日 (三) 10:00的最新版本

Hex - The Zig-Zag Game - Parker Brothers - 1950
六貫棋的常見擺法，除了橫擺(見下圖)和這種擺法、外，六貫棋亦可 擺成矩形 （页面存档备份，存于互联网档案馆）。

六貫棋（英語：Hex）是在六邊形格的棋盤上玩的圖版遊戲，亦是數學遊戲，通常使用10乘10或11乘11的菱形棋盤（約翰·納什則採用14×14的棋盤）。

在計算複雜性理論，六貫棋的複雜性已證明了是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的六貫棋都可以人手找到先行一方的必勝路線。

相關遊戲

[编辑]

外部連結

[编辑]

程式

[编辑]
检索自“https://zh.wikipedia.org/zhwiki/w/index.php?title=六貫棋&oldid=84084918”