【正文】 機(jī)器人研究所 迭代深化的 時(shí)間復(fù)雜度 ? 深度優(yōu)先的迭代深化搜索 D 層搜索的總結(jié)點(diǎn)數(shù)為 DBBBB DDD ???? ?? . . . . . .32 21所以深度優(yōu)先的迭代深化的時(shí)間復(fù)雜度為 )( DBO 值得關(guān)注的是，由于一系列剪枝算法的使用，使得此時(shí) 的平均分枝度可以數(shù)量級(jí)地減小。許多算法已經(jīng)做到 B = 2~5 東北大學(xué)人工智能與機(jī)器人研究所 啟發(fā)式 搜索 （ Heuristic search） ? 具體問(wèn)題的領(lǐng)域決定了初始狀態(tài) 、 算符和目標(biāo)狀態(tài) ，進(jìn)而決定了搜索空間 。 ? 因此 ， 具體問(wèn)題領(lǐng)域的信息常?？梢杂脕?lái)簡(jiǎn)化搜索 。此種信息叫做啟發(fā)信息 ， 而把利用啟發(fā)信息的搜索方法叫做啟發(fā)性搜索方法 。 ? 利用象棋的領(lǐng)域知識(shí) （ 啟發(fā)信息 ） 設(shè)計(jì)博弈搜索的啟發(fā)式算法或方法 ， 在著法排序中就有許多成功的應(yīng)用 。 ? 這里需要特別提及的則是平靜搜索 、 空著搜索和兌子搜索等 。 東北大學(xué)人工智能與機(jī)器人研究所 平靜搜索 （ Quiescent Search） ?αβ搜索使用的是給定深度搜索 ， 當(dāng)局面變化劇烈的時(shí)候 ， 雖然已經(jīng)達(dá)到搜索的最大深度 ， 但此時(shí)評(píng)估函數(shù)的返回值并不能準(zhǔn)確地表示當(dāng)前局面的情況 。 ?舉個(gè)簡(jiǎn)單的例子 ， 某個(gè)葉節(jié)點(diǎn)上紅車(chē)吃掉了黑炮 ， 但是下一步紅車(chē)會(huì)被黑方吃掉 。 如果在此葉節(jié)點(diǎn)調(diào)用評(píng)估函數(shù) ， 返回值肯定對(duì)紅方十分有利 ，但會(huì)引起判斷失誤 。 ?平靜搜索判斷局面 是否劇烈振蕩的準(zhǔn)則是走棋方是否還有吃子走法 ， 一直延伸到走棋方無(wú)吃子走法 ， 也就是相對(duì)平靜的局面 。 東北大學(xué)人工智能與機(jī)器人研究所 將軍延伸 （ Check Extension） ?是指 當(dāng)本方受到對(duì)方將軍時(shí)所進(jìn)行的擴(kuò)展 。 由于逃避對(duì)方對(duì)本帥攻擊的解將著法不多 ， 所以我們可以對(duì)當(dāng)前節(jié)點(diǎn)的搜索深度增加一層 ， 以更準(zhǔn)確地評(píng)估攻擊的危險(xiǎn)性 。 ?唯一著法延伸 （ One_Reply Extension） 。 當(dāng)本方受對(duì)方將軍的時(shí)候 ， 并且解將著法只有一步 ，這時(shí)候由于搜索量不大 ， 我們 在將軍延伸之外 ，還要對(duì)其進(jìn)行額外的延伸 。 東北大學(xué)人工智能與機(jī)器人研究所 啟發(fā)式 搜索 ? 兌子延伸 （ Recapture Extension） 。 搜索過(guò)程中 ， 如果出現(xiàn) A棋子吃掉對(duì)方的 B棋子 ， 隨即Ａ棋子又被對(duì)方吃掉 ，那么也要對(duì)這樣的局面進(jìn)行延伸 ， 以 保證對(duì)兌子進(jìn)行準(zhǔn)確的評(píng)估 。 ? 空著搜索 （ NullMove） 是在 1993年由 Chrilly Donninger最先提出的 。 NullMove的思想是 放棄本方的走棋權(quán)利 ，讓對(duì)方連續(xù)走棋 ， 如果得到的分值還大于原先的值 ， 說(shuō)明對(duì)方 沒(méi)有 “ 硬著 ” 可施 ， 于是在此分枝下搜索的意義已經(jīng)不大 ， 免于搜索 。 ? NullMove危險(xiǎn)性比較小 ， 實(shí)現(xiàn)較為簡(jiǎn)單 ， 剪枝效果明顯 ，現(xiàn) 已被棋類(lèi)博弈廣泛采用 。 東北大學(xué)人工智能與機(jī)器人研究所 負(fù)極大值算法 （ NegaMax algorithm） ? 博弈搜索是一種 “ 變性 ” 搜索 。 在偶數(shù)層進(jìn)行“ Max搜索 ” ， 而在奇數(shù)層進(jìn)行 “ Min搜索 ” 。這無(wú)疑給算法的實(shí)現(xiàn) 帶來(lái)一大堆麻煩 。 ? Knuth和 Moore充分利用了 “ 變性 ” 搜索的內(nèi)在規(guī)律，在 1975年提出了 意義重大的負(fù)極大值算法 。 ? 它的思想是：父節(jié)點(diǎn)的值是各子節(jié)點(diǎn)值的變號(hào)極大值，從而避免奇數(shù)層取極小而偶數(shù)層取極大的尷尬局面。 東北大學(xué)人工智能與機(jī)器人研究所 MAX MAX MIN 1 2 9 8 7 6 5 4 3 3 2 1 3 MaxMin搜索 （ 1） 由此產(chǎn)生最佳路徑和最佳著法 NegaMax NegaMax NegaMax搜索（ ）東北大學(xué)人工智能與機(jī)器人研究所 負(fù)極大值算法 （ NegaMax algorithm） ? 此時(shí)需要特別注意的則是 ，如果葉節(jié)點(diǎn)是紅方（走棋方）走棋，評(píng)估函數(shù)返回 RedValueBlackValue，如果是黑方（應(yīng)對(duì)方）走棋，則返回 BlackValue RedValue。 ? 另外，由于 負(fù)極大值計(jì)算等價(jià)于“ Min搜索” ，所以這里 只進(jìn)行 β剪枝 ，非常有利于編程實(shí)現(xiàn)和提高搜索速度。 ? ? ? ? ? ? ? ?? ?12m a x , , nF v F F Fv v v? ? ? ?東北大學(xué)人工智能與機(jī)器人研究所 開(kāi)局庫(kù) 設(shè)計(jì) （ Opening book） ?象棋博弈 三大階段 ：開(kāi)局 、 中局 、 殘局 。 ?雖然有時(shí)在中局就決出了勝負(fù)而沒(méi)有殘局 ，但所有的對(duì)局都必須有開(kāi)局 。 ?開(kāi)局是開(kāi)始的 10～ 20個(gè)回合 ， 對(duì)戰(zhàn)雙方各自展開(kāi)子力 ， 占據(jù)棋盤(pán)的有利位置 。 ?中國(guó)象棋講究的是快速出動(dòng)子力 ， 各棋子協(xié)調(diào)作戰(zhàn) ， 并且盡早占據(jù)中心位置 。 ?從開(kāi)始就進(jìn)行搜索 ， 容易犯戰(zhàn)略性錯(cuò)誤 。 ?借助成熟的開(kāi)局棋譜 ， 建立開(kāi)局庫(kù) 。 東北大學(xué)人工智能與機(jī)器人研究所 開(kāi)局庫(kù) 設(shè)計(jì) ? 開(kāi)局庫(kù)中通常存放了數(shù)以十萬(wàn)計(jì)甚至更多的棋局； ? 如何能夠快速準(zhǔn)確地搜索到對(duì)應(yīng)的棋局 成為開(kāi)局庫(kù)設(shè)計(jì)的 關(guān)鍵技術(shù)之一 。 ? 國(guó)際象棋的成功經(jīng)驗(yàn)表明，開(kāi)局庫(kù)最好是采用Zobrist哈希技術(shù) 加以實(shí)現(xiàn) ； 東北大學(xué)人工智能與機(jī)器人研究所 開(kāi)局庫(kù) ? 作為棋局的索引值，記載常用著法 ； ? 可以采用的著法， 常常不止一個(gè)，每個(gè)著法都對(duì)應(yīng)有輸贏統(tǒng)計(jì)比率、作者偏好權(quán)重 等，以便使用時(shí)選擇。 ? 一般還應(yīng)該具有 自學(xué)習(xí)的功能 ，將新的對(duì)弈結(jié)果補(bǔ)充進(jìn)來(lái)，并且不斷自行調(diào)整比率與權(quán)重值。 ???? kkhH321為異或算符， H 為 64位數(shù) 形成哈希數(shù)（值） 東北大學(xué)人工智能與機(jī)器人研究所 殘局庫(kù) （ Endgame database） ? 殘局 ——少數(shù)殘余子力所構(gòu)成并進(jìn)入決定勝負(fù)階段的對(duì)峙局面 。 ? 目標(biāo) ——優(yōu)勢(shì)求勝 ， 下風(fēng)謀和 ， 均勢(shì)求機(jī) 。 ? 在殘局階段 ， 象棋大師的知識(shí) 、 人類(lèi)的直覺(jué)與靈感往往能夠戰(zhàn)勝程序的搜索能力 。 ? 一般計(jì)算機(jī)在殘局階段是不占優(yōu)勢(shì)的 。 ? 在國(guó)際象棋中通常使用 回溯法 （ Retrograde algorithm）構(gòu)造殘局庫(kù) 。 ? 殘局階段對(duì)于 象棋規(guī)則 的考慮應(yīng)該給與特別的關(guān)注 。 ? 就國(guó)內(nèi)而言 ， 中國(guó)象棋殘局庫(kù)的開(kāi)發(fā)基本還是空白 。 東北大學(xué)人工智能與機(jī)器人研究所 系統(tǒng)開(kāi)發(fā)與實(shí)現(xiàn) （ System development and realization） ? 象棋博弈軟件的程序規(guī)模都比較龐大 ， 難以從頭做起 。 ? 最為現(xiàn)實(shí)的開(kāi)發(fā)方案：借助一些國(guó)象和中象的 開(kāi)源軟件 ： ? (國(guó)象 crafty網(wǎng)站 ) ? (國(guó)象 Fruit網(wǎng)站 ) ? (中象象眼網(wǎng)站 ) ? 在已有的人機(jī)界面和搜索引擎基礎(chǔ)上不斷消化 、 改造 、完善和豐富 ， 從而形成具有自己特色和知識(shí)產(chǎn)權(quán)的博弈軟件 。 東北大學(xué)人工智能與機(jī)器人研究所 系統(tǒng)開(kāi)發(fā)與實(shí)現(xiàn) ? 各種矩陣的一維數(shù)組實(shí)現(xiàn) 。因?yàn)樵诔绦蜻\(yùn)行過(guò)程中，二維數(shù)組的計(jì)算要比一維數(shù)組更為耗時(shí)。 ? 由于博弈樹(shù)展開(kāi)的規(guī)模十分龐大，一般中局搜索的節(jié)點(diǎn)數(shù)可達(dá)千萬(wàn)個(gè)，因此 節(jié)點(diǎn)信息的存儲(chǔ)內(nèi)容與方式便要非常講究 。 ? 運(yùn)行時(shí)間的矛盾更為突出 ，它是影響搜索深度和質(zhì)量的瓶頸。 如何以空間換時(shí)間 ，是各種算法研究的焦點(diǎn)問(wèn)題。 ? 探討人類(lèi)博弈的認(rèn)知過(guò)程， 結(jié)合象棋對(duì)弈過(guò)程中出現(xiàn)的實(shí)際問(wèn)題，研究新型的啟發(fā)式搜索算法 ，將是機(jī)器博弈獲得升華的不竭動(dòng)力。 東北大學(xué)人工智能與機(jī)器人研究所 系統(tǒng)測(cè)試與參數(shù)優(yōu)化 ? 系統(tǒng)測(cè)試的重要性是不言而喻的 。 除了排除一般的錯(cuò)誤 ， 更重要的是 參數(shù)的優(yōu)化與棋力的提高 。 ? 在評(píng)估函數(shù)中就有成百上千個(gè)參數(shù) ， 都需要在調(diào)試和實(shí)際對(duì)弈過(guò)程中不斷改進(jìn) 。 ? 測(cè)試的最好辦法是通過(guò) 對(duì)戰(zhàn)平臺(tái) 。 ? 為了參數(shù)優(yōu)化 ， 需要相當(dāng)數(shù)量的測(cè)試棋局 。 由于 事先知道棋局正解 （ 最佳著法 ） ， 檢查被測(cè)軟件是否找到了正解 ， 研究為什么出現(xiàn)了偏離 。 ? 一般出現(xiàn)偏離原因或是在評(píng)估中 缺少了什么 ， 或是權(quán)值給的不好 ， 常常還是 盲點(diǎn) ,找不到原因 。 ? 參數(shù)優(yōu)化是一個(gè)非常需要耐心 、 又非常需要象棋專(zhuān)業(yè)知識(shí)的細(xì)活 ， 聘請(qǐng)象棋高手和象棋大師參加工作是必不可少的 。 東北大學(xué)人工智能與機(jī)器人研究所 The end Thank you