亚洲免费在线-亚洲免费在线播放-亚洲免费在线观看-亚洲免费在线观看视频-亚洲免费在线看-亚洲免费在线视频

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

系統(tǒng) 2011 0
利用電腦探討中國(guó)古代益智遊戲─「華容道」之解法
魏仲良、林順喜
國(guó)立臺(tái)灣師範(fàn)大學(xué)
資訊教育系
摘要
在本文中,我們嘗試設(shè)計(jì)演算法,利用電腦找出中國(guó)古代流傳下來(lái)的益智遊戲─「華容道」的最少步數(shù),以驗(yàn)證前人資料上所記載各盤(pán)面的最少步數(shù)是否正確。此遊戲中許多盤(pán)面之解答的移動(dòng)步數(shù)超過(guò) 100步,因此不能直接用暴力法搜尋,目前文獻(xiàn)上尚未見(jiàn)到電腦之解法,只有一些人為的解答有記錄,也有一些程式將這些人為的、不是最佳的解答直接記錄下來(lái)作展示。因此我們構(gòu)思如何解決此困難之問(wèn)題。在此論文中,我們發(fā)展了一些技術(shù),目標(biāo)是求出完全的最佳解,並實(shí)際撰寫(xiě)程式測(cè)試,要求在可忍受的時(shí)間內(nèi)解出。程式的執(zhí)行結(jié)果與先前得到的前人資料有所出入,有些與資料記載的吻合,有的則較記錄為多,還有一些比資料上的少上三至五步之多。驗(yàn)證了一下程式輸出到檔案的最佳解,發(fā)現(xiàn)程式所求得比資料記載還要少的結(jié)果應(yīng)是正確的。至於程式求得較前人資料為多的部份,可能是前人的文獻(xiàn)資料有誤,因?yàn)橘Y料上只記載著各盤(pán)面最少步數(shù)的解題記錄,並無(wú)參考的解法。
一.緒論
1.華容道遊戲的介紹:
華容道,這是從中國(guó)古代就流傳下來(lái)的智慧遊戲,出自三國(guó)演義中「關(guān)羽橫讓捉放曹操」的情節(jié)。由於盤(pán)面變化多端,曾被譽(yù)為「智力遊戲界的三大不可思議」的遊戲之一。其玩法為在所有棋子均不離開(kāi)棋盤(pán)的前提之下,如何使曹操越過(guò)重重的包圍,逃回曹營(yíng)。這個(gè)遊戲可在下列網(wǎng)站均可找到程式下載來(lái)玩 (用人工嘗試錯(cuò)誤法來(lái)玩):

華容道基本上其棋盤(pán)為橫四格縱五格的盤(pán)面,曹操為占四格的 2x2的正方形棋子;占兩格的為五虎將的關(guān)羽、張飛、趙雲(yún)、馬超與黃忠,其中只有關(guān)羽橫兩格,其餘四將均為豎兩格;還有四個(gè)各占一格的兵(如圖一)。所以在遊戲的時(shí)候,只能利用盤(pán)面上留下的兩個(gè)空格來(lái)移動(dòng)棋子,只要想辦法將曹操移到鄰接曹營(yíng)上方的正中央的位置,即表示我們已成功讓曹操逃回曹營(yíng),遊戲至此於是結(jié)束。移動(dòng)的步數(shù)愈少愈好。而在移動(dòng)的過(guò)程中我們可以發(fā)現(xiàn),關(guān)羽跟曹操不能在同一排,關(guān)羽必須要橫讓?zhuān)懿俨庞锌赡芡ㄟ^(guò)向下走,這正好符合了三國(guó)演義中的情節(jié),所以這項(xiàng)遊戲又被稱(chēng)為「捉放曹」。除了上述標(biāo)準(zhǔn)的盤(pán)面之外,橫擺的五虎將除了關(guān)羽之外,也可以將其他四將橫擺,使得盤(pán)面有更多變化,更富挑戰(zhàn)性。

