目標(biāo)
1.使用對抗搜索方法(MINMAX和Alpha-beta)實現(xiàn)五子棋AI掂之。
2. 比較采用不同實現(xiàn)方法的五子棋AI的性能差異脆丁。
搜索方法
AI根據(jù)對棋盤局勢的判斷，采用對抗搜索的方法得到最佳下棋位置歼培，下棋位置的優(yōu)劣可以通過效用函數(shù)評估姊氓。
MINMAX:極小極大方法读跷。搜索從MAX節(jié)點開始禾唁，MAX節(jié)點返回直接后繼MIN節(jié)點中效用值最大作為對該MAX節(jié)點效用評估丐枉；而MIN節(jié)點返回直接后繼MAX節(jié)點中效用值最小的作為對該MIN節(jié)點的效用評估瘦锹。當(dāng)搜索條件達(dá)到時弯院，返回對棋盤（針對MAX節(jié)點）效用值（通過效用函數(shù)計算得到）听绳。
Alpha-beta: MINMAX的改進(jìn)方法。算法在搜索時維持當(dāng)前MAX節(jié)點最優(yōu)值alpha和當(dāng)前MIN節(jié)點最優(yōu)值beta塔拳。當(dāng)節(jié)點的效用值比MAX節(jié)點的alpha或MIN節(jié)點的beta更差時量九，剪枝掉該節(jié)點的分支孕荠。最好的情況下，Alpha-beta比MINMAX搜索深度要多一倍棺克。
決策方法
注意到上述的搜索方法是效用評估是針對MAX節(jié)點的伙菜，換句話說就是搜索MAX選手（這里是AI）的最大效用位置。但在五子棋實現(xiàn)時艳汽，由于效用函數(shù)設(shè)計只對優(yōu)勢特征計分，沒有對劣勢特征進(jìn)行扣分馋艺，所以搜索得到的位置沒有考慮到對手的對自身效用的評估捐祠，換句話說沒有考慮到棋盤局勢。當(dāng)棋盤局勢對AI不利時桑李，AI不考慮局勢踱蛀，只下對自己優(yōu)勢有幫助的位置，而不去下能減少對手優(yōu)勢（對手效用高）的位置贵白，很可能導(dǎo)致失敗率拒。另外，考慮到采用固定策略的AI變化性不大戒洼，可以引入一些隨機(jī)因素增加AI的變化性俏橘。因此允华，這里設(shè)計了A圈浇、B兩種策略進(jìn)行決策靴寂。
策略A：AI計算自身棋盤效用值U1和對手棋盤效用值U2剖踊。當(dāng)U1不小于U2時固惯，選擇對自己效用貢獻(xiàn)最大的位置贴捡；否則源祈，選擇對對手效用貢獻(xiàn)最大的位置。
策略B：AI計算自身棋盤效用值U1和對手棋盤效用值U2祸轮。當(dāng)U1高出U2一定值時（棋盤局勢對AI有利），選擇對自己效用貢獻(xiàn)最大的位置敢伸；否則，在對自己效用貢獻(xiàn)最大的位置和對對手效用貢獻(xiàn)最大的位置進(jìn)行隨機(jī)選擇。
效用函數(shù)
設(shè)效用函數(shù)為Ultility(C)痕慢，塔次，C為棋子顏色巾表，
為的權(quán)重，為第i個特征政溃。這里云头，特征選擇分別是棋盤中棋子能夠二連、三連、四連和五連的個數(shù)蛇捌。
AI設(shè)計
結(jié)果分析
對不同方法實現(xiàn)AI一共進(jìn)行了6組對比實驗，如下表所示绩郎。
由實驗可見梳庆，黑棋要比白棋優(yōu)勢胧后，主要是因為黑棋先下芋浮，比白棋多占據(jù)一個位置，這也是五子棋里普遍認(rèn)同的（由于黑棋優(yōu)勢壳快，通常比賽對黑棋進(jìn)行禁手限制纸巷，更何況這里沒有禁手限制）。
由組1和組2比較可知眶痰，策略A要略優(yōu)于策略B瘤旨。組1中，MM-A執(zhí)黑完勝MM-B竖伯；組2中存哲，MM-B執(zhí)黑和MM-A沒能有較大優(yōu)勢，即使有黑棋優(yōu)勢的MM-B也只比MM-A只多勝一局七婴。分析原因可能是策略B在進(jìn)行局勢判斷時可能準(zhǔn)確度可能不夠祟偷；另外，策略A是一個確定策略打厘，而策略B是一個部分隨機(jī)策略修肠，在局勢不具有優(yōu)勢隨機(jī)選擇進(jìn)攻或防守可能為AI帶來不好的影響。
理論上户盯，搜索深度更深的AI要優(yōu)于搜索深度較淺的AI嵌施。由組5和組6可知，AB-A要優(yōu)于MM-B莽鸭。組4中吗伤，AB-B優(yōu)于MM-B；而在組3中硫眨，MM-B卻優(yōu)于AB-B牲芋，這里可能是黑棋優(yōu)勢的原因和實驗次數(shù)少導(dǎo)致的結(jié)果沒能反映出AB-B的優(yōu)勢。
總結(jié)
1.實驗使用了對抗搜索方法和不同的決策策略實現(xiàn)了五子棋AI捺球。
2. MINMAX和Alpha-beta本質(zhì)上并沒有什么區(qū)別缸浦，只是Alpha-beta對無搜索意義節(jié)點進(jìn)行了剪枝，大大提高了性能氮兵，最好情況下使搜索深度翻倍裂逐。
3.使用MINMAX和Alpha-beta方法的AI算法復(fù)雜度主要在于MINMAX和Alpha-beta方法本身的復(fù)雜度與效用函數(shù)的計算復(fù)雜度關(guān)系不大。因為MINMAX和Alpha-beta方法是指數(shù)級復(fù)雜度泣栈，而效用計算復(fù)雜度不高卜高。
4.效用函數(shù)對MINMAX和Alpha-beta方法有效性影響很大弥姻。效用函數(shù)越準(zhǔn)確，MINMAX和Alpha-beta方法得到最佳節(jié)點有效性越高掺涛。但設(shè)計一個完全準(zhǔn)確的效用函數(shù)幾乎是不可能的庭敦，找到一個有效的效用函數(shù)是困難的。為了方便實現(xiàn)和降低效用函數(shù)計算量薪缆，實驗設(shè)計的效用函數(shù)較簡單秧廉，未來可以考慮多個更準(zhǔn)確和計算復(fù)雜度低的效用函數(shù)進(jìn)行對比。
5. MINMAX和Alpha-beta方法搜索得到一個效用值最大的節(jié)點拣帽，但效用值最大的節(jié)點可能有多個疼电，在其中隨機(jī)選擇一個可以為AI增加更多的變化性，可以考慮修改算法得到這些節(jié)點减拭。
