【正文】 及展望。 第三章重點講述人機對弈中的 AI，包括數(shù) 據(jù)結(jié)構(gòu)表示、走法產(chǎn)生、搜索算法以及估值核心。 Pentium174。 Core174。 （ 2）下法：兩人分別執(zhí)黑白兩色棋子，輪流在棋盤上選擇一個無子的交叉點（又稱為空點）走子，規(guī)定執(zhí)黑者先行。它是中西文化的交流點，是古今哲理的結(jié)晶。 甲： 1 乙： 2 乙： 3 甲： 4 乙： 8 乙： 9 甲： 5 乙： 10 乙： 11 甲： 6 甲： 7 乙： 12 乙： 13 乙： 14 乙： 15 ?? ?? ?? 圖 博弈樹的例子 圖 博弈樹的例子 甲： 1 2 3 M+1 ?? 圖 乙： 2 AlphaBeta剪枝實例圖 乙： 1 K+1 K+2 K+N ?? 圖 乙方面對的局勢 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 3 頁 五子棋基本知識介紹 五子棋是起源于中國古代的傳統(tǒng)黑白棋種之一。 博弈樹最終的葉 結(jié) 點有甲贏乙輸，甲輸乙贏，甲乙平手三種。假設(shè)甲選擇了形成局面 2的走法，輪到乙下棋。只要看看棋盤，就一清二楚。 本文以計算機五子棋博弈系統(tǒng)作為研究課題。目前，各發(fā)達國家都把人工智能任務(wù)重點列入本國的高科技發(fā)展計劃當(dāng)中，投入巨大的人力和物力。 目 錄 1 緒論 .......................................................... 1 選題背景 .................................................. 1 計算機博弈介紹 ............................................ 1 五子棋基本知識介紹 ........................................ 3 開發(fā)及運行環(huán)境 ............................................ 3 開發(fā)環(huán)境 .............................................. 3 運行環(huán)境 .............................................. 3 本文結(jié)構(gòu) .................................................. 3 2 系統(tǒng)總體設(shè)計 .................................................. 5 系統(tǒng)架構(gòu) .................................................. 5 系統(tǒng)功能劃分 .............................................. 5 系統(tǒng)總體邏輯流程 .......................................... 5 關(guān)鍵技術(shù)點 ................................................ 5 AI 算法 ............................................... 6 界面生成 .............................................. 6 網(wǎng)絡(luò)連接 .............................................. 6 系統(tǒng)交互性 ............................................ 6 3 人機對弈中 AI 的實現(xiàn) ........................................... 7 數(shù)據(jù) 結(jié)構(gòu) .................................................. 7 走法產(chǎn)生 .................................................. 7 搜索算法 及增強 ............................................ 8 傳統(tǒng) AlphaBeta 算法介紹 ............................... 8 NegaScout 算法及 Minimal Window..................... 10 置換表（ Transposition Table） ..................... 11 歷史啟發(fā)（ History Heuristic） ..................... 12 估值函數(shù) ................................................. 15 4 界面的設(shè)計與實現(xiàn) ........................................ 17 設(shè)計思想 ................................................. 17 主要類及其關(guān)系 ........................................... 17 用戶界面設(shè)計的 6 個核心類 .......................... 17 消息消息傳遞圖 ................................... 18 主體界面 ................................................. 19 5 聯(lián)機功能的實現(xiàn) ............................................... 23 消息機制的架構(gòu) ........................................... 23 各種消息說明 ............................................. 23 6 總結(jié)和展望 ................................................... 28 總結(jié) ..................................................... 28 未來展望 ................................................. 28 參考文獻 ....................................................... 29 翻 譯部分 ....................................................... 31 英文原文 ..................................................... 31 中文譯文 ..................................................... 41 致 謝 ........................................................... 49 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 1 頁 1 緒論 選題背景 人工智能是一門正 在迅速發(fā)展的新興的綜合性很強的邊緣科學(xué)。作為一門邊緣學(xué)科，它有諸多的研究領(lǐng)域：專家系統(tǒng)、決策支持系統(tǒng)、機器學(xué)習(xí)、機器視覺、自然語言理解等等，計算機博弈也是其中 之 一，博弈就是對策，這是自然界中的普遍現(xiàn)象，它不僅存在于游戲、下棋之中，而且存在于政治、經(jīng)濟、軍事和生物競爭中，博弈的參加者可以是個人、集 體、一類生物和機器，他們都力圖用自己的智力去擊敗對手。主要是考慮到當(dāng)前網(wǎng)絡(luò)上流傳的五子棋游戲功能并不盡善盡美，其中最主要的問題就是人機對戰(zhàn)和網(wǎng)絡(luò)對戰(zhàn)沒有結(jié)合在一起實現(xiàn)；同時還存在游戲界面簡單、計算機智能水平不足、也沒有諸如保存棋譜和背景音樂等極有用的附加功能，所以不能吸引玩家興趣。象棋、圍棋等都屬于完全知識博弈。乙面對局面 2，又可以有 N 種可能的走法，形成 N 種新的局面K+1,K+2,?? K+N，如圖 所示。下棋者總是從當(dāng)前局面出發(fā)選擇最有利于自己的走法下一子，如甲在局面 1，他將從乙 乙 3 等局面中選擇最有利于自己的走法；同樣，乙在局面 2 時也從甲 甲 5 等局面中選擇最有利自己的走法?，F(xiàn)代五子棋日文稱之為“連珠”，英譯為“ Renju”，英文稱之為“ Gobang”或“ FIR”（ Five in a Row 的縮寫），亦有“連五子” 、 “五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。 現(xiàn)在世界上有許多五子棋的變種，在某種程度上，它們都是對棋手的限制，主要是抑制黑方先行者的優(yōu)勢。 （ 3）勝負(fù)判斷：網(wǎng)絡(luò)對弈時黑、白某方在橫、豎或斜方向上出現(xiàn)五子連珠時判該方勝。 T2300 ， 1GB 內(nèi)存， 60G 硬盤 ? Microsoft174。 2及以上處理器， 128M 以上內(nèi)存 ? Microsoft174。 第四章闡述 UI界面設(shè)計。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 5 頁 2 系統(tǒng)總體設(shè)計 系統(tǒng)架構(gòu) 智能 五子棋是使用 Visual Studio 2021 開發(fā)的基于對話框的 MFC 程序。邏輯上，網(wǎng)絡(luò)連接模塊與單機 AI 算法模塊相互獨立，而界面模塊則時時 負(fù)責(zé) 與這兩大模塊交互，接受用戶所有的消息以及 對 界面進行相應(yīng)輸出和更新。 網(wǎng)絡(luò) 連接 使用的 WinSock 版本號為 。因為客戶端在與服務(wù)器斷開后，自己也可以選擇做服務(wù)器，而原來的服務(wù)端也可以 迅速轉(zhuǎn)換角色，反過來做客戶端。如老板鍵功能，可以使程序“招之即來，揮之即去”。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計（論文） 第 7 頁 3 人機對弈中 AI的實現(xiàn) 數(shù)據(jù) 結(jié)構(gòu) 單機 AI 算法中用到的核心數(shù)據(jù) 結(jié)構(gòu) 總結(jié)為如下幾個 ： （ 1）程序包括一個 記錄 棋盤數(shù)據(jù)二維數(shù)組 BYTE m_FiveBoard[15][15]和一個走步記錄棧 std::vectorSTONEPOS m_vecStepList。 （ 2）用數(shù)字“ 0”和“ 1”來表示不同顏色的棋子，其中黑色棋子用“ 0”表示，白色棋子用“ 1”表示。 // 走法得分 } STONEMOVE。 m_nMoveCount = 0。 j GRID_NUM。 } } } // 為了提高剪枝效率 ,對走法隊列進行 (從大到小的 )排序 MergeSort_Desc( m_MoveList[nPly], m_nMoveCount )。 AlphaBeta 剪枝算法的效率與子結(jié)點擴展的先后順序相關(guān)，在最理想情況下，其生成的結(jié)點數(shù)目為： ND=2BD/21（ D為偶數(shù)） ND=2B（ D+1） /2+B(D1)/21 (D 為奇數(shù) ) 其中， B為 Branch Factor， D 為深度 由于不使用 AlphaBeta 剪枝算法時， ND=BD，所以最理想 情況下 AlphaBeta 算法搜索深度為 D 的結(jié)點數(shù)僅相當(dāng)于不使用 AlphaBeta 時搜索深度為 D/2 的結(jié)點數(shù)。 if( w == 0 ) return ( Evalutate(p) )。 i++ ) { t = AlpahBeta( pi, β, a )。 } 圖 NegaMax形式的 AlphaBeta類 C偽代碼 下圖 AlphaBeta剪枝實例圖： 圖 AlphaBeta剪枝實例圖 在上圖中，最左邊的分枝先以初始窗口（ ∞ ,∞）進行搜索。在對 E的左子 結(jié) 點完成遍歷后， Alpha值被調(diào)整為新值 7（ beta），因此 可以 對 E的右子 結(jié) 點 L進行（ Beta） 剪枝。 NegaScout 算法及 Minimal Window Minimal Window：是指窗口為 0的 Alpha、 Beta限制范圍，譬如 [N,N+1]，因為不可能存在一個整數(shù)既 大于 N又小于 N+1，所以這個范圍內(nèi)不可能存在真實結(jié)果。 在采用 Minimal Window的 NegaScout算法中，每次遞歸擴展的時候，第一個節(jié)點用正常的 AlphaBeta窗口擴展，而后面的都用 Minimal Window進行擴展，這樣的話如果說最優(yōu)的孩子結(jié)點最先擴展，則此后的其他孩子結(jié)點通過 Alpha值對應(yīng)的Minimal Window進行搜索都可以輕松剪枝，并且由于采用了 Minimal Window，AlphaBeta窗口縮到最小，剪枝也更容易，搜索節(jié)點也更少，反之，如果發(fā)現(xiàn)該擴展結(jié)點使用 Minimal Window不產(chǎn)生剪枝（ 即值小于 Beta），且值仍大于 Alpha，我們才用正常的 AlphaBet