關于Hex博弈最優獲勝策略的一種新方法

摘 要:Hex博奕Hex(n)是一種在六邊形拼接的n×n棋盤上進行的二人博奕，博奕中二人輪流下紅色和藍色棋子，先構造出一條從一邊連到對邊的單色路者為勝者。Hex博奕中先手有必勝策略。設δ(n)為Hex(n)中先手能保證獲勝所需的最少步數，Garikai Campbell通過研究其他對象間接地證明了δ(n)>n對任意n≥4成立。利用新的方法來分析對稱性，給出了δ(n)>n一個直接而簡單的證明，并在此基礎上利用計算證明了δ(5)=7。

關鍵詞:Hex博弈; 步數; 最優策略

中圖分類號:TP301.6

文獻標志碼:A

文章編號:1001-3695(2010)02-0498-02

doi:10.3969/j.issn.1001-3695.2010.02.025

New approach on optimal play in Hex game

PENG Yuan1， XU Xiao-dong1， LUO Hai-peng1， CUI Xiu-feng2

(1.Guangxi Academy of Sciences， Nanning 530007， China; 2. Network Information Center， Qiqihar University， Qiqihar Heilongjiang 161006， China)

Abstract:Hex game Hex(n) is a two person game played on an n×n board of hexagonal tiles， in which the players take turns trying to construct paths from one side of the board to the other. There exists a winning strategy for the first player. Let δ(n) be the minimum number of moves that player one must make to guarantee a win in Hex(n)，Garikai Campbell proved δ(n)>n for any n≥4 by studying another question. In this note， gave a directed and much simpler proof based on a new approach， based on what proved δ(5)=7 by computing.

Key words:Hex game; moves; optimal play

0 引言

Hex博弈Hex(n)亦稱納什(Nash)博弈，是一種在n×n棋盤上進行的一種二人博奕，博奕中二人輪流下紅色和藍色棋子， 先構造出一條從自己的一邊連到對邊的單色路者為勝者。圖1中給出了一個Hex(5)的棋盤。人們知道Hex博奕中不可能出現平局，且先手有必勝策略，但想找到具體的必勝策略往往十分困難[1，2]。

設λ(n)為Hex(n)中先手獲勝的通路所能保證的最短步數，δ(n)為Hex(n)中先手能保證獲勝所需的最少步數。顯然[1]δ(n)≥λ(n)。

對任意n≥4，G. Campbell證明了λ(n)>n，從而得到δ(n)>n成立[1]。他用了大約七頁才證明了λ(4)>4，這也是他證明λ(n)>n的關鍵部分。文獻[1]中還猜想δ(5)=7和δ(6)=9。

本文在第1章通過分析Hex博奕中的對稱性，給出δ(n)>n一個直接而簡單的證明;在此基礎上，在第2章中通過計算證明了δ(5)=7。

1 δ(k)>k的一個直接證明

證明δ(4)>4是證明δ(k)>k的關鍵。對于下述定理，本文將主要處理k=4的情況。

定理 對于任意k≥4有δ(k)>k。

證明 只證明δ(4)>4，因為其他情形可用完全相同的方法來證明。

下面用反證法來證明四步并不足以讓紅方勝。假設紅方能用四步勝。

如圖2所示，如果紅方第一手選在第一行，另三種選擇不會比(1，1)更好。這是因為其他三種選擇與(1，1)的區別在于將在一個更小的盤上行棋，而第一手棋的位置是等價的。如果紅方第一步下在(1，1)，易知后面的博弈只需在圖2的黑線右側的棋盤上進行。

下面來證明如果紅方第一步下在(1，1)，則紅方不能用四步獲勝。這是因為，藍方將下在如圖3所示的(3，2)上，下面無論紅方如何行棋，藍方將能得到(2，2)和(3，3)兩個位置中的至少一個，能得到(2，1)和(3，1)兩個位置中的至少一個。所以在這種情況下紅方不可能有四步必勝的策略。

如果紅方第一手選在第二行，另三種選擇不會比(2，2)更好。這是因為其他三種選擇與(2，2)的區別在于將在一個更小的盤上行棋，而第一手棋的位置是等價的。

類似地，如果紅方第一步下在(2，2)，易知后面的博弈只需在如圖4所示的兩條黑線之間的棋盤上進行。

與上面的討論類似，如果紅方第一步下在(2，2)，則紅方不能用四步獲勝。這是因為，藍方將下在如圖4所示的(4，3)上，下面無論紅方如何行棋，藍方將能得到(3，3)和(4，4)兩個位置中的至少一個，能得到(3，2)和(4，2)兩個位置中的至少一個。所以在這種情況下紅方也不可能有四步必勝的策略了。

綜上所述，有δ(4)>4，證畢。

2 δ(5)=7

