【正文】 未來展望 在未來的 智能 五子棋改進(jìn)版本中，將會(huì)著重對(duì)并行搜索的研究。 服務(wù)端忙消息 —— FM_SERVER_BUSY 表明服務(wù)端現(xiàn)在正處于連接之中，不能接受連 接請(qǐng)求。 圖 再次開局 圖 對(duì)方離開 同意再玩一局消息 —— FM_AGREE_REPLAY 表明對(duì)方同意了再次 戰(zhàn)一局 的請(qǐng)求，除 uID 成員外其余成員皆無效。如果用戶設(shè)置了“聲音提示”，雙方系統(tǒng)會(huì)播放和棋音樂。接到這個(gè)消息后，將進(jìn)行正常的悔棋操作。 } FIVEMSG。 “總在最前端”將 智能 五子棋主界面置為 Topmost Window。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 22 頁 “防沉迷 3h”的意思是：如果用戶連續(xù)玩 智能 五子棋三小時(shí)而沒有關(guān)閉軟件，軟件會(huì)自動(dòng)彈出對(duì)話框，提示用戶該休息一會(huì)兒了；然后軟件進(jìn)入自鎖狀態(tài)，不接受用戶的任何請(qǐng)求，除非用戶將其關(guān)閉或五分鐘 讓 它自動(dòng)激活自 己。右邊的“ +”按鈕是用來添加或搜索磁盤音樂文件的，當(dāng) 然搜索是不能用主線程來完成的，否則在程序搜索的時(shí)間內(nèi)，用戶只能等待了。 （ 3）人機(jī)大戰(zhàn)頁面 在程序啟動(dòng)時(shí)，其上的某些元素是被 禁用的 。 圖 汽球提示 （ 2） 音樂頁面 用來控制背景音樂的播放、暫停、停止等功能。 圖 棋盤運(yùn)行效果 三大 Tab頁面 這三大 Tab 頁面 [21]是支撐起程序正常運(yùn)轉(zhuǎn)的核心部件 。玩過 五子棋的讀者一定不會(huì)對(duì)左邊的界面感到陌生。一是單機(jī)游戲處理：選擇棋子顏色、設(shè)定電腦搜索深度、開始 ，悔棋，認(rèn)輸，提示。菜單和熱鍵消息的響應(yīng)也由該類負(fù)責(zé)。 （ 3）程序盡可能地具有“記憶”功能。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 17 頁 4 界面的設(shè)計(jì)與實(shí)現(xiàn) 設(shè)計(jì)思想 UI 在一個(gè) Windows 程序中雖然算不上核心部件，但絕對(duì) 也 是重量級(jí)元素。如果輪到某一方落子，而此時(shí)某一方出現(xiàn)沖四棋型，返回極 值。也就是說估值函數(shù)分別對(duì)當(dāng)前棋盤的若干個(gè)特征進(jìn)行計(jì)算，獲得其特征值，所有這些特征值及其特征系數(shù)乘積的累加，得出最后的評(píng)價(jià)函數(shù)值。 else EnterHashTable( UPPER_BOUND, a, depth, 0 )。 } if( a = beta ) { // 將下邊界存入置換表 EnterHashTable( LOWER_BOUND, a, depth, 0 )。 bestmove = i。 // 遞歸搜索子節(jié)點(diǎn) ,對(duì)第個(gè)節(jié)點(diǎn)是全窗口 ,其后是空窗探測(cè) t = NegaScout_MIN( depth1, b, a )。 int eval_is_exact = 0。 } for( i = 0。 // 已分出勝負(fù) ,返回極值 } // 查詢置換表看是否有當(dāng)前節(jié)點(diǎn)的有效數(shù)據(jù) score = LookUpHashTable( alpha, beta, depth, 0 )。 在基于 AlphaBeta 的搜索中，一個(gè)好的走法可以定義如下 [4]： （ 1）由其產(chǎn)生的 結(jié) 點(diǎn)引發(fā)了剪枝。 Transposition Table 的作用： （ 1）如果在 Transposition Table 訪問中能直接得到結(jié)果的話，則可以避免該結(jié)點(diǎn)以下子樹的搜索，減少了搜索時(shí)間。這是根據(jù)兩次異或同一個(gè)數(shù)結(jié)果保持不變的原理，避免重新計(jì)算整個(gè)棋盤的 Hash 值，并且位的異或在計(jì)算機(jī)內(nèi)部運(yùn)算中速度極快。在 Transposition Table 中，記錄的信息為最優(yōu)著法、得分、深度等 。 // 重新搜索 //t位于空窗之外 a = max( a, t )。 i++ ) { t = NegaScout( pi, b, a )。 NegaScout算法偽代碼如下圖 [7]： int NegaScout( 局面 p。我們也可以將這個(gè)過程從負(fù)極大值觀點(diǎn)上看成是確定 min(6,max(7 ,L))或者是max(6,max(7,L))的值。 // 遞歸調(diào)用 .注意返回值取負(fù) a = max( a, t )。但在最壞的情況下， AlphaBeta 算法產(chǎn)生的結(jié)點(diǎn)數(shù)與極大極小算法完全一樣 [9]！ 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 9 頁 下圖 是 以 NegaMax 形式（每層之間更改 Alpha,Beta 值符號(hào)，使 Alpha 剪枝在代碼中也簡(jiǎn)化成 Beta 剪枝的形式表現(xiàn)出來）表現(xiàn)的 AlphaBeta 算法偽代碼 [7]： int AlphaBeta( 局面 p。 ++j ) { if( position[i][j] == NOSTONE ) { m_MoveList[nPly][m_nMoveCount]. = j。 走法產(chǎn)生 相對(duì)于象棋等游戲來說，五子棋的走法產(chǎn)生規(guī)則是十分簡(jiǎn)單的：棋盤上所有空白的位置都是合法的落子點(diǎn)（本論文并沒有討論禁手規(guī)則，詳見第一章 節(jié) 規(guī)則說明）。 m_FiveBoard 數(shù)組中存儲(chǔ)當(dāng)前棋盤格子落子顏色，而 m_vecStepList 存儲(chǔ)走步 STONEPOS 值，它主要用于支持悔棋功能。所以，在邏輯上可以說這種工作方式是類似于 P2P 的。 系統(tǒng)總體邏輯流程 關(guān)鍵技術(shù)點(diǎn) 通過對(duì) 系統(tǒng) 功能的分析和設(shè)計(jì)，在實(shí)現(xiàn)過程中需要解決如下幾個(gè)關(guān)鍵技術(shù)點(diǎn)： 系統(tǒng)啟動(dòng)運(yùn)行 用戶選擇游戲模式 單機(jī)版 網(wǎng)絡(luò)版 看棋譜 播放音樂 保存棋譜 兩人聊天 保存棋譜 播放音樂 游戲 結(jié)束 游戲結(jié)束 圖 系統(tǒng)流程圖 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 6 頁 AI算法 包括估值核心和 搜索算法 。主要包括界面設(shè)計(jì)思想和核心界面盤點(diǎn)。 Windows? XP Home ? Microsoft174。在本文中，并沒有涉及職業(yè)五子棋 中 對(duì)于黑方的禁手限制，而是討論通常的自由式的五子棋對(duì)弈。為了從很多的局面中選出最有利的，就需要一個(gè)搜索算法和一個(gè)對(duì)局面形勢(shì) 進(jìn)行 判斷的函數(shù)。要想實(shí)現(xiàn)人和計(jì)算機(jī)雙方對(duì) 弈，不妨假設(shè)人是甲方， 計(jì)算機(jī) 是乙方，人和計(jì)算機(jī)對(duì)弈的過程可以如下表達(dá)：假設(shè)首先由甲方走棋，他面對(duì)的是一個(gè)開 始局面 1，從這個(gè)局面可以有 M 種走法分別形成了局面 2， 3， ?? ， M+1。 作為人工智能研究的一個(gè)重要分支，計(jì)算機(jī)博弈是檢驗(yàn)人工智能發(fā)展水平的一個(gè)重要方面。它的中心任務(wù)是研究如何使計(jì)算機(jī)去做那些過去只能靠人的智力才能做的工作。 計(jì)算機(jī)博弈介紹 計(jì)算機(jī)五子棋對(duì)弈是一種完備信息博弈 [15]（ Games of Perfect Information），意思是指參與雙方在任何時(shí)候都完全清楚每一個(gè)棋子是否存在，位于何處。這樣甲乙雙方輪流下棋，棋盤局面發(fā)展變化就形成如圖 所示的一棵樹狀，通常稱為博弈樹。五子棋既有現(xiàn)代休閑的明顯特征“短、平 、快”，又有古典哲學(xué)的高深學(xué)問“陰陽易理”；它既有簡(jiǎn)單易學(xué)的特性，為人民群眾所喜聞樂見，又有深?yuàn)W的技巧和高水平的國際性比賽；它的棋文化源淵流長(zhǎng)，具有東方的神秘和西方的直觀；既有“場(chǎng)”的概念，亦有“點(diǎn)”的連接。 開發(fā)及運(yùn)行環(huán)境 開發(fā)環(huán)境 ? Intel174。 第二章 簡(jiǎn)略地 敘述 系統(tǒng) 的 總體設(shè)計(jì)。其中核心類 11 個(gè)，包括用于實(shí)現(xiàn)單機(jī) AI 算法的 4 個(gè)類： CEvaluation（估值核心）、 CHistoryHeuristic（歷史啟發(fā)增強(qiáng)）、 CTranspositionTable（置換表增強(qiáng)）和 CNegaScout_TT_HH（ 核心的 NegaScout 算法類）；用于實(shí)現(xiàn)網(wǎng)絡(luò)通信的CFiveSocket 類和用于用戶界面交互的 6 個(gè)類： CChessBoard（棋盤類）、 CFiveDlg（主對(duì)話框類）、 CMusic 類（音樂 類 ）、 CTabChatDlg（聊天頁面類）、 CTabHCGameDlg（單機(jī)游戲頁面類）和 CTabMusicDlg（迷你音樂播放器頁面類）。該類派生自 MFC的 CAsyncSocket類。棋譜的“靜默保存”模式，省去了用戶在每局棋結(jié)束之后，必須：點(diǎn)擊保存按鈕 設(shè)定文件名 點(diǎn)擊“確定”按鈕，這一系列煩瑣工作，程序在后臺(tái)靜靜地為用戶處理好了一切。這三個(gè)數(shù)值都有相應(yīng)的宏，以避免出差錯(cuò)： define BLACK 0 define WHITE 1 define NOSTONE 0xFF （ 3）搜索算法還用到了一個(gè)重要的走法結(jié)構(gòu)體 STONEMOVE typedef struct _tagStoneMove { STONEPOS stonePos。 i GRID_NUM。 // 返回合法走法的個(gè)數(shù) } 搜索算法 及增強(qiáng) 傳統(tǒng) AlphaBeta 算法介紹 在極大極小樹搜索的過程中，實(shí)際相當(dāng)一部分結(jié)點(diǎn)的搜索并不會(huì)影響最終搜索樹的值， Bruno 在 1963 年首先提出了 AlphaBeta 算法， 1975 年 Knuth 和 Moore 給出了 AlphaBeta 的數(shù)學(xué)正確性證明。 for( i = 1。在節(jié)點(diǎn) E， Alpha已經(jīng)被更新為 6了（因?yàn)?對(duì)結(jié)點(diǎn) B的左子 結(jié) 點(diǎn) D的遍歷 已經(jīng)完成 ）。 采用 Minimal Window的意義：如果搜索一個(gè)子結(jié)點(diǎn)的時(shí)候，當(dāng)其值大于 Beta，即產(chǎn)生 Beta剪枝的概率比較大的時(shí)候，我們可以先用 [Beta1,Beta]進(jìn)行搜索，如果搜索的結(jié)果 Fail High，即說明了結(jié)果 =Beta，這時(shí)我們可以立刻進(jìn)行 Beta剪枝，相反如果結(jié)點(diǎn) Fail Low，則說明結(jié)果不可能大于 Beta，也就是說無 法剪枝，那么我們剛才用 [Beta1,Beta]的 MinimalWindow就無法得到真實(shí)結(jié)果，所以我們必須重新用 [Alpha,Beta]進(jìn)行搜索。 b = β。 i 1amp。在后面的章節(jié)中將給出部分源代碼。對(duì)于搜索過程中的每一個(gè)結(jié)點(diǎn)， Zobrist 方法用增量式計(jì)算方法，無須每次都加總所有棋子。（ 3） Exact，Alpha=結(jié)點(diǎn)分值 =Beta，此值為準(zhǔn)確值。而在 結(jié) 點(diǎn)的排序最不理想的情況下， AlphaBeta 搜索要遍歷的結(jié)點(diǎn)數(shù)同極大極小算法一樣多。 int score。 } count = CreatePossibleMove( CurPosition, depth, 0 )。 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 14 頁 int bestmove = 1。m_MoveList[depth][i], 0 )。 i 0 ) // FAILHIGH: { a = NegaScout_MIN( depth1, beta, t )。 if( a t ) { // 第次搜索命中 eval_is_exact = 1。 /* 設(shè)置新 的空 窗 */ } if( bestmove != 1 ) // 將最佳走法匯入歷史記錄 EnterHistoryScore( amp。一般來說領(lǐng)域知識(shí)常以感性的形式存在，在計(jì)算機(jī)實(shí)現(xiàn)的過程中，則必須將其理性化，也就是說建立研究對(duì)象的數(shù)學(xué)模型。如果已五連，直接返回極值 （極值并不是真正數(shù)學(xué)意義上的無窮大 /小，在本系統(tǒng)中絕對(duì)值大于 8000 的數(shù)值看成是極值，下同） 。最后要指出的是，程序中用到的是負(fù)極大值形式的 AlphaBeta 搜索算法，因此為了所搜索算法正確動(dòng)作，估值函數(shù)對(duì)輪到誰下棋敏感。對(duì)用戶來說，這是非常不 友好的功能，因?yàn)樘鄶?shù)信息都不是特別地緊急，用戶完全有可能選擇忽略或者延后處理它們。從界面到功能，無 處不是 五子棋的影子。 （ 3） CTabChatDlg（聊天頁面類） 中國礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 18 頁 這個(gè)類主要負(fù)責(zé)處理網(wǎng)絡(luò)對(duì)戰(zhàn)過程中來自雙方的消息。 （ 6） CMusic（音樂類） 音樂播放實(shí)質(zhì)性的工作由該類承擔(dān)。特別是指示框：在 OnMouseMove函數(shù)中捕獲鼠標(biāo)當(dāng)前屏幕坐標(biāo)值 x, y，程序通過宏 DATA_X(x)和 DATA_Y(y)將當(dāng)前鼠標(biāo) 位置轉(zhuǎn) 換為棋盤坐標(biāo)值 x1， y1（ [0,