在本文中 ,盤(pán)面資料來(lái)源為「阿集好用軟體區(qū)→休閒益智軟體( http://www.ntctcps.tc.edu.tw/13-3.htm) 內(nèi)的「華容道益智遊戲中文版(視窗95版)」。除了華容道之外,還有兩個(gè)類(lèi)似的棋戲:「包青天」(圖二)與「箱入娘」。其中,包青天亦可在「阿集好用軟體區(qū)→休閒益智軟體」內(nèi)找到。這些軟體都只是純粹為了遊戲之用,並無(wú)參考的解答。另外,網(wǎng)路上可以找到一個(gè)DOS下的華容道遊戲軟體(604.zip),它有提供參考的解答,但大部份盤(pán)面所的步數(shù)比我們多,所以並不是最佳解(請(qǐng)見(jiàn)「四、結(jié)論」中說(shuō)明)。上面提到的這些程式,已經(jīng)收集整理在 ftp://alg.ice.ntnu.edu.tw/pub/chess/ ,有興趣的讀者,可以上網(wǎng)去取得。
1.以人腦移動(dòng)棋子與以電腦求解的不同:
一般人在玩這類(lèi)的遊戲的時(shí)候,大概會(huì)很直覺(jué)地看到哪顆棋子可以移動(dòng),就移動(dòng)那顆棋子。等到發(fā)現(xiàn)錯(cuò)誤的時(shí)候,再將棋子擺回原位。但是,當(dāng)移動(dòng)的步數(shù)一多,大概很少人能記得如何從一開(kāi)始的盤(pán)面一步步移動(dòng)棋子,走到目前的狀態(tài)。而且在移動(dòng)棋子的過(guò)程中,很可能出現(xiàn)重覆的盤(pán)面而不自知。
利用電腦求解,可以記錄下哪些盤(pán)面已經(jīng)走過(guò),避免浪費(fèi)時(shí)間在相同搜尋重覆的路徑;除此之外,可以依循一定的規(guī)則來(lái)展開(kāi)每一個(gè)盤(pán)面中所有能移動(dòng)的方法。如此,窮舉所有的可能,只要給定的盤(pán)面有解,一定能找到解,剩下的只是求解需要時(shí)間的長(zhǎng)短罷了。但因?yàn)榻獯鸬牟綌?shù)有過(guò)100步以上的,所以不能直接以暴力法去窮舉。以下我們說(shuō)明如何去克服此難題。
二. 電腦解題之演算法

在正式開(kāi)始寫(xiě)程式求解之前,我們先利用目前已知的資料。華容道的棋盤(pán)為橫四格縱五格,為了辨別棋子在棋盤(pán)上的位置,先對(duì)棋盤(pán)上的每個(gè)格子編號(hào):左上角為 0,右下角為19,共二十個(gè)格子(表一)。為了識(shí)別每顆棋子,我們也將棋子加以編號(hào):曹操為1號(hào),五虎將給予2至6的編號(hào),剩下四個(gè)兵則編為7至10號(hào),而以0表示空白(表二)。最後,以棋子的長(zhǎng)寬分類(lèi),共可分為四類(lèi):第一類(lèi)為2x2大小,第二類(lèi)為2x1,第三類(lèi)1x2,而第四類(lèi)則為1x1(表三)。

以每顆棋子左上角所佔(zhàn)據(jù)的格子編號(hào)來(lái)表示棋子的位置,如此,每個(gè)盤(pán)面的狀態(tài)則可以用一個(gè)陣列表示。例如圖一「橫刀立馬」的盤(pán)面,曹操的(編號(hào)為1)的位置為1、關(guān)羽(編號(hào)為2)的位置為9,其餘可類(lèi)推,我們可以表示為:
[1 90381113141619]
因?yàn)橹朗w棋子的位置就可以推知兩個(gè)空格的所在,因此,我們並不需要額外記錄空格的位置。

在每個(gè)盤(pán)面要尋找下一步該怎麼走,若檢查每顆棋子可以走的路,棋盤(pán)上共有十顆棋子,則十顆棋子都要檢查,而且大部份的棋子可能都無(wú)法移動(dòng)。為了減少麻煩,改由空白格下手。由於盤(pán)面上只會(huì)有兩個(gè)空格,只要檢查空格周?chē)钠遄邮欠衲芡崭褚苿?dòng),如此即可減少許多不必要的判斷,而加快搜尋的速度。為了推知空格的位置,首先將棋盤(pán)上所有的格子都先填入 0,再依棋子的位置以及種類(lèi),將棋子的編號(hào)填入棋盤(pán)內(nèi),填完之後,即可得知空格的所在。舉例說(shuō)明,下面是我們將棋子編號(hào)填入「橫刀立馬」盤(pán)面之後所得的結(jié)果(表四):


由此可以得知兩個(gè)空格的位置分別為 17與18。接著則分別判斷每個(gè)空格上下左右四個(gè)方向緊鄰的棋子能否往空格移動(dòng),若可,更動(dòng)該棋子的位置後則可得到新的盤(pán)面。