棋盤位置編號如圖1所示。為了便于計算機程序設計及盡可能地減小計算量，本文列出了所有包含一條紅方獲勝通路的六個位置，也相當于是六步棋。通過計算，得出一共有942種選擇。這里包括一些特殊的情況，如紅方在1 6 11 16 21 五步就取勝了，在此基礎上另加了額外的一步，于是這個棋形由1 6 11 16 21變成了1 6 11 16 21 2，1 6 11 16 21 3，1 6 11 16 21 4，…，1 6 11 16 21 25，并且不再包括原來的1 6 11 16 21。將這942種選擇列成一個942行6列的表Q0，其中每行的六個數字代表這種選擇中的六個位置或六步。如果紅方存在六步之內的必勝策略，則紅方取勝的棋形必包含在這942情況當中。

在程序中對紅方的所有可供選擇的行棋位置進行遍歷計算，而藍方的行棋策略則利用貪婪算法對紅方能夠在六步之內取勝的棋形進行最大可能地破壞來確定。

下面給出計算(博弈)過程設計方案。

當紅方走完第一步s1后，將表Q0中所有不包含s1的行去掉，并且將剩余部分每行中的s1也去掉，這時將得到一個m1行5列的表Q1(m1<942)。然后統計在Q1的各行中哪個位置出現的次數最多，將此位置作為藍方下一步所走的位置，設為s2(當有多于一個位置出現的次數相同時，暫且選取編號最小的)。接下來將Q1當中所有包含s2的行去掉，得到表Q3，然后再統計Q3中還有那些位置可以供紅方選擇。重復上述過程，一直到表Qn為空。如果Q10仍然不為空，則說明在藍方采用上述貪婪算法的情況下，紅方在六步之內取得了勝利。

程序流程如下:

a)確定s1、s2;求出Q2并記錄;求出s3可選位置。

b)確定s3、s4;求出Q4并記錄。

c)判斷Q4是否為空，是則轉b);否則求出s5可選位置。

d)確定s5、s6;求出Q6并記錄。

e)判斷Q6是否為空，是則轉d);否則求出s7可選位置。

f)確定s7、s8;求出Q8并記錄。

g)判斷Q8是否為空，是則轉f);否則求出s9可選位置。

h)確定s9、s10;求出Q10并記錄。

i)判斷Q10是否為空，是則轉h);否則求出s11并記錄。

經過運算，在得到的結果中，紅方第一步走在3、5、7、8、9、12、13、17、21這九個位置的時候，結果中有紅方六步取勝的情況。根據文獻[1]中關于對稱性的分析可知，3~23、7~19、8~18、12~14是對稱的，而計算結果證明紅方第一步走在23、19、18、14這幾個位置時不可能在六步之內取勝。顯然這是由于藍方在應用貪婪算法的過程中，當有多于一個位置可供選擇時只選擇序號最小的位置而不是最終效果最好的位置造成的。因此可用紅方第一步走在23、19、18、14的策略替代第一步走在3、7、8、12時的策略。同樣的情況也出現在5~21、9~17當中。

于是，只需要對紅方第一步走在13、17、21這三種情況進行進一步分析。通過分析發現，這三種情況要復雜得多，問題源于貪婪算法自身存在的局限性。下面分別對這三種情況逐一分析:

a)當紅方第一步走在位置13時，會出現如下六個紅方六步之內取勝的情況:

13 8 5 9 10 14 15 19 20 24 25

13871294517182223

138945181417192324

1389451817212212

138945181914172122

13812794517182223

而如果試著將s2改為4，則會出現如下兩種紅方六步取勝的情況:

(a)13 4 5 9 10 14 15 19 20 24 25

將s8由19改為24問題即可解決。

(b)13 4 7 2 3 12 8 17 18 22 23

將s8由17改為22問題即可解決。

b)當紅方第一步走在位置17時，會出現如下六個紅方六步之內取勝的情況，并且作如下修改:

(a)17 12 5 13 10 14 15 19 20 24 25

17 125 13 14 18 199 10 23 24

將s4由13改為9，并且將17 12 5 9 10 14 15 19 20 24 25中的s8由19改為24，問題即可解決。

(b)17 129 13 14 18 19 45 23 24

將s4由13改為5，并且將17 12 9 5 4 13 14 18 19 23 24中的s6由13改為22，問題即可解決。

(c)17 12 13894 5 21 18 22 23

17 12 13 8 9 4 5 21 22 1 2

17 12 13 8 9 4 5 21 23 18 22

將s4由8改為4問題即可解決。

c)當紅方第一步走在位置21時，會出現如下六個紅方六步之內取勝的情況，并且作如下修改:

(a)21 17 5 16 10 14 15 19 20 24 25

將s8由19改為24問題即可解決。

(b)21 17 5 16 14 9 10 18 19 23 24