α-β截斷

博弈樹的某些部分並不會產生任何有意義的值,因而也根本用不著去擴展博弈樹的這一部分。識別博弈樹中這些可忽略部分的技術,稱之為α-β截斷。之所以叫這個名字,是由於歷史原因造成的。

α-β截斷,原則敘述,後記,

α-β截斷

考慮下圖的情況,我們可以看出,在輪到棋手下棋的節點上,其部分回溯值是10。而它的當前計算出來的子節點的部分回溯值是8。現在,由於該子節點是輪到對手下棋的節點,而對手總是要走那個具有最小值的棋局,故進一步探察的結果只會小於這個值。無論最後的確定值是多少,它總是小於或等於8。
從另一方面來看,該節點本身的部分回溯值是10。因為這時輪到棋手下棋,所以只有大於10的子節點的值才能改變這個部分回溯值。
所以我們得出的結論是:不需要去進一步擴展其子節點或其它任意後續節點。這是因為進一步的擴展至多只能減少其子節點的回溯值,而其目前的值已經足夠小到不能影響其親節點的部分回溯值了。這種情況就是所謂的α截斷。

原則敘述

現在,我們把一般的原則敘述如下:
在考慮輪到棋手下棋的一個親節點及輪到對手下棋的一個子節點時,如果該子節點的數值已經小於或等於其親節點的回溯值,那么就不需要對該節點或者其後續節點做更多的處理了。計算的過程可以直接返回到親節點上。
當親節點是輪到對手下棋的一個節點時,該原則作相應的改動:
在考慮輪到對手下棋的一個親節點及輪到棋手下棋的一個子節點時,如果該子節點的部分回溯值已經大於或等於其親節點的部分回溯值,那么就不需要對該子節點或者其後裔節點做更多的處理了。計算過程可以直接返回到親節點上。這就是所謂的β截斷。

後記

截斷這一技術允許我們有時可以不去考慮某節點的某些子節點的情況。然而,由於非終節點的每一個子節點又是其後續節點所組成的整個博弈樹的根,所以,如果我能忽略掉那些子節點的話,不僅僅是忽略了它們本身,還忽略了它們所有的後續節點。因此,這一技術可以刪去數量相當大的節點,因而也就大大的節省了搜尋博弈樹所需要的時間。

相關詞條

熱門詞條

聯絡我們