【正文】 // 產(chǎn)生子節(jié)點(diǎn)的哈希值 Hash_MakeMove( amp。 a = alpha。 if( depth == m_nMaxDepth ) { // 在根節(jié)點(diǎn)設(shè)定進(jìn)度條 ( 0, count )。 if( depth 0 ) { i = IsGameOver( CurPosition, depth )。如何調(diào)整待展開的走法排列的順序，是提高搜索效率的關(guān)鍵。一般只有 Exact 類型，才可作為當(dāng)前結(jié)點(diǎn)的準(zhǔn)確值存入 Transposition Talbe，但 Fail High(=Beta)、 Fail Low(=Alpha)所對(duì)應(yīng)的邊界值仍可幫助我們作進(jìn)一步的剪枝，所以我們?cè)?Transposition Table用字段 entry_type表示 類型，其中 Exact類型為準(zhǔn)確值，其余的是表示值的范圍 [12]。在程序根部，作一次加總操作求出根節(jié)點(diǎn)的哈希值，當(dāng)搜索一個(gè)新 結(jié) 點(diǎn)時(shí)只要將該位置對(duì)應(yīng)的隨機(jī)數(shù) 和根 結(jié) 點(diǎn)哈希值相加即可。 置換表（ Transposition Table） 在一棵搜索樹中，不 少結(jié)點(diǎn)之間雖然是經(jīng)過不同的路徑到達(dá)的，但其狀態(tài)是完全一致的。amp。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 11 頁 for( i = 1。雖然當(dāng)無法 Beta Cutoff需要重新搜索的時(shí)候，實(shí)際比原來多出了 Minimal Window [Beta1,Beta]的搜索過程，但是由于 Minimal Window內(nèi)的子樹產(chǎn)生剪枝的概率比較大，所以實(shí)際增加的搜索結(jié)點(diǎn)數(shù)相對(duì)比較少，同時(shí)當(dāng)Move Ordering比較好的時(shí)候，大部分結(jié)點(diǎn)能夠產(chǎn)生 Beta剪枝的概率相當(dāng)大，這樣我們就可以避免更繁重的全 AlphaBeta窗口搜索。因 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）。 i = w。 AlphaBeta 算法通過下界（ Alpha）上界（ Beta）對(duì)搜索樹值的最終范圍進(jìn)行了劃定，當(dāng)某些子樹其值被證明會(huì)在上述界限之外，無法影響整顆樹的值時(shí)，便可進(jìn)行剪枝 [5]。 ++i ) 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 8 頁 { for( j = 0。 // 棋子位置 int score。系統(tǒng)特別重視出錯(cuò)處理，能夠?qū)Α靶涡紊钡腻e(cuò)誤 作出對(duì)應(yīng)的提示，避免在錯(cuò)誤發(fā)生以后，用戶不知所措，其中絕大多數(shù)錯(cuò)誤以ToolTip 的形式 呈現(xiàn) 給用戶。網(wǎng)絡(luò)通信基于客戶機(jī) /服務(wù)器（ Client/Server）模式，但它的工作方式卻更類似于 P2P[16]。 系統(tǒng)功能劃分 系統(tǒng)主體分為三大功能模塊：界面模塊、網(wǎng)絡(luò) 連接 模塊 及單機(jī) AI 算法模塊。 第三章重點(diǎn)講述人機(jī)對(duì)弈中的 AI，包括數(shù) 據(jù)結(jié)構(gòu)表示、走法產(chǎn)生、搜索算法以及估值核心。 Core174。它是中西文化的交流點(diǎn)，是古今哲理的結(jié)晶。 博弈樹最終的葉 結(jié) 點(diǎn)有甲贏乙輸，甲輸乙贏，甲乙平手三種。只要看看棋盤，就一清二楚。目前，各發(fā)達(dá)國家都把人工智能任務(wù)重點(diǎn)列入本國的高科技發(fā)展計(jì)劃當(dāng)中，投入巨大的人力和物力。作為一門邊緣學(xué)科，它有諸多的研究領(lǐng)域：專家系統(tǒng)、決策支持系統(tǒng)、機(jī)器學(xué)習(xí)、機(jī)器視覺、自然語言理解等等，計(jì)算機(jī)博弈也是其中 之 一，博弈就是對(duì)策，這是自然界中的普遍現(xiàn)象，它不僅存在于游戲、下棋之中，而且存在于政治、經(jīng)濟(jì)、軍事和生物競爭中，博弈的參加者可以是個(gè)人、集 體、一類生物和機(jī)器，他們都力圖用自己的智力去擊敗對(duì)手。象棋、圍棋等都屬于完全知識(shí)博弈。下棋者總是從當(dāng)前局面出發(fā)選擇最有利于自己的走法下一子，如甲在局面 1，他將從乙 乙 3 等局面中選擇最有利于自己的走法；同樣，乙在局面 2 時(shí)也從甲 甲 5 等局面中選擇最有利自己的走法。 現(xiàn)在世界上有許多五子棋的變種，在某種程度上，它們都是對(duì)棋手的限制，主要是抑制黑方先行者的優(yōu)勢。 T2300 ， 1GB 內(nèi)存， 60G 硬盤 ? Microsoft174。 第四章闡述 UI界面設(shè)計(jì)。邏輯上，網(wǎng)絡(luò)連接模塊與單機(jī) AI 算法模塊相互獨(dú)立，而界面模塊則時(shí)時(shí) 負(fù)責(zé) 與這兩大模塊交互，接受用戶所有的消息以及 對(duì) 界面進(jìn)行相應(yīng)輸出和更新。因?yàn)榭蛻舳嗽谂c服務(wù)器斷開后，自己也可以選擇做服務(wù)器，而原來的服務(wù)端也可以 迅速轉(zhuǎn)換角色，反過來做客戶端。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 7 頁 3 人機(jī)對(duì)弈中 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。 // 走法得分 } STONEMOVE。 j GRID_NUM。 AlphaBeta 剪枝算法的效率與子結(jié)點(diǎn)擴(kuò)展的先后順序相關(guān)，在最理想情況下，其生成的結(jié)點(diǎn)數(shù)目為： ND=2BD/21（ D為偶數(shù)） ND=2B（ D+1） /2+B(D1)/21 (D 為奇數(shù) ) 其中， B為 Branch Factor， D 為深度 由于不使用 AlphaBeta 剪枝算法時(shí)， ND=BD，所以最理想 情況下 AlphaBeta 算法搜索深度為 D 的結(jié)點(diǎn)數(shù)僅相當(dāng)于不使用 AlphaBeta 時(shí)搜索深度為 D/2 的結(jié)點(diǎn)數(shù)。 i++ ) { t = AlpahBeta( pi, β, a )。在對(duì) E的左子 結(jié) 點(diǎn)完成遍歷后， Alpha值被調(diào)整為新值 7（ beta），因此 可以 對(duì) E的右子 結(jié) 點(diǎn) L進(jìn)行（ Beta） 剪枝。 在采用 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值對(duì)應(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 = w。d maxdepth1) //FailHigh: a = NegaScout( pi, β, t )。通過建立 Transposition Table 保存已搜索結(jié)點(diǎn)的信息，那么再次遇到相同狀態(tài)的結(jié)點(diǎn)時(shí)便可以套用之前的搜索結(jié)果。當(dāng)對(duì)這個(gè)局面搜索完成后，再將搜索過程加上的值減去，就恢復(fù)了當(dāng)前 結(jié) 點(diǎn)的哈希值。 在搜索過程中，首先檢查 Transposition Table 中保存的結(jié)果能否直接代表當(dāng)前結(jié)點(diǎn)的值或使當(dāng)前結(jié)點(diǎn)產(chǎn)生 Alpha、 Beta 剪枝，不能的話則繼續(xù)進(jìn)行該結(jié)點(diǎn)的搜索。根據(jù)部分已經(jīng)搜索的結(jié)果來調(diào)整將要進(jìn)行搜索的 結(jié) 點(diǎn)順序是一個(gè)可行的方向。 if( i != 0 ) return i。 ( 1 )。 b = beta。m_MoveList[depth][i], CurPosition )。 // 設(shè)數(shù)據(jù)類型為精確值 if( depth == m_nMaxDepth ) // 保留最佳走法 m_cmBestMove = m_MoveList[depth][i]。 if( depth == m_nMaxDepth ) // 保存最佳走法 m_cmBestMove = m_MoveList[depth][i]。 if( eval_is_exact ) // 將搜索結(jié)果放進(jìn)置換表 EnterHashTable( EXACT, a, depth, 0 )。 在數(shù)學(xué)上，估值函數(shù)是對(duì)一個(gè)盤面定性的靜態(tài)評(píng)價(jià)，其計(jì)算方法為： EvaluationScore = ∑ KiFi(P)，其中 Ki為特征系數(shù)， Fi(P)為特征函數(shù)， P為當(dāng)前棋盤。如果有活四的棋型，返回極值。 棋子位置價(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} }。這就保證程序在特殊情況下不至于占用用戶寶貴的桌面空間。注冊(cè)表數(shù)據(jù)的讀取 在 CFiveDlg 的構(gòu)造函數(shù)中完成，而 寫入注冊(cè)表 則放在析構(gòu)函數(shù)中。 （ 4） CTabHCGameDlg（單機(jī)游戲頁面類） 該類的主要工作分為兩大塊。 消息傳遞圖 程序啟動(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è)置”對(duì)話框（見 小節(jié)）進(jìn)行選定和取消。事實(shí)上程序中大量使用的正是這種美觀的汽球提示控件 [19]，而不是煩人的 MessageBox。點(diǎn)出“列表管理”按鈕會(huì)彈出 小節(jié) 即將介紹的播放列表對(duì)話框。如果連續(xù)點(diǎn)擊“ ↑” 按鈕兩次 ， 播放列表就會(huì)立即自動(dòng)隱藏到屏幕上端了。 自然 智能 五子棋也少不了了（如圖 ）。 “ 整點(diǎn)報(bào)時(shí)”是模仿的“雪狐桌面精靈”，報(bào)時(shí)所用的 WAV 文件是從該軟件里 拷貝 過來的。 // 消息正文 TCHAR szText[128]。 圖 請(qǐng)求悔棋 同意悔棋消息 —— FM_AGREE_BACK 表明對(duì)方接受了玩家的悔棋請(qǐng)求，除 uID 成員外其余成員皆無效。接到這個(gè)消息后，雙方和棋。接到這個(gè)消息后，會(huì)彈出 MessageBox 詢問是否接受對(duì)方的請(qǐng)求（如圖 所示），并根據(jù)玩家的選擇回返 FM_AGREE_REPLAY消息 或直接斷開網(wǎng)絡(luò)，如果某一方斷開了網(wǎng)絡(luò) 連接 ，對(duì)方的主界面 上 提示如圖 所示 。在開始游戲的時(shí)候，由客戶端向服務(wù)端發(fā)送這條消息，服務(wù)端接到后設(shè)置對(duì)方的姓名， 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文）