【正文】 a窗口進行再搜索 (research)。 if( w == 0 ) return ( Evalutate(p) )。 i = w。 t β amp。d maxdepth1) //FailHigh: a = NegaScout( pi, β, t )。 // 設置新的空窗 } return ( a )。通過建立 Transposition Table 保存已搜索結(jié)點的信息，那么再次遇到相同狀態(tài)的結(jié)點時便可以套用之前的搜索結(jié)果。然后，將此數(shù)組中填滿隨機數(shù)。當對這個局面搜索完成后，再將搜索過程加上的值減去，就恢復了當前 結(jié) 點的哈希值。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 12 頁 Transposition Table 結(jié)合 AlphaBeta 搜索：在 AlphaBeta 搜索的過程中，一個結(jié) 點會出現(xiàn)以下三種情況之一： （ 1） Fail High，結(jié)點值至少 =Beta，但不知道其具體值。 在搜索過程中，首先檢查 Transposition Table 中保存的結(jié)果能否直接代表當前結(jié)點的值或使當前結(jié)點產(chǎn)生 Alpha、 Beta 剪枝，不能的話則繼續(xù)進行該結(jié)點的搜索。在節(jié)點排列順序處于理想狀態(tài)的情況下，AlphaBeta 搜索需要遍歷的節(jié)點數(shù)僅為極大極小算法所需遍歷的 結(jié) 點數(shù)的平方根的兩倍左右。根據(jù)部分已經(jīng)搜索的結(jié)果來調(diào)整將要進行搜索的 結(jié) 點順序是一個可行的方向。 本 系 統(tǒng) 在實 現(xiàn) 時使 用 NegaScout 算法 并 配 合 上面 介 紹過 的 置換 表（ Transposition Table） 和歷史啟發(fā)（ History Heuristic） 增強 ，核心搜索算法源代碼 如下 [613]： 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 13 頁 // 主調(diào)例程必須將 alpha設為 COMP_LOSS,將 beta設為 COMP_WIN int CNegaScout_TT_HH::NegaScout_MAX( int depth, int alpha, int beta ) { // 用于偶數(shù)層 (從算起 ) int count, i。 if( i != 0 ) return i。 // 將估值存入置換表 EnterHashTable( EXACT, score, depth, 0 )。 ( 1 )。m_MoveList[depth][i] )。 b = beta。 ++i ) { if( depth == m_nMaxDepth ) ( )。m_MoveList[depth][i], CurPosition )。 t beta amp。 // 設數(shù)據(jù)類型為精確值 if( depth == m_nMaxDepth ) // 保留最佳走法 m_cmBestMove = m_MoveList[depth][i]。 // 撤銷子節(jié)點 UnMakeMove( amp。 if( depth == m_nMaxDepth ) // 保存最佳走法 m_cmBestMove = m_MoveList[depth][i]。 return a。 if( eval_is_exact ) // 將搜索結(jié)果放進置換表 EnterHashTable( EXACT, a, depth, 0 )。更高的目標結(jié)點估值函數(shù)值是搜索樹所追求的目標，與研究對象變化規(guī)律越接近的估值函數(shù)，由越能反映未來局勢的變化。 在數(shù)學上，估值函數(shù)是對一個盤面定性的靜態(tài)評價，其計算方法為： EvaluationScore = ∑ KiFi(P)，其中 Ki為特征系數(shù)， Fi(P)為特征函數(shù)， P為當前棋盤。具體的過程如下：對棋盤上所有棋子在水平、垂直、左斜和右斜方向上進行分析。如果有活四的棋型，返回極值。如果沒有返回極值，則對所有眠三加 10，所有活三加 4，所有眠二加 1。 棋子位置價值表 如下： 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} }。 智能 五子棋界面設計思想主要有如下幾點： （ 1）盡量少用模態(tài)對話框，大量使用非模態(tài)對話框。這就保證程序在特殊情況下不至于占用用戶寶貴的桌面空間。 （ 4）程序支持類似 Windows 系統(tǒng)的拖放功能（鼠標大顯身手之地?。梢愿玫?體現(xiàn) 和用戶 的 交互 性 。注冊表數(shù)據(jù)的讀取 在 CFiveDlg 的構(gòu)造函數(shù)中完成，而 寫入注冊表 則放在析構(gòu)函數(shù)中。包括清 空 棋盤、設置 游戲模式（單機 或 網(wǎng)絡）、畫棋子，坐標，數(shù)字，跟隨框，十字形提示、響應右鍵彈出菜單消息等等。 （ 4） CTabHCGameDlg（單機游戲頁面類） 該類的主要工作分為兩大塊。 強大的背景音樂支持大部分工作與該類相關。 消息傳遞圖 程序啟動運行 程序界面初始化 CFiveDlg::OnInitDialog 單機 等待中 ... 音樂 網(wǎng)絡 播放 CMusic::Play 用戶選擇 游戲初始化 CGame::InitGame CGame::BeforeStart Replay 結(jié)束 玩家落子 CChessBoard::OnPaint 游戲結(jié)束 CGame::Over 保存棋譜 Auto/Manually? 界面更新 ClearBoard/Score 退出 圖 消息傳遞圖 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 19 頁 主體界面 棋盤、棋子、指 示十字形和提示框 這些元素（如圖 ） 顯然都是程序運行的基本“面子工程”。棋盤和棋子相對來說是 繪制比較容易， 直接位圖 拷貝 就 可以 了。這些效果都可以通過“設置”對話框（見 小節(jié)）進行選定和取消。它主要包括一個聊天顯示框（用程序術(shù)語說是一個 Edit 控件 ） 、一個聊天輸入框（ Combobox 控件 ） 和一些按鈕（ Button 控件 ） 。事實上程序中大量使用的正是這種美觀的汽球提示控件 [19]，而不是煩人的 MessageBox。標題和路徑信息欄可能會遇到文件名過長而省略的情況（見圖 路徑欄后面的省略號），如果 文字 有省略，用戶只需將鼠標移動到相應的信息欄，程序即會在它們的上面用 ToolTip 控件彈出包含完整信息的提示。點出“列表管理”按鈕會彈出 小節(jié) 即將介紹的播放列表對話框。 播放列表對話框 播放 列表（如圖 ）主要用于對背景音樂的快捷管理 [18]。如果連續(xù)點擊“ ↑” 按鈕兩次 ， 播放列表就會立即自動隱藏到屏幕上端了。 這個對話框當然 也 少不了支持拖放功能 的 ，而且支持更加強大的拖放功能。 自然 智能 五子棋也少不了了（如圖 ）。在 該“設置”對話框里，幾乎所有的選項 都對應著一個注冊表項值，當用戶退出程序后，程序會自動調(diào)用類的析構(gòu)函數(shù)將用戶最后一次設置寫入注冊表，以保證程序下一次啟動時，能夠讀出注冊表值將軟件設置為和上次一致。 “ 整點報時”是模仿的“雪狐桌面精靈”，報時所用的 WAV 文件是從該軟件里 拷貝 過來的。 消息機制的架構(gòu) 當繼承自 CAsyncSocket 的套接字類 CFiveSocket 收到消息時，會觸發(fā)CFiveSocket::OnReceive 事件，這個事件里調(diào)用 CChessBoard::Receive， 該函數(shù)開始按照自定義的消息格式接收套接字發(fā)送的數(shù)據(jù)，并對不同的消息類型進行分發(fā)處理 [3]。 // 消息正文 TCHAR szText[128]。注意：對方棋子顏色無需傳送，因為程序規(guī)則是執(zhí)黑者先行，以后每下一局，雙方交換先后手和棋子顏色。 圖 請求悔棋 同意悔棋消息 —— FM_AGREE_BACK 表明對方接受了玩家的悔棋請求，除 uID 成員外其余成員皆無效。 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 25 頁 圖 拒絕悔棋 請求和棋消息 —— FM_REQUEST_DRAW 表明對方請求和棋，除 uID 成員外其余成員皆無效。接到這個消息后，雙方和棋。 圖 拒絕和棋 認輸消息 —— FM_GIVEUP 表明對方已經(jīng)投子認輸（如圖 和 所示），除 uID 成員外其余成員皆無效。接到這個消息后，會彈出 MessageBox 詢問是否接受對方的請求（如圖 所示），并根據(jù)玩家的選擇回返 FM_AGREE_REPLAY消息 或直接斷開網(wǎng)絡，如果某一方斷開了網(wǎng)絡 連接 ，對方的主界面 上 提示如圖 所示 。接到這個信息后，會將對方聊天的內(nèi)容顯示在主對話框的聊天記錄窗口內(nèi)。在開始游戲的時候，由客戶端向服務端發(fā)送這條消息，服務端接到后設置對方的姓名， 中國礦業(yè)大學 2021 屆本科生畢業(yè)設計（論文） 第 27 頁 并將自己的姓名同樣用這條消息回發(fā)給客戶端；同時如果某一方在游戲進行過程中改變了自己的名字，也會即時發(fā)送該消息給對手，讓其在主界面上做出相應修改。連接者收到 FM_SERVER_BUSY 消息后，在主界面提示如圖 所示。 我知道這一切只要自己程序員時代的起點，我希望以后做得越來越好，寫出更多優(yōu)秀的軟件。此外， 將來還 可以考慮加入開局庫（ Opening Book） 和殘局庫（ Endgame Database），來進一步加 快 程序的運行速度。通過并行搜索，可充分利用當前的多 CPU 硬件平臺，在不改變程序大部分結(jié)構(gòu)的基礎上實現(xiàn)速度的倍增，由于對相同的搜索與估值函數(shù)來說，程序棋力隨速度的增加而增加，而這種增加其實是搜索深度增加與程序棋力的一種相對關系。通過個人較長時間對軟件的測試來看，運行效果還是不錯的 ，基本上達到了自己預定的許多目標。因為五子棋是二人游戲，所以服務端同時只能和一位玩家連接。接到這個信息后，會將對方選擇了列表框某項文本內(nèi)容顯示在主對話框的聊天記錄窗口內(nèi)，同時如果 szText[1]為 1，系統(tǒng)將用聲音讀出該文本的內(nèi)容，這里所用到的聲音 WAV 文件是從 游戲 的斗地主目錄里 拷貝 過來的。接到這個消息后，將開啟一局新游戲。如果用戶了“聲音提示”，系統(tǒng)為勝利方播放贏棋音樂，為 認輸方 播放輸棋音樂。 圖 同意和棋 拒絕和棋消息 —— FM_REFUSE_DRAW 表明對方拒絕了玩家的和棋請求（如圖 所示），除 uID 成員外其余成員皆無效。另外，在發(fā)送這個消息之后，主界面上的某些元素將暫時不響應用戶的操作。 拒絕悔棋消息 —— FM_REFUSE_BACK 表明對方拒絕了玩家的悔棋請求（如圖 所 示），除 uID 成員外其余成員皆無效。接到 這個消息后，會彈出MessageBox 詢問是否接受對方的請求（如圖 所示），并根據(jù)玩家的選擇回返FM_AGREE_BACK 或 FM_REFUSE_BACK 消息。 隨著 uID 表示 消息 ID， stonePos(有 x,y 兩個成員 )表示落子坐標 ， szText 隨著 uID 的不同而有不同的含義。 各種消息說明 網(wǎng)絡間傳遞的消息，都遵循以下一個結(jié)構(gòu)體的形式： 網(wǎng)絡數(shù)據(jù) CFiveSocket CFiveSocket::OnReceive CChessBoard::Receive 對各種消息分發(fā)處理 調(diào)用 CFiveSocket::Send