六貫棋






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

Chris Pine

Image
Not to be confused with Christopher Pyne or Chris Pyne. Chris Pine Pine in 2018 Born Christopher Whitelaw Pine ( 1980-08-26 ) August 26, 1980 (age 38) Los Angeles, California, U.S. Alma mater UC Berkeley Occupation Actor Years active 2003–present Parent(s) Robert Pine Gwynne Gilford Relatives Anne Gwynne (grandmother) Christopher Whitelaw Pine (born August 26, 1980) [1] [2] is an American actor. Pine made his feature debut as Lord Devereaux in The Princess Diaries 2: Royal Engagement (2004). He is known for playing James T. Kirk in the Star Trek reboot film series (2009–2016), Will in Unstoppable (2010), Cinderella's Prince in Into the Woods (2014), Jack Ryan in Jack Ryan: Shadow Recruit (2014), Toby Howard in Hell or High Water (2016), Bernie Webber in The Finest Hours (2016), Steve Trevor in Wonder Woman (2017), and Dr. Alexander Murry in A Wrinkle in Time (2018). Contents 1 Early life 2 Career 2.1 2003–200
Read more

Kashihara Line

Image
Kashihara Line   B   A Kashihara Line train passing Yakushi-ji temple Overview Native name 橿原線 Type Commuter rail System Kintetsu Railway Locale Nara, Nara, Japan Yamtokoriyama, Nara, Japan Tenri, Nara, Japan Kawanishi, Nara, Japan Miyake, Nara, Japan Tawaramoto, Nara, Japan Kashihara , Nara, Japan Termini Yamato-Saidaiji Kashiharajingu-mae Stations 17 Operation Opened April 1, 1921 ; 98 years ago  ( 1921-04-01 ) Owner Kintetsu Railway Character Commuter rail Technical Line length 23.8 km (14.8 mi) Track gauge 1,435 mm ( 4 ft  8   1 ⁄ 2  in ) Minimum radius 240 m Electrification 1,500 V DC Overhead lines Operating speed 100 km/h (60 mph) [1] The Kashihara Line ( 橿原線 , Kashihara-sen ) is a 23.8 km (14.8 mi) north-south bound railway line in Nara Prefecture, Japan, owned and operated by the Kintetsu Railway, a private railway operator. It connects Yamato-Saidaiji Station and Kashiharajingu
Read more