六貫棋






Hex - The Zig-Zag Game - Parker Brothers - 1950




六貫棋的常見擺法，除了橫擺(見下圖)和這種擺法之外，六貫棋亦可 擺成矩形。


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


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




11×11的六貫棋棋盤




目录






  • 1 歷史


  • 2 規則


  • 3 必勝策略


  • 4 相關遊戲


  • 5 外部連結


    • 5.1 程式







歷史


六貫棋最初在丹麥數學家海恩於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拿許棋盤的必是點之一，如此就能確保上下兩端貫通，如果將這一塊棋盤旋轉，取剛好完全重疊的部份，能到一個六邊形的方格，可想成以一個方格為基礎所做出來的大方格，而這個方格，即是這一點所具有的”完整領域”，而先手接下來只要確保領域和領域了貫通，就能做出必勝策略，至於要如何貫通，就是要預測貫通點，只要預測出的貫通點或貫通方式有兩種或兩種以上，就能得到必勝策略。



外部連結



  • 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


  • Hex at BoardGameGeek


  • 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



程式




  • 楊靖的網站(英文)，8×8和7×7的必勝Java程式(程式先行)

  • Queenbee


  • Six，Linux的程式


  • Hexy，Windows的程式




-

Popular posts from this blog

Lambaréné

Image
Place in Moyen-Ogooué, Gabon Lambaréné Street in Lambaréné Lambaréné Location in Gabon Coordinates: 0°41′18″S 10°13′55″E  /  0.68833°S 10.23194°E  / -0.68833; 10.23194 Coordinates: 0°41′18″S 10°13′55″E  /  0.68833°S 10.23194°E  / -0.68833; 10.23194 Country   Gabon Province Moyen-Ogooué Population (2013 census)  • Total 38,775 Lambaréné is a town and the capital of Moyen-Ogooué in Gabon. With a population of 38,775 as of 2013, it is located 75 kilometres south of the equator. Lambaréné is based in the Central African Rainforest at the river Ogooué. This river divides the city into 3 districts: Rive Gauche, Ile Lambaréné and Rive Droite. The Albert Schweitzer Hospital and the districts Adouma and Abongo are located on Rive Droite. The districts Atongowanga, Sahoty, Dakar, Grand Village, Château, Lalala and Bordamur build the Ile Lambaréné. The majority of the people in Lambaréné live in the district Isaac located on Rive Gauche. This distr
Read more

維納斯堡 (華盛頓州)

Image
body.skin-minerva .mw-parser-output table.infobox caption{text-align:center} 維納斯堡 Venersborg （英文） CDP Venersborg, Washington 維納斯堡位置圖 坐标： 45°46′58″N 122°27′43″W  /  45.7828°N 122.462°W  / 45.7828; -122.462 國家   美國 州 華盛頓州 郡 克拉克县 面积  •  总计 27.8 平方公里（10.7 平方英里）  • 陸地 27.8 平方公里（10.7 平方英里）  • 水域 0.0 平方公里（0.0 平方英里） 海拔 155 米（509 英尺） 人口 （2000年）  • 總計 3,274  • 密度 118.0/平方公里（305.6/平方英里） 时区 PST （UTC-8）  • 夏时制 PDT（UTC-7） FIPS碼 53-74585 [1] GNIS編號 1527695 [2] 維納斯堡 （ 英语： Venersborg ）是美国华盛顿州克拉克县的一個普查规定居民点（CDP），2000年美國人口普查時人口為2,085人。 最初為瑞典人聚居地。 參見 維納什堡 参考資料 ^ American FactFinder. United States Census Bureau. [ 2008-01-31 ] .   ^ US Board on Geographic Names. United States Geological Survey. 2007-10-25 [ 2008-01-31 ] .   查 论 编 克拉克县 行政區劃 郡治 ： 溫哥華 市 巴特爾格朗德 | 卡默斯 | 拉申特 | 里奇菲尔德 | 溫哥華 | 瓦休戈 | 林地市‡ 鎮 亞科爾特 CDP 安波伊 | 巴伯頓 | 布拉什普雷里 | 櫻桃樹叢區 |
Read more

Mononymous person

Image
Plato, the Greek philosopher, is universally known by a single name. A mononymous person is an individual who is known and addressed by a single name, or mononym. [a] [b] In some cases, that name has been selected by the individual, who may have originally been given a polynym ("multiple name"). In other cases, it has been determined by the custom of the country [c] or by some interested segment. In the case of historical figures, it may be the only one of the individual's names that has survived and is still known today. Contents 1 Antiquity 2 Medieval uses 2.1 Europe 2.2 The Americas 3 Post-medieval uses 3.1 France 3.2 Other Europe 3.3 North America 4 Royalty 5 Modern times 5.1 Mononym-normal 5.2 Asia 5.3 The West 6 Gallery 7 See also 8 Notes 9 References 10 Bibliography 11 External links Antiquity Narmer The structure of persons' names has varied across ti
Read more