利用電腦探討中國古代益智遊戲─「華容道」之解法
魏仲良、林順喜
國立臺灣師範大學
資訊教育系
摘要
在本文中,我們嘗試設計演算法,利用電腦找出中國古代流傳下來的益智遊戲─「華容道」的最少步數,以驗證前人資料上所記載各盤面的最少步數是否正確。此遊戲中許多盤面之解答的移動步數超過100步,因此不能直接用暴力法搜尋,目前文獻上尚未見到電腦之解法,只有一些人為的解答有記錄,也有一些程式將這些人為的、不是最佳的解答直接記錄下來作展示。因此我們構思如何解決此困難之問題。在此論文中,我們發展了一些技術,目標是求出完全的最佳解,並實際撰寫程式測試,要求在可忍受的時間內解出。程式的執行結果與先前得到的前人資料有所出入,有些與資料記載的吻合,有的則較記錄為多,還有一些比資料上的少上三至五步之多。驗證了一下程式輸出到檔案的最佳解,發現程式所求得比資料記載還要少的結果應是正確的。至於程式求得較前人資料為多的部份,可能是前人的文獻資料有誤,因為資料上只記載著各盤面最少步數的解題記錄,並無參考的解法。
一.緒論
1.華容道遊戲的介紹:
華容道,這是從中國古代就流傳下來的智慧遊戲,出自三國演義中「關羽橫讓捉放曹操」的情節。由於盤面變化多端,曾被譽為「智力遊戲界的三大不可思議」的遊戲之一。其玩法為在所有棋子均不離開棋盤的前提之下,如何使曹操越過重重的包圍,逃回曹營。這個遊戲可在下列網站均可找到程式下載來玩(用人工嘗試錯誤法來玩):
華容道基本上其棋盤為橫四格縱五格的盤面,曹操為占四格的2x2的正方形棋子;占兩格的為五虎將的關羽、張飛、趙雲、馬超與黃忠,其中只有關羽橫兩格,其餘四將均為豎兩格;還有四個各占一格的兵(如圖一)。所以在遊戲的時候,只能利用盤面上留下的兩個空格來移動棋子,只要想辦法將曹操移到鄰接曹營上方的正中央的位置,即表示我們已成功讓曹操逃回曹營,遊戲至此於是結束。移動的步數愈少愈好。而在移動的過程中我們可以發現,關羽跟曹操不能在同一排,關羽必須要橫讓,曹操才有可能通過向下走,這正好符合了三國演義中的情節,所以這項遊戲又被稱為「捉放曹」。除了上述標準的盤面之外,橫擺的五虎將除了關羽之外,也可以將其他四將橫擺,使得盤面有更多變化,更富挑戰性。
1.以人腦移動棋子與以電腦求解的不同:
一般人在玩這類的遊戲的時候,大概會很直覺地看到哪顆棋子可以移動,就移動那顆棋子。等到發現錯誤的時候,再將棋子擺回原位。但是,當移動的步數一多,大概很少人能記得如何從一開始的盤面一步步移動棋子,走到目前的狀態。而且在移動棋子的過程中,很可能出現重覆的盤面而不自知。
利用電腦求解,可以記錄下哪些盤面已經走過,避免浪費時間在相同搜尋重覆的路徑;除此之外,可以依循一定的規則來展開每一個盤面中所有能移動的方法。如此,窮舉所有的可能,只要給定的盤面有解,一定能找到解,剩下的只是求解需要時間的長短罷了。但因為解答的步數有過100步以上的,所以不能直接以暴力法去窮舉。以下我們說明如何去克服此難題。
二.電腦解題之演算法
在正式開始寫程式求解之前,我們先利用目前已知的資料。華容道的棋盤為橫四格縱五格,為了辨別棋子在棋盤上的位置,先對棋盤上的每個格子編號:左上角為0,右下角為19,共二十個格子(表一)。為了識別每顆棋子,我們也將棋子加以編號:曹操為1號,五虎將給予2至6的編號,剩下四個兵則編為7至10號,而以0表示空白(表二)。最後,以棋子的長寬分類,共可分為四類:第一類為2x2大小,第二類為2x1,第三類1x2,而第四類則為1x1(表三)。
以每顆棋子左上角所佔據的格子編號來表示棋子的位置,如此,每個盤面的狀態則可以用一個陣列表示。例如圖一「橫刀立馬」的盤面,曹操的(編號為1)的位置為1、關羽(編號為2)的位置為9,其餘可類推,我們可以表示為:
[1 90381113141619]
因為知道十顆棋子的位置就可以推知兩個空格的所在,因此,我們並不需要額外記錄空格的位置。
在每個盤面要尋找下一步該怎麼走,若檢查每顆棋子可以走的路,棋盤上共有十顆棋子,則十顆棋子都要檢查,而且大部份的棋子可能都無法移動。為了減少麻煩,改由空白格下手。由於盤面上只會有兩個空格,只要檢查空格周圍的棋子是否能往空格移動,如此即可減少許多不必要的判斷,而加快搜尋的速度。為了推知空格的位置,首先將棋盤上所有的格子都先填入0,再依棋子的位置以及種類,將棋子的編號填入棋盤內,填完之後,即可得知空格的所在。舉例說明,下面是我們將棋子編號填入「橫刀立馬」盤面之後所得的結果(表四):
由此可以得知兩個空格的位置分別為17與18。接著則分別判斷每個空格上下左右四個方向緊鄰的棋子能否往空格移動,若可,更動該棋子的位置後則可得到新的盤面。
由於我們的目的在尋找由給定盤面開始,最終將曹操移動至曹營上方中央的位置最少需要多少步,因此第一個念頭即是利用BFS(Breadth-First Search)配合Branch and Bound的方式求解,如此,第一個找到的解一定是最佳解。但是,利用BFS需要額外的空間來存放等待著要被展開盤面的Queue,因此,當我們要展開的深度很深時(例如100層以上),需要耗費的空間就很驚人了。所以改而採用DFS(Depth-First Search)來展開Game Tree。為了加快DFS的效率,每當找到一個解時,則立即記錄下至目前為止的最少步數,倘若目前步數超過最少步數則不繼續往下展開;除此之外,另外用Binary Search Tree記錄已經走過的盤面(這些盤面有一次序值,如下所述),以及先前走到此盤面時的步數:第一步,先將同一類棋子的位置加以排序,例如圖三「三軍聯防」盤面中,十顆棋子的位置如表五所示:
我們將十顆棋子的位置依序存放在一陣列中:
[0 138102312151619]
再依照棋子的類別可以分為四組:
[0]、[13810]、[23]、[12151619]
這四組分別排序過後再組合可得:
[0810132312151619]
這樣的目的在於減少重複的盤面。相同類別的棋子,位置互調,其實是一樣的狀況。經過此步驟之後,可過濾掉這些重複狀況的盤面,因而能減少展開的盤面,縮短程式搜尋的時間。
第二步,再透過公式將十個棋子的位置編碼成一個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##O
O##O
H[]H
HHHH
HH
|
34步
|
3859
|
71秒
|
層層設防
|
H##H
H##H
O[]O
O[]O
[]
|
103步
|
30375
|
1474秒
|
橫刀立馬
|
H##H
H##H
H[]H
HOOH
OO
|
81步
|
23853
|
1835秒
|
兵將聯防
|
O##O
H##H
H[]H
O[]O
[]
|
121步
|
36557
|
1127秒
|
將守角樓
|
H##H
H##H
O[]O
HOOH
HH
|
70步
|
23111
|
1660秒
|
四路進兵
|
##OH
##OH
OO
[][]
[][]
|
65步
|
13753
|
1005秒
|
屯兵東路
|
##HH
##HH
[]OO
HHOO
HH
|
74步
|
20935
|
1245秒
|
比翼橫空
|
[]##
[]##
[][]
O OH
O OH
|
28步
|
5779
|
307秒
|
插翅難飛
|
H##O
H##O
[]OO
H[]H
HH
|
63步
|
42290
|
3023秒
|
夾道藏兵
|
##OH
##OH
[][]
[][]
OO
|
76步
|
13753
|
858秒
|
重重包圍
|
H##O
H##O
H[]H
H[]H
OO
|
74步
|
42271
|
2738秒
|
水洩不通
|
O##H
O##H
[][]
[][]
OO
|
80步
|
13600
|
813秒
|
雲遮霧障
|
H##H
H##H
H[]O
H[]O
OO
|
81步
|
42165
|
3080秒
|
將擋後路
|
[]##
[]##
[][]
[]OO
OO
|
21步
|
2761
|
137秒
|
守口如瓶
|
O##O
H##H
HH H
OH O
[][]
|
100步
|
43669
|
2483秒
|
前呼後擁
|
OO##
[]##
[][]
[][]
OO
|
22步
|
6234
|
173秒
|
三軍聯防
(又名交錯堵道)
|
##HH
##HH
[][]
O[]O
OO
|
69步
|
16227
|
1046秒
|
調兵遣將
|
##OO
##OO
[][]
[][]
[]
|
52步
|
5078
|
240秒
|
四將聯防
(又名四將連關)
|
##[]
##[]
HH[]
HHOO
OO
|
40步
|
5476
|
126秒
|
巧過五關
|
O##O
O##O
[][]
[][]
[]
|
33步
|
6052
|
189秒
|
表五程式執行結果
四.結論
(1)目前之結論
計算步數的方式有兩種:第一種為只要棋子移動一格就算一步,第二種狀況則為若兩個空格相鄰,棋子得以連續移動兩格只算一步。依據文獻上的記錄推測,前人文獻計算步數的方法應為後者,故本程式亦採用後者為計算步數的方式。程式所得到的結果,與先前得到的文獻資料比較後,有以下三種狀況(表六)。
與前人資料相符者
|
盤面名稱
|
起始盤面
|
資料數據
|
執行結果
|
盤面名稱
|
起始盤面
|
資料數據
|
執行結果
|
左右佈兵
|
O##O
O##O
H[]H
HHHH
HH
|
34步
|
34步
|
橫刀立馬
|
H##H
H##H
H[]H
HOOH
OO
|
81步
|
81步
|
水洩不通
|
O##H
O##H
[][]
[][]
OO
|
80步
|
80步
|
|
|
|
|
步數較前人資料記錄少者
|
三軍聯防
|
##HH
##HH
[][]
O[]O
OO
|
74步
|
69步
|
四路進兵
|
##OH
##OH
OO
[][]
[][]
|
67步
|
65步
|
步數較前人資料記錄多者
|
插翅難飛
|
H##O
H##O
[]OO
H[]H
HH
|
62步
|
63步
</
分享到:
Global site tag (gtag.js) - Google Analytics
|
相关推荐
该程序采用了Python的smtplib模块和pyqt5模块,实现了自动登录QQ邮箱的功能,并且支持向其他QQ邮箱或如网易邮箱等其他类型的邮箱发送文本邮件和附带文件的邮件。
2024年全球胚胎移植玻璃化冷冻介质行业总体规模、主要企业国内外市场占有率及排名
多式联运 (1)
sklearn中决策树算法进行泰坦尼克号人员幸存预测 有包的导入、数据处理、特征提取、预测结果等
编译原理实验报告(1和2)(可运行)
数据库第一次满分上机报告
j2se6.chm.zip
ins爬虫on工具,能够批量爬取ins资源
库房检测APP.apk
系统主要分员工管理员两个角色 管理模块具体有商品管理,部门员工管理,进货管理,订单管理,换货管理,供应商管理,供应商管理,客户管理,公告通知管理等模块,而员工模块具体由商品管理,进货管理,订单管理,供应商管理,客户管理,换货订单管理,公告通知管理等模块组成。 仓库管理信息系统所涉及的主要数据包括商品管理、进货管理、订单管理、换货管理和供应商管理,客户管理,公告通知管理下面分别分析这些数据需求。 (1)商品管理 商品管理主要是管理商品分类信息以及管理商品信息。 (2)进货管理 进货管理主要员工可以登记进货信息,以及查看我的进货记录,而管理员可以添加进货信息以及对进货信息的管理。 (3)订单管理 订单管理主要是对订单的一个统计,员工对销售的订单进行登记,管理员可以管理员工们的订单销售。 (4)换货管理 换货管理主要员工可以登记换货信息,以及查看我的换货记录,而管理员可以添加换货信息以及对换货信息的管理。 (5)供应商管理 管理员可以管理对他们厂家的供应商,来达到可以很好及时的跟供应商进行沟通。 (6)客户管理 管理员可以管理客户。对客户进行维护。
没有word只有图片,打印图片打印出来发黑怎么办?如何像打印doc一样清楚。教你一招搞定
matlab 独立分量分析 fastica,icaplot,remmean,whiten,盲源分离,去均值,白化处理.zip
文档Python双指针算法模板和题目同向相向快速排序归并排序提取方式是百度网盘分享地址
向天歌【简约扁平化】大学生实习社会实践报告.ppt
GEK气化炉sw18可编辑设计图纸.7z
数据来源:中经数据库 数据范围:各个省份的区县财政收入即一般公共预算收入、税收收入 (一般财政收入即一般公共预算收入的完整度较高。税收收入一般50%的区县会有数据) 数据年度区间:2000-2023(具体看文件名上的年度区间) 珍贵数据,包含了各省所有的区、县、县级市哦,很难找到的哦
tetris.rar
100L化学槽罐sw18可编辑设计图纸.7z
自动驾驶-决策规划算法八:贝塞尔曲线(C++)