博弈是人工智能的主要研究領域之一，它涉及人工智能中的推理技術、搜索方法和決策規(guī)劃。人工智能之父圖靈在1950年曾說過：下棋是很抽象的活動，是機器可以和人競爭的純智能領域之一。自此以后的半個世紀中，人機對弈就成了人工智能研究的熱門領域。而人們對五子棋人機對弈的研究也有很長的歷史了。如今，博弈樹搜索算法，更是五子棋人機對弈的熱門研究方向。本文主要研究了博弈樹搜索算法和alpha-beta剪枝技術，改進了棋局評估函數(shù)，并提出連續(xù)沖四搜索算法的概念。本文設計了一個改進的評估函數(shù)。傳統(tǒng)的評估函數(shù)，只考慮了單一直線上的棋形。這種評估函數(shù)雖然實現(xiàn)起來比較簡單，但在兩直線交叉的復合棋形下，往往不能很好地評判。本文設計的評估函數(shù)，在單一直線評估的基礎上，加入了交叉組合分值加成。改進的評估函數(shù)能有效避免計算機程序錯過三三或三四組合等必勝的情況，增強了程序的棋力。本文通過研究專業(yè)五子棋知識，提出了連續(xù)沖四搜索算法。在五子棋游戲中，沖四是一種很強的進攻手段，除非對手能在下一步連成五顆，否則他必須選擇進行封鎖的那一步。連續(xù)沖四取勝，就是通過連續(xù)沖四進攻，最終構造出制勝的三四。連續(xù)沖四搜索即是搜索連續(xù)沖四取勝的步... 

【文章來源】：華南理工大學廣東省 211工程院校 985工程院校 教育部直屬院校

【文章頁數(shù)】：61 頁

【學位級別】：碩士

【部分圖文】：

特殊情況

21圖 2-5 連續(xù)沖四例子圖 2-5 所示，這是一個連續(xù)沖四的例子。假設現(xiàn)在輪到黑棋下子，在這個棋局中，白棋已經(jīng)形成一個活三。在一般情況下，黑方很可能選擇封鎖白方的活三，即 a 位置或b 位置。而在兩個位置中，a 更為有利，因為在封鎖對方活三的同時，給自己形成了活三。若此時黑棋落在 a 點，而白方回應下一步肯定是阻止黑活四形成，并形成新的白活三，黑棋仍處于被動的狀態(tài)，在可預見的幾步內，黑棋將失敗。但如果此時黑棋置白活三不顧，落在 A 處形成沖四，白棋則不得不防住這沖四。黑棋緊接著走 B、C 連續(xù)沖四，進而連接 A、B、C 三點形成活四，黑棋獲勝。從上面的例子可以看到，連續(xù)沖四獲勝也是一種重要的獲勝手段。雖然在連續(xù)沖四步數(shù)不多的情況下，依靠博弈樹搜索也能找到勝利的方法，但連續(xù)沖四的步數(shù)在多數(shù)情況下仍是比較多的。就像上面這個簡單的例子，從開始連續(xù)沖四到真正取勝，需要黑白

第二章 算法描述3 連續(xù)沖四搜索優(yōu)化但即使連續(xù)沖四搜索較博弈樹搜索更高效，其算法的時間復雜度依然很高。不化的博弈樹搜索的時間復雜度為 O(MN)，其中 M 為分支個數(shù)，N 為搜索深度，連續(xù)沖四取勝對沖四的順序也是有一定要求的，連續(xù)沖四搜索可近似看成一搜索的問題，故其時間復雜度為 O(M!)，其中 M 為可沖四五元組的個數(shù)。當!)是這個算法的時間復雜度上界，實際情況下其復雜度會小很多。針對最壞情況下的連續(xù)沖四搜索，可以考慮加入一些優(yōu)化以降低計算時間。如元組進行分組，使位置較近的五元組分在一組進行搜索。這樣做可以減小 M雖然算法的時間復雜度不變，但計算時間會小很多。這個優(yōu)化考慮的是，并不四五元組都能為取勝作出貢獻的�？紤] 0 的情況，兩個沖四五元組并不能構成。如果將無關的沖四五元組一起搜索，會大大增加運算時間。


本文編號：3281673