【正文】 圖 服務(wù)端忙 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 28 頁 6 總結(jié)和展望 總結(jié) 本文 論述了五子棋程序“ 智能 五子棋”的設(shè)計(jì)與實(shí)現(xiàn)的方法與原理。接到這個(gè)消息后，整個(gè)界面將轉(zhuǎn)換為勝利后的狀態(tài)。 請求悔棋消息 —— FM_REQUEST_BACK 表明對方請求悔棋，除 uID 成員外其余成員皆無效。 圖 設(shè)置對話框 其它 UI 元素 “關(guān)于”對話框唯一值得一提的地方是它退出時(shí) 是 動(dòng)畫效果 （ 它不是立即消失，而是“淡出”效果 ） 。上面的四個(gè)和下面左邊第一個(gè)按鈕是只是簡單的調(diào)用前面 音樂頁面的 相應(yīng)按鈕函數(shù)罷了。圖 右下角的 Check 控件是用來控制是否用語音向?qū)Ψ桨l(fā)送聊天輸入框自帶的聊天信息。包括顯示播放中歌曲信息、播放模式設(shè)定、音量控制、列表管理等等。 （ 5）程序“大規(guī)?！钡啬７? 五子棋游戲。最后雙方棋子價(jià)值都加上棋子位置價(jià)值表（如 下表 所示）。由于大部分研究對象不存在絕對準(zhǔn)確體現(xiàn)最終結(jié)果的估值函數(shù)，所以使估值函數(shù)值盡量能刻 畫 研究對象是估值函數(shù)的主要目標(biāo)，這就需要大量的領(lǐng)域相關(guān)的知識(shí)。m_MoveList[depth][i] )。 // 走進(jìn)度條 // 走子節(jié)點(diǎn) MakeMove( amp。 return score。也就是說對一棵極大極小樹來說，如果極大極小搜索需遍歷 106 個(gè) 結(jié)點(diǎn)求得結(jié)果，那么處于理想狀態(tài)的 AlphaBeta 搜索僅需遍歷 約 2021 個(gè) 結(jié) 點(diǎn)就可求得結(jié)果。若要求某一局面的哈希值，則將棋盤上所有棋子在數(shù)組 Z 中對應(yīng)的隨機(jī)數(shù)相加，即可得到。amp。同時(shí)因 Minimal Window的 Alpha、 Beta限制范圍最小，所以產(chǎn)生剪枝的概率也比正常的搜索窗口的大 [10]。 // 葉結(jié)點(diǎn)返回估值 a = α。 for( i = 0。棋盤右鍵快捷菜單可以使用戶迅速地對相應(yīng)功能進(jìn)行設(shè)置。本程序由 37 個(gè)類、 6 個(gè)結(jié)構(gòu)體、 12 個(gè)全局函數(shù)以及若干其它變量、枚舉類型、宏等組成。人機(jī)對弈時(shí)由于估值函數(shù)的特殊性，計(jì)算機(jī)只要發(fā)現(xiàn)某方局面估值的絕對值大于 8000 即判該方勝（如活三、沖四等棋型出現(xiàn)時(shí)，系統(tǒng)可能就提示游戲結(jié)束了 ） 。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 2 頁 如果甲選擇形成局面 3， 4， ?? ， N+1 走法，乙方都對應(yīng)有若干種走法。它與生物工程、空間技術(shù)一起被并列為二十一世紀(jì)三大尖端技術(shù)。如圖 。 本論文中五子棋基本規(guī)則如下： （ 1）棋盤：采用國際上標(biāo)準(zhǔn)的 15*15 路線的正方形 棋盤。 第五章討論聯(lián)機(jī)功能的實(shí)現(xiàn)，核心技術(shù)在于五子棋消息系統(tǒng)。因?yàn)橥ㄐ烹p方既可以做服務(wù)端也可以做客戶端。搜索類 CNegaScout_TT_HH的 CreatePossibleMove函數(shù)用來完成走法產(chǎn)生 [4]。 int α, int β ) { // 計(jì)算局面 p的的極大極小值 int a, t, i。不管 L的值是多少，我們獲得的值總是 6， 或者用負(fù)極大值形式來說 6。 // 遞歸調(diào)用 .注意返回值取負(fù) if(t 1amp。 為了快速檢測當(dāng)前結(jié)點(diǎn)是否已經(jīng)搜索過，我們一般對當(dāng)前狀態(tài)進(jìn)行編碼，然后利用 Hash 表的方式進(jìn)行查找，這里采用的編碼方式是 Zobrist Hash 方法 [13]。 （ 2）如果在 Transposition Table 中能查找到當(dāng)前結(jié)點(diǎn)信息，并且存儲(chǔ)深度比當(dāng)前結(jié)點(diǎn)大， 那么實(shí)際上是增加了當(dāng)前子樹的搜索深度，也即增加了結(jié)果的準(zhǔn)確性。 if( score != 66666 ) return score。 for( i = 0。 // 記住最佳走法的位置 } // 恢復(fù)當(dāng)前節(jié)點(diǎn)的哈希值 Hash_UnMakeMove( amp。 return a。如果有沖四和活三的棋型，返回極值。即用戶當(dāng)前對程序某個(gè)功能進(jìn)行設(shè)定以后，程序假設(shè)用戶下次仍然對這個(gè)設(shè)定感興趣而記住當(dāng)前設(shè)定。二是棋譜管理：保存本局棋譜及載入并 播放 歷史棋譜。它們分別是：聊天頁面（如圖 ）、音樂頁面（如圖 ）和人機(jī)大戰(zhàn)頁面（如圖 ）。這個(gè)頁面相當(dāng)簡潔而且selfexplanatory。老板 鍵 也是游戲必備之 功能。 隨著 uID 表示 消息 ID， stonePos(有 x,y 兩個(gè)成員 )表示落子坐標(biāo) ， szText 隨著 uID 的不同而有不同的含義。 圖 同意和棋 拒絕和棋消息 —— FM_REFUSE_DRAW 表明對方拒絕了玩家的和棋請求（如圖 所示），除 uID 成員外其余成員皆無效。因?yàn)槲遄悠迨嵌擞螒颍苑?wù)端同時(shí)只能和一位玩家連接。 我知道這一切只要自己程序員時(shí)代的起點(diǎn)，我希望以后做得越來越好，寫出更多優(yōu)秀的軟件。接到這個(gè)消息后，會(huì)彈出 MessageBox 詢問是否接受對方的請求（如圖 所示），并根據(jù)玩家的選擇回返 FM_AGREE_REPLAY消息 或直接斷開網(wǎng)絡(luò)，如果某一方斷開了網(wǎng)絡(luò) 連接 ，對方的主界面 上 提示如圖 所示 。 圖 請求悔棋 同意悔棋消息 —— FM_AGREE_BACK 表明對方接受了玩家的悔棋請求，除 uID 成員外其余成員皆無效。 “ 整點(diǎn)報(bào)時(shí)”是模仿的“雪狐桌面精靈”，報(bào)時(shí)所用的 WAV 文件是從該軟件里 拷貝 過來的。如果連續(xù)點(diǎn)擊“ ↑” 按鈕兩次 ， 播放列表就會(huì)立即自動(dòng)隱藏到屏幕上端了。事實(shí)上程序中大量使用的正是這種美觀的汽球提示控件 [19]，而不是煩人的 MessageBox。 消息傳遞圖 程序啟動(dòng)運(yùn)行 程序界面初始化 CFiveDlg::OnInitDialog 單機(jī) 等待中 ... 音樂 網(wǎng)絡(luò) 播放 CMusic::Play 用戶選擇 游戲初始化 CGame::InitGame CGame::BeforeStart Replay 結(jié)束 玩家落子 CChessBoard::OnPaint 游戲結(jié)束 CGame::Over 保存棋譜 Auto/Manually? 界面更新 ClearBoard/Score 退出 圖 消息傳遞圖 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 19 頁 主體界面 棋盤、棋子、指 示十字形和提示框 這些元素（如圖 ） 顯然都是程序運(yùn)行的基本“面子工程”。注冊表數(shù)據(jù)的讀取 在 CFiveDlg 的構(gòu)造函數(shù)中完成，而 寫入注冊表 則放在析構(gòu)函數(shù)中。 棋子位置價(jià)值表 如下： int g_arrPosValue[GRID_NUM][GRID_NUM] = { {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0}, {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0}, {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0}, {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0}, {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0}, {0,1,2,3,4,5,6,7,6,5,4,3,2,1,0}, {0,1,2,3,4,5,6,6,6,5,4,3,2,1,0}, {0,1,2,3,4,5,5,5,5,5,4,3,2,1,0}, {0,1,2,3,4,4,4,4,4,4,4,3,2,1,0}, {0,1,2,3,3,3,3,3,3,3,3,3,2,1,0}, {0,1,2,2,2,2,2,2,2,2,2,2,2,1,0}, {0,1,1,1,1,1,1,1,1,1,1,1,1,1,0}, {0,0,0,0,0,0,0,0,0,0,0,0,0,0,0} }。 在數(shù)學(xué)上，估值函數(shù)是對一個(gè)盤面定性的靜態(tài)評價(jià)，其計(jì)算方法為： EvaluationScore = ∑ KiFi(P)，其中 Ki為特征系數(shù)， Fi(P)為特征函數(shù)， P為當(dāng)前棋盤。 if( depth == m_nMaxDepth ) // 保存最佳走法 m_cmBestMove = m_MoveList[depth][i]。m_MoveList[depth][i], CurPosition )。 ( 1 )。根據(jù)部分已經(jīng)搜索的結(jié)果來調(diào)整將要進(jìn)行搜索的 結(jié) 點(diǎn)順序是一個(gè)可行的方向。當(dāng)對這個(gè)局面搜索完成后，再將搜索過程加上的值減去，就恢復(fù)了當(dāng)前 結(jié) 點(diǎn)的哈希值。d maxdepth1) //FailHigh: a = NegaScout( pi, β, t )。 在采用 Minimal Window的 NegaScout算法中，每次遞歸擴(kuò)展的時(shí)候，第一個(gè)節(jié)點(diǎn)用正常的 AlphaBeta窗口擴(kuò)展，而后面的都用 Minimal Window進(jìn)行擴(kuò)展，這樣的話如果說最優(yōu)的孩子結(jié)點(diǎn)最先擴(kuò)展，則此后的其他孩子結(jié)點(diǎn)通過 Alpha值對應(yīng)的Minimal Window進(jìn)行搜索都可以輕松剪枝，并且由于采用了 Minimal Window，AlphaBeta窗口縮到最小，剪枝也更容易，搜索節(jié)點(diǎn)也更少，反之，如果發(fā)現(xiàn)該擴(kuò)展結(jié)點(diǎn)使用 Minimal Window不產(chǎn)生剪枝（ 即值小于 Beta），且值仍大于 Alpha，我們才用正常的 AlphaBeta窗口進(jìn)行再搜索 (research)。 i++ ) { t = AlpahBeta( pi, β, a )。 j GRID_NUM。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 7 頁 3 人機(jī)對弈中 AI的實(shí)現(xiàn) 數(shù)據(jù) 結(jié)構(gòu) 單機(jī) AI 算法中用到的核心數(shù)據(jù) 結(jié)構(gòu) 總結(jié)為如下幾個(gè) ： （ 1）程序包括一個(gè) 記錄 棋盤數(shù)據(jù)二維數(shù)組 BYTE m_FiveBoard[15][15]和一個(gè)走步記錄棧 std::vectorSTONEPOS m_vecStepList。邏輯上，網(wǎng)絡(luò)連接模塊與單機(jī) AI 算法模塊相互獨(dú)立，而界面模塊則時(shí)時(shí) 負(fù)責(zé) 與這兩大模塊交互，接受用戶所有的消息以及 對 界面進(jìn)行相應(yīng)輸出和更新。 T2300 ， 1GB 內(nèi)存， 60G 硬盤 ? Microsoft174。下棋者總是從當(dāng)前局面出發(fā)選擇最有利于自己的走法下一子，如甲在局面 1，他將從乙 乙 3 等局面中選擇最有利于自己的走法；同樣，乙在局面 2 時(shí)也從甲 甲 5 等局面中選擇最有利自己的走法。作為一門邊緣學(xué)科，它有諸多的研究領(lǐng)域：專家系統(tǒng)、決策支持系統(tǒng)、機(jī)器學(xué)習(xí)、機(jī)器視覺、自然語言理解等等，計(jì)算機(jī)博弈也是其中 之 一，博弈就是對策，這是自然界中的普遍現(xiàn)象，它不僅存在于游戲、下棋之中，而且存在于政治、經(jīng)濟(jì)、軍事和生物競爭中，博弈的參加者可以是個(gè)人、集 體、一類生物和機(jī)器，他們都力圖用自己的智力去擊敗對手。只要看看棋盤，就一清二楚。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。 第三章重點(diǎn)講述人機(jī)對弈中的 AI，包括數(shù) 據(jù)結(jié)構(gòu)表示、走法產(chǎn)生、搜索算法以及估值核心。網(wǎng)絡(luò)通信基于客戶機(jī) /服務(wù)器（ Client/Server）模式，但它的工作方式卻更類似于 P2P[16]。 // 棋子位置 int score。 AlphaBeta 算法通過下界（ Alpha）上界（ Beta）對搜索樹值的最終范圍進(jìn)行了劃定，當(dāng)某些子樹其值被證明會(huì)在上述界限之外，無法影響整顆樹的值時(shí)，便可進(jìn)行剪枝 [5]。因 6 6 7 4 極小值結(jié)點(diǎn) A (∞ , ∞ ) (∞ , 6) B C 5 3 7 1 4 2 6 6 4 F G E D L (∞ , ∞ ) (∞ ,∞ ) (∞ , 6) (∞ , 6) (∞ , 6) Beta 剪枝 (6, ∞ ) Alpha 剪枝 (∞ , 6) (∞ , 6) (∞ , 6) 極大值結(jié)點(diǎn) 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 10 頁 此 B的右子 結(jié) 點(diǎn) E的搜索窗口為（ ∞ ,6）。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文）