版權(quán)說明:本文檔由用戶提供并上傳,收益歸屬內(nèi)容提供方,若內(nèi)容存在侵權(quán),請(qǐng)進(jìn)行舉報(bào)或認(rèn)領(lǐng)
文檔簡(jiǎn)介
1、<p><b> 摘 要</b></p><p> 棋類博弈是人工智能的重要研究主題之一。而在圍棋方面,由于圍棋的搜索空間太大、計(jì)算機(jī)難于處理模糊概念且難于設(shè)計(jì)學(xué)習(xí)算法,目前最優(yōu)秀的圍棋程序的水平還處于業(yè)余低段水平。計(jì)算機(jī)圍棋被認(rèn)為是在繼國(guó)際象棋之后人工智能領(lǐng)域中最困難的新挑戰(zhàn)之一。圍棋是檢驗(yàn)人工智能發(fā)展水平的良好環(huán)境,如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。所以
2、計(jì)算機(jī)圍棋研究具有重要的理論意義和實(shí)用價(jià)值。</p><p> 本論文將介紹如何基于UCT算法設(shè)計(jì)和實(shí)現(xiàn)圍棋引擎。第一部分介紹了計(jì)算機(jī)圍棋研究背景及意義、研究狀況和關(guān)鍵技術(shù),包括Monte Carlo方法和UCT算法的理論。第二部分在圍棋引擎總體概述的基礎(chǔ)上說明其總體功能模塊,并對(duì)各個(gè)子功能模塊進(jìn)行描述,重點(diǎn)講解了交替下子的流程以及棋步產(chǎn)生模塊。第三部分闡明了基于UCT算法的圍棋引擎的設(shè)計(jì),先設(shè)計(jì)圍棋引擎的總體
3、流程,再依次說明UCT算法流程、棋步合法性的判斷等模塊的具體設(shè)計(jì)流程。第四部分探討了基于UCT算法的圍棋引擎的實(shí)現(xiàn),在分析圍棋引擎核心模塊UCT算法實(shí)現(xiàn)的基礎(chǔ)上,詳細(xì)說明了候選步的產(chǎn)生及管理機(jī)制,節(jié)點(diǎn)的UCT選擇,展開節(jié)點(diǎn)和棋局模擬,分析指出不同的因素和策略對(duì)計(jì)算機(jī)圍棋引擎的影響,其中棋局模擬的著手庫(kù)模式匹配和其它圍棋知識(shí)對(duì)加強(qiáng)程序棋力有至關(guān)重要的作用。最后對(duì)主要工作做了總結(jié),提出進(jìn)一步的發(fā)展目標(biāo)。</p><p&g
4、t; 基于上述內(nèi)容,實(shí)現(xiàn)了一個(gè)基于UCT算法的圍棋引擎Tao Go,支持GMP、GTP圍棋協(xié)議,SGF文件調(diào)試輸出和統(tǒng)計(jì)UCT模擬棋局的數(shù)據(jù),目前能正常與圍棋客戶端進(jìn)行通信,實(shí)現(xiàn)人機(jī)和機(jī)機(jī)對(duì)弈。</p><p> 關(guān)鍵詞:人工智能 計(jì)算機(jī)圍棋 UCT算法 模式匹配</p><p><b> 目 錄</b></p><p>&l
5、t;b> 1 緒論1</b></p><p> 1.1 研究背景及意義1</p><p> 1.2 研究狀況1</p><p> 1.3 關(guān)鍵技術(shù)2</p><p> 1.3.1 Monte Carlo方法2</p><p> 1.3.2 UCT算法2</p>&
6、lt;p> 2 基于UCT的圍棋引擎的概述5</p><p> 2.1 圍棋引擎的總體概述5</p><p> 2.2 圍棋引擎的總體功能模塊5</p><p> 2.3 交替下子流程模塊7</p><p> 2.4 棋步產(chǎn)生(UCT)模塊8</p><p> 2.5 棋步合法性判斷模塊9
7、</p><p> 2.6 算氣模塊9</p><p> 2.7 更新棋盤(提子)模塊10</p><p> 2.8 勝負(fù)計(jì)算模塊10</p><p> 3 基于UCT的圍棋引擎的設(shè)計(jì)11</p><p> 3.1 圍棋引擎總體流程設(shè)計(jì)11</p><p> 3.2 UCT
8、算法具體流程設(shè)計(jì)12</p><p> 3.3 棋步合法性判斷模塊設(shè)計(jì)14</p><p> 3.4 算氣模塊設(shè)計(jì)16</p><p> 3.5 更新棋盤(提子)模塊設(shè)計(jì)17</p><p> 3.6 勝負(fù)計(jì)算模塊設(shè)計(jì)18</p><p> 4 基于UCT的圍棋引擎的實(shí)現(xiàn)20</p>
9、<p> 4.1 軟硬件開發(fā)環(huán)境20</p><p> 4.2 圍棋引擎的數(shù)據(jù)結(jié)構(gòu)20</p><p> 4.2.1 棋局?jǐn)?shù)據(jù)20</p><p> 4.2.2 UCT Tree數(shù)據(jù)21</p><p> 4.3 圍棋引擎的UCT算法實(shí)現(xiàn)21</p><p> 4.3.1 UCT算法的
10、核心實(shí)現(xiàn)21</p><p> 4.3.2 候選步的產(chǎn)生方式及管理機(jī)制23</p><p> 4.3.3 選擇節(jié)點(diǎn)(UCT選擇)25</p><p> 4.3.4 展開節(jié)點(diǎn)27</p><p> 4.3.5 棋局模擬29</p><p> 4.4 圍棋引擎運(yùn)行效果36</p><
11、;p> 4.4.1 圍棋協(xié)議對(duì)弈測(cè)試36</p><p> 4.4.2 調(diào)試模式的SGF文件37</p><p> 4.4.3 UCT模擬棋局?jǐn)?shù)據(jù)統(tǒng)計(jì)38</p><p> 5 工作總結(jié)及未來展望39</p><p> 5.1 工作總結(jié)39</p><p> 5.2 未來展望39</
12、p><p><b> 致謝40</b></p><p><b> 參考文獻(xiàn)41</b></p><p><b> 英文摘要43</b></p><p><b> 1 緒論</b></p><p> 1.1 研究背景及意義
13、</p><p> 博弈是人工智能的重要研究主題,人工智能的發(fā)展在很大程度上得益于博弈研究的發(fā)展。1997年著名的深藍(lán)計(jì)算機(jī)戰(zhàn)勝國(guó)際象棋世界冠軍卡斯帕羅夫成為轟動(dòng)一時(shí)的新聞事件[l]??梢哉f,作為博弈研究的主要內(nèi)容之一,棋類博弈得到了滿意的解決,唯一的例外的是圍棋,目前最優(yōu)秀的圍棋程序還處于業(yè)余低段水平。</p><p> 圍棋是博弈的一種,屬雙人零和博弈[2]。它起源于3000多年前
14、的中國(guó),充分體現(xiàn)了東方人的智慧,盛行于中日韓,逐漸在歐美流行。它比國(guó)際象棋復(fù)雜得多,正因?yàn)槿绱耍芏嗳斯ぶ悄軐W(xué)家、心理學(xué)家和數(shù)學(xué)家也投入到了計(jì)算機(jī)圍棋研究領(lǐng)域。計(jì)算機(jī)圍棋這個(gè)名稱來自于Computer Go的直譯,略顯生硬。簡(jiǎn)單地說,計(jì)算機(jī)圍棋就是結(jié)合人工智能技術(shù)教計(jì)算機(jī)下圍棋,以達(dá)到與人類棋手相抗衡的目的。</p><p> 由于圍棋的搜索空間太大、計(jì)算機(jī)難于處理模糊概念且難于設(shè)計(jì)學(xué)習(xí)算法,造成了計(jì)算機(jī)圍棋程
15、序的棋力難于提高。圍棋是檢驗(yàn)人工智能發(fā)展水平的良好環(huán)境,如何提高圍棋程序的棋力是人工智能領(lǐng)域的一大難題。同時(shí),開發(fā)出與人類棋手水平相當(dāng)?shù)膰宄绦蛞灿兄趯?duì)人類認(rèn)知能力的理解。所以計(jì)算機(jī)圍棋研究具有重要的理論意義和實(shí)用價(jià)值。</p><p><b> 1.2 研究狀況</b></p><p> 計(jì)算機(jī)圍棋自Zobrist在1970年設(shè)計(jì)出第一個(gè)可與人對(duì)弈的程序以來[
16、3],至今已有約四十年的歷史。由于圍棋本身的特質(zhì),使得計(jì)算機(jī)圍棋在繼西洋棋、象棋之后,成為人工智能中一個(gè)相當(dāng)引人注目的新挑戰(zhàn)。</p><p> 然而計(jì)算機(jī)圍棋的難點(diǎn)之一,便在于缺乏良好的局面評(píng)估函數(shù)[4],使其不能跟國(guó)際象棋一樣,運(yùn)用設(shè)計(jì)良好的局面評(píng)估函數(shù)、搜尋樹以及優(yōu)秀的剪枝法,即可獲得不錯(cuò)的棋力;計(jì)算機(jī)圍棋大多借鑒一些經(jīng)驗(yàn)法則,以靜態(tài)的評(píng)估為主,而動(dòng)態(tài)的搜尋則僅用于局部的、目標(biāo)明確的棋串攻殺,較少的全局搜
17、尋。因此,人類的經(jīng)驗(yàn)如何應(yīng)運(yùn)用于計(jì)算機(jī)圍棋,就成了設(shè)計(jì)的重點(diǎn)。</p><p> 自2003年起,Bouzy試圖打破這種情況[5]。他運(yùn)用蒙特卡羅(Monte Carlo)方法作為評(píng)估函數(shù),并且試圖運(yùn)用這一評(píng)估函數(shù),作全局性的搜索,然而在棋力上始終沒有大的突破。直到2006年,同樣使用蒙特卡羅方法的程序Crazy Stone[6~7],才在杜林舉行的第11屆計(jì)算機(jī)奧林匹克的九路圍棋項(xiàng)目中奪得金牌。雖然如此,Cr
18、azy Stone僅在19路圍棋項(xiàng)目中奪得第五名,仍未撼動(dòng)以人類思維為主的圍棋程序GNU Go在19路圍棋的地位。</p><p> 然而,隨著基于蒙特卡羅的UCT(Upper Confidence bounds applied to Trees) 搜索方法的出現(xiàn),以UCT為基礎(chǔ)的圍棋程序MoGo[8~10]也逐漸在一些較非正式的比賽中嶄露頭角。2007年6月,第12屆計(jì)算機(jī)奧林匹克于阿姆斯特丹舉行,上屆冠軍G
19、NU Go、亞軍GO Intellect以及前文介紹過的Crazy Stone等程序均有參賽,MoGo在強(qiáng)敵環(huán)伺之下,以全勝戰(zhàn)績(jī)奪得了19路圍棋項(xiàng)目的金牌,Crazy Stone也拿到了第二名,GNU Go退居第三。這象征UCT的成功,也代表一個(gè)嶄新的局面的到來。</p><p><b> 1.3 關(guān)鍵技術(shù)</b></p><p> 1.3.1 Monte Car
20、lo方法</p><p> Monte Carlo[11~12]方法主要理論基礎(chǔ)是依據(jù)大數(shù)定理,在隨機(jī)取樣的情況下,可以獲得有誤差的評(píng)估值,取樣的數(shù)量越多,誤差將越小,評(píng)估值將越準(zhǔn)確。</p><p> 將Monte Carlo方法應(yīng)用于圍棋[13],其核心的思想是,在于通過統(tǒng)計(jì)許多模擬棋局的結(jié)果,進(jìn)行局面的優(yōu)劣判斷。亦即將蒙特卡羅方法作為局面評(píng)估函數(shù),以決定著手的好壞。</p&
21、gt;<p> 其中,所謂的模擬棋局,指的是對(duì)某一目標(biāo)盤面,由電腦隨機(jī)落子,直到終盤而可以判定勝負(fù)為止。在隨機(jī)落子時(shí),除了基本的圍棋規(guī)則外,只有一個(gè)限制:不得自填眼位,這個(gè)限制是為了防止棋局無(wú)法結(jié)束而設(shè)定的。模擬棋局的結(jié)果,與目前常見的只判斷黑勝或白勝不同,而是會(huì)判斷輸贏的目數(shù),在決定著手優(yōu)劣時(shí),則是統(tǒng)計(jì)此著手下所有模擬棋局平均的輸贏目數(shù)來決定的。</p><p> 1.3.2 UCT算法<
22、;/p><p> UCT又名UCB for Tree Search,是UCB(Upper Confidence Bound)在Tree Search上的應(yīng)用。而UCB本來是為了解決吃角子老虎機(jī)問題(Bandit Problem)而產(chǎn)生的。所謂的吃角子老虎機(jī)問題,簡(jiǎn)述如下:目前有若干臺(tái)吃角子老虎機(jī),每臺(tái)機(jī)器可以投錢并拉動(dòng)操縱桿,此時(shí)會(huì)得到收益(reward),投錢、拉桿、得到收益的過程,稱之為一個(gè)Play。每臺(tái)吃角子
23、老虎機(jī)有不同的收益率,倘若玩家想要在若干次的Play里獲得最大總收益,那么該怎么做?</p><p> 一般來說,玩家會(huì)開始動(dòng)手玩,并且依照目前積累的經(jīng)驗(yàn)來決定下一次的Play要選擇哪一臺(tái)機(jī)器,這稱之為開發(fā)(exploitation)。相對(duì)地,如果玩家不斷地依照目前所獲得的經(jīng)驗(yàn)來決定,而不試圖嘗試其它的其他的機(jī)器,則可能會(huì)忽略收益率更高的機(jī)器,因此適度地嘗試其他機(jī)器是必須的,這稱之為探險(xiǎn)(exploration
24、)。如何在開發(fā)與探險(xiǎn)之間保持平衡,就是UCB試圖解決的ExE(exploitation vs. exploration)問題。</p><p> UCB根據(jù)目前獲得的信息,配合上一個(gè)調(diào)整值,試圖在開發(fā)與探險(xiǎn)間保持平衡。大致上來說,每一次Play時(shí),UCB會(huì)根據(jù)每一臺(tái)機(jī)器目前的平均收益值(亦即其到目前為止的表現(xiàn)),加上一個(gè)額外的參數(shù),得出本次Play此臺(tái)機(jī)器的UCB值,然后根據(jù)此值,挑選出擁有最大UCB值的機(jī)器,
25、作為本次Play所要選擇的機(jī)器。其中,所謂額外參數(shù),會(huì)隨每一臺(tái)機(jī)器被選擇的次數(shù)增加而相對(duì)減少,其目的在于讓選擇機(jī)器時(shí),不過分拘泥于舊有的表現(xiàn),而可以適度地探索其他機(jī)器。UCB公式表示如下(也稱為UCB1)[14]:</p><p> 錯(cuò)誤!未找到引用源。 (3)</p><p> 錯(cuò)誤!未找到引用源。是第j臺(tái)機(jī)器到目前為止的平均收益, 錯(cuò)誤!未找到引用源。是第j臺(tái)機(jī)器被測(cè)試的次數(shù),n是
26、所有機(jī)器目前被測(cè)試的總次數(shù)。讓公式(3)的值最大的機(jī)器將是下一個(gè)被選擇的機(jī)器。前項(xiàng)即為此臺(tái)機(jī)器的過去表現(xiàn),后項(xiàng)則是調(diào)整參數(shù)。</p><p> 而UCB1-TUNED是相對(duì)于UCB1實(shí)驗(yàn)較佳的配置策略[14]。UCB1-TUNED的公式如下:</p><p> 錯(cuò)誤!未找到引用源。 (4)</p><p> 錯(cuò)誤!未找到引用源。 (5)</p
27、><p> 讓公式(5)的值最大的機(jī)器將是下一個(gè)被告選擇來測(cè)試的機(jī)器。</p><p> UCT(UCB for Tree Search)其實(shí)就是把UCB1或UCB1-TUNED(統(tǒng)稱為UCB)等公式運(yùn)用于Tree Search上的一個(gè)方法[14]。以概念而言,UCT把每一個(gè)節(jié)點(diǎn)都當(dāng)作是一個(gè)吃角子老虎機(jī)問題,而此節(jié)點(diǎn)的每一個(gè)分支,都是一臺(tái)吃角子老虎的機(jī)器。選擇分支,就會(huì)獲得相應(yīng)的收益。&l
28、t;/p><p> Tree Search開始時(shí),UCT會(huì)建立一棵Tree,然后:</p><p><b> 從根節(jié)點(diǎn)開始</b></p><p> 利用UCB公式計(jì)算每個(gè)子節(jié)點(diǎn)的UCB值,選擇UCB值最高的子節(jié)點(diǎn)</p><p> 若此子節(jié)點(diǎn)并非葉節(jié)點(diǎn)(從未拜訪過的節(jié)點(diǎn)),則由此節(jié)點(diǎn)開始,重復(fù)(2)</p&g
29、t;<p> 直到遇到葉節(jié)點(diǎn),則計(jì)算葉節(jié)點(diǎn)的收益值,并依此更新根節(jié)點(diǎn)到此一節(jié)點(diǎn)路 徑上所有節(jié)點(diǎn)的收益值</p><p> 由(1)開始重復(fù),直到時(shí)間結(jié)束,或達(dá)到某一預(yù)設(shè)次數(shù)</p><p> 由根節(jié)點(diǎn)的所有子節(jié)點(diǎn)中,選擇平均收益值最高者,作為最佳節(jié)點(diǎn)</p><p> 此一節(jié)點(diǎn),就是UCT的結(jié)果。</p><p&
30、gt; 2 基于UCT的圍棋引擎的概述</p><p> 2.1 圍棋引擎的總體概述</p><p> 計(jì)算機(jī)圍棋程序通常也可稱為計(jì)算機(jī)圍棋引擎,具體表現(xiàn)為引擎本身沒有也不需要實(shí)現(xiàn)圖形圍棋界面(這通常是交由圍棋客戶端來做的),而是通過特定的圍棋協(xié)議與引擎外部進(jìn)行通信,如圖2.1所示。這樣的好處是邏輯簡(jiǎn)單,功能明確,只需要關(guān)注圍棋引擎的核心部分,即圍棋引擎是如何去思考的,并嘗試產(chǎn)生最優(yōu)
31、棋步。如果不去考慮圍棋引擎具體的思考過程,它表現(xiàn)出來的僅僅是它思考的最終結(jié)果,一個(gè)棋步而已。除此之外,圍棋引擎所做的工作就是實(shí)現(xiàn)對(duì)弈雙方交替落子的過程,同時(shí)根據(jù)棋規(guī)進(jìn)行相應(yīng)的更新棋盤處理,并在棋局結(jié)束時(shí)計(jì)算勝負(fù)。</p><p> 事實(shí)上,圍棋引擎與圍棋客戶端的關(guān)系可以拿IDE和編譯器的關(guān)系來類比。在編譯源文件的時(shí)候,首先需要設(shè)置使用哪個(gè)編譯器和相應(yīng)的編譯參數(shù),然后IDE會(huì)調(diào)用編譯器去編譯源文件,接著編譯器執(zhí)行
32、編譯過程,最后編譯器返回編譯結(jié)果給IDE,IDE則顯示編譯結(jié)果給用戶查看。而在圍棋對(duì)弈的時(shí)候,首先需要設(shè)置使用哪個(gè)圍棋引擎和圍棋協(xié)議參數(shù),然后圍棋客戶端會(huì)通過圍棋協(xié)議告訴圍棋引擎為黑棋(或白棋)產(chǎn)生一個(gè)棋步,接著圍棋引擎進(jìn)行思考,最后圍棋引擎返回思考得到的棋步給圍棋客戶端,圍棋客戶端則在棋盤上顯示該棋步給圍棋用戶查看。</p><p> 圖2.1 圍棋引擎與圍棋客戶端的通信</p><p&g
33、t; 2.2 圍棋引擎的總體功能模塊</p><p> 圍棋引擎Tao Go的總體功能模塊圖如圖2.2所示。其中交替下子流程功能模塊是圍棋引擎的總體流程。如何基于UCT產(chǎn)生棋步是圍棋引擎的核心功能模塊,在棋步產(chǎn)生(UCT)功能模塊下面的五個(gè)子功能模塊中除了候選步產(chǎn)生及管理子模塊是起輔助作用以外,其它四個(gè)子功能模塊實(shí)際上是一個(gè)有機(jī)聯(lián)系的整體,構(gòu)成圍棋引擎的UCT算法流程。棋步合法性判斷模塊是根據(jù)圍棋規(guī)則來判斷一
34、個(gè)棋步是否合法。更新棋盤(提子)模塊是檢查是否有吃子,有則提掉,并記錄可能的打劫位置。勝負(fù)計(jì)算模塊是在棋局結(jié)束時(shí)根據(jù)圍棋規(guī)則來計(jì)算勝負(fù)。算氣模塊是計(jì)算一個(gè)棋串的氣數(shù)。</p><p> 圖2.2 圍棋引擎總體功能模塊</p><p> 如圖2.3,是圍棋引擎各個(gè)模塊之間的關(guān)系??梢钥吹?,圍棋引擎交替下子流程模塊對(duì)外負(fù)責(zé)與圍棋客戶端進(jìn)行通信,然后調(diào)用引擎內(nèi)部其它模塊進(jìn)行處理。例如圍棋客戶
35、端輸入了對(duì)手棋步,圍棋引擎交替下子流程模塊會(huì)調(diào)用棋步合法性判斷模塊對(duì)棋步進(jìn)行判斷,如果合法則更新棋盤,然后調(diào)用棋步產(chǎn)生(UCT)模塊產(chǎn)生棋步,最后輸出棋步返回給圍棋客戶端。圍棋引擎交替下子流程模塊在棋局開始時(shí),還會(huì)進(jìn)行一些初始化工作,主要是商定圍棋規(guī)則,在棋局結(jié)束時(shí)則計(jì)算對(duì)弈雙方的勝負(fù)。棋步產(chǎn)生(UCT)模塊在產(chǎn)生棋步過程中會(huì)執(zhí)行多次模擬棋局,正式對(duì)局中所需要用到的功能模塊同樣會(huì)被調(diào)用,包括棋步合法性判斷模塊、更新棋盤(提子)模塊和勝負(fù)
36、計(jì)算模塊。 算氣模塊作為最基礎(chǔ)的模塊,為各個(gè)模塊提供依據(jù),服務(wù)的上層的模塊包括棋步產(chǎn)生(UCT)模塊、棋步合法性判斷模塊和更新棋盤(提子)模塊。</p><p> 圖2.3 圍棋引擎模塊間的關(guān)系</p><p> 2.3 交替下子流程模塊</p><p> 交替下子流程模塊展示了圍棋引擎的基本流程活動(dòng),如圖2.4是交替下子流程模塊的活動(dòng)圖?;顒?dòng)一開始是進(jìn)行初始
37、化引擎,主要是商定圍棋規(guī)則和初始化圍棋引擎內(nèi)部的一些參數(shù)和數(shù)據(jù)。然后進(jìn)入對(duì)弈雙方交替下子的過程,直到棋局結(jié)束。交替下子時(shí),如果是對(duì)手下子,則從圍棋引擎外部得到對(duì)手棋步,否則輪到引擎下子,此時(shí)引擎的棋步產(chǎn)生模塊會(huì)產(chǎn)生合法棋步,然后輸出產(chǎn)生的棋步到圍棋引擎外部。每當(dāng)有下子的動(dòng)作發(fā)生,則進(jìn)行更新棋盤,對(duì)棋局改變的狀態(tài)進(jìn)行相應(yīng)的處理。當(dāng)棋局結(jié)束時(shí),根據(jù)圍棋規(guī)則計(jì)算雙方的勝負(fù),如果對(duì)弈雙方對(duì)計(jì)算勝負(fù)的結(jié)果沒有爭(zhēng)議,棋局正式結(jié)束,否則繼續(xù)對(duì)弈。有一
38、點(diǎn)需要指出的是,在這里沒有明顯指出得到對(duì)手棋步是否要考慮該棋步的合法性。棋步的合法性通常圍棋引擎外部的圍棋客戶端也會(huì)判斷保證,不過在設(shè)計(jì)時(shí)應(yīng)該考慮加入對(duì)對(duì)手棋步的合法性判斷和相應(yīng)的錯(cuò)誤處理,以保證邏輯的完整性,使得棋局能夠順利進(jìn)行。</p><p> 圖2.4 交替下子流程的活動(dòng)圖</p><p> 2.4 棋步產(chǎn)生(UCT)模塊</p><p> 棋步產(chǎn)生(
39、UCT)模塊使用UCT算法來產(chǎn)生棋步,是整個(gè)圍棋引擎的核心功能模塊。前面1.3.2小節(jié)已經(jīng)介紹了UCT算法的理論,下面來說明UCT算法究竟是如何應(yīng)用在圍棋上的。</p><p> UCT使用在圍棋上,主要的概念,就是每個(gè)節(jié)點(diǎn)代表一個(gè)盤面,此節(jié)點(diǎn)的分支代表此盤面下的合法著手,每個(gè)分支聯(lián)結(jié)到的子節(jié)點(diǎn),就是原盤面加上分支代表的著手后,所產(chǎn)生的新盤面。一般而言,目前盤面為根節(jié)點(diǎn),根節(jié)點(diǎn)的分支代表目前盤面下的合法著手,根
40、節(jié)點(diǎn)的子節(jié)點(diǎn)代表根節(jié)點(diǎn)的盤面加上分支代表的著手后所形成的新盤面,如圖2.5所示。</p><p> 圖2.5 UCT Tree的概念表示,其中每個(gè)節(jié)點(diǎn)均記錄訪問次數(shù),勝利次數(shù),形成此節(jié)點(diǎn)的著手,著手顏色等信息</p><p> 此外,UCB公式的收益值,如前1.3.1小節(jié)所述,就是依照Monte Carlo方法的概念,用模擬棋局的結(jié)果來決定。上面1.3.2小節(jié)中UCT 算法第4個(gè)步驟中
41、,計(jì)算機(jī)收益值,在此應(yīng)該改為執(zhí)行模擬棋局。所謂的模擬棋局,就是給定一個(gè)盤面(在此給的是葉節(jié)點(diǎn)所代表的盤面),由計(jì)算機(jī)接手落子,直到終局,然后判定并回傳勝負(fù)結(jié)果(黑勝或白勝)。在此要注意的是,UCT會(huì)據(jù)此結(jié)果,更新葉節(jié)點(diǎn)到根節(jié)點(diǎn)上所有節(jié)點(diǎn)的收益值,也就是說,一個(gè)節(jié)點(diǎn)會(huì)概括承受所有子節(jié)點(diǎn)模擬棋局的結(jié)果。對(duì)于任一節(jié)點(diǎn),其收益值為:此一節(jié)點(diǎn)的模擬棋局勝利數(shù)/此節(jié)點(diǎn)被訪問的次數(shù),亦即其勝率。上式中所謂的勝利數(shù),指的是指向此節(jié)點(diǎn)的分支所代表的顏色(
42、黑棋或白棋)在模擬時(shí)的勝利次數(shù)。</p><p> UCT Tree搜索流程總結(jié)如下:UCT算法使用極小極大游戲樹(minimax game tree),搭配節(jié)點(diǎn)選擇公式(UCB公式),選擇樹節(jié)點(diǎn),展開要測(cè)試的節(jié)點(diǎn),然后使用Monte Carlo方法執(zhí)行模擬棋局,最后將模擬棋局的結(jié)果回饋更新。流程示意圖如圖2.6所示。</p><p> 圖2.6 UCT Tree搜索流程示意圖<
43、/p><p> 2.5 棋步合法性判斷模塊</p><p> 一個(gè)棋步是否合法,是根據(jù)圍棋規(guī)則來確定的,規(guī)則如下:</p><p> pass(也稱虛著)是合法的棋步,允許任何一方放棄下子權(quán)而使用虛著。黑白雙方輪流在空點(diǎn)上落子,即不能在非空棋點(diǎn)上落子。</p><p> 禁著點(diǎn)。棋盤上的任何一點(diǎn),如某方下子后,該子立即呈無(wú)氣狀態(tài),同時(shí)又不
44、能提取對(duì)方的棋子。這個(gè)點(diǎn)叫做禁著點(diǎn)。</p><p> 禁止全局同形。著子后不得使對(duì)方重復(fù)面臨曾出現(xiàn)過的局面。其中打劫是全局同形最基本的情況。</p><p><b> 2.6 算氣模塊</b></p><p> 當(dāng)任何一方落子后,除了虛著以外,都有可能把對(duì)方的棋子提掉,這個(gè)時(shí)候就要計(jì)算與所落子相鄰的所有對(duì)方棋串的氣數(shù)。事實(shí)上,在判斷棋步
45、的合法性時(shí)也往往需要計(jì)算雙方棋串的氣數(shù)。計(jì)算棋串的氣數(shù)主要采用標(biāo)記法,從棋串的某一個(gè)棋子開始,先標(biāo)記該棋子已訪問過,然后對(duì)于該棋子四個(gè)相鄰的棋點(diǎn),如果相鄰棋點(diǎn)是空點(diǎn),則棋串氣數(shù)加1;如果相鄰棋點(diǎn)上是對(duì)方的棋子,則無(wú)需對(duì)該方向上的相鄰棋點(diǎn)繼續(xù)進(jìn)行探索;如果相鄰棋點(diǎn)上是己方棋子,則對(duì)該相鄰棋點(diǎn)上的己方棋子進(jìn)行同樣的操作,直至計(jì)算完整個(gè)棋串的氣數(shù)。</p><p> 2.7 更新棋盤(提子)模塊</p>
46、<p> 更新棋盤時(shí),主要是利用計(jì)算棋串氣數(shù)的功能檢查是否有提子, 有提子時(shí)將對(duì)方的棋串提掉,即清空對(duì)應(yīng)棋串位置,并記錄可能導(dǎo)致劫爭(zhēng)的位置。</p><p> 2.8 勝負(fù)計(jì)算模塊</p><p> 著子完畢的棋局,采用數(shù)子法計(jì)算勝負(fù)。將雙方死子清理出盤外后,對(duì)任意一方的活棋和活棋圍住的點(diǎn)以子為單位進(jìn)行計(jì)數(shù)。 雙方活棋之間的空點(diǎn)各得一半。 棋盤總點(diǎn)數(shù)的一半點(diǎn)為歸本數(shù)。一方
47、總得點(diǎn)數(shù)超過此數(shù)為勝,等于此數(shù)為和,小于此數(shù)為負(fù)。如果有貼子,則要按照相關(guān)的規(guī)定進(jìn)行計(jì)算。</p><p> 3 基于UCT的圍棋引擎的設(shè)計(jì)</p><p> 3.1 圍棋引擎總體流程設(shè)計(jì)</p><p> 圖3.1 圍棋引擎總體流程</p><p> 如圖3.1所示,圍棋引擎的總體流程實(shí)際就是模擬對(duì)弈雙方交替落子的過程。當(dāng)輪到對(duì)手落
48、子時(shí),圍棋引擎通過圍棋協(xié)議從引擎外部得到對(duì)手的棋步。否則圍棋引擎使用UCT算法產(chǎn)生棋步,并通過圍棋協(xié)議輸出產(chǎn)生的棋步到引擎外部。不管是得到對(duì)手棋步之后或者是輸出產(chǎn)生棋步之前,都必須檢查棋步的合法性,如不合法則進(jìn)行相應(yīng)的出錯(cuò)處理。如果檢查的棋步是合法的,接下來就根據(jù)圍棋規(guī)則做出正確的處理。如果合法棋步是pass時(shí),則將pass數(shù)加1;否則將pass置為0。更新棋盤時(shí),對(duì)于非pass合法棋步,則提取可能的死子并記錄可能的打劫位置,對(duì)于pas
49、s棋步則不做任何改變。最后,棋步數(shù)加1,然后回去判斷pass是否大于等于2,如果是說明雙方都pass,棋局結(jié)束,否則雙方繼續(xù)落子。</p><p> 3.2 UCT算法具體流程設(shè)計(jì)</p><p> UCT算法的流程大致分為四個(gè)部分:</p><p> 第一部分是選擇節(jié)點(diǎn),在游戲樹中選擇子節(jié)點(diǎn)。</p><p> 第二部分是展開節(jié)點(diǎn),
50、產(chǎn)生新的子節(jié)點(diǎn)。</p><p> 第三部分是棋局模擬,執(zhí)行模擬的棋局。</p><p> 第四部分是回饋更新,將模擬棋局的結(jié)果以回溯方式更新游戲樹節(jié)點(diǎn)的信息。</p><p> 在本論文中,將針對(duì)該流程前三部分進(jìn)行詳細(xì)說明。</p><p> 圍棋引擎Tao Go使用的UCT流程如下,其示意圖如圖3.2所示。</p>
51、<p><b> 選擇節(jié)點(diǎn)</b></p><p> 若有未被訪問過的子節(jié)點(diǎn),則優(yōu)先以隨機(jī)方式選擇其中一個(gè)子節(jié)點(diǎn)落子然后執(zhí)行模擬棋局(轉(zhuǎn)到(3)),否則繼續(xù)使用節(jié)點(diǎn)選擇公式UCB1或UCB1-TUNED選擇子節(jié)點(diǎn)。當(dāng)被選中的子節(jié)點(diǎn)為葉節(jié)點(diǎn)并且該子節(jié)點(diǎn)被訪問的次數(shù)未達(dá)到指定的次數(shù)時(shí),則選擇該子節(jié)點(diǎn)落子然后執(zhí)行模擬棋局(轉(zhuǎn)到(3))。當(dāng)被選中的子節(jié)點(diǎn)為葉節(jié)點(diǎn)并且該子節(jié)點(diǎn)被訪問的次數(shù)
52、達(dá)到指定的次數(shù),則需先展開該子節(jié)點(diǎn)(轉(zhuǎn)到(2))。否則重復(fù)此步驟直到找到被訪問的次數(shù)未達(dá)到指定的次數(shù)或未被訪問過的葉節(jié)點(diǎn)為止。</p><p><b> 展開</b></p><p> 當(dāng)節(jié)點(diǎn)為葉節(jié)點(diǎn)并且該節(jié)點(diǎn)被訪問的次數(shù)達(dá)到指定的次數(shù)時(shí),進(jìn)行展開子結(jié)點(diǎn)。展開時(shí)對(duì)候選步作篩選,去除不適合的候選步,再將篩選后的候選步展開成子節(jié)點(diǎn)并隨機(jī)選擇其中一個(gè)節(jié)點(diǎn)(轉(zhuǎn)到(1))。
53、</p><p><b> 棋局模擬</b></p><p> 當(dāng)被選擇的葉節(jié)點(diǎn)落子后開始執(zhí)行模擬棋局,在模擬棋局中檢查是否有棋串少于四氣,若有則嘗試逃跑;如果有符合簡(jiǎn)單的模式庫(kù)的棋形,執(zhí)行棋形庫(kù)模式匹配;如果沒有符合棋形的空點(diǎn),則嘗試攻擊對(duì)方少于四氣的棋串;如果都沒有合適的棋步,最后使用隨機(jī)方式選擇合法棋步。</p><p><b&
54、gt; 回饋更新</b></p><p> 將模擬棋局的結(jié)果回溯更新游戲樹節(jié)點(diǎn)的信息。</p><p> 圖3.2 Tao Go的UCT具體流程示意圖</p><p> 在實(shí)際上執(zhí)行UCT Search時(shí),其流程可以用圖3.3表示。</p><p> 在圖3.3中,所謂GetBestSequence,指的是從根節(jié)點(diǎn)開始,
55、根據(jù)UCB公式向下搜索,直到找到被訪問次數(shù)不超過指定次數(shù)的葉節(jié)點(diǎn)為止的過程。當(dāng)搜索時(shí),若被訪問的節(jié)點(diǎn)達(dá)到指定的次數(shù),則會(huì)產(chǎn)生子節(jié)點(diǎn),子節(jié)點(diǎn)的多寡,直接影響到搜索的深度與棋力的高低,因此對(duì)于產(chǎn)生出來的子節(jié)點(diǎn),必須加以裁減。</p><p> 第三個(gè)步驟是模擬棋局。所謂模擬棋局,就是由上一個(gè)步驟所找到的葉節(jié)點(diǎn)開始,由計(jì)算機(jī)接手下完,并回傳勝負(fù)結(jié)果,以更新UCT Tree。模擬棋局的核心就是其決定著手的方法。最簡(jiǎn)單的
56、方法,就是純粹隨機(jī)落子(除了非法著手或自填眼位以外),這種方法的好處就是快速、簡(jiǎn)單,且符合Monte Carlo的精神。但缺點(diǎn)則是用這種方法做出來的圍棋程序,棋力低落。要使棋力進(jìn)步的重點(diǎn),在于棋局的手順要有意義,而不是隨機(jī)落子,天南地北地亂下。Tao Go建立了一個(gè)著手庫(kù)對(duì)常見棋形進(jìn)行模式匹配,如果沒有棋形可以匹配則對(duì)少于四氣的己方棋串進(jìn)行長(zhǎng)氣或叫吃對(duì)方少于四氣的棋串,如果以上都不成功,則隨機(jī)落子[15-24]。</p>
57、<p> 有了模擬棋局的結(jié)果,就要依此更新UCT Tree。所謂更新,指的是把從根節(jié)點(diǎn)到第二步驟中所找到的葉節(jié)點(diǎn)所形成的路徑上的所有點(diǎn),依照模擬棋局的結(jié)果來更新勝場(chǎng)數(shù)和訪問次數(shù),亦即若此點(diǎn)為黑,且模擬棋局之結(jié)果為黑勝,則此節(jié)點(diǎn)的勝利次數(shù)加一,反之亦然。訪問次數(shù)則是此路徑上的所有節(jié)點(diǎn)都加一。</p><p> 若總模擬次數(shù)達(dá)到所設(shè)定的次數(shù),或限制時(shí)間已用完,則結(jié)束UCT Search,并且挑出根節(jié)點(diǎn)下
58、被訪問次數(shù)最多的子節(jié)點(diǎn),作為此次搜索的最佳著手。</p><p> 圖3.3 UCT Search的流程圖</p><p> 3.3 棋步合法性判斷模塊設(shè)計(jì)</p><p> 棋步的合法性是根據(jù)圍棋規(guī)則來判斷,如圖3.4所示。分別檢查是否是虛著,是否在棋盤內(nèi),是否是打劫以及是否是自殺(禁著點(diǎn))。虛著,通常采用特殊的棋盤坐標(biāo)來表示,正常棋步跟特殊棋盤坐標(biāo)比較即可
59、知道知道是虛著。有時(shí)候產(chǎn)生的棋步的坐標(biāo)值是不合法的,此時(shí)棋步不在棋盤內(nèi),跟正常棋盤坐標(biāo)范圍比較即可。而打劫可借助記錄可能造成打劫的位置,只要比較棋步的坐標(biāo)和造成打劫的位置即可。至于自殺棋步的判斷,如圖3.5所示。棋子自殺顧名思義是使得下子后棋子所在的棋串沒有氣數(shù),但同時(shí)必須沒有殺死對(duì)方的任何棋串。先計(jì)算下子后棋子所在的棋串的氣數(shù),如果棋串氣數(shù)不為0則說明肯定不是自殺棋步。如果棋串氣數(shù)為0,則需要考慮有沒有可能殺死對(duì)方棋子??赏ㄟ^計(jì)算與該
60、棋串相鄰的對(duì)方棋串的氣數(shù)來判斷,如果沒有相鄰對(duì)方棋串氣數(shù)為0,即提取死子數(shù)為0,屬于自殺,是不合法棋步。如果有提取對(duì)方死子,此時(shí)也有可能是打劫,不過打劫的情況已經(jīng)在前面被排除了,說明盡管有提取死子,但肯定不是由于打劫造成的。這也是打劫要先進(jìn)行判斷的原因。</p><p> 圖3.4 棋步合法性判斷流程圖</p><p> 圖3.5 自殺棋步判斷</p><p>
61、 3.4 算氣模塊設(shè)計(jì)</p><p> 算氣模塊用來計(jì)算一個(gè)棋串的氣數(shù)。通常是已知棋串的某一個(gè)棋子,計(jì)算該棋串的氣數(shù)。使用如下步驟進(jìn)行計(jì)算:</p><p> 將當(dāng)前棋子標(biāo)記為已訪問。</p><p> 對(duì)當(dāng)前棋子的四個(gè)相鄰棋點(diǎn)進(jìn)行如下操作:</p><p> 如果相鄰棋點(diǎn)是空點(diǎn)并且該空點(diǎn)未被訪問過,則氣數(shù)加一,然后將空點(diǎn)標(biāo)記為已
62、訪問。</p><p> 如果相鄰棋點(diǎn)是己方棋子并且該己方棋子未被訪問過,則對(duì)相鄰的己方棋子按照(1)~(4)的步驟進(jìn)行同樣的操作。</p><p> 當(dāng)對(duì)整個(gè)棋串所有的棋子進(jìn)行上述步驟的操作后,整個(gè)棋串的棋子和棋串相鄰的所有空點(diǎn)都會(huì)被標(biāo)記為已訪問,此時(shí)的氣數(shù)和即是要計(jì)算的棋串的氣數(shù)。算氣模塊四個(gè)相鄰棋點(diǎn)操作轉(zhuǎn)換的示意圖如圖3.6所示。</p><p> 圖3
63、.6 算氣轉(zhuǎn)換示意圖</p><p> 3.5 更新棋盤(提子)模塊設(shè)計(jì)</p><p> 如圖3.7,是更新棋盤的具體流程。更新棋盤時(shí),首先將產(chǎn)生的棋步下在棋盤上,將對(duì)應(yīng)的棋盤坐標(biāo)標(biāo)為棋步的顏色。然后計(jì)算相鄰的對(duì)方棋串的氣數(shù)和棋串的棋子個(gè)數(shù)。接著判斷計(jì)算出來的棋串的氣數(shù)是否為0并且棋串的棋子數(shù)為1,有可能出現(xiàn)會(huì)造成打劫的情況,所以需要判斷下子后周圍的棋形是不是會(huì)造成打劫的棋形,如果是
64、會(huì)造成打劫的棋形則記錄會(huì)造成打劫的位置。不管是否有會(huì)造成打劫的情況出現(xiàn),只要有對(duì)方的棋串的氣數(shù)為0,則將對(duì)方的棋串的所有棋子的清空,即提掉對(duì)方死子,同時(shí)增加相應(yīng)的擔(dān)子數(shù)。最后,當(dāng)一方的棋步處理完畢后,則交換對(duì)方下子??梢钥吹?,更新棋盤時(shí)總共有兩個(gè)功能,即是提取對(duì)方的死子和記錄打劫的位置,如果上述情況存在。</p><p> 圖3.7 更新棋盤(提子)流程圖</p><p> 3.6 勝
65、負(fù)計(jì)算模塊設(shè)計(jì)</p><p> 計(jì)算勝負(fù)時(shí),對(duì)棋盤上的每一個(gè)棋點(diǎn),進(jìn)行如圖3.8的數(shù)子流程判斷。一個(gè)棋點(diǎn),無(wú)非是被黑棋或白棋占據(jù),要不然則為空點(diǎn)。當(dāng)被白棋占據(jù)時(shí),白棋子數(shù)加一。當(dāng)被黑棋占據(jù)時(shí),黑棋子數(shù)加一。而空點(diǎn)在棋局結(jié)束時(shí),無(wú)非是被白棋或黑棋占據(jù)(雙活除外),所以如果空點(diǎn)被白棋圍住,白棋子數(shù)加一,否則空點(diǎn)被黑棋圍住,黑棋子數(shù)加一。當(dāng)棋盤所有的棋點(diǎn)計(jì)算完畢后,白棋和黑棋的子數(shù)都已經(jīng)知道,只需比較雙方的子數(shù)即可
66、知道勝負(fù)結(jié)果。</p><p> 圖3.8 數(shù)子流程圖</p><p> 4 基于UCT的圍棋引擎的實(shí)現(xiàn)</p><p> 4.1 軟硬件開發(fā)環(huán)境</p><p> 硬件平臺(tái):AMD Athlon(tm) 64 X2 Dual Core Processor 4000+, 1G內(nèi)存</p><p> 軟件平臺(tái):
67、Slackware Linux 13.0和Windows XP</p><p><b> 開發(fā)語(yǔ)言:C語(yǔ)言</b></p><p> 開發(fā)工具:采用(g)Vim-7.2+Makefile+gcc-4.3.3的方式,前期代碼的編寫和測(cè)試主要</p><p> 是在Linux環(huán)境下完成,后期代碼移植通過MinGW-5.1.6編譯出可運(yùn)行<
68、;/p><p> 在Windows環(huán)境下的圍棋程序。</p><p> 其它工具:cgoban-1.9.14和gogui-1.1.10分別支持GMP和GTP圍棋協(xié)議,用于測(cè)試圍棋引擎的協(xié)議接口,并提供良好的人機(jī)、機(jī)機(jī)對(duì)弈界面。另外,也可以使用引擎的控制臺(tái)字符界面進(jìn)行操作和測(cè)試。StoneBase 4.6.1.2147用來查看與編輯引擎調(diào)試輸出的SGF文件。</p><p
69、> 4.2 圍棋引擎的數(shù)據(jù)結(jié)構(gòu)</p><p> 在程序中主要有兩類數(shù)據(jù)結(jié)構(gòu):一是與棋局相關(guān)數(shù)據(jù),用于記錄棋盤信息和保證棋局的正常進(jìn)行;二是與UCT算法相關(guān)數(shù)據(jù),里面保存了創(chuàng)建UCT Tree的節(jié)點(diǎn)信息及模擬棋局相關(guān)參數(shù)和數(shù)據(jù)。</p><p> 4.2.1 棋局?jǐn)?shù)據(jù)</p><p> 以下是正式棋局?jǐn)?shù)據(jù)的拷貝,因?yàn)檫M(jìn)行UCT模擬棋局時(shí)會(huì)改變相關(guān)棋局信
70、息,必須另外復(fù)制一份數(shù)據(jù),以便于操作和防止錯(cuò)誤修改原有的數(shù)據(jù)。棋局?jǐn)?shù)據(jù)包括了棋盤,棋盤大小,當(dāng)前下棋的顏色,貼目,劫爭(zhēng)位置等。這些數(shù)據(jù)有的可能在初始化后在棋局中沒有任何改變(如貼目),有的可能會(huì)時(shí)刻變化(如當(dāng)前下棋的顏色),全部進(jìn)行復(fù)制是為了保持一致性,即正式棋局的數(shù)據(jù)和模擬棋局的數(shù)據(jù)是一致的,只是在名稱上不同。</p><p> 4.2.2 UCT Tree數(shù)據(jù)</p><p> 這
71、里包含了UCB公式參數(shù)和UCT Tree結(jié)點(diǎn)的結(jié)構(gòu),說明了結(jié)點(diǎn)代表的著手,勝利的次數(shù),被訪問的次數(shù),以及結(jié)點(diǎn)之間的關(guān)系。</p><p> 4.3 圍棋引擎的UCT算法實(shí)現(xiàn)</p><p> 4.3.1 UCT算法的核心實(shí)現(xiàn)</p><p> 這一小節(jié)給出Tao Go的UCT算法的核心代碼,并對(duì)代碼中各個(gè)變量和函數(shù)的意義及作用進(jìn)行分析說明。</p>
72、<p> UCT算法流程實(shí)現(xiàn)主要在play_simulation函數(shù),而uct_search是調(diào)用play_simulation函數(shù)來提供產(chǎn)生棋步著手的接口函數(shù)。</p><p> uct_search函數(shù)的功能是在進(jìn)行UCT搜索之前進(jìn)行初始化工作,包括創(chuàng)建和初始化根節(jié)點(diǎn),首次展開節(jié)點(diǎn)。主體是進(jìn)行numsim次UCT搜索,并在調(diào)用play_simulation之前復(fù)制棋局信息。進(jìn)行完numsim
73、次UCT搜索后,從根節(jié)點(diǎn)下面找到最佳子節(jié)點(diǎn)并返回該節(jié)點(diǎn)代表的著手和釋放UCT樹。</p><p> 在uct_search函數(shù)中變量numsim用于控制模擬次數(shù),在其他條件不變的情況下,通常認(rèn)為模擬次數(shù)越多,程序能搜索的棋步越多越深,棋力也會(huì)越強(qiáng)。當(dāng)然也有賴于模擬質(zhì)量的好壞。</p><p> 在uct_search函數(shù)中根節(jié)點(diǎn)初始化時(shí)子節(jié)點(diǎn)為空,被訪問次數(shù)為0,進(jìn)行模擬之前必須對(duì)其展
74、開子節(jié)點(diǎn)(create_children),才能在play_simulation函數(shù)中選擇子節(jié)點(diǎn)。展開子節(jié)點(diǎn)時(shí)包含了對(duì)子節(jié)點(diǎn)裁減的判斷,控制搜索棋步的廣度。</p><p> 在uct_search函數(shù)中copy_state函數(shù)的功能就是復(fù)制在4.2小節(jié)中提到的有關(guān)棋局?jǐn)?shù)據(jù)的信息,防止錯(cuò)誤修改棋局信息,同時(shí)為下一次模擬恢復(fù)數(shù)據(jù)。</p><p> 在uct_search函數(shù)中g(shù)et_b
75、est_child函數(shù)是獲得根節(jié)點(diǎn)下面被訪問次數(shù)最多的子節(jié)點(diǎn),此節(jié)點(diǎn)代表的著手被認(rèn)為是UCT算法產(chǎn)生的最佳著手,也是圍棋引擎思考的結(jié)果,并最終被輸出到引擎外部。</p><p> play_simulation函數(shù)功能是實(shí)現(xiàn)了UCT算法的流程,表現(xiàn)為遞歸選擇子節(jié)點(diǎn)直到選中符合要求的葉節(jié)點(diǎn)(在必要時(shí)進(jìn)行展開節(jié)點(diǎn)),然后進(jìn)行模擬棋局,最后將棋局勝負(fù)結(jié)果回饋更新。</p><p> 在pla
76、y_simulation函數(shù)中變量num_visits控制節(jié)點(diǎn)被擴(kuò)展時(shí)的次數(shù),能降低UCT Tree節(jié)點(diǎn)在內(nèi)存的增長(zhǎng)速率,在相同模擬次數(shù)的情況下,增加對(duì)節(jié)點(diǎn)搜索模擬的次數(shù),在一定程度上增加程序搜索的有效程度,負(fù)面影響是會(huì)減少棋步搜索的深度。</p><p> 在play_simulation函數(shù)中play_random_game函數(shù)包含了模擬棋局的功能:棋形模式匹配、長(zhǎng)氣逃子和吃子。uct_select函數(shù)中要
77、優(yōu)先選擇未被訪問過的子節(jié)點(diǎn),這也是一個(gè)策略問題。關(guān)于play_random_game和uct_select函數(shù)的功能分別在4.3.5小節(jié)和4.3.4小節(jié)會(huì)有詳細(xì)說明。</p><p> 至于make_move函數(shù)則是根據(jù)圍棋規(guī)則對(duì)落子進(jìn)行更新棋盤處理,關(guān)于基本圍棋規(guī)則會(huì)在討論play_random_grame函數(shù)模擬棋局功能時(shí)進(jìn)行介紹。而update_node函數(shù)是當(dāng)模擬棋局勝利時(shí)將勝率加1,被訪問次數(shù)不管勝利
78、與否都加1。注意update_node更新節(jié)點(diǎn)信息時(shí),模擬棋局勝負(fù)的結(jié)果對(duì)于不同深度的節(jié)點(diǎn)是相反的。某一深度的節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)代表對(duì)方著手的節(jié)點(diǎn),如果模擬棋局結(jié)果對(duì)該節(jié)點(diǎn)來說是勝利著手,則模擬棋局對(duì)于對(duì)方而言就是失敗的,所以更新到該節(jié)點(diǎn)的父節(jié)點(diǎn)和子節(jié)點(diǎn)的勝負(fù)結(jié)果是相反的。實(shí)際上也就是說,UCT樹本質(zhì)是一棵極小極大(minimax)樹,對(duì)于己方有利的棋步對(duì)對(duì)方則是不利的,反之亦然。</p><p> 4.3.
79、2 候選步的產(chǎn)生方式及管理機(jī)制</p><p> 棋局一開始時(shí),雖然棋盤上有八十一個(gè)空點(diǎn),黑棋可以任意選擇其一,也就是說有八十一個(gè)候選步。如此一來,游戲樹的樹支將緩慢遞減,但是,并不時(shí)每個(gè)候選步都是合適的,根據(jù)圍棋知識(shí),選擇如圖4.1中的二十五個(gè)候選步為棋局開始的候選步。</p><p> 圖4.1 二十五個(gè)候選步</p><p> 如果一開始只有十五個(gè)空戰(zhàn)成
80、為候選步,必須要在適當(dāng)時(shí)機(jī),把其它空點(diǎn)也加入候選步中,否則,有些空點(diǎn)將就永遠(yuǎn)不會(huì)被選擇,而造成錯(cuò)誤。因此,需要一個(gè)候選步的產(chǎn)生方式及管理機(jī)制。</p><p> 由于每下一子(稱為著手),就會(huì)讓周圍附近的空點(diǎn)成為下一步合適的候選步。因此,產(chǎn)生候選步的方式就是對(duì)于每一個(gè)空點(diǎn),檢查其周圍是否有下子,看是否將其納入候選步。而檢查的方式是根據(jù)空點(diǎn)所在線,周圍棋子與空點(diǎn)之間的距離和已下棋子的步數(shù)來判斷的。其中兩個(gè)棋子的距
81、離是指兩個(gè)棋子橫坐標(biāo)差的絕對(duì)值和縱坐標(biāo)差的絕對(duì)值之和,即有P1(X1, Y1)和P2(X2, Y2),則兩個(gè)棋子距離為</p><p> |P1P2| = |X1-X2| + |Y1-Y2|</p><p><b> 一線空點(diǎn)</b></p><p> 已下棋子的步數(shù)不超過預(yù)定的步數(shù)(如10)時(shí),不考慮一線空點(diǎn)作為候選步。達(dá)到預(yù)定的步數(shù)后
82、,對(duì)于一線的空點(diǎn),當(dāng)周圍有棋子在一線或二線上而且和該空點(diǎn)的距離小于3時(shí),將該空點(diǎn)納入候選步。如圖4.2中,交叉點(diǎn)代表空點(diǎn),其陰影部分代表如果這些地方有棋子,則說明該空點(diǎn)適合作為候選步。</p><p> 圖4.2 一線空點(diǎn)候選步范圍</p><p><b> 二線空點(diǎn)</b></p><p> 已下棋子的步數(shù)不超過預(yù)定的步數(shù)(如5)時(shí),不
83、考慮一線空點(diǎn)作為候選步。達(dá)到預(yù)定的步數(shù)后,對(duì)于二線的空點(diǎn),當(dāng)周圍縱橫坐標(biāo)都不超過兩線所構(gòu)成的矩形范圍內(nèi),如果有棋子距離該空點(diǎn)小于4時(shí),即類似于中國(guó)象眼的位置不考慮,則將空點(diǎn)納入候選步。如圖4.3所示,用三角形標(biāo)記的地方即為象眼位置,不考慮該位置是否有棋子。</p><p> 圖4.3 二線空點(diǎn)候選步范圍</p><p><b> 三線及三線以上空點(diǎn)</b><
84、/p><p> 三線及三線以上空點(diǎn),考慮到九路棋盤的特殊性,無(wú)條件納入候選步。</p><p> 由于圍棋棋盤上的空點(diǎn)數(shù)目是固定的,九路棋盤只有八十一個(gè)棋點(diǎn),可以成為候選步的空點(diǎn)最多也只有八十一個(gè),所有使用candidate_move數(shù)組來保存是適合的。根據(jù)“敵之要點(diǎn)即我之要點(diǎn)”的指導(dǎo)思想,這里不考慮空點(diǎn)是由于黑棋或白棋而納入候選步的,簡(jiǎn)化了產(chǎn)生候選步操作,同時(shí)也避免錯(cuò)失好點(diǎn)。當(dāng)然有時(shí)某些
85、空點(diǎn)并非是要點(diǎn)或好點(diǎn),將其納入候選步,在展開子節(jié)點(diǎn)時(shí)不僅浪費(fèi)了游戲樹內(nèi)存空間,而且增加了搜索空間,減少有效搜索次數(shù),搜索到不好的著手的幾率也會(huì)增大。這就體現(xiàn)了計(jì)算機(jī)圍棋中不同的策略對(duì)圍棋程序的影響。</p><p> 候選步的產(chǎn)生與管理是在每次落子時(shí)執(zhí)行,也就是在程序的流程中只要有下子的動(dòng)作,不論是展開節(jié)點(diǎn)還是棋局模擬時(shí)隨機(jī)下子,都會(huì)使用候選步的產(chǎn)生與管理。</p><p> 4.3.
86、3 選擇節(jié)點(diǎn)(UCT選擇)</p><p> 上文中提到過的uct_select函數(shù)是從父節(jié)點(diǎn)中選擇uct值最大的節(jié)點(diǎn)進(jìn)行搜索,其中uct值的計(jì)算如下簡(jiǎn)略代碼所示:</p><p> 可變參數(shù)對(duì)uct值的影響</p><p> 首先來關(guān)注子節(jié)點(diǎn)被訪問過的情況時(shí),uct值的計(jì)算用以下公式計(jì)算:</p><p> uctvalue = w
87、inrate + UCTK * sqrt(log(parent->visits) / child->visits)</p><p> 要注意到UCTK的值是可變的,不同的值對(duì)程序的影響也不同。在CGOS上運(yùn)行許多實(shí)現(xiàn)了基礎(chǔ)UCT算法,使用不同參數(shù)值的圍棋機(jī)器人找到最優(yōu)參數(shù)值。它們使用如下方法</p><p> UCB1 = avgScore + c * sqrt(log(n
88、) / m)</p><p> 其中上一行的公式和uct_select函數(shù)中的計(jì)算公式實(shí)際上等價(jià)的。要注意K和c都是在根號(hào)sqrt外面的。不同參數(shù)對(duì)圍棋機(jī)器人的影響如圖4.4所示。圖中Nick代表圍棋機(jī)器人的名稱。ELO代表等級(jí)分排行,Plts代表圍棋機(jī)器人的實(shí)力,10k表示10級(jí)。c為可變參數(shù)。</p><p> 圖4.4 可變參數(shù)對(duì)圍棋機(jī)器人的影響</p><p
89、> FPU(First-play urgency)</p><p> 當(dāng)子節(jié)點(diǎn)從未被訪問過時(shí),使用下面的公式計(jì)算uct值:</p><p> uctvalue = 10000 + 1000 * rand(); (1)</p><p> 子節(jié)點(diǎn)被創(chuàng)建時(shí),其被訪問數(shù)和勝利數(shù)都為0。而更新節(jié)點(diǎn)信息時(shí),即便模擬棋局返回勝利結(jié)果,勝利數(shù)僅加1,被訪問數(shù)加1。也
90、就是說當(dāng)節(jié)點(diǎn)被訪問的次數(shù)很少時(shí),用公式</p><p> uctvalue = winrate + UCTK * sqrt(log(parent->visits) / child->visits)(2)</p><p> 計(jì)算出來的uct值實(shí)際很小,遠(yuǎn)遠(yuǎn)小于用公式(1)計(jì)算出來的uct值,這就確保了能夠優(yōu)先隨機(jī)未被訪問過的子節(jié)點(diǎn)。用公式(1)計(jì)算出來的uct值,稱為FP
91、U[8]。</p><p> 將FPU值賦給未被訪問過的節(jié)點(diǎn)。任意節(jié)點(diǎn),至少被訪問過一次之后,它的uct值是根據(jù)公式(2)來計(jì)算。選擇最高uct值的節(jié)點(diǎn)來落子。因此FPU很大時(shí)能保證在開發(fā)已訪問過的子節(jié)點(diǎn)之前探索未被訪問過的節(jié)點(diǎn)一次。</p><p> 如果總是至少訪問一次所有的子節(jié)點(diǎn),有時(shí)這樣會(huì)導(dǎo)致搜索的低效,尤其是搜索的次數(shù)的次數(shù)相對(duì)于游戲樹的節(jié)點(diǎn)數(shù)目不大的時(shí)候。例如一個(gè)節(jié)點(diǎn)如果持
92、續(xù)返回勝利的結(jié)果,沒有好的理由需要去探索其它的節(jié)點(diǎn)。從另一方面來說,取較小的FPU值同樣可以使得不去搜索其它一些未被訪問過的節(jié)點(diǎn)。</p><p> 4.3.4 展開節(jié)點(diǎn)</p><p> 當(dāng)節(jié)點(diǎn)要展開時(shí),并不是每個(gè)候選步都是合適的。如4.2.1小節(jié)提到的,九路棋局一開始雖然有八十一個(gè)空點(diǎn)可以選擇,但是依據(jù)圍棋知識(shí),并非八十一個(gè)空點(diǎn)都是合適的。因此,對(duì)于候選步有篩選的必要。將不合理的候
93、選步予以去除,篩選的作用可以樹的分支,在相同的時(shí)間或相同的模擬棋局次數(shù),可以增加搜索的深度。</p><p> 每一個(gè)節(jié)點(diǎn)代表一個(gè)盤面,對(duì)于一個(gè)特定的盤面其候選步也是固定的。當(dāng)一個(gè)節(jié)點(diǎn)要展開產(chǎn)生子節(jié)點(diǎn)時(shí),先對(duì)所有候選步進(jìn)行篩選,將篩選后的候選步分別記錄在子節(jié)點(diǎn)中,子節(jié)點(diǎn)之間以伙伴關(guān)系(鏈接形式)鏈接起來,將該節(jié)點(diǎn)的子節(jié)點(diǎn)指針指向鏈頭子關(guān)點(diǎn)。</p><p> 棋局開始時(shí),節(jié)點(diǎn)只有根節(jié)點(diǎn)
94、,盤面上有八十一個(gè)空點(diǎn)可供選擇,但是只有二十五個(gè)空點(diǎn)為合適的候選步(圖4.1),此為第一步粗略的篩選。再更進(jìn)一步,由于對(duì)稱的點(diǎn)可以視為同一個(gè),所以,僅六個(gè)候選步需要測(cè)試。如此一來,樹分支由原來的八十一縮減成六。</p><p> 圖4.5 六個(gè)需要測(cè)試的候選步</p><p> 同樣地,對(duì)于開局時(shí),棋局可能會(huì)對(duì)稱,篩選候選步時(shí)還可以進(jìn)行簡(jiǎn)單的篩選,直到發(fā)現(xiàn)棋局不對(duì)稱為止。例如圖4.6所
95、示,只需要考慮陰影部分即可。</p><p> 圖4.6 對(duì)稱棋局候選步</p><p> 對(duì)于任何樹節(jié)點(diǎn),在展開子節(jié)點(diǎn)之前,都執(zhí)行候選步篩選,去除不合理的候選步,能減少樹分支,增加搜索深度,進(jìn)而提高搜索結(jié)果的準(zhǔn)確性。但是,篩選的進(jìn)行需要圍棋知識(shí)的輔助,而且,不當(dāng)?shù)暮Y選有可能把合適的甚至是最佳的候選步予以去除,造成無(wú)法挽救的錯(cuò)誤。因此,對(duì)于候選步的篩選必須謹(jǐn)慎地進(jìn)行,不僅篩選的條件必須
96、嚴(yán)謹(jǐn),更需要經(jīng)過測(cè)試驗(yàn)證以確認(rèn)不會(huì)造成不必要的副作用。目前Tao Go中所使用的候選步篩選僅依據(jù)圍棋基本規(guī)則,將不合法及不適合的候選步予以去除。</p><p> 目前歸納共有三種棋步,第一種如圖4.7的A1,A9等棋點(diǎn)對(duì)黑棋而言是自殺的著手,由于使用中國(guó)圍棋規(guī)則,因此自殺著手是禁著的一種。第二種是劫,如圖4.7的H1,由于上一步黑棋下G2吃掉H2,白棋不能下,這稱為打劫立即反提著手,也是禁著的一種,打劫立即反
97、提著手是圍棋規(guī)則中避免棋局無(wú)法結(jié)束的一項(xiàng)規(guī)定,如果沒有這項(xiàng)規(guī)定,黑白雙方將會(huì)因?yàn)榛ハ喑缘魧?duì)方的子而不斷地循環(huán)而讓棋局無(wú)法結(jié)束。第三種是真眼,如圖4.7中的A6,C9,D8等為白棋的真眼,是棋串死活重要的部分,白棋沒有理由把自己的真眼填掉,對(duì)白棋而言是不合適的著手,對(duì)黑棋而言則是禁著。</p><p> 圖4.7 禁著與打劫</p><p> 4.3.5 棋局模擬</p>
98、<p> 模擬棋局的好壞是決定節(jié)點(diǎn)(著手)好壞的一個(gè)重要依據(jù),因此,模擬棋局的合理性與正確性是相當(dāng)重要的,雖然在大量的隨機(jī)取樣下,可以得到誤差小到忽略的結(jié)果,但是,一盤棋局的比賽時(shí)間是有限的,每一個(gè)著手更需要在更短的時(shí)間內(nèi)獲得結(jié)果,所以,執(zhí)行合理而正確的模擬棋局是有其必要性的。</p><p> 另外,對(duì)于一些常見的棋形,人類棋手總結(jié)出其特定的比較好的著手,雖然在某些盤面下可能不是最佳的著手,但通常
99、來說都不會(huì)太壞,對(duì)于這部分的加強(qiáng)就需要圍棋的知識(shí)。當(dāng)愈多的檢查與處理被加入,模擬棋局的合理性與正確性也隨之增加,但是模擬棋局的所需時(shí)間也隨之增加,在相同時(shí)間內(nèi)可以執(zhí)行的模擬棋局的數(shù)量也就相對(duì)減少。</p><p> 因此,如何讓模擬棋局足夠合理與正確,同時(shí)不會(huì)讓一盤模擬棋局的所需時(shí)間太長(zhǎng),將是一項(xiàng)困難的挑戰(zhàn)。對(duì)此,采取的策略是先確認(rèn)在相同的模擬棋局次數(shù)情況下,棋力是否有提升,再確認(rèn)能在限定內(nèi)時(shí)間內(nèi)完成棋局比賽。
100、</p><p> 在此對(duì)模擬棋局的加強(qiáng)方法分別說明如下:</p><p><b> 棋局結(jié)束的判斷</b></p><p> 無(wú)論一盤棋局下得好壞,總得知道如何判斷棋局是否結(jié)束。前文中曾提到過在蒙特卡羅方法中模擬棋局用不自填眼位來確保棋局正常結(jié)束。自填眼位通常是指如圖4.8中第一行最左邊圖所示,E5位置的空點(diǎn)相鄰的四個(gè)棋點(diǎn)都是是同色(圖
101、中為黑棋)的棋子,而不考慮其周圍四個(gè)對(duì)角點(diǎn)(用交叉標(biāo)記)的顏色。</p><p> 圖4.8 中央自填眼位的判斷</p><p> 在中央一個(gè)空點(diǎn)如果周圍四個(gè)對(duì)角點(diǎn)至少有兩個(gè)被敵方棋子占據(jù)時(shí),而不能將對(duì)方棋子殺死,該空點(diǎn)將成為假眼,最終會(huì)被對(duì)方打吃而自己自填眼位。即如圖4.8第一行中,如果圖中交叉點(diǎn)被白棋占據(jù),E5點(diǎn)將成為假眼而最終自填眼位。而圖4.8第二行則是真眼。如圖4.9,在邊、
102、角一個(gè)空點(diǎn)周圍的對(duì)角點(diǎn)如果有一個(gè)被敵方棋子占據(jù),則該空點(diǎn)也會(huì)自填眼位。</p><p> 圖4.9 邊、角自填眼位的判斷</p><p> 從上面的分析中要明確的是不自填眼位確切來說應(yīng)該是不自填真眼。注意,這里的真假眼是從形狀上來簡(jiǎn)單判斷的,并不考慮棋串的氣數(shù)和死活,因此有一些比較少見的棋形是假眼成真眼活棋的,如果把假眼填掉,會(huì)導(dǎo)致棋子被殺,模擬棋局失真。如圖4.10,黑棋兩個(gè)都是假眼
103、,都因?yàn)椴蝗霘舛钇濉?lt;/p><p> 圖4.10 雙假眼成活棋</p><p> 除了不自填眼位外,還涉及到公氣(黑棋和白棋共同擁有的氣點(diǎn))的填充,在中國(guó)圍棋規(guī)則數(shù)子法里要求填公氣。圍棋顧名思義就是圍地,當(dāng)棋子占據(jù)的地盤比較大時(shí),難以判斷一個(gè)空點(diǎn)是否是公氣。在棋局結(jié)束時(shí),如果有不能活棋的又沒有馬上被提掉的棋子,稱為俘虜,也是要提掉的。另外,一塊地被圍起來,也很難檢查是屬于哪方棋子的
104、地盤。當(dāng)然,還有更多的情況,可以說棋局的結(jié)束情況是相當(dāng)復(fù)雜的。</p><p> 對(duì)此,Tao Go采取以實(shí)戰(zhàn)為最高原則,基本的圍棋規(guī)則和不自填眼位,一直下到將棋盤上所有的公氣填完,提盡俘虜,活棋下成兩個(gè)或兩個(gè)以上真眼的棋形。這樣做的好處是在結(jié)束棋局時(shí)只要黑白雙方都發(fā)現(xiàn)沒有地方可下,雙方都pass棋局即可宣告結(jié)束,而且在計(jì)算勝負(fù)時(shí)也是和中國(guó)圍棋規(guī)則的數(shù)子法的精神是一致的,計(jì)算簡(jiǎn)單。不過這樣下也會(huì)對(duì)模擬棋局效率有
105、一定的影響,因?yàn)樘畛涔珰?,提取俘虜,作真眼等并不?huì)對(duì)勝負(fù)的結(jié)果有影響,如果這類棋步步數(shù)太多會(huì)浪費(fèi)時(shí)間。如圖4.11,是棋局結(jié)束時(shí)的盤面圖。</p><p> 圖4.11 棋局結(jié)束盤面</p><p> 還有一個(gè)會(huì)對(duì)判斷棋局結(jié)束有影響的是雙活的情形。雙活時(shí)如果強(qiáng)制要求填公氣,將導(dǎo)致被吃,對(duì)棋局的勝負(fù)可能會(huì)造成影響。如圖4.12,E9,E8為黑白兩個(gè)棋串共有,誰(shuí)都不能下,強(qiáng)制要求填公氣時(shí)填
106、公氣的一方會(huì)被吃。由于雙活的情形比較少見,而判斷是否雙活又非常困難,簡(jiǎn)單忽略雙活是可行的。</p><p><b> 圖4.12 雙活</b></p><p><b> 圍棋基本規(guī)則處理</b></p><p> 在模擬棋局中,有可能會(huì)選擇到非法或不合理的棋步,非法的棋步因?yàn)榈財(cái)倗宓幕疽?guī)則,是一定要去除的,但是不
107、合理的棋步,如果不去除,則會(huì)造成不合理的模擬棋局。</p><p> 這部分使用候選步篩選方式處理,不再贅述,但是對(duì)于假眼,則是必須確認(rèn)是否能成為真眼,也就是檢查其斜角四個(gè)相鄰的棋點(diǎn)是否為空點(diǎn),如果是空點(diǎn),表示有機(jī)會(huì)形成真眼,此時(shí)就以斜角的相鄰空點(diǎn)任選其一為棋步,如果無(wú)空點(diǎn),表示此假眼已成為劫,填此假眼只是粘劫,不屬于眼位。如果選擇到的是對(duì)方的假眼,則要檢查是否此棋步會(huì)吃掉對(duì)方棋串,也就是對(duì)方的棋串只剩一氣,且
108、其最后一氣就是此假眼。如果不是,則此對(duì)方的假眼是己方的禁著。</p><p><b> 模式匹配</b></p><p> 對(duì)于常見的棋形,人類棋士通過長(zhǎng)期經(jīng)驗(yàn)積累,總結(jié)出一些著手比較合理,得失大致均等,雙方都能接受的定型,就是在圍棋上稱為“定式”。由于定式的數(shù)量很多,棋步較復(fù)雜,要想在快速的模擬棋局中構(gòu)建一個(gè)高效的定式庫(kù),實(shí)現(xiàn)起來非常復(fù)雜,對(duì)于模擬次數(shù)很大的模擬
溫馨提示
- 1. 本站所有資源如無(wú)特殊說明,都需要本地電腦安裝OFFICE2007和PDF閱讀器。圖紙軟件為CAD,CAXA,PROE,UG,SolidWorks等.壓縮文件請(qǐng)下載最新的WinRAR軟件解壓。
- 2. 本站的文檔不包含任何第三方提供的附件圖紙等,如果需要附件,請(qǐng)聯(lián)系上傳者。文件的所有權(quán)益歸上傳用戶所有。
- 3. 本站RAR壓縮包中若帶圖紙,網(wǎng)頁(yè)內(nèi)容里面會(huì)有圖紙預(yù)覽,若沒有圖紙預(yù)覽就沒有圖紙。
- 4. 未經(jīng)權(quán)益所有人同意不得將文件中的內(nèi)容挪作商業(yè)或盈利用途。
- 5. 眾賞文庫(kù)僅提供信息存儲(chǔ)空間,僅對(duì)用戶上傳內(nèi)容的表現(xiàn)方式做保護(hù)處理,對(duì)用戶上傳分享的文檔內(nèi)容本身不做任何修改或編輯,并不能對(duì)任何下載內(nèi)容負(fù)責(zé)。
- 6. 下載文件中如有侵權(quán)或不適當(dāng)內(nèi)容,請(qǐng)與我們聯(lián)系,我們立即糾正。
- 7. 本站不保證下載資源的準(zhǔn)確性、安全性和完整性, 同時(shí)也不承擔(dān)用戶因使用這些下載資源對(duì)自己和他人造成任何形式的傷害或損失。
最新文檔
- 基于靜態(tài)評(píng)估的計(jì)算機(jī)圍棋UCT算法改進(jìn)研究.pdf
- uct工藝
- 點(diǎn)格棋博弈中UCT算法的研究與實(shí)現(xiàn).pdf
- research on recovery of computer data based on windows system
- UCT工藝處理城市污水的試驗(yàn)研究.pdf
- 基于UCT算法的非完備信息多人軍棋博弈系統(tǒng).pdf
- UCT工藝脫氮除磷運(yùn)行優(yōu)化試驗(yàn)與研究.pdf
- 多品種小批量運(yùn)營(yíng)的分析與改善——UCT公司實(shí)踐.pdf
- 投加硅藻精土強(qiáng)化UCT工藝試驗(yàn)研究.pdf
- 改良型UCT與生物膜耦合工藝除磷性能研究.pdf
- UCT-MBR中混合液特性及膜污染研究.pdf
- 基于matlab的數(shù)字圖像分割的研究與實(shí)現(xiàn)(the research and implementation of digital image segmentation based on the matlab)
- research on computer software engineering management
- uct畢業(yè)設(shè)計(jì)--污水處理廠設(shè)計(jì)
- 螺旋升流式SUFR-UCT系統(tǒng)脫氮除磷試驗(yàn)研究.pdf
- 基于.net框架的web服務(wù)的研究與實(shí)現(xiàn)(research & implementation on web services based on the .net framwork)
- 基于matlab的電機(jī)仿真研究(simulation research of motor based on matlab)
- 改良型UCT工藝在合成廢水中脫氮除磷的效能研究.pdf
- 基于dynaform的板料成形研究(based on the dynaform plate forming research)
- applied research of computer technology to the development of embedded systems
評(píng)論
0/150
提交評(píng)論