中國(guó)象棋計(jì)算機(jī)博弈關(guān)鍵技術(shù)分析(已改無(wú)錯(cuò)字)
2022-08-15 03:14:08 本頁(yè)面
【正文】 對(duì)博弈樹(shù)進(jìn)行必要的裁剪 （ cutoff/pruning）。 東北大學(xué)人工智能與機(jī)器人研究所 奠基者 ——香儂教授 ? 香儂 (Claude Shannon)教授早在 1950年首先提出了 極大 極小算法 （ Minimax Algorithm），從而 奠定了計(jì)算機(jī)博弈的理論基礎(chǔ) 。 ? Shannon, Claude E., Programming a puter for playing chess [J], Philosophical Magazine, Vol. 41:256275, 1950. 東北大學(xué)人工智能與機(jī)器人研究所 博弈樹(shù) 特點(diǎn)分析 ? 博弈樹(shù)不同于一般的搜索樹(shù)，它是由對(duì)弈雙方共同產(chǎn)生的一種 “ 變性 ” 搜索樹(shù) 。 ? 紅方為走棋方，它在偶數(shù)層的著法選擇是要在其全部子節(jié)點(diǎn)中找到評(píng)估值最大的一個(gè)，即實(shí)行 “ Max搜索 ” 。紅方稱為 MAX方 。 ? 而其應(yīng)對(duì)方 ——黑方在奇數(shù)層的著法選擇則是在其全部子節(jié)點(diǎn)中要找到評(píng)估值最小的一個(gè)，即實(shí)行 “ Min搜索 ” 。黑方稱為 MIN方 。 東北大學(xué)人工智能與機(jī)器人研究所 MAX MAX MIN 1 2 9 8 7 6 5 4 3 3 2 1 3 MaxMin搜索 （ 1） 由此產(chǎn)生最佳路徑和最佳著法 東北大學(xué)人工智能與機(jī)器人研究所 MAX MAX MIN 5 2 9 8 7 6 1 4 3 1 2 4 4 MaxMin搜索 （ 2） 由此產(chǎn)生最佳路徑和最佳著法 東北大學(xué)人工智能與機(jī)器人研究所 αβ剪枝搜索 ? 一種基于剪枝 （ αβcutoff） 的 深度優(yōu)先搜索 （ depthfirst search） 。 ? 將走棋方定為 MAX方 ， 因?yàn)樗x擇著法時(shí)總是對(duì)其子節(jié)點(diǎn)的評(píng)估值取極大值 ， 即 選擇對(duì)自己最為有利的著法 ； ? 將應(yīng)對(duì)方定為 MIN方 ， 因?yàn)樗咂鍟r(shí)需要對(duì)其子節(jié)點(diǎn)的評(píng)估值取極小值 ， 即 選擇對(duì)走棋方最為不利的 、 最有鉗制作用的著法 。 東北大學(xué)人工智能與機(jī)器人研究所 MAX MAX MIN 4 5 6 8 2 4 3 4 α剪枝 （ 1） 由此產(chǎn)生最佳路徑和最佳著法 α=4 東北大學(xué)人工智能與機(jī)器人研究所 ? 在對(duì)博弈樹(shù)采取 深度優(yōu)先 的搜索策略時(shí)， 從左路分枝的葉節(jié)點(diǎn)倒推得到某一層 MAX節(jié)點(diǎn) 的值，可表示到此為止 得以 “ 落實(shí) ” 的著法最佳值 ，記為 α。 ? 顯然此值可作為 MAX方著法指標(biāo)的 下界 。 ? 在搜索此 MAX節(jié)點(diǎn)的 其它子節(jié)點(diǎn) ，即探討另一著法時(shí)，如果發(fā)現(xiàn) 一個(gè)回合（ 2步棋）之后評(píng)估值變差，即孫節(jié)點(diǎn) 評(píng)估值低于下界 α值 ，則便可以剪掉此枝（以該子節(jié)點(diǎn)為根的子樹(shù)），即 不再考慮此 “ 軟著 ” 的延伸 。 ? 此類剪枝稱為 α剪枝 。 東北大學(xué)人工智能與機(jī)器人研究所 MAX MAX MIN 1 3 6 8 2 1 5 4 α剪枝 （ 2） 7 4 9 1 2 24由此產(chǎn)生最佳路徑和最佳著法 α=4 東北大學(xué)人工智能與機(jī)器人研究所 剪枝效果 差別很大 ? 不難發(fā)現(xiàn)， 和最佳著法關(guān)系密切 ? 什么是最佳著法？ ? 怎樣找到最佳著法 ？ （ 1） （ 2） 東北大學(xué)人工智能與機(jī)器人研究所 β剪枝 （ 1） 1 7 4 2 9 8 MAX MIN MIN 7 7 由此產(chǎn)生最佳路徑和最佳著法 β =7 東北大學(xué)人工智能與機(jī)器人研究所 ? 同理 ， 由左路分枝的葉節(jié)點(diǎn)倒推得到某一層MIN節(jié)點(diǎn)的值 ， 可表示到此為止對(duì)方著法的鉗制值 ， 記為 β。 ? 顯然此 β值可作為 MAX方無(wú)法實(shí)現(xiàn)著法指標(biāo)的上界 。 ? 在搜索該 MIN節(jié)點(diǎn)的其它子節(jié)點(diǎn) ， 即探討另外著法時(shí) ， 如果發(fā)現(xiàn)一個(gè)回合之后鉗制局面減弱 ，即孫節(jié)點(diǎn)評(píng)估值高于上界 β值 ， 則便可以剪掉此枝 ， 即 不再考慮此 “ 軟著 ” 的延伸 。 ? 此類剪枝稱為 β剪枝 。 東北大學(xué)人工智能與機(jī)器人研究所 β剪枝 （ 2） 8 3 5 7 9 1 MAX MIN MIN 8 4 2 6 由此產(chǎn)生最佳路徑和最佳著法 44 8 β =4 東北大學(xué)人工智能與機(jī)器人研究所 β剪枝和 α剪枝具有 同樣規(guī)律 剪枝效果與 最佳著法 的位置密切相關(guān) 與博弈樹(shù) 展開(kāi)的順序 密切相關(guān) （ 1） （ 2） 東北大學(xué)人工智能與機(jī)器人研究所 需要指出的是 ? αβ剪枝是根據(jù)極大 極小搜索規(guī)則的進(jìn)行的， 雖然它沒(méi)有遍歷某些子樹(shù)的大量節(jié)點(diǎn)，但它仍不失為窮盡搜索的本性 。 ? αβ剪枝技巧的發(fā)現(xiàn)，一下便為博弈樹(shù)搜索效率的提高開(kāi)創(chuàng)了 嶄新的局面 。 東北大學(xué)人工智能與機(jī)器人研究所 Knuth和 Moore重要貢獻(xiàn) ? 1975年給出了 αβ算法正確性的數(shù)學(xué)證明 。 ? αβ剪枝算法的效率與子節(jié)點(diǎn)擴(kuò)展的先后順序相關(guān)。 在最理想情況下（極小樹(shù)） ，其生成的節(jié)點(diǎn)數(shù)目為 /221DDN B??( 1 ) / 2 ( 1 ) / 2 1DDDN BB??? ? ?（ D為偶數(shù)） （ D為奇數(shù)） DD BN ?而蠻力搜索 （ D為搜索深度） 可見(jiàn)不做任何剪枝僅能搜索到一半深度 東北大學(xué)人工智能與機(jī)器人研究所 如何才能得到 極小樹(shù) ？ ? 不難看出 ， 如果最左路的分枝就是最佳路徑 ，亦即理智雙方最為精彩的對(duì)弈著法序列 ， 那么就可以將右路各分枝陸續(xù)剪掉 ， 從而使 αβ搜索的節(jié)點(diǎn)數(shù)僅為極大樹(shù)的 。 ? 為了得到最好的節(jié)點(diǎn)擴(kuò)展順序，許多搜索算法在著法（節(jié)點(diǎn)擴(kuò)展的分枝）排序上給予特別的關(guān)注。 ? 比如在著法生成（節(jié)點(diǎn)擴(kuò)展）時(shí)， 先生成吃子著法 ，尤其先生成 吃分值高的 “ 大子 ” 著法 ，因?yàn)橛纱水a(chǎn)生著法更有可能是最佳的。 2/2 DB?東北大學(xué)人工智能與機(jī)器人研究所 面向著法排序 的算法 ? 圍繞著法排序 ， 已經(jīng)出現(xiàn)許多優(yōu)秀的搜索算法與舉措 。如： ? 同形表法 （ Transposition table） ? 吃子走法的 SEE 排序 ? 殺手走法 （ Killer heuristic） ? 未吃子走法的歷史啟發(fā)排序 （ Historic heuristic） ? 類比法 （ Method of analogies） 等 。 ? 有人將 αβ剪枝作用延伸到多個(gè)回合之后，于是又出現(xiàn)了 深層 αβ剪枝 （ Deep αβ cutoff）算法。也取得很好效果。 東北大學(xué)人工智能與機(jī)器人研究所 αβ窗口搜索 （ αβwindows search） ? 從 αβ剪枝原理中得知： ? α值可作為 MAX方 可實(shí)現(xiàn)著法指標(biāo)的 下界 ? β值可作為 MAX方 無(wú)法實(shí)現(xiàn)著法指標(biāo)的 上界 ? 于是由 α和 β可以形成一個(gè) MAX方 候選著法的窗口 ? 也便出現(xiàn)了各種各樣的 αβ窗口搜索算法 。 東北大學(xué)人工智能與機(jī)器人研究所 αβ窗口 的搜索算法 ? 圍繞如何能夠快速得到一個(gè) 盡可能小而又盡可能準(zhǔn)確的窗口 ， 也便出現(xiàn)了各種各樣的 αβ窗口搜索算法 。 如 ? FailSoft AlphaBeta ? Aspiration Search（ 渴望搜索 ） ? Minimal Window Search（ 最小窗口搜索 ） ? Principal Variable Search（ PVS搜索 ） ? Negascout搜索 ? 寬容搜尋 （ Tolerance search） 等 。 東北大學(xué)人工智能與機(jī)器人研究所 迭代深化 搜索 （ Iterative deepening search） ? 不難想像， 深度為 D－ 1層的最佳路徑，最有可能成為深度為 D層博弈樹(shù)的最佳路徑 。 ? Knuth和 Moore分析表明 ，對(duì)于分枝因子為 B的博弈樹(shù)，利用剪枝搜索 D層所需時(shí)間大約是搜索 D1層所需時(shí)間的 倍 。 ? 如果取 B=36， 每多搜一層就要花上原先的 6倍時(shí)間 。 BB東北大學(xué)人工智能與機(jī)器人研究所 迭代深化 搜索 ? 于是 DUCHENSS課題組開(kāi)始采用逐層加深搜索算法。 ? 先花 1/6的時(shí)間做 D1層的搜索，找到最佳路徑 ； ? 同時(shí)記載同形表、歷史啟發(fā)表、殺手表等有價(jià)值的著法評(píng)估信息； ? 以求達(dá)到 D層最好的剪枝效果。 ? 目前機(jī)器博弈引擎普遍采用迭代深化搜索策略 。 東北大學(xué)人工智能與
高考資料相關(guān)推薦
鄂ICP備17016276號(hào)-1