?
01、Alpha-Beta剪枝算法
極小化極大算法會(huì)遍歷所有的可能性，但是根據(jù)經(jīng)驗(yàn)可以知道，并不是所有的選項(xiàng)都需要進(jìn)行深入的考慮，存在著某些明顯不利的選項(xiàng)，當(dāng)出現(xiàn)這種選項(xiàng)時(shí)就可以換一種思路進(jìn)行考慮了。Alpha-Beta剪枝算法的出現(xiàn)正是為了減少極小化極大算法搜索樹(shù)的節(jié)點(diǎn)數(shù)。1997年5月11日，擊敗加里·卡斯帕羅夫的IBM公司“深藍(lán)”就采用了這種算法。
以井字棋為例，先來(lái)看看在下棋的過(guò)程中是否有優(yōu)化空間。參考圖1，當(dāng)前輪到畫(huà)○方，如果不在虛線圈上落棋，下一步畫(huà)×方畫(huà)在虛圈處，游戲就結(jié)束了。當(dāng)發(fā)現(xiàn)這類問(wèn)題時(shí)，再去思考其他5個(gè)△標(biāo)注的位置上的落子收益其實(shí)是沒(méi)有意義的，白白浪費(fèi)了計(jì)算資源。
?
■?圖1 畫(huà)○方的回合
再來(lái)看一個(gè)象棋的例子。如圖2所示，此時(shí)輪到執(zhí)“帥”的一方走子。將炮橫在中路是一種非常具有殺傷力的下法，后續(xù)可能可以配合自己的馬走出“馬后炮”的殺招。但是如果走了這一步，自己的馬將會(huì)被對(duì)方的車(chē)立即吃掉，這一損失實(shí)在是太大了，所以面對(duì)此局面，實(shí)戰(zhàn)時(shí)基本只會(huì)考慮如何走馬以避免被車(chē)吃掉，其他的走子都不會(huì)再深入考慮。
■?圖2 執(zhí)紅方的選擇
在行棋的過(guò)程中，當(dāng)發(fā)現(xiàn)己方會(huì)出現(xiàn)極大損失或者極大獲利時(shí)，僅考慮這些收益顯著的情況而忽略掉其他可選項(xiàng)的行為就是剪枝算法的基本思想，而Alpha-Beta剪枝算法就是專門(mén)設(shè)計(jì)用來(lái)減少極小化極大算法搜索樹(shù)節(jié)點(diǎn)數(shù)的搜索算法。它的基本思想是根據(jù)上一層已經(jīng)得到的當(dāng)前最優(yōu)結(jié)果，決定目前的搜索是否要繼續(xù)下去，當(dāng)算法評(píng)估出某策略的后續(xù)走法比之前策略的還差時(shí)，就會(huì)停止計(jì)算該策略的后續(xù)發(fā)展。Alpha-Beta剪枝算法將搜索時(shí)間用在“更有希望”的子分支上，繼而提升搜索深度，則同樣時(shí)間內(nèi)搜索深度平均來(lái)說(shuō)可達(dá)極小化極大算法的兩倍多。
根據(jù)算法介紹可知，如果要使用Alpha-Beta剪枝算法就會(huì)額外需要一套局面價(jià)值評(píng)估系統(tǒng)來(lái)決定哪些搜索分支是有希望的，而哪些是沒(méi)有希望的。所謂局面價(jià)值，就是指當(dāng)前盤(pán)面的勝負(fù)概率，勝率越高則價(jià)值越大，反之則價(jià)值越小，甚至是負(fù)價(jià)值。各種采用Alpha-Beta剪枝算法的人工智能程序之間的實(shí)力差距其實(shí)就是由于局面價(jià)值評(píng)估系統(tǒng)的不同所造成的。局面價(jià)值評(píng)估系統(tǒng)帶有很強(qiáng)的主觀性，對(duì)于如何評(píng)估棋局的價(jià)值有點(diǎn)像莎士比亞說(shuō)的，“一千個(gè)觀眾眼中有一千個(gè)哈姆雷特”。下面將繼續(xù)使用井字棋來(lái)演示Alpha-Beta剪枝算法。為了省去設(shè)計(jì)井字棋的價(jià)值函數(shù)，代碼片段1粗暴地認(rèn)為除了贏和輸，其他所有盤(pán)面(包括和棋)的價(jià)值均為零，贏棋的盤(pán)面價(jià)值為1，輸棋的盤(pán)面價(jià)值為-1。如果讀者想自己在圍棋游戲上嘗試一下這個(gè)算法，最簡(jiǎn)單的局面評(píng)估算法之一就是計(jì)算當(dāng)前雙方在棋盤(pán)上剩余棋子的差額。不過(guò)實(shí)戰(zhàn)中很少會(huì)有棋手主動(dòng)提取對(duì)方已經(jīng)窮途末路的棋子，所以也許這種評(píng)估方法得到的高價(jià)值局面反而會(huì)帶來(lái)更加不利的影響。
【代碼片段1】得到對(duì)弈的評(píng)估結(jié)果。
MyGo tic - tac - toe ttt.py
def evl game(game) :
if getResult(game.board.board)[1] != None:
if game.player == getResult(game.board.board) == (0,1)[1]:
return 1
else:
return - 1
else:
return 0
?說(shuō)明?/
(1) 判斷盤(pán)面結(jié)果，按照約定，對(duì)于井字棋，只有當(dāng)棋局勝負(fù)已分時(shí)才對(duì)盤(pán)面價(jià)值進(jìn)行判斷，否則盤(pán)面價(jià)值為零。
(2) 判斷當(dāng)前進(jìn)行價(jià)值評(píng)估的棋手是否是棋局的勝利方。
(3) 如果勝利方是當(dāng)前棋手，則盤(pán)面價(jià)值為1；如果勝利方是當(dāng)前棋手的對(duì)手，則盤(pán)面價(jià)值為-1，其他情況的價(jià)值按約定默認(rèn)是0。
引入了對(duì)棋局盤(pán)面的價(jià)值評(píng)估表明在使用Alpha-Beta剪枝算法時(shí)并不需要執(zhí)著于搜索時(shí)窮盡棋局，即在模擬思考行為時(shí)未必非要下到棋局結(jié)束時(shí)才停止。通常在使用這種算法時(shí)會(huì)設(shè)置一個(gè)搜索深度參數(shù)來(lái)控制算法仿真思考的回合數(shù)。從本質(zhì)上來(lái)說(shuō)，Alpha-Beta剪枝算法是通過(guò)價(jià)值評(píng)估函數(shù)來(lái)控制算法的搜索廣度，用參數(shù)設(shè)置來(lái)控制算法的搜索深度。
同極小化極大算法相比，Alpha-Beta剪枝算法并不是要等到棋局下到結(jié)束才給出對(duì)局面的評(píng)估，每個(gè)不同可選項(xiàng)得到的評(píng)估結(jié)果會(huì)由價(jià)值評(píng)估函數(shù)給出不同的數(shù)值結(jié)果，不盡相同的評(píng)估結(jié)果(極小化極大算法只有勝、負(fù)、和三種評(píng)估結(jié)果)導(dǎo)致Alpha-Beta剪枝算法在使用過(guò)程中需要記錄博弈雙方在搜索過(guò)程中所能取得的最佳價(jià)值，可以把雙方記錄的最佳價(jià)值等價(jià)地看作是極小化極大算法中的勝利結(jié)果。傳統(tǒng)上把一方所能搜索到的當(dāng)前盤(pán)面最佳價(jià)值叫作Alpha，另一方的最佳價(jià)值稱為Beta，這種叫法也正是這個(gè)算法名稱的由來(lái)。對(duì)于井字棋，將其簡(jiǎn)記為best_o和best_x。代碼片段2演示了Alpha-Beta剪枝算法是如何實(shí)現(xiàn)的。
【代碼片段2】Alpha-Beta減枝算法的代碼框架。
MyGo tic - tac - toe ttt.py
if self.mode == 'ab':
move = self.game.getLegalMoves()
best_moves = []
best_socre = None
best_o = manValue
best_x = minValue
for move in moves:
new game = self.game.simuApplyMove(move)
op_best_outcome = alpha beta prune(new_game, max_depth,best_o, best_x,evl_game)
my best outcome = -1 * op_best outcome
if (not_best_moves) or my_best_outcome > best_score:
best_moves = [move]
best_score = my_best_outcome
if self.game.player == player_x:
best_x = best_score
elif self.game.player == player_o:
best_o = best_score
elif_my_best_outcome == best_score:
best_moves.append(move)
return random.choice(best_moves)
?說(shuō)明?/
(1) 模式ab代表Alpha-Beta剪枝算法。
(2) 獲取當(dāng)前盤(pán)面上符合游戲規(guī)則的可選項(xiàng)。
(3) 存放最佳的落子選項(xiàng)。
(4) best_score存放當(dāng)前盤(pán)面在搜索過(guò)程中得到過(guò)的最高選項(xiàng)價(jià)值，這個(gè)值在搜索過(guò)程中會(huì)不斷地被更高的值所替換。將執(zhí)○方和執(zhí)×方的Beta值初始化為最低的價(jià)值，并在后面用搜索到的best_score值來(lái)更新。
(5) 逐個(gè)搜索可選項(xiàng)。
(6) 仿真一下當(dāng)前選項(xiàng)的落子。
(7) 仿真對(duì)手在當(dāng)前落子下能取得的最佳價(jià)值。
(8) 己方能取得的最佳價(jià)值是對(duì)方能取得的最佳價(jià)值的反面。
(9) 只對(duì)當(dāng)前價(jià)值高于已有記錄的落子步進(jìn)行處理。
(10) 搜索到了更高的價(jià)值，于是需要更新最佳落子。
(11) 更新已有記錄的最佳落子價(jià)值。
(12) 將最佳價(jià)值更新給當(dāng)前棋盤(pán)盤(pán)面的實(shí)際落子方。
(13) 如果搜索到的價(jià)值和記錄的最高價(jià)值一致，則僅補(bǔ)充最佳落子的可選范圍，通過(guò)隨機(jī)抽取高價(jià)值落子使得下棋過(guò)程中棋局更多變，也更貼近人類行為。
代碼片段3-11和代碼片段3-8的極小化極大算法在框架上是非常相似的，如果讀者仔細(xì)思索就會(huì)發(fā)現(xiàn)，雖然算法的定性描述介紹好像有點(diǎn)玄乎，但是實(shí)現(xiàn)上Alpha-Beta剪枝算法和極小化極大算法并沒(méi)有本質(zhì)上的區(qū)別，僅僅是將勝負(fù)結(jié)果的判斷用一個(gè)價(jià)值判斷函數(shù)替代了。既然Alpha-Beta剪枝算法是對(duì)極小化極大算法的優(yōu)化，它也只能通過(guò)遞歸的方式來(lái)實(shí)現(xiàn)。alpha_beta_prune()函數(shù)是整個(gè)遞歸方法的核心，讀者可以將極小化極大算法中的bestResultForOP()和這個(gè)alpha_beta_prune()比較著來(lái)看。代碼片段3演示了算法的核心遞歸方法是如何實(shí)現(xiàn)的。
【代碼片段3】通過(guò)減枝算法查找對(duì)方的最優(yōu)著法。
MyGo\tic-tac-toe\ttt.py
max depth =4
def alpha_beta_prune(game, max_depth,best_o,best_x,evl_fn):
if game.state == GameState.over :
if game.winner == game.player:
return maxValue
elif game.winner == None:
return 0
else:
return minValu
elif max depth == 0:
return evl fn(game)
best so_far = minValue
for move in game.getLegalMoves():
next_game = game.simuApplyMove(move):
op_best_result = alpha_beta_prune(
next_game，max_depth - 1,
best_o，best_x,
evl_fn)
my_result = -1 * op_best_result
if my_result > best_so_far:
best_so_far = my_result
if game.player == plaver_o:
if best_so_far > best_o:
best_o = best_so_far
outcome_for_x = -1 * best_so_far
if outcome_for_x < best_x:
break
elif game.player == player_x:
if best_so_far > best_x:
best_x = best_so_far
outcome_for_o = -1 * best_so_far
if outcome_for_o < best_o:
break
return best_so_far
?說(shuō)明?/
(1) 控制搜索深度。由于人為定義平局和進(jìn)行中的棋局的價(jià)值設(shè)置為0，而井字棋一共就9步落子，所以當(dāng)這個(gè)搜索深度設(shè)置得比較淺時(shí)，算法在開(kāi)頭的幾步和隨機(jī)落子并沒(méi)有什么區(qū)別。如果隨機(jī)落子法在前3步完成了橫豎相連，就可以擊敗剪枝算法。這也從側(cè)面說(shuō)明了一個(gè)好的價(jià)值評(píng)估算法對(duì)于剪枝算法的重要性。
(2) 由于采用價(jià)值評(píng)估函數(shù)來(lái)對(duì)勝負(fù)的可能性進(jìn)行評(píng)估，這里用一個(gè)極大數(shù)字或極小數(shù)字來(lái)表示明確的輸贏勝負(fù)。
(3) 控制搜索深度，如果到達(dá)一定深度游戲還沒(méi)有結(jié)束，就用價(jià)值評(píng)估函數(shù)的值來(lái)代替勝負(fù)的判斷。
(4) 和極小化極大算法一樣，初始化當(dāng)前盤(pán)面能取得的最佳價(jià)值。
(5) 這幾步和bestResultForOP()中的寫(xiě)法是幾乎相同的。
(6) 如果結(jié)果比之前記錄的好則更新最佳價(jià)值。極小極大化算法中的最佳價(jià)值就是贏棋，所以沒(méi)有更新最佳價(jià)值這一步，而Alpha-Beta剪枝中因?yàn)槭峭ㄟ^(guò)價(jià)值評(píng)價(jià)函數(shù)來(lái)估計(jì)勝負(fù)結(jié)果的，這個(gè)值可能會(huì)有很多不同的值，所以可能需要不停地更新最大的值。
(7) 根據(jù)當(dāng)前執(zhí)棋者是誰(shuí)，將上一步得到的最佳值更新給不同的對(duì)象的最佳值。
(8) 如果當(dāng)前玩家是畫(huà)○方，當(dāng)前搜索值大于畫(huà)○方記錄的最大值，則更新其記錄的最大值。下面對(duì)畫(huà)×方的判斷后也使用了類似的操作步驟，就不再贅述了。
(9) 一方的最佳進(jìn)行反操作就是另一方的最差。
(10) 如果當(dāng)前的一方最佳操作可以使得對(duì)方的最佳降低，那么就可以認(rèn)為找到了一步必勝棋，并退出，當(dāng)然也可以繼續(xù)搜索不退出，但是由于已經(jīng)找到了，再多找?guī)讉€(gè)意義不大，反而浪費(fèi)了計(jì)算資源，這個(gè)在bestResultForOP()中也有相似的對(duì)應(yīng)操作。
(11) 返回當(dāng)前玩家所能取得的最佳結(jié)果。
搜索選項(xiàng)時(shí)算法會(huì)根據(jù)棋盤(pán)局面上的可落子順序進(jìn)行搜索。如果碰巧在一開(kāi)始就找到了一個(gè)最好的選項(xiàng)，在搜索其他后續(xù)選項(xiàng)時(shí)會(huì)由于剩下的選項(xiàng)收益較低而被迅速地剪枝掉，如果運(yùn)氣不好，最好的選項(xiàng)在最后才被搜索到，那么Alpha-Beta剪枝算法的速度并不會(huì)比極小化極大算法快。但是數(shù)學(xué)期望上，Alpha-Beta剪枝算法的消耗時(shí)間會(huì)是極小化極大算法的一半。如果在搜索開(kāi)始前引入一些啟發(fā)性的算法先從最有潛質(zhì)的著法開(kāi)始搜索，也許可以緩解算法對(duì)著法尋找順序的依賴并使得算法能有很大的改進(jìn)。
02、送書(shū)活動(dòng)
本期送書(shū)活動(dòng)由機(jī)械工業(yè)出版社獨(dú)家贊助，本期的送書(shū)書(shū)單如下：
?
?
?
?
?
?
?
?
?
?參與方式：文章來(lái)源：http://www.zghlxwxcb.cn/news/detail-528708.html
文章三連并評(píng)論任意與文章相關(guān)的內(nèi)容即可參與抽獎(jiǎng)，48小時(shí)后，程序自動(dòng)抽獎(jiǎng)，送出6本技術(shù)圖書(shū)[如上]！希望大家多多參與，堅(jiān)持學(xué)習(xí)！文章來(lái)源地址http://www.zghlxwxcb.cn/news/detail-528708.html
到了這里，關(guān)于秒懂算法 | 圍棋中的Alpha-Beta剪枝算法的文章就介紹完了。如果您還想了解更多內(nèi)容，請(qǐng)?jiān)谟疑辖撬阉鱐OY模板網(wǎng)以前的文章或繼續(xù)瀏覽下面的相關(guān)文章，希望大家以后多多支持TOY模板網(wǎng)！
