【文章內(nèi)容簡介】 4 12 18 18 18 12 14 1212 16 14 20 20 20 14 16 126 10 8 14 14 14 8 10 64 8 6 14 12 14 6 8 48 4 8 16 8 16 8 4 82 10 6 14 12 14 6 10 2mre?????????? ????????? ?????車坐大堂分值最高！ 東北大學(xué)人工智能與機器人研究所 2 ( )4 8 16 12 4 12 16 8 44 10 28 16 8 16 28 10 412 14 16 20 18 20 16 14 128 24 18 24 20 24 18 24 86 16 14 18 16 18 14 16 64 12 16 14 12 14 16 12 42 6 8 6 10 6 8 6 24 2 8 8 4 8 8 2 40 2 4 4 2 4 4 2 00 4 0 0 0 0 0 4 0mhe?????????? ?????????????馬窩心和馬臥槽大不相同！ 紅馬 位置評估值 (m=h) 東北大學(xué)人工智能與機器人研究所 當(dāng)頭炮分值較高！ 2 ( )6 4 0 10 12 10 0 4 62 2 0 4 14 4 0 2 22 2 0 10 8 10 0 2 20 0 2 4 10 4 2 0 00 0 0 2 8 2 0 0 02 0 4 2 6 2 4 0 20 0 0 2 4 2 0 0 04 0 8 6 10 6 8 0 40 2 4 6 6 6 4 2 00 0 2 6 6 6 2 0 0mce????????? ? ???? ? ?????? ????????????紅炮 位置評估值 (m=c) 東北大學(xué)人工智能與機器人研究所 紅兵 位置評估值 (m=p) 2 ( )0 3 6 9 12 9 6 3 018 36 56 80 12 0 80 56 36 1814 26 42 60 80 60 42 26 1410 20 30 34 40 34 30 20 106 12 18 18 20 18 18 12 62 0 8 0 8 0 8 0 20 0 2 0 4 0 2 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0mpe?????????? ????????????可見進入九宮的兵頂大車！ 東北大學(xué)人工智能與機器人研究所 棋子靈活度 評估值 —e3 ? 對各兵種而言， 每多一個可走位置就加上一定分值 。 ? 如設(shè)定：兵 15 士 1 象 1 車 6 馬 12 炮 6 將 0 東北大學(xué)人工智能與機器人研究所 棋子配合 評估值 —e4 ? 重點是 車馬炮的配合 與牽制。 ? 過河兵牽手可加 120分。 ? 連環(huán)馬、擔(dān)子炮、霸王車等都可以考慮加分。 將帥安全 評估值 —e5 ? 此項多從 盤勢 上加以考慮。 ? 多子歸邊、空頭炮、當(dāng)頭炮、沉底炮、將帥位置等，都要給予一定的 懲罰或獎勵 分。 東北大學(xué)人工智能與機器人研究所 評估函數(shù)的 計算 ? 本方為正值，對方為負值，其 代數(shù)和即為當(dāng)前局面評估值。 ? 顯然， 總值為正對我方有利 ，負值對對方有利。絕對值的大小說明雙方棋勢的差距。 ? 不難看出，評估函數(shù)中涉及到的 權(quán)值系數(shù)可能多達上千個 ，都需要認真選擇與權(quán)衡。 ——系統(tǒng)開發(fā)難點 。 ? ? ?? ? ???NkNkTlRlkRkR eEE1 1 1,? ? ?? ? ???NkNkTlBlkBkB eEE1 1 1,東北大學(xué)人工智能與機器人研究所 博弈搜索引擎 （ Game search engine) 東北大學(xué)人工智能與機器人研究所 基本定義、概念與稱謂 ? 博弈樹 /對局樹 （ Game tree） ? 狀態(tài)空間 （ State space ） ——狀態(tài) 、 初始 狀態(tài) 、 目標(biāo)狀態(tài) ? 搜索空間 （ Search space） ? 方 ——走棋方 /對方 ， 紅方 /黑方 ， Max/Min ? 節(jié)點 （ 局面 ） ——根節(jié)點 ， 祖父節(jié)點 /父節(jié)點 /子節(jié)點 /孫節(jié)點 ， 葉節(jié)點 ? 回合 ——連續(xù)兩個著法 ， 2步為一個回合 ? 著法得分 （ 評估值 ） 東北大學(xué)人工智能與機器人研究所 博弈搜索 引擎 ? 搜索策略 —廣度優(yōu)先 （ Breadthfirst search） 深度優(yōu)先 （ Depthfirst search） 迭代深化 （ Iterative search） ? 搜索技巧 — 截斷 /剪枝 （ cutoff） 剪枝 （ pruning） 擴展 /延伸 （ extended） ? 搜索結(jié)果 —返回值 /倒推值 /局面評估值 最佳路徑 /當(dāng)前著法 （ The best move） 東北大學(xué)人工智能與機器人研究所 廣度優(yōu)先 搜索 ——近根為先 東北大學(xué)人工智能與機器人研究所 深度優(yōu)先 搜索 ——遠根為先 東北大學(xué)人工智能與機器人研究所 紅方 紅方 紅方 黑方 黑方 Depth 1 Depth 3 Depth 4 Depth 2 Depth 0 紅方走棋 時展開深度為 4的 博弈樹 東北大學(xué)人工智能與機器人研究所 博弈樹分析 ? 博弈樹上的 每一個節(jié)點都代表一個棋局 ，棋手就是要在眾多的葉子節(jié)點上 挑選一個“最佳的路徑與局面 ”作為自己的選擇，從而 反推到當(dāng)前的著法 。 ? 中國象棋博弈樹的龐大是可以想象的。 ? 如果按照每一步平均有 45種可行著法，每局棋平均走 90步，那從開始局面展開到分出勝負，則要考慮 種局面。 ? 據(jù)說，這一天文數(shù)字要比地球上的原子數(shù)目還要多， 即使用世界上最快的計算機進行計算，直到地球毀滅也無法算出第一步的著法。 15090 1045 ?東北大學(xué)人工智能與機器人研究所 搜索法是 求解此類圖模型 的基本方法 ? 無法搜索到最終的勝負狀態(tài) ， 只能靠評估 。 ? 搜索的目標(biāo) ——如何在有限深度的博弈樹中找到評估值最高而又不劇烈波動的最佳棋局 ——目標(biāo)狀態(tài) 。 ? 最佳路徑 （ Principal continuation） ——從當(dāng)前狀態(tài)出發(fā)到達最佳狀態(tài)的路徑 ， 它代表著理智雙方精彩對弈的系列著法 。 ? 最佳著法 （ The best move） ——最佳路徑上的第 1步棋 。 ? 所謂 “ 不劇烈波動 ” 就是說最佳棋局不是在進行子力交換與激烈拼殺的過程當(dāng)中 。 東北大學(xué)人工智能與機器人研究所 搜索策略 的劃分 ? A類 ——窮盡搜索 （ Exhaustive search） ? B類 ——選擇性搜索 （ Selective search） ? C類 ——目標(biāo)導(dǎo)向搜索 （ Goal oriented search） ? “一著不慎，滿盤皆輸” ? 于是，看得遠（搜索的深），看得準(zhǔn)（真正找到指定深度內(nèi)的最佳的平穩(wěn)棋局），便成為搜索算法的基本著眼點。 ? 顯然 窮盡搜索成為人們首選的搜索策略 。 東北大學(xué)人工智能與機器人研究所 蠻力搜索 （ Brute search） ? 一般采用 廣度優(yōu)先 搜索 ? 一層層展開，一層層搜索，因為“窮盡”而沒有風(fēng)險，不會漏掉展開深度內(nèi)的最優(yōu)解。 ? 假設(shè)計算機搜索節(jié)點速率為 1M/秒 ，中國象棋 B=45 （分枝因子 B=40~50） ? 下表為 在不同的給定時間內(nèi)達到的搜索層數(shù) 。 給定時間 1秒 1分 1小時 1天 1年 10年 100年 搜索層數(shù) 東北大學(xué)人工智能與機器人研究所 出路在哪里？ ? 由于完整的博弈樹過于龐大 ， 盲目搜索 所能達到的層數(shù)十分有限 ， 在象棋博弈中 幾乎沒有實用價值 。 ? 若想在指定時間內(nèi)將搜索深度加以提高，一方面需要 改進硬件與優(yōu)化程序代碼 ，提高單位時間內(nèi)搜索的節(jié)點數(shù)； ? 另一方面就需要像人類棋手一樣 有選擇性地進行搜索，即