由於我們的目的在尋找由給定盤(pán)面開(kāi)始,最終將曹操移動(dòng)至曹營(yíng)上方中央的位置最少需要多少步,因此第一個(gè)念頭即是利用 BFS(Breadth-First Search)配合Branch and Bound的方式求解,如此,第一個(gè)找到的解一定是最佳解。但是,利用BFS需要額外的空間來(lái)存放等待著要被展開(kāi)盤(pán)面的Queue,因此,當(dāng)我們要展開(kāi)的深度很深時(shí)(例如100層以上),需要耗費(fèi)的空間就很驚人了。所以改而採(cǎi)用DFS(Depth-First Search)來(lái)展開(kāi)Game Tree。為了加快DFS的效率,每當(dāng)找到一個(gè)解時(shí),則立即記錄下至目前為止的最少步數(shù),倘若目前步數(shù)超過(guò)最少步數(shù)則不繼續(xù)往下展開(kāi);除此之外,另外用Binary Search Tree記錄已經(jīng)走過(guò)的盤(pán)面(這些盤(pán)面有一次序值,如下所述),以及先前走到此盤(pán)面時(shí)的步數(shù):第一步,先將同一類(lèi)棋子的位置加以排序,例如圖三「三軍聯(lián)防」盤(pán)面中,十顆棋子的位置如表五所示:

我們將十顆棋子的位置依序存放在一陣列中:
[0 138102312151619]
再依照棋子的類(lèi)別可以分為四組:
[0]、[13810]、[23]、[12151619]
這四組分別排序過(guò)後再組合可得:
[0810132312151619]
這樣的目的在於減少重複的盤(pán)面。相同類(lèi)別的棋子,位置互調(diào),其實(shí)是一樣的狀況。經(jīng)過(guò)此步驟之後,可過(guò)濾掉這些重複狀況的盤(pán)面,因而能減少展開(kāi)的盤(pán)面,縮短程式搜尋的時(shí)間。
第二步,再透過(guò)公式將十個(gè)棋子的位置編碼成一個(gè)64-bit大小可表示的數(shù)值。這裡所採(cǎi)用的公式如下:(假設(shè)儲(chǔ)存棋子位置的陣列為C[])
Value = C[0]*20 9 + C[1]*20 8 + C[2]*20 7 + C[3]*20 6 + C[4]*20 5 +
C[5]*20 4 + C[6]*20 3 + C[7]*20 2 + C[8]*20 + C[9]
以圖一為例,我們可將盤(pán)面換算成:
0*20 9 + 8*20 8 + 10*20 7 + 13*20 6 + 2*20 5 + 3*20 4 + 12*20 3 + 15*20 2 + 16*20 + 19 = 218438982339
這樣有兩個(gè)好處:一是可減少空間的使用,另一則為同一類(lèi)別的棋子,若在相同的位置上,實(shí)際上是同一種情況,如此可大大減少展開(kāi)盤(pán)面的次數(shù)。Binary Search Tree內(nèi)所記錄的盤(pán)面就是透過(guò)公式計(jì)算得來(lái)的數(shù)值insert進(jìn)去的。

原則上,在展開(kāi)一個(gè)盤(pán)面之前,會(huì)先自 Binary Search Tree中搜尋該盤(pán)面是否已經(jīng)展開(kāi)過(guò),若無(wú),則繼續(xù)展開(kāi),若有,則表示此盤(pán)面先前已經(jīng)走過(guò),所以不展開(kāi)此重複的盤(pán)面,但是除了一種特殊的情況:雖然先前已經(jīng)走過(guò)此盤(pán)面,但當(dāng)時(shí)的步數(shù)比目前走到此的步數(shù)還多,則得重新由此盤(pán)面展開(kāi)一次,並更新Binary Search Tree裡所記錄盤(pán)面的步數(shù)。目前的步數(shù)較少,表示此時(shí)由起始盤(pán)面至此盤(pán)面的解較先前走到此盤(pán)面時(shí)的解為佳,重新展開(kāi)的目的則在於更新Binary Search Tree裡的步數(shù)記錄。圖四顯示啟始盤(pán)面為「 橫刀立馬」的展開(kāi)情況。

三.程式執(zhí)行結(jié)果與分析
我們使用一臺(tái)普通的個(gè)人電腦做為測(cè)試的工具: Petium 166MMX CPU,160MB PC-100 SD-RAM。使用的Compiler為Borland C++ Builder 3.0, 原始程式碼約 480 行,以下為程式執(zhí)行後所得的最佳解結(jié)果(表五):
符號(hào)說(shuō)明:曹操: ##五虎將(橫): []五虎將(縱):H 兵:O
盤(pán)面名稱(chēng)
啟始盤(pán)面
最少步數(shù)
展開(kāi)盤(pán)面總數(shù)
執(zhí)行時(shí)間
盤(pán)面名稱(chēng)
啟始盤(pán)面
最少步數(shù)
展開(kāi)盤(pán)面總數(shù)
執(zhí)行時(shí)間
左右佈兵
(又名兵臨曹營(yíng) )
O##O
O##O
H[]H
HHHH
HH
34步
3859
71秒
層層設(shè)防
H##H
H##H
O[]O
O[]O
[]
103步
30375
1474秒
橫刀立馬
H##H
H##H
H[]H
HOOH
OO
81步
23853
1835秒
兵將聯(lián)防
O##O
H##H
H[]H
O[]O
[]
121步
36557
1127秒
將守角樓
H##H
H##H
O[]O
HOOH
HH
70步
23111
1660秒
四路進(jìn)兵
##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秒
雲(yún)遮霧障
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秒
三軍聯(lián)防
(又名交錯(cuò)堵道 )
##HH
##HH
[][]
O[]O
OO
69步
16227
1046秒
調(diào)兵遣將
##OO
##OO
[][]
[][]
[]
52步
5078
240秒
四將聯(lián)防
(又名四將連關(guān) )
##[]
##[]
HH[]
HHOO
OO
40步
5476
126秒
巧過(guò)五關(guān)
O##O
O##O
[][]
[][]
[]
33步
6052
189秒
表五程式執(zhí)行結(jié)果
四. 結(jié)論
(1)目前之結(jié)論

計(jì)算步數(shù)的方式有兩種:第一種為只要棋子移動(dòng)一格就算一步,第二種狀況則為若兩個(gè)空格相鄰,棋子得以連續(xù)移動(dòng)兩格只算一步。依據(jù)文獻(xiàn)上的記錄推測(cè),前人文獻(xiàn)計(jì)算步數(shù)的方法應(yīng)為後者,故本程式亦採(cǎi)用後者為計(jì)算步數(shù)的方式。程式所得到的結(jié)果,與先前得到的文獻(xiàn)資料比較後 ,有以下三種狀況(表六)。

與前人資料相符者
盤(pán)面名稱(chēng)
起始盤(pán)面
資料數(shù)據(jù)
執(zhí)行結(jié)果
盤(pán)面名稱(chēng)
起始盤(pán)面
資料數(shù)據(jù)
執(zhí)行結(jié)果
左右佈兵
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步
步數(shù)較前人資料記錄少者
三軍聯(lián)防
##HH
##HH
[][]
O[]O
OO
74步
69步
四路進(jìn)兵
##OH
##OH
OO
[][]
[][]
67步
65步
步數(shù)較前人資料記錄多者
插翅難飛
H##O
H##O
[]OO
H[]H
HH
62步
63步
</
分享到:
評(píng)論
wapysun
  • 瀏覽: 4880685 次
  • 性別: Icon_minigender_1
  • 來(lái)自: 杭州
存檔分類(lèi)
最新評(píng)論

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


更多文章、技術(shù)交流、商務(wù)合作、聯(lián)系博主

微信掃碼或搜索:z360901061

微信掃一掃加我為好友

QQ號(hào)聯(lián)系: 360901061

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描下面二維碼支持博主2元、5元、10元、20元等您想捐的金額吧,狠狠點(diǎn)擊下面給點(diǎn)支持吧,站長(zhǎng)非常感激您!手機(jī)微信長(zhǎng)按不能支付解決辦法:請(qǐng)將微信支付二維碼保存到相冊(cè),切換到微信,然后點(diǎn)擊微信右上角掃一掃功能,選擇支付二維碼完成支付。

【本文對(duì)您有幫助就好】

您的支持是博主寫(xiě)作最大的動(dòng)力,如果您喜歡我的文章,感覺(jué)我的文章對(duì)您有幫助,請(qǐng)用微信掃描上面二維碼支持博主2元、5元、10元、自定義金額等您想捐的金額吧,站長(zhǎng)會(huì)非常 感謝您的哦!!!

發(fā)表我的評(píng)論
最新評(píng)論 總共0條評(píng)論
主站蜘蛛池模板: 国产成人丝袜网站在线看 | 国产在线激情 | 欧美a一片xxxx片 | 国产精品久久免费 | 日日爽夜夜操 | 欧美日韩国产亚洲一区二区三区 | 国产97色在线 | 亚洲 | 久久精品爱| 午夜伦情电午夜伦情影院 | 久久久久久久久久综合情日本 | 亚洲 欧美 精品 中文第三 | 欧美aaa毛片免费看 欧美aaa性bbb毛片 | 中文乱码在线观看 | 在线看一区二区 | 久久99网站 | 日日碰碰 | se成人国产精品 | 一级毛片老太婆交性欧美 | 深夜成人在线 | 青青青国产免费线在 | 99riav视频| 日日干日日操日日射 | 久久国产精品吴梦梦 | 日本视频一区二区三区 | 久久国产精品视频一区 | 一级国产视频 | 色综合久久综合网欧美综合网 | 成人精品亚洲 | 四虎高清成人永久免费影院 | 91热精品 | 日本高清h色视频在线观看 日本高清不卡二区 | 精品久久伦理中文字幕 | 国产午夜亚洲精品久久999 | 亚洲精品成人一区二区www | 农村妇女又色黄一级毛片 | 夜色视频网站 | 久草在线视频看看 | 欧美精品久久久久久久小说 | 日韩精品亚洲人成在线播放 | 亚洲小视频在线播放 | 亚洲免费成人 |