[音樂] 那我們當時舉的是例子,就是
直接跟,跟各位講說在整個tree的search裡面有一些是不需要被探索的。
那我們怎麼在演算法上直接 用計算方式直接讓我們知道這些是不需要被探索的呢?那我們稱為alpha-beta
pruning。
那原因是因為原paper, 第一次發表的paper,它的 iii code裡面就使用了alpha
它利用了一個alpha來keep lower bound,就是keep下限,叫lower bound
那就是到目前為止,我至少是iii, 那用另外一個beta來keep上限
好,upper bound,好,也就是說我造成一個window,就是alpha 在,在這邊,beta在這邊。
造成這個window。
在這個window 以內的我才有探索的價值,在這個window以外的其實都沒有特別的探索的價值
那既然第一篇paper使用,使用了alpha-beta這兩個數字來記錄,所以我們習- 慣上就把這個pruning方法稱為 alpha-beta pruning。
那這樣重點是在這整個alpha-beta pruning的過程其實是不失真的,也就是說你使用
的pruning會讓你少搜尋一些節點,可它完全不影響你最後的結果。
它結果跟minimax應該是完全是identical的 好接下來我們看一下alpha-beta pruning實際的一個例子。
呃,好,首先 就是我們一開始沒有特別的假設,所以alpha就是負無窮大 然後beta是無窮大。
也就是說我們接受任何 從負無窮大到無窮大之間的範圍,整個值,也就說我們
不特別預設這個節點的回傳值大概是多少,反正就是負無窮大到無窮大。
那之後 各位可以參照那個我們的後面有兩三頁的code,接下來就是把這個alpha-beta-
一直往下傳 那所以一開始很單純,就是負無窮大,無窮大,然後傳到這邊,傳到這邊。
好。 一直到這裡的時候然後你看到 應該說看到這一個。
好到這邊你dfs嘛,做dfs, 看到第一個3的時候,那這邊是一個min node嘛
那min node的時候呢,看到一個3,那它就會更改 大家可以記一下哈,min值會修改。
呃,min值修改beta max 修改alpha。
好,這是基本原則 就是,min的話,它會一直想辦法,就是alpha,beta是上限,就是我目前的上限。
那 它會一直根據你看到的東西不斷地往下修正。
就是修到目前認為 最好的,最okay的值。
譬如說像這邊那它看到3的時候,那它就會把這個 這個window改成負無窮大。
負無窮大到3之間 意思是什麼呢?因為這個是min
node,意思就是說,這個,它的意思就是預估 這一個節點的值。
我現在還沒看這一個對不對?我現在還沒看這個值。
但是不管這個值 看到是什麼,我都有只有可能再把3往下修了。
也就是說這個 值的意思,這邊我說負無窮大到3的意思其實相當於最後最終的值應該是一個小於等於3的東西
好,答案就是大於等於負無窮大這個實際上這個節點的值,就界在3到負無窮大之間。
也就是說 如果我這邊,如果我今天看到負一百,那我會再度把這個beta值再往下修到負100
但是如果我今天看到這一個,這個值,下次等晚一點我如果看到 別的值,如果更大,那我就不用修正,其實就是我們等一下發生的事情
好,所以我今天做的第一個動作就是去修正這個,這個beta值
那接下來我又看到10,好,這邊還會做一個動作,就是它會取一個 目前的beta值是等於3的。
對不對?然後再看一個10,我看到 實際上是10,然後我會這兩個東西取它的min 好取它的最小的那一個。
然後再去修正,如果它有比現在3還小,那我就,比現在beta還小,我就 修正beta,好等到這個這兩個都看完以後,beta就確定。
也就是這個節點雖然我寫 負無窮大到3那實際上就是3了。
實際上就是看完就是3。
那之後min會把自己的 beta的值傳上去。
好傳上去其實就,用那上面,上面這一個是max 那max就會用這個值來修正它的alpha
好,也就是說在這裡的話,就是,就是它會比我們之前的
alpha是負無窮大對不對?那下面回傳一個3上,呃,3上來。
然後我們就會 比這兩個的最大的值。
就是負無窮大和3,所以我會把負無窮大丟掉。
改成 3.。
那現在alpha就是3,那這個節點呢其實就是3 呃,無窮大。
意思是說呢,就是,這邊畫這個圖。
意思就是說我接 下來的這個值,我還沒有看完,可是這個節點的值應該是界在3到無窮大之間的一個值
okay,另外講法就是應該說大於等於3嘛,這個不知道是什麼 總要大於等於3,小於等於無窮大。
為什麼?因為它是一個max node嘛,那我已經有一個 節點傳回來跟我講是3了,那之後如果傳回5,那我知道它
anyway,要大於,就是比3,可以比3還要大。
那如果是,接下來有一個譬如說 比3還小的節點,如果說負2等等,那我不會跟動3,因為max會選擇大的那一個
也就是知道這個節點至少是3起跳。
好,這是這個概念。
好這邊畫的 window就是相對,就是這一個,就是我這邊畫的意思 好。
那再繼續做下去呢,嗯,回到這裡 我們剛才這個位置。
那這邊已經知道是3,無窮大,那接下來它會把自己的 alpha beta值傳到下,下面去。
然後這邊就是看到就是3無窮大。
也就是說如果今天 我在這邊看到任何一個不在3到無窮大之間的這個範圍的值 代表我不需要再看。
因為你剛才傳上去,上面那個節點也 不會take你這個值。
我是上面這個node已經確定了它的值是3到無窮大之間,那我如果
現在下面看到任何一個不在這裡面的話,那,上面,不會影響我上面的這個節點的決定 好那我們一步一步來,好。
這邊3無窮大傳過來說這邊到這個時間點 還是3,無窮大。
好,那接下來一樣dfs嘛,往左邊看,看到2.
好,這是一個min,這是一個min node。
那同理,min node我們更改的呢 是,呃,beta所以我就把這一個上限往下修正,就是
無窮大and 2,裡面取最小值,那這是2。
好那2的意思 是什麼呢?到這邊其實你看這個window已經中間沒有交集。
就是說它是一個 呃,beta值已經小於alpha值了,上限其實跟下限兩個交錯
這代表什麼意思呢?因為這邊的2的意思是說 這個上限的2的意思是這一,這個點的上限
因為我看到一個2了嘛,那接下來因為我會取min,我是min node,,接下來我不管看到什麼值 我會取2跟這個值的min。
也就是說我最大最大這個值,回,這個點回傳的值會是2 也就是說,呃,小於等於2.
好我這邊,接下來我這個還沒看,對不對? 這個點還沒看。
但是不管我看到什麼。
我這個節點已經確定可以回傳的值是小於等於2。
那這一個 這一個3呢是上面傳過來的。
是上面的alpha值 意思是說我不管這一個,自己這個min
node節點回傳什麼 這一邊只會回傳大於等於3的。
好那既然我在這個節點 我在這一個地方,我知道我回傳的值會小於等於2,我上面這個東西回傳會大於等於3
意思就是說我這個地方不用看。
我不管看到什麼都沒有差。
好。 我,我們 舉強烈一點的例子。
譬如說,我舉個很小和很大,譬如說我這邊是負100的話 這個值是負100的話,我2跟負100取的min會是負100
對不對?然後這邊是3,這個節點是3,所以3跟負100來說它還是會 選擇3,它會選擇3。
那我們再換一個,如果今天這一個 值,這個值是呃,100的話,那2跟100
取min會取出2,然後2跟3取的max還是選3
大家就會看到我不管這個,這個,我還沒看的節點 是很負的值,或很正的值,都不會影響這個節點所選擇的
這一條,既然不影響,那意思就是說我們可以很,很開心地直接把它砍掉 好,這個值完全不影響我們的東西。
那在演算法上,就是簡單講,就是這個alpha是上一個節點傳下來的alpha 這個beta呢是你現在修正的beta。
當你這兩個交錯的意思就是說我接下來 不管看到什麼都不會影響我上一個,上一層節點做的決定。
這個時候我可以安全地把這個節點砍掉 好,呃,我們繼續把它run一下,因為大家第一次碰到,好。
那接下來,這邊砍掉以後 這是2,然後,回,這邊還是會回傳一個值2.。
那可是 2跟3,這邊會回傳一個值2,然後2跟3
會比較max,然後並不會跟動 並不會跟動3,所以它還是一個3。
然後這個3會回傳 回傳3,然後這時候會修正
這是一樣min node,這是一個min node,所以它會修正它的beta
好,所以會改成就是這邊看到的,負無窮大,3。
也就是說這個node 我已經看到一個3了。
如果是min node,我又看到了一個3,所以接下來不管看到什麼,我知道一定是小於等於3
負無窮大的一個值。
okay,接下來,我們繼續看右邊這一支。
那一樣就是 負無窮大和3,alpha beta 傳進來,所以這邊一開始是負無窮大還有3,然後接下來
dfs一樣走到這一支負無窮大,3,好,接下來我們看到15這一個數字。
那 15 這個是 min nod 嘛,那基本上就是一樣,做一樣的事就是會更正
β 值,那 3 和 15 中會取一個,它們的 min,那 min 還是 3,所以這邊β
值並沒有 動,那這邊已經走完了,所以它會回傳,目前這個,這個節點所要決定要走的
15,所以這個這個 回傳值其實就是這個節點,它說了展開
children 裡面, 若是 min 的話就 take min 最小的那一個值。
也就是說,實際上我 如果真的走下去會走的那一個,那個 value,那如果是 max 的話就 take 那個 children 裡面的 max 的值。
好回傳 15 以後,這邊是一個 max nod。
那 Max nod 做的事情就是要 更正,修正那個 α,就修正那個下限。
所以它會做 -10,-∞ 和 15 取它的 max,那取得結果就是
15,所以直接就會把 -∞ 改正, 改成 15。
好這時候就發生了 Pruning,就發生了 cutoff,也就是 15
跟 3 已經 沒有,就是你看這個圖,已經沒有,這邊已經沒有交集的,所以有興趣已經沒有交集了,所-
以這時候 cutoff 發生以後,就可以,下面就可以全部砍掉。
好就是在這邊發生,我從 -∞ 到 3 回傳至
15,然後我們修正它的 α 值, 砍掉的時候發生的 Pruning。
號這個 Pruning 的意義是什麼呢?也就是說這個 3, β,是從上面 parent 傳下來的。
意思就是說我只有 在 parent 上只有小於等於
3 的數值, 它的 parent,就是這個 nod 才有興趣。
有這個 nod 有興趣的就是 小於等於 3,大於等於 -∞。
好原則上我們跟剛剛講過的 一樣,就是這個 nod,因為我們有看到一直是 3 嘛,因為它是
min nod,所以它, 一直是 3,是 min nod 的情況下,它回傳的值,我不管其它看到是什麼,我一定回傳的值是小於等於
3,所以小於等於 3 呢就是 這個 β 值我才有興趣。
那這個 15 呢是從它的子帶傳上來的,意思是說我有看到
某一個是 15了,那我自己呢又是 max nod,所以 我接下來要回傳的值一定是大於等於 15。
好,我大於,我回傳值是大於等於 15的,那我的 parent 有興趣值小於等於
3,所以兩者沒有交集,也就是接下來我這個 nod,我這個 max nod 在看到什麼 我的 parent 都不會採用。
好多種情況下我們可以安全的把這下面的 這個整個樹狀砍掉,好這是α,β Pruning 發生的狀態。
好,我們大致上把這個大概走一下,那接下來到這邊 你會回傳的是
3,然後你會把原來的 -∞ 和 ∞ 這一 個的 α 值修掉。
好 α 值修掉,因為這個一樣,這是 max nod。
好,那接下來這個(3,∞)就會, df(x)就這樣回傳下來,(3,∞)
(3,∞),(3,∞)到這邊還是(3,∞),那一樣這邊你會看到一個 2,這是 min nod。
你修正的是 β,對於你把 β 修正成 2,那一樣
發生 cutoff,所以這邊,把,又可以把這個值切掉,好類似的
是一樣,那你這邊 2,因為你看的是 2 嘛,2
會回傳,那 到這裡回傳值的時候,一樣會,在這時候會發生一個
(3,∞),然後,這是 這是 min nod。
所以它修正 β 值,那 β 值這邊回傳的是 2,之後會發生
cutoff,就是 3 跟 2 cutoff,所以接下來的這一整個樹都可以砍掉。
好我們前邊 tree 這邊比較 detail 那這兩頁請同學回去試試看,你如果
tree 的結果能得到跟我一樣的結果,那你應該就是正確的。
那最後就是,到這邊,最後就是回傳這個值是 3,那麼這個如果你用
min-max search 的話會跟我們用 α—β Pruning 的結果是一模一樣的。
好這邊是 α β 的[iii] 那為了簡單起見,我們這邊,這邊先提供一下,
同樣我們可以用,因為 min,max
然後因為突破了記錄上的結果,我們一樣可以把這兩塊 我們這一區,還有這一區,這個是
max 的,那 這一區是 min 的,那我們一樣可以把它寫成一個
[iii]的方法,好我們等下一期,下一個投影片裡面會秀。
那這裡就是在做所謂的 上限,如果是 max 的話它修的就是在修
α 值,好配合這一個啦,配合這一個。
就是第 6 行,第 8 行在做的就是修 α 值。
然後,第 6 行其實 v 就是,就是,就是我現在的這個節點所會,最後所會回傳的值。
那第 7 行, 這一邊,就是還有第 14 行發生的就是 cutoff。
就如果這個這個 [iii]成立的時候,就代表接下來我 的我不用再 search,這是一個full
loop,這個 full loop 裡面我不用再繼續做,我直接return,cutoff。
發射,ok。
那,然後我最後回傳的是 v,就是我這個節點所會 做的最後決定的那個數值。
好這是這幾個重點點出來。
好那 我們剛剛提過,就是一樣,因為突破了記錄上,所以一樣你不用一個選
max 一個選 min,你可以選 取負號然後求 max 然後再取負號,那這和你求 min 的做法是一樣的。
那我們可以用類似的做法做成 就是 AB,這個 AB 就是 α β 的意思,然後 NEGAMAX。
好那如果 是 NEGAMAX 裡面我們永遠都取 max,那回傳的那個值我們
take 負號, 就是一次取得就是 max,那下一個,下一層
[iii] 取得 取得 effective 取得就是 min,再下一層去的就是 max。
但是我們有一個小問題就是 大家還記得麼,max 你修正的是,max 你修正的是 α,min
你修正的是 β, 那你我要怎麼做這件事情呢,就是你,你在不同,我要同一個方法來寫 iii,所以我傳進去的時候這邊 α β 要互換。
要調換。
它們取負號是為了,取負號是為了那個取 min 和 max,但是你要
一個修正 α,一個修正 β,所以你,你就把 β α 互換,要當做那個傳下去。
當做下一個節點的 α β 傳下去。
這樣的話,你雖然,我們修正,這邊看起來修正的似乎都是 α,
但是因為我這邊會互換,所以在遞回呼叫的時候下一層修正的 其實是 β,再下一層是 α,再下一層是 β。
等等。
我盟剛剛做了一些 trees,那 detail code 也提供給各位,那大家回去真的,要真的很了解這個
整個,就是按照那個 code 一個一個,一步一步 trees,這樣你如果能 trees,
剛剛的例子你其實應該就完全懂了 α β,那 α—β Pruning
它有個 它的,如果用比較抽象化的講法它是什麼意思呢,基本上
就是如果我這邊,我會走到的是 m,那麼這邊是 n 節點。
如果 m 其實比較好的話,概念上就是其實我永遠都不會 在。
實際上如果你的對手也是一樣,很強的話,那實際上我永遠都不會走到的。
走到這一個地方,也就是這一個地方是可以砍掉的。
好,那問題是,我怎麼知道 m 比較好。
好這是我的問題,我怎麼知道 m 比 n 好。
那就是利用 α β 這個上限和下限的辦法,來不斷地 慢慢,就是一開始是 -∞
到 ∞ 嘛,那隨著你整個 search 的過程,你收集的資訊越來越多,你會把
α 往上提,然後 β 往下拉,使這個 window,你有一個新的
window,就是你對這個 m 的估計你會越來越 知道我有興趣的值在哪裡。
直到我有足夠的資訊確定 m 絕對比 n 好的時候,我就可以做這個 Pruning。
好這是 α β 的基本想法。
α β,我們做這個 Pruning, 到底能 Prune
多少呢,到底多有效率?其實 如果你真的去撞幾個
case,你會發現它跟我 check[iii]的次序有絕對的關係。
如果我一開始看的都是很 不 promising 的[iii],其實基本上我能 pruning 的很少。
那如果我一開始看的 都是蠻好的部署,通常我就能把比較 不好的部砍掉。
就是呼應到我們前壹頁講的,就是如果我 先看 m,那搜集到足夠多的資訊,那 n
是一個比較遭的,那我就可以馬上,就可以找我搜集到的 夠多的資訊說 m 比 n 好,那我就可以把 n 砍掉。
可如果我現在反過來,你是比較差的先看,那你 你就算是收集到很多的資訊,你還是沒辦法
pruning 嘛,因為後面那個 m 就是比它好,你如果就算你收集的再多,你還是一定要走到 m 那個 地方。
所以說你的次序其實很重要。
但是如果你沒有 pruning 的時候, 就是你用 α β[iii],也 了不起
你完全沒發生 pruning,那其實就是你 reduce 回 min-max search,就是沒有更糟。
α—β Pruning 很好 的特性就是其實就算 cutoff 從來都不發生,你的
效能跟 min-max 基本是一樣的,當然你有一些 overhead,因為你要比較一些數值的大小。
可是你會有 overhead。
但是這些 overhead 的代價其實一般來講一般非常非常少。
你會比傳統的 min-max 可能慢個 1%,2%,這樣 的 price 我們一般來說都是付得起的。
那 best case 是什麼呢? best case 其實你如果永遠都 check
最好的prune 的話, 我們能做最大化的 cutoff。
那大致上 畫出來是這個樣,就是,如果我畫一個三元素的話。
好如果很好的情況下,基本上到這邊,我過來 這個都要看,這三個都要看我才能知道這多少。
可是接下來做的事就是可以這兩個不用看,這兩個不用看。
好,全部都是,如果還有更多,更多 nod 的話。
如果真的做得到,這兩個都可以看到。
也就是我第一個值已拿到的時候 到的時候,我就發生了,在這一個地方發生了cut off,把後面這個砍掉,這個砍掉。
哦,這件事是可以做得到。
那這種情況下你會發現只有我, 我effective的就是什麽呢?這邊的branch factor
就是b,那接下來我只, 接下來這邊雖然有一個b,但是平均來說,這一層平均只有1。
對不對?就是只有b得到全砍,剩下大慨都是平均大慨是1,所以這層是1。
那種感覺,就是你平均的effective branch factor.
那到下一層又會發生一樣的事,就是minimise 的,的特性。
這一層又一定要全砍哦,就是,這一個,這一層也一定要全砍。
如果下面還有,那你才能確定這一個是多少?所以類似的事會一直重復,所以best case
是其實 其實大致上是類似iiifactor 就像是這樣,b乘1乘b乘1乘b乘1。
好,那哦,如果這樣做的話,其實平均就是 b的2 之m次方。
好 好[iii],那,如果我今天我一個ren 等O,ren 等O的情況下,哦,我這
我比較複雜的分析,好,那有這些paper可以跟你講大致上是4分之3m,b的4分- 之3m。
好!大部分在,我們在分一[iii]上,我們該勇敢[iii] 我們在[iii]分析最care的是兩個case嘛。
一個是哦,worse case,哦,worse case analysis.那另外一個很重要的是,哦
哦,average case,就是平均來說我大慨要花多少的時間。
一般在大部分也算法的分析,我們實際上很少 比較少去care best case.因爲best case的地方很少發生。
好,這在α–β pruning 剛好是完全的例外。
我們雖然average case 是這麽多 worse case 是這麽慘。
其實α–β pruning很容易做到接近best case. 很容易,並不是非常的困難。
哦, 最簡單的方法就是用,利用iterative deepening.
好,我們剛剛秀的例子都是,都是,我,我畫個元素就好,我們剛剛秀的例子都是,
是直接走到最後,
就是DFS直接沖到下面 哎,我真的很會畫傘。
好,um,就直接沖到最下面。
但是你可以用 iterative deepening,比如説你第一次search卡在這一邊,對不對?在這個時候你如果-
apply你的 哦,我們等一下會講到heuristic。
如果你在這邊有辦法用評估函式估計這兩個,那個比較好的話,你可以先對它做一次評估。
好,然後之後,你去order。
譬如說,這一個比較好,這個比較差。
你可以reorder,你可以優先走這一個. 然後之後你在第二次做iterative
deepening, 做到第二層的時候, 你在這邊評估嘛,對不對?然後你會有囘傳值。
這時候你的評估點可能更好。
就是你會囘傳。
這邊會囘傳一個,你這邊apply heuristic.我們那之前有講過,越底
底層apply heuristic. 你的[iii]可能,可能狀態越好。
那在這一邊囘傳,譬如說你這是 mean 的話,就取這兩個的mean.那你在這邊一樣取這 這下面兩個mean.
那下一次你在,你在,你在的search時候,你再用一個 第二層的評估來做你的ordering.
而且這時候第二層也有,你要攝取第三層的時候,你把 一跟二層的次序用,前一面iterative
deepening的, 的結果來做reorder.
那其實這樣做蠻多,蠻多case一下,只要heuristic不要太差的話,你都可以達- 到非常接近 best case.哦,非常接近。
當然還是比不上best case.但是不會差很遠。
所以我們大部分來説,在評估α–β pruning的效率,我們通常都以best case來當作 當作基準點來討論。
好,那best case的這種情況下到底我們 哦,省了多少東西呢?你有兩三种講法來講嚄。
有種講法就是説, 因爲基本上它是等於根號b的m次方嘛。
哦,它就 完全等於這個東西。
所以有一種講法就是你可以把,用branch factor來講話就是你把
breffective branch factor從 b 變成根號b. 想法就是這樣。
就是説如果平均你這一,平均所有50部的話,它現在平均 等於每個一盤麵面你只要吃一部就好了。
這是一種講法。
另外一種講法是說 如果給你的同樣的時間,好,你可以搜絮到兩層,因爲在m
m,m比二分之m的狀況。
也就是說如果在 在你不考慮,就是你不用branch factor來講,那給你同樣的時間,原來你只能搜尋 同樣時間你可以搜尋五層的。
但現在你apply alpha beta pruning后,大致上 致上你可以搜尋到十層。
這個a,α–β pruning效率的另外一種講法。
[SOUND]