【正文】 14]數(shù)值），然后根據(jù)棋盤坐標(biāo)值確定指示框的十字交叉點(diǎn)的屏幕坐標(biāo)值（通過(guò) CUR_X(x1)和 CUR_Y(y1)宏 ） ，從而進(jìn)一步確定提示框四個(gè)角的坐標(biāo)值，最后根據(jù)這些坐標(biāo)值畫出 8 條紅線（長(zhǎng)度為 4Pixels，寬度為 1Pixel）。 Check 控件上面的發(fā)送按鈕不會(huì)允許用戶發(fā)送空消息，因?yàn)?空 消息會(huì)導(dǎo)致程序崩潰 ！ 如果用戶發(fā)送了空消息 ， 則會(huì)彈出 如 圖 所示的 汽球提示（ ToolTip 控件）。剩下的一些 Buttons、Check box、 Slider Volume Control就不 在此 詳細(xì)介紹 了。下面中間兩個(gè)分別是清空列表和顯示 /隱藏主面板。甚至是多個(gè)快捷方式也是支持的 [20]。 “更改玩家名字”對(duì)話框可以動(dòng)態(tài)地改變玩家名字，如果 是聯(lián)機(jī)狀態(tài)，同時(shí)通知對(duì)手將自己的名字顯示為最新。 各種消息說(shuō)明 網(wǎng)絡(luò)間傳遞的消息，都遵循以下一個(gè)結(jié)構(gòu)體的形式： 網(wǎng)絡(luò)數(shù)據(jù) CFiveSocket CFiveSocket::OnReceive CChessBoard::Receive 對(duì)各種消息分發(fā)處理 調(diào)用 CFiveSocket::Send 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 24 頁(yè) // 摘自 typedef struct _tagFiveMsg { // 消息 ID USHORT uID。接到 這個(gè)消息后，會(huì)彈出MessageBox 詢問(wèn)是否接受對(duì)方的請(qǐng)求（如圖 所示），并根據(jù)玩家的選擇回返FM_AGREE_BACK 或 FM_REFUSE_BACK 消息。另外，在發(fā)送這個(gè)消息之后，主界面上的某些元素將暫時(shí)不響應(yīng)用戶的操作。如果用戶了“聲音提示”，系統(tǒng)為勝利方播放贏棋音樂(lè)，為 認(rèn)輸方 播放輸棋音樂(lè)。接到這個(gè)信息后，會(huì)將對(duì)方選擇了列表框某項(xiàng)文本內(nèi)容顯示在主對(duì)話框的聊天記錄窗口內(nèi)，同時(shí)如果 szText[1]為 1，系統(tǒng)將用聲音讀出該文本的內(nèi)容，這里所用到的聲音 WAV 文件是從 游戲 的斗地主目錄里 拷貝 過(guò)來(lái)的。通過(guò)個(gè)人較長(zhǎng)時(shí)間對(duì)軟件的測(cè)試來(lái)看，運(yùn)行效果還是不錯(cuò)的 ，基本上達(dá)到了自己預(yù)定的許多目標(biāo)。此外， 將來(lái)還 可以考慮加入開局庫(kù)（ Opening Book） 和殘局庫(kù)（ Endgame Database），來(lái)進(jìn)一步加 快 程序的運(yùn)行速度。連接者收到 FM_SERVER_BUSY 消息后，在主界面提示如圖 所示。接到這個(gè)信息后，會(huì)將對(duì)方聊天的內(nèi)容顯示在主對(duì)話框的聊天記錄窗口內(nèi)。 圖 拒絕和棋 認(rèn)輸消息 —— FM_GIVEUP 表明對(duì)方已經(jīng)投子認(rèn)輸（如圖 和 所示），除 uID 成員外其余成員皆無(wú)效。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 25 頁(yè) 圖 拒絕悔棋 請(qǐng)求和棋消息 —— FM_REQUEST_DRAW 表明對(duì)方請(qǐng)求和棋，除 uID 成員外其余成員皆無(wú)效。注意：對(duì)方棋子顏色無(wú)需傳送，因?yàn)槌绦蛞?guī)則是執(zhí)黑者先行，以后每下一局，雙方交換先后手和棋子顏色。 消息機(jī)制的架構(gòu) 當(dāng)繼承自 CAsyncSocket 的套接字類 CFiveSocket 收到消息時(shí)，會(huì)觸發(fā)CFiveSocket::OnReceive 事件，這個(gè)事件里調(diào)用 CChessBoard::Receive， 該函數(shù)開始按照自定義的消息格式接收套接字發(fā)送的數(shù)據(jù)，并對(duì)不同的消息類型進(jìn)行分發(fā)處理 [3]。在 該“設(shè)置”對(duì)話框里，幾乎所有的選項(xiàng) 都對(duì)應(yīng)著一個(gè)注冊(cè)表項(xiàng)值，當(dāng)用戶退出程序后，程序會(huì)自動(dòng)調(diào)用類的析構(gòu)函數(shù)將用戶最后一次設(shè)置寫入注冊(cè)表，以保證程序下一次啟動(dòng)時(shí)，能夠讀出注冊(cè)表值將軟件設(shè)置為和上次一致。 這個(gè)對(duì)話框當(dāng)然 也 少不了支持拖放功能 的 ，而且支持更加強(qiáng)大的拖放功能。 播放列表對(duì)話框 播放 列表（如圖 ）主要用于對(duì)背景音樂(lè)的快捷管理 [18]。標(biāo)題和路徑信息欄可能會(huì)遇到文件名過(guò)長(zhǎng)而省略的情況（見圖 路徑欄后面的省略號(hào)），如果 文字 有省略，用戶只需將鼠標(biāo)移動(dòng)到相應(yīng)的信息欄，程序即會(huì)在它們的上面用 ToolTip 控件彈出包含完整信息的提示。它主要包括一個(gè)聊天顯示框（用程序術(shù)語(yǔ)說(shuō)是一個(gè) Edit 控件 ） 、一個(gè)聊天輸入框（ Combobox 控件 ） 和一些按鈕（ Button 控件 ） 。棋盤和棋子相對(duì)來(lái)說(shuō)是 繪制比較容易， 直接位圖 拷貝 就 可以 了。 強(qiáng)大的背景音樂(lè)支持大部分工作與該類相關(guān)。包括清 空 棋盤、設(shè)置 游戲模式（單機(jī) 或 網(wǎng)絡(luò)）、畫棋子，坐標(biāo)，數(shù)字，跟隨框，十字形提示、響應(yīng)右鍵彈出菜單消息等等。 （ 4）程序支持類似 Windows 系統(tǒng)的拖放功能（鼠標(biāo)大顯身手之地！），可以更好地 體現(xiàn) 和用戶 的 交互 性 。 智能 五子棋界面設(shè)計(jì)思想主要有如下幾點(diǎn)： （ 1）盡量少用模態(tài)對(duì)話框，大量使用非模態(tài)對(duì)話框。如果沒有返回極值，則對(duì)所有眠三加 10，所有活三加 4，所有眠二加 1。具體的過(guò)程如下：對(duì)棋盤上所有棋子在水平、垂直、左斜和右斜方向上進(jìn)行分析。更高的目標(biāo)結(jié)點(diǎn)估值函數(shù)值是搜索樹所追求的目標(biāo)，與研究對(duì)象變化規(guī)律越接近的估值函數(shù)，由越能反映未來(lái)局勢(shì)的變化。 return a。 // 撤銷子節(jié)點(diǎn) UnMakeMove( amp。 t beta amp。 ++i ) { if( depth == m_nMaxDepth ) ( )。m_MoveList[depth][i] )。 // 將估值存入置換表 EnterHashTable( EXACT, score, depth, 0 )。 本 系 統(tǒng) 在實(shí) 現(xiàn) 時(shí)使 用 NegaScout 算法 并 配 合 上面 介 紹過(guò) 的 置換 表（ Transposition Table） 和歷史啟發(fā)（ History Heuristic） 增強(qiáng) ，核心搜索算法源代碼 如下 [613]： 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 13 頁(yè) // 主調(diào)例程必須將 alpha設(shè)為 COMP_LOSS,將 beta設(shè)為 COMP_WIN int CNegaScout_TT_HH::NegaScout_MAX( int depth, int alpha, int beta ) { // 用于偶數(shù)層 (從算起 ) int count, i。在節(jié)點(diǎn)排列順序處于理想狀態(tài)的情況下，AlphaBeta 搜索需要遍歷的節(jié)點(diǎn)數(shù)僅為極大極小算法所需遍歷的 結(jié) 點(diǎn)數(shù)的平方根的兩倍左右。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 12 頁(yè) Transposition Table 結(jié)合 AlphaBeta 搜索：在 AlphaBeta 搜索的過(guò)程中，一個(gè)結(jié) 點(diǎn)會(huì)出現(xiàn)以下三種情況之一： （ 1） Fail High，結(jié)點(diǎn)值至少 =Beta，但不知道其具體值。然后，將此數(shù)組中填滿隨機(jī)數(shù)。 // 設(shè)置新的空窗 } return ( a )。 t β amp。 if( w == 0 ) return ( Evalutate(p) )。 NegaScout 算法及 Minimal Window Minimal Window：是指窗口為 0的 Alpha、 Beta限制范圍，譬如 [N,N+1]，因?yàn)椴豢赡艽嬖谝粋€(gè)整數(shù)既 大于 N又小于 N+1，所以這個(gè)范圍內(nèi)不可能存在真實(shí)結(jié)果。 } 圖 NegaMax形式的 AlphaBeta類 C偽代碼 下圖 AlphaBeta剪枝實(shí)例圖： 圖 AlphaBeta剪枝實(shí)例圖 在上圖中，最左邊的分枝先以初始窗口（ ∞ ,∞）進(jìn)行搜索。 if( w == 0 ) return ( Evalutate(p) )。 } } } // 為了提高剪枝效率 ,對(duì)走法隊(duì)列進(jìn)行 (從大到小的 )排序 MergeSort_Desc( m_MoveList[nPly], m_nMoveCount )。 m_nMoveCount = 0。 （ 2）用數(shù)字“ 0”和“ 1”來(lái)表示不同顏色的棋子，其中黑色棋子用“ 0”表示，白色棋子用“ 1”表示。如老板鍵功能，可以使程序“招之即來(lái)，揮之即去”。 網(wǎng)絡(luò) 連接 使用的 WinSock 版本號(hào)為 。 中國(guó)礦業(yè)大學(xué) 2021 屆本科生畢業(yè)設(shè)計(jì)（論文） 第 5 頁(yè) 2 系統(tǒng)總體設(shè)計(jì) 系統(tǒng)架構(gòu) 智能 五子棋是使用 Visual Studio 2021 開發(fā)的基于對(duì)話框的 MFC 程序。 2及以上處理器， 128M 以上內(nèi)存 ? Microsoft174。 （ 3）勝負(fù)判斷：網(wǎng)絡(luò)對(duì)弈時(shí)黑、白某方在橫、豎或斜方向上出現(xiàn)五子連珠時(shí)判該方勝。現(xiàn)代五子棋日文稱之為“連珠”，英譯為“ Renju”，英文稱之為“ Gobang”或“ FIR”（ Five in a Row 的縮寫），亦有“連五子” 、 “五子連”、“串珠”、“五目”、“五目碰”、“五格”等多種稱謂。乙面對(duì)局面 2，又可以有 N 種可能的走法，形成 N 種新的局面K+1,K+2,?? K+N，如圖 所示。主要是考慮到當(dāng)前網(wǎng)絡(luò)上流傳的五子棋游戲功能并不盡善盡美，其中最主要的問(wèn)題就是人機(jī)對(duì)戰(zhàn)和網(wǎng)絡(luò)對(duì)戰(zhàn)沒有結(jié)合在一起實(shí)現(xiàn)；同時(shí)還存在游戲界面簡(jiǎn)單、計(jì)算機(jī)智能水平不足、也沒有諸如保存棋譜和背景音樂(lè)等極有用的附加功能，所以不能吸引玩家興趣。 目 錄 1 緒論 .......................................................... 1 選題背景 .................................................. 1 計(jì)算機(jī)博弈介紹 ............................................ 1 五子棋基本知識(shí)介紹 ........................................ 3 開發(fā)及運(yùn)行環(huán)境 ............................................ 3 開發(fā)環(huán)境 .............................................. 3 運(yùn)行環(huán)境 .............................................. 3 本文結(jié)構(gòu) .................................................. 3 2 系統(tǒng)總體設(shè)計(jì) .................................................. 5 系統(tǒng)架構(gòu) .................................................. 5 系統(tǒng)功能劃分 .............................................. 5 系統(tǒng)總體邏輯流程 .......................................... 5 關(guān)鍵技術(shù)點(diǎn) ................................................ 5 AI 算法 ............................................... 6 界面生成 .............................................. 6 網(wǎng)絡(luò)連接 .............................................. 6 系統(tǒng)交互性 ............................................ 6 3 人機(jī)對(duì)弈中 AI 的實(shí)現(xiàn) ........................................... 7 數(shù)據(jù) 結(jié)構(gòu) .................................................. 7 走法產(chǎn)生 .................................................. 7 搜索算法 及增強(qiáng) ............................................ 8 傳統(tǒng) AlphaBeta 算法介紹 ............................... 8 NegaScout 算法及 Minimal Window..................... 10 置換表（ Transposition Table） ..................... 11 歷史啟發(fā)（ History Heuristic） ..................... 12 估值函數(shù) ................................................. 15