目标
1.使用對抗搜尋方法(MINMAX和Alpha-beta)實作五子棋AI。
2. 比較采用不同實作方法的五子棋AI的性能差異。
搜尋方法
AI根據對棋盤局勢的判斷，采用對抗搜尋的方法得到最佳下棋位置，下棋位置的優劣可以通過效用函數評估。
MINMAX:極小極大方法。搜尋從MAX節點開始，MAX節點傳回直接後繼MIN節點中效用值最大作為對該MAX節點效用評估；而MIN節點傳回直接後繼MAX節點中效用值最小的作為對該MIN節點的效用評估。當搜尋條件達到時，傳回對棋盤(針對MAX節點)效用值(通過效用函數計算得到)。
Alpha-beta: MINMAX的改進方法。算法在搜尋時維持目前MAX節點最優值alpha和目前MIN節點最優值beta。當節點的效用值比MAX節點的alpha或MIN節點的beta更差時，剪枝掉該節點的分支。最好的情況下，Alpha-beta比MINMAX搜尋深度要多一倍。
決策方法
注意到上述的搜尋方法是效用評估是針對MAX節點的，換句話說就是搜尋MAX選手(這裡是AI)的最大效用位置。但在五子棋實作時，由于效用函數設計隻對優勢特征計分，沒有對劣勢特征進行扣分，是以搜尋得到的位置沒有考慮到對手的對自身效用的評估，換句話說沒有考慮到棋盤局勢。當棋盤局勢對AI不利時，AI不考慮局勢，隻下對自己優勢有幫助的位置，而不去下能減少對手優勢(對手效用高)的位置，很可能導緻失敗。另外，考慮到采用固定政策的AI變化性不大，可以引入一些随機因素增加AI的變化性。是以，這裡設計了A、B兩種政策進行決策。
政策A：AI計算自身棋盤效用值U1和對手棋盤效用值U2。當U1不小于U2時，選擇對自己效用貢獻最大的位置；否則，選擇對對手效用貢獻最大的位置。
政策B：AI計算自身棋盤效用值U1和對手棋盤效用值U2。當U1高出U2一定值時(棋盤局勢對AI有利)，選擇對自己效用貢獻最大的位置；否則，在對自己效用貢獻最大的位置和對對手效用貢獻最大的位置進行随機選擇。
效用函數
設效用函數為Ultility(C)，
，C為棋子顔色，
為的權重，為第i個特征。這裡，特征選擇分别是棋盤中棋子能夠二連、三連、四連和五連的個數。
AI設計
由于五子棋搜尋分支過大(超過100)，效用函數複雜度比較高(達到
)，而搜尋複雜度是指數級的(
)，搜尋深度達到3時算法效率不高，是以搜尋深度最大設定為2。
結果分析
對不同方法實作AI一共進行了6組對比實驗，如下表所示。
AI對弈AI對比實驗
由實驗可見，黑棋要比白棋優勢，主要是因為黑棋先下，比白棋多占據一個位置，這也是五子棋裡普遍認同的(由于黑棋優勢，通常比賽對黑棋進行禁手限制，更何況這裡沒有禁手限制)。
由組1群組2比較可知，政策A要略優于政策B。組1中，MM-A執黑完勝MM-B；組2中，MM-B執黑和MM-A沒能有較大優勢，即使有黑棋優勢的MM-B也隻比MM-A隻多勝一局。分析原因可能是政策B在進行局勢判斷時可能準确度可能不夠；另外，政策A是一個确定政策，而政策B是一個部分随機政策，在局勢不具有優勢随機選擇進攻或防守可能為AI帶來不好的影響。
理論上，搜尋深度更深的AI要優于搜尋深度較淺的AI。由組5群組6可知，AB-A要優于MM-B。組4中，AB-B優于MM-B；而在組3中，MM-B卻優于AB-B，這裡可能是黑棋優勢的原因和實驗次數少導緻的結果沒能反映出AB-B的優勢。
總結
1.實驗使用了對抗搜尋方法和不同的決策政策實作了五子棋AI。
2. MINMAX和Alpha-beta本質上并沒有什麼差別，隻是Alpha-beta對無搜尋意義節點進行了剪枝，大大提高了性能，最好情況下使搜尋深度翻倍。
3.使用MINMAX和Alpha-beta方法的AI算法複雜度主要在于MINMAX和Alpha-beta方法本身的複雜度與效用函數的計算複雜度關系不大。因為MINMAX和Alpha-beta方法是指數級複雜度，而效用計算複雜度不高。
4.效用函數對MINMAX和Alpha-beta方法有效性影響很大。效用函數越準确，MINMAX和Alpha-beta方法得到最佳節點有效性越高。但設計一個完全準确的效用函數幾乎是不可能的，找到一個有效的效用函數是困難的。為了友善實作和降低效用函數計算量，實驗設計的效用函數較簡單，未來可以考慮多個更準确和計算複雜度低的效用函數進行對比。
5. MINMAX和Alpha-beta方法搜尋得到一個效用值最大的節點，但效用值最大的節點可能有多個，在其中随機選擇一個可以為AI增加更多的變化性，可以考慮修改算法得到這些節點。