利用電腦探討中國古代益智遊戲─「華容道」之解法

魏仲良、林順喜國立臺灣師範大學資訊教育系摘要在本文中，我們嘗試設計演算法，利用電腦找出中國古代流傳下來的益智遊戲─「華容道」的最少步數，以驗證前人資料上所記載各盤面的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步，因此不能直接用暴力法搜尋，目前文獻上尚未見到電腦之解法，只有一些人為的解答有記錄，也有一些程式將這些人為的、不是最佳的解答直接記錄下來作展示。因此我們構思如何解決此困難之問題。在此論文中，我們發展了一些技術，目標是求出完全的最佳解，並實際撰寫程式測試，要求在可忍受的時間內解出。程式的執行結果與先前得到的前人資料有所出入，有些與資料記載的吻合，有的則較記錄為多，還有一些比資料上的少上三至五步之多。驗證了一下程式輸出到檔案的最佳解，發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較前人資料為多的部份，可能是前人的文獻資料有誤，因為資料上只記載著各盤面最少步數的解題記錄，並無參考的解法。一.緒論1.華容道遊戲的介紹：華容道，這是從中國古代就流傳下來的智慧遊戲，出自三國演義中「關羽橫讓捉放曹操」的情節。由於盤面變化多端，曾被譽為「智力遊戲界的三大不可思議」的遊戲之一。其玩法為在所有棋子均不離開棋盤的前提之下，如何使曹操越過重重的包圍，逃回曹營。這個遊戲可在下列網站均可找到程式下載來玩(用人工嘗試錯誤法來玩)：http://www.tces.chc.edu.tw/center/school1.htmhttp://www.sivs.chc.edu.tw/goodware/13.htmhttp://www.nchu.edu.tw/~tnes/13-3.htmhttp://content.edu.tw/primary/music/tp_ck/softgood-03.htm華容道基本上其棋盤為橫四格縱五格的盤面，曹操為占四格的2x2的正方形棋子；占兩格的為五虎將的關羽、張飛、趙雲、馬超與黃忠，其中只有關羽橫兩格，其餘四將均為豎兩格；還有四個各占一格的兵(如圖一)。所以在遊戲的時候，只能利用盤面上留下的兩個空格來移動棋子，只要想辦法將曹操移到鄰接曹營上方的正中央的位置，即表示我們已成功讓曹操逃回曹營，遊戲至此於是結束。移動的步數愈少愈好。而在移動的過程中我們可以發現，關羽跟曹操不能在同一排，關羽必須要橫讓，曹操才有可能通過向下走，這正好符合了三國演義中的情節，所以這項遊戲又被稱為「捉放曹」。除了上述標準的盤面之外，橫擺的五虎將除了關羽之外，也可以將其他四將橫擺，使得盤面有更多變化，更富挑戰性。

在本文中,盤面資料來源為「阿集好用軟體區→休閒益智軟體(http://www.ntctcps.tc.edu.tw/13-3.htm)內的「華容道益智遊戲中文版(視窗95版)」。除了華容道之外，還有兩個類似的棋戲：「包青天」(圖二)與「箱入娘」。其中，包青天亦可在「阿集好用軟體區→休閒益智軟體」內找到。這些軟體都只是純粹為了遊戲之用，並無參考的解答。另外，網路上可以找到一個DOS下的華容道遊戲軟體(604.zip)，它有提供參考的解答，但大部份盤面所的步數比我們多，所以並不是最佳解(請見「四、結論」中說明)。上面提到的這些程式，已經收集整理在ftp://alg.ice.ntnu.edu.tw/pub/chess/，有興趣的讀者，可以上網去取得。1.以人腦移動棋子與以電腦求解的不同：一般人在玩這類的遊戲的時候，大概會很直覺地看到哪顆棋子可以移動，就移動那顆棋子。等到發現錯誤的時候，再將棋子擺回原位。但是，當移動的步數一多，大概很少人能記得如何從一開始的盤面一步步移動棋子，走到目前的狀態。而且在移動棋子的過程中，很可能出現重覆的盤面而不自知。利用電腦求解，可以記錄下哪些盤面已經走過，避免浪費時間在相同搜尋重覆的路徑；除此之外，可以依循一定的規則來展開每一個盤面中所有能移動的方法。如此，窮舉所有的可能，只要給定的盤面有解，一定能找到解，剩下的只是求解需要時間的長短罷了。但因為解答的步數有過100步以上的，所以不能直接以暴力法去窮舉。以下我們說明如何去克服此難題。二. 電腦解題之演算法在正式開始寫程式求解之前，我們先利用目前已知的資料。華容道的棋盤為橫四格縱五格，為了辨別棋子在棋盤上的位置，先對棋盤上的每個格子編號：左上角為0，右下角為19，共二十個格子(表一)。為了識別每顆棋子，我們也將棋子加以編號：曹操為1號，五虎將給予2至6的編號，剩下四個兵則編為7至10號，而以0表示空白(表二)。最後，以棋子的長寬分類，共可分為四類：第一類為2x2大小，第二類為2x1，第三類1x2，而第四類則為1x1(表三)。

以每顆棋子左上角所佔據的格子編號來表示棋子的位置，如此，每個盤面的狀態則可以用一個陣列表示。例如圖一「橫刀立馬」的盤面，曹操的(編號為1)的位置為1、關羽(編號為2)的位置為9，其餘可類推，我們可以表示為：[1     9 0 3 8 11 13 14 16 19]因為知道十顆棋子的位置就可以推知兩個空格的所在，因此，我們並不需要額外記錄空格的位置。在每個盤面要尋找下一步該怎麼走，若檢查每顆棋子可以走的路，棋盤上共有十顆棋子，則十顆棋子都要檢查，而且大部份的棋子可能都無法移動。為了減少麻煩，改由空白格下手。由於盤面上只會有兩個空格，只要檢查空格周圍的棋子是否能往空格移動，如此即可減少許多不必要的判斷，而加快搜尋的速度。為了推知空格的位置，首先將棋盤上所有的格子都先填入0，再依棋子的位置以及種類，將棋子的編號填入棋盤內，填完之後，即可得知空格的所在。舉例說明，下面是我們將棋子編號填入「橫刀立馬」盤面之後所得的結果(表四)：

由此可以得知兩個空格的位置分別為 17與18。接著則分別判斷每個空格上下左右四個方向緊鄰的棋子能否往空格移動，若可，更動該棋子的位置後則可得到新的盤面。由於我們的目的在尋找由給定盤面開始，最終將曹操移動至曹營上方中央的位置最少需要多少步，因此第一個念頭即是利用BFS(Breadth-First Search)配合Branch and Bound的方式求解，如此，第一個找到的解一定是最佳解。但是，利用BFS需要額外的空間來存放等待著要被展開盤面的Queue，因此，當我們要展開的深度很深時(例如100層以上)，需要耗費的空間就很驚人了。所以改而採用DFS(Depth-First Search)來展開Game Tree。為了加快DFS的效率，每當找到一個解時，則立即記錄下至目前為止的最少步數，倘若目前步數超過最少步數則不繼續往下展開；除此之外，另外用Binary Search Tree記錄已經走過的盤面(這些盤面有一次序值，如下所述)，以及先前走到此盤面時的步數：第一步，先將同一類棋子的位置加以排序，例如圖三「三軍聯防」盤面中，十顆棋子的位置如表五所示：

我們將十顆棋子的位置依序存放在一陣列中：[0     13 8 10 2 3 12 15 16 19]再依照棋子的類別可以分為四組：[0]、[13 8 10]、[2 3]、[12 15 16 19]這四組分別排序過後再組合可得：[0 8 10 13 2 3 12 15 16 19]這樣的目的在於減少重複的盤面。相同類別的棋子，位置互調，其實是一樣的狀況。經過此步驟之後，可過濾掉這些重複狀況的盤面，因而能減少展開的盤面，縮短程式搜尋的時間。第二步，再透過公式將十個棋子的位置編碼成一個64-bit大小可表示的數值。這裡所採用的公式如下：(假設儲存棋子位置的陣列為C[])Value = C[0]*209 + C[1]*208 + C[2]*207 + C[3]*206 + C[4]*205 +C[5]*204 + C[6]*203 + C[7]*202 + C[8]*20 + C[9]以圖一為例，我們可將盤面換算成：0*209 + 8*208 + 10*207 + 13*206 + 2*205 + 3*204 + 12*203 + 15*202 + 16*20 + 19 =  218438982339這樣有兩個好處：一是可減少空間的使用，另一則為同一類別的棋子，若在相同的位置上，實際上是同一種情況，如此可大大減少展開盤面的次數。Binary Search Tree內所記錄的盤面就是透過公式計算得來的數值insert進去的。原則上，在展開一個盤面之前，會先自Binary Search Tree中搜尋該盤面是否已經展開過，若無，則繼續展開，若有，則表示此盤面先前已經走過，所以不展開此重複的盤面，但是除了一種特殊的情況：雖然先前已經走過此盤面，但當時的步數比目前走到此的步數還多，則得重新由此盤面展開一次，並更新Binary Search Tree裡所記錄盤面的步數。目前的步數較少，表示此時由起始盤面至此盤面的解較先前走到此盤面時的解為佳，重新展開的目的則在於更新Binary Search Tree裡的步數記錄。圖四顯示啟始盤面為「橫刀立馬」的展開情況。

三.程式執行結果與分析我們使用一台普通的個人電腦做為測試的工具：Petium 166MMX CPU,160MB PC-100 SD-RAM。使用的Compiler為Borland C++ Builder 3.0, 原始程式碼約 480 行，以下為程式執行後所得的最佳解結果(表五)：符號說明：曹操：## 五虎將(橫)：    [] 五虎將(縱)：H   兵：O盤面名稱啟始盤面最少步數展開盤面總數執行時間盤面名稱啟始盤面最少步數展開盤面總數執行時間左右佈兵(又名 兵臨曹營)O##OO##OH[]HHHHHHH34步385971秒層層設防H##HH##HO[]OO[]O[]103步303751474秒橫刀立馬H##HH##HH[]HHOOHO O81步238531835秒兵將聯防O##OH##HH[]HO[]O[]121步365571127秒將守角樓H##HH##HO[]OHOOHH H70步231111660秒四路進兵##OH##OHOO[][][][]65步137531005秒屯 兵東路##HH##HH[]OOHHOOHH74步209351245秒比翼橫空[]##[]##[][]O OHO OH28步5779307秒插翅難飛H##OH##O[]OOH[]HH H63步422903023秒夾道藏兵##OH##OH[][][][]O O76步13753858秒重重包圍H##OH##OH[]HH[]HO O74步422712738秒水洩不通O##HO##H[][][][]O O80步13600813秒雲遮霧障H##HH##HH[]OH[]OO O81步421653080秒將擋後路[]##[]##[][][]OOOO21步2761137秒守口如瓶O##OH##HHH HOH O[][]100步436692483秒前呼後擁OO##[]##[][][][]OO22步6234173秒三軍聯防(又名 交錯堵道)##HH##HH[][]O[]OO O69步162271046秒調兵遣將##OO##OO[][][][][]52步5078240秒四將聯防(又名 四將連關)##[]##[]HH[]HHOOO O40步5476126秒巧過五關O##OO##O[][][][][]33步6052189秒表五 程式執行結果四.結論(1)目前之結論計算步數的方式有兩種：第一種為只要棋子移動一格就算一步，第二種狀況則為若兩個空格相鄰，棋子得以連續移動兩格只算一步。依據文獻上的記錄推測，前人文獻計算步數的方法應為後者，故本程式亦採用後者為計算步數的方式。程式所得到的結果，與先前得到的文獻資料比較後,有以下三種狀況(表六)。與前人資料相符者盤面名稱起始盤面資料數據執行結果盤面名稱起始盤面資料數據執行結果左右佈兵O##OO##OH[]HHHHHHH34步34步橫刀立馬H##HH##HH[]HHOOHO O81步81步水洩不通O##HO##H[][][][]O O80步80步步數較前人資料記錄少者三軍聯防##HH##HH[][]O[]OO O74步69步四路進兵##OH##OHOO[][][][]67步65步步數較前人資料記錄多者插翅難飛H##OH##O[]OOH[]HH H62步63步層層設防H##HH##HO[]OO[]O[]102步103步表六　文獻資料數據與執行結果比較與先前得到的前人數據有所出入，有幾個可能的原因：一是因為原先得到的數據就不是正確的，二則是因為計算步數的方法不一樣。但是仔細驗證幾組程式執行得到較少的參考解(附錄)，發現我們的程式並無錯誤。但是先前收集到的資料只註明盤面的最少解題步數，並沒有附上參考的移動過程，所以應該是以前文獻資料有誤所致。此外，我們在網路上收集到一個DOS下的華容道遊戲軟體(604.zip)，它有提供參考解答，但大部份盤面所走的步數都比本程式得到的結果為多，如下表所示(表七)。特別注意的是，在此處計算步數的方式和附錄一中的不同，步數的計算乃是移動一格即算一步，而附錄一則採用若連續移動兩格只算一步的方式計算步數。盤面名稱啟始盤面604.zip本演算法盤面名稱啟始盤面604.zip本演算法左右佈兵(又名兵臨曹營)O##OO##OH[]HHHHHHH49步49步層層設防H##HH##HO[]OO[]O[]140步138步橫刀立馬H##HH##HH[]HHOOHO O118步116步兵將聯防O##OH##HH[]HO[]O[]158步158步將守角樓H##HH##HO[]OHOOHH H102步100步比翼橫空[]##[]##[][]O OHO OH46步39步屯兵東路##HH##HH[]OOHHOOHH104步102步夾道藏兵##OH##OH[][][][]O O110步107步插翅難飛H##OH##O[]OOH[]HH H77步77步水洩不通O##HO##H[][][][]O O115步114步重重包圍H##OH##OH[]HH[]HO O94步92步將擋後路[]##[]##[][][]OOOO30步30步雲遮霧障H##HH##HH[]OH[]OO O105步104步前呼後擁OO##[]##[][][][]OO41步31步守口如瓶O##OH##HHH HOH O[][]132步131步調兵遣將##OO##OO[][][][][]74步72步三軍聯防(又名交錯堵道)##HH##HH[][]O[]OO O96步89步巧過五關O##OO##O[][][][][]46步45步四將聯防(又名四將連關)##[]##[]HH[]HHOOO O59步55步表七　604.zip與本演算法結果之比較(1)未來需要再研究的方向本程式使用DFS的方式求解，只用一些粗略的方法加快程式求解的速度也減少程式之發展時間，雖然多數的盤面在半個小時內能找到最佳解，最慢也能在一個小時內完成。但是如果運用在遊戲中隨時給玩家提示在任一種盤面狀況下，下一步該怎麼走，則似乎又太久了點。因此，如何找出更快的演算法，讓任一個有解的盤面均能在很短的時間內找到最佳解，是未來需要再努力的目標。五.誌謝本研究部份由國科會專案補助，計畫編號為NSC-88-2815-C-003-002-E，特此誌謝。六.參考文獻Grimaldi Ralph P. (1994). Discrete and combinatorial mathematics : an applied introduction. 3rd ed.Ronald E. Walpole & Raymond H. Myers (1993). Probability and Statistics for Engineers and Scientists 5th Edition by Prentice-Hall, Inc.Wackerly & Mendenhall & Scheaffer (1996). Mathematical Statistics with Applications 5th Edition by Wadsworth Publishing Company.David Kincaid & Ward Cheney (1996). Numeriacl analysis : mathematics of scientific computing. 2nd ed.Harry R. Lewis & Christos H. Papadimitriou (1998). Elements of the theory of computation. 2nd ed.Neapolitan & Naimipour (1996). Foundations of algorithms by D. C. Heath and CompanyHorowitz & Sahni (1994). Fundamentals of Data Structures in Pascal 4th Edition by Computer Science PressGilbert Strang (1988). Linear Algebra and Its Applications 3rd Edition by Harcourt Brace Jovanovich, Inc.冼鏡光 (1990). : 名題精選百則 技巧篇 - 使用C語言。格致圖書公司。fromhttp://www2.kuas.edu.tw/