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

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

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

【學(xué)位級(jí)別】：碩士

【部分圖文】：

特殊情況

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

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


本文編號(hào)：3281673