好在我們定義完game，一個game上面所有的這些 符號之後，接下來我們看下在這樣的fomulate玩這樣的game裡面，如果2 players zero-sum的情況下那何謂 Optimal Decision哦。那在這邊我們定義一個minimax的函數。 基本上就是在這個state裡面，如果你這個state是已經terminal的情況下- 那我就直接 回傳utility。好，那否則的話，看你這個term,如果你這個state還沒有 terminal那，看你這個state你這一回合的玩家是誰，我們有兩個玩家嘛。 如果是zero-sum上的情況下，那玩家1的utitlity越 高，就代表玩家2的utility越低。因為我們後來fomulation上只寫 一個utility。那我們如果把這個utility定義在player1的身上，那- 也就是說 player1會想要盡量最大化這個utility。那相對來說，player2想要 盡量最小化這個utility。那因為他們這兩個player這種 特性不同所以我們習慣上把一個player我們player1稱作max,player2稱作min 這個很好記。你就只要想說max就是想要max那個utility， min就是想要minimize那個utility. 那這樣的話，那所謂Optimal Decision會發生就是在 如果你player是max的情況下，他就會想在你目前這個state裡面如有可能的action裡 面挑選一個使得，我剛這裡面result,就是 你在這個state裡面做這個A1之後會到的那個state的那個utility是最大的 它會做這樣。那同樣min的話走的就會，想要這個值最小。那我們接下來，在這個圖裡面 我們有一些symbol，因為我們在這一講之後，我們會不斷地使用到，所以我們這邊簡單- 介紹一下。那 首先就是這一個符號來代表max 那用這個符號來代表min 那這還滿容易，視覺上還滿有效果的。那在滿多人工智慧的 課本或是範例上，他們用另外一套系統。 是用方塊來作為max,然後用圓圈來代表min。 所以各位同學如果在不同網站或是課後不同教課書上看到這套符號 也要稍微習慣一下。但是在這一講里我們都會以這個符號來作為例子。 好，也就是說，用我們symbol來說這一層,就是這個回合 是，我們從上面講呵，這個回合是max ok, 那，接下來這是min然後換max下，換min下 好那在這種情況下那下面這邊列的，最後這邊 假設我們在這一層的時候，假設這個game都已經終止了terminal的情況下，都可以直接把它算出來 我們之前講的通常習慣，我舉的例子可能都是零，或是正負一這樣子，正一就贏了，零是和局，負一就是輸。 零是和局，負一就是輸。那在不同的，可能在不同的game,有些時假可能不是只有輸贏那- 麼簡單了，所以他utility可能 如果說有分數，那你希望,就一個希望分數越多越好，player2就希望player1- 的分數越少越好。反正 總合是零和。所以utiility可能有不同的數值。那我們以下面這個例子而言， 那，比如說我們看這個四跟八，那min這個player的話，在這個之間點，如果已經到- 這個狀態 的話，那他會選擇的是走四這一條。對不對，因為他希望player1的utility- 越少越好 所以我們就可以把這個節點寫四。那同理來說，象這個一就寫一，那這邊二和五裡面取小的 這邊會是二，然後這是五跟十，小的是五。這十五。二跟零小的是零，然後三 跟十小的是三。好，那這是，如果 如果game已經走到這一個，這個state的情況下 min這個player會，如果你假設他是就合理的，做這些事，他應該會選擇這樣的路。 我可以把，這邊可以標一下。二是這條，一是這一條。 十五，零是這一條。三是這一條，好。 那我們在回溯上一層，到這個state上一層是max在做決定的。 那所以max來做的話，他這邊只有一條路，他就一定會選擇這一條，我們一樣可以把這標成四 那在第二個這個地方，二跟 一，二跟 一這兩個情況下，max會選擇，河流要盡量最大化自己嘛。 所以他會選擇二這一條路，那這個是二，以五跟 十五這裡面他會選擇十五這一條路。 這裡就寫十五。三跟零他會選擇三這一條路。 好，那在他回述上一個，同樣，你可以繼續往上做，min會選擇二這一條路 然後這邊min會選擇三這一條路。 好，最後一個比較，三跟 二裡面，三比較大 所以max應該會選擇三這一條路。好，也就是說在這個game tree裡面，如果 min和max這兩個player都很合理的去做他們自己的決定的話，這個optimal decision在這個時間點 max的optimal decision應該是左邊這一條路，結果他有 兩部可以下，他應該選左邊這一條。因為左邊這一條對他最有利他可以拿到 如果min都好好地下的話，他可以拿到三的utility，那選擇右邊那條路只有二。 那這樣的前提，你當然要注意一下，這個前提當然是假設min是很合理的 行為。，因為你有兩個人下，這個optimal不是一 個單一的決定。你還要depend on 對手。 因為說實話，max走這條路，走右邊這條路 你也有可能，比如說右邊這條路最大的是八嘛 你仍然有這個可能拿到八這個utility，不過那是要指對手犯錯的情況下你會拿到八。 那你想像，你可能不應該去假設對手會犯錯這件事，那你，所以比較合理的決定還是往左邊。那 這是在我們這個例子，在min max這個栗子我們一般習慣上 所這樣的decision稱作optimal decision，那是背上一個minmax的manner. 那它的implementation上，課本上也有一個pseudocode,就是minmax search的pseudocode 那基本上他分成兩個function，一個是就是min，一個是max 然後min就是第一個遞廻呼叫了，min第一回呼叫max,max第一回呼叫min 那，他有，當然你在這兩個函式一開始先確定 有沒有達到terminal state。那，那如果關於 implementation有興趣的同學就看一下課本上的例子就好了 但是實際上我們在實做這個程式的時候，你如果真的把它寫出來，你會發現 min跟max 這兩個函式基本上長得一模一樣，唯一的差別就是min在找的min, max在找的是max,其他的基本上都一樣。那我們觀察一下，如果在two players，就是我們剛剛 我們現在講two players零合的情況下，我要找這些action裡面，就這些數值裡面最小的那一個 其實完全相當於我在找這所有數值裡面去負號，然後找它最大的那一個，然後之後再 取負號。好，這樣應該沒有問題吧。就假設這是一，二，三，那我最小的就是一嘛。 那有一種方法可以直接把這全部取負號，負一，負二，負三，那這裡面最大的 是負一，對不對？對這邊為止，最大的是負一，那你再負回來，他就是一 好，好，那這數學式當然是滿 明顯的。 所以我們可以把兩個function直接 就是在code上我們可以直接縮減成一個。也就是我們如果找max 但是你上一次，下一次呼叫的那 回傳值，你要回傳一個，回傳一個負號回來，就回傳值你就一個負。 遞廻呼叫的時候就一正一負，一正一負，你每次都取max,然後 當你呼叫那負的那一部分的時候，其實你就是在找min 找負的max時你就在找min。好，那這是這一種implementation的方式。 那只要，不過要記得這邊要回傳的可能，你必須要player一起考慮進去，就是 看，因為terminal不一定在max那個節點結束，可能在min那個player結- 束。因為 不同的地方有不同的結束，所以你，你的確就是如果在max回，結束的話，你直接回傳utility就行。 好，你要寫一個X也行，就max, 你要回傳utility，如果min的話，你要回傳負utility. 好，這樣才能保證整個過種是是一樣的。那我這邊寫 你也可以直接寫utility P這是一樣的。就把player傳進去，這是一樣的結果。 好，這邊還有一個小小detail的地方，在我們的第五行這邊，那第五行 按我們function來說，我們要拿到從S執行一個A,我們要拿到一個S'，好，可是- 實際在做的時候呢，因為你如果 從，等於你這邊要有一個local的variable一個S,一個state,然後你 要弄到另一個S'這個state，那當然因為實際上我們是用 dfs，所以 記憶體其實還好，可是其實你 記這個盤面狀況棋盤其實還滿不小的呵，那你如果，即使linear有時候也是某些情況也是- 有點過大 執行效率會比較糟。那我們比較常做 的方法其實是有一種，我們在這邊其實並不會記錄S跟S'而是真的把S do 一個A 然後真的把它變成S',然後把S'呼叫進去。那這個呼叫完了以後 在這個呼叫完了以後，在第六行和第七行之間 我們插入一個就是undo，或就是一個backtrack，那這個東西做，實際上做 說一件事就是把s'再把它變回s. 好，這件事還蠻常做因為很多時候棋盤的更動都是非常local的. 譬如說像 我如果我們真的寫個五子棋好了。你唯一的差別就只是說某一個子。什麼顏色的子， 黑子還白子，擺在某一個坐標。 你只要記錄那坐標就可以了。那你undo的事情也很單純就是把那坐標的地方重新變成空格。就這樣。 跟之前一樣我們用四個面向來探討以下MiniMax search. 呃，就是，呃，第一個是它會不會complete. 呃， 那只要tree, 你要given tree是finite的情況下，yes. 好，在大部分的遊戲， 如果是像象棋，中國象棋或是 西洋棋它其實是有可能有無窮廻圈的啦。就是 呃，可是大部分情況下我們都會用，運用一些規則來避掉無窮迴圈。 譬如說像在象棋裡面就是你不可常將，不可以長捉。 呃，如果，你如果得有在下象棋這些你應該知道我在講什麼。 那還有包含是長捉有很多定義。就包含說如果是 A能捉B，B不能捉A的情況下。那譬如說我車，車要吃炮， 炮就移，移一線嘛，那車再過去捉。 因為這種情況下如果炮沒有隔一個不能打。車，所以，車捉炮，炮移， 然後再捉炮，再捉炮。那這樣有規則規定是 持車的那一方要先變招。不然的話就先當作是輸。那像西洋棋裡面有好像 呃，你可能詳細要看一下規則，這裡還蠻細的。但是我印象中是比較 沒有防止這樣loop的 條件，但它大部分國際賽是有規定就是你如果過多少步你還沒有終局就視為和棋收場。 那這樣的話其實也是使得game tree是一個finite。 而且其實有這樣的規則其實是有利的那一方 想要變招嘛。因為他會想要避免和棋因為和棋對他不利。所以大部分情況下就是yes, 就是completeness. 在實際上的大部分的電腦對局。好，那如果是， 呃，我問，optimality其實我們剛有談過一陣子。就是，呃， 我們可以做在MiniMax上用MiniMax的manner來做optimal的 decision. 但是它optimal的保證只有在你的對手也是optimal的時候 你才是叫optimal. 我就用我們剛剛秀的這個事情，就我們剛剛這個例子。其實我們說optimal的情形 跟據MiniMax來說你應該往左走。 可是實際上你往右走如果你的，你的對手不是optimal你有可能拿到8。這是有可能。 你如果這邊你往這邊走就對手都下 反而下都下很好你只拿到3。好這邊只有拿到8。那顯得，就好像顯得我們往左走這個 決定不是，當時，在當時不是optimal decision. 所以我們必須要討論 你的optimality是yes, but only if你的對手也是optimal. 這種情況下你的決，你那個決定才是optimal. 那在實際的電腦對局上其實有很多小技巧。譬如說， 呃，如果電腦這以憑形式判斷它已經是覺得不利的情況下，就是覺得它這樣下下去一定會輸的情況下 其實我們也不贊成就是，呃，在製作期的時候其實我們也不贊成 你繼續用這種optimal decision 來做。因為這樣下去你一定是輸定的。好在圍棋上其實也有這樣的現象。 好其實甚至不要說電 腦對局，就人跟人 互下也是有，我們稱為放「勝負手」。就是圍棋就是在圍地嘛。那你， 你已經覺得我繼續護圍下去遲早我感覺我會輸個五目或十目。 平和地圍下去一定會輸。這時候我們稱為放「勝負手」就是你可以毅然決然破人家的空。 雖然破人家的空很可能最後就被人家吃掉，然後人家活更大一塊。然後那種情況下你就可以投降。 好我們稱為，就放「勝負手」那輸了話你就投降。那這個策略在電腦的話其實一樣的。 當你覺得平穩地下下去會輸的情況下你也許不應該繼續走 所謂MiniMax manner的optimal decision. 你也許應該設法誘使對方犯錯。譬如說像這種情況下就是說你算出來的utility， 假設電腦算出來自己的utility都- 是負的。 你就是最好的那個下法也是負的。意味著你繼續下下去會輸。 那，你可能走那個，可以考慮走那個branch factor比較大的那一隻。 就是因為步數你走到這個state, 人家branch factor非常多。 那你可能傾向於相信人 比較希望就對手犯一個錯誤使得你可以扭轉趨勢。好在這種情況下，optimal, 因為你是兩人下所以optimal要depend on你的對手 來決定。 好，那time complexity這種search大部分都一樣。 就是你還是 exponential ，還是 branch factor的 m次方。 那space complexity, 呃，MiniMax可以直接用DFS來做。其實我剛在講的時候， 你如果看到intermine是一個遞迴呼叫的東西嘛。 那如果看一下跟，其實這跟我們dfs的invitation非常，根本上就是一樣 啦。即使你用Min.Max兩個遞迴呼叫也 是一樣，但你用naga更明顯。就是你一路， 就是，呃，這個code其實一路就伸下去。它的search方式是， search方式根據code的話它是先這樣走。走到這邊再回來。然後再走到這邊再回來- ，再走到這邊。 大家可以trace以下那個code它整個感，它整個走法就是標準的DFS。 而既然是DFS的話那它的space complexity就是很好，基本上就是linear了。好，大致上是這個樣， 那我們也提過 就是你只需要b乘m這麼多。那你如果intermission小心一點你是可以做到big O(m). 但一般來說你不見得需要這樣嘛。 這樣的space，我們是已經很好可以接受的。好，那 如果像針對西洋棋這樣的遊戲來說。那branch factor大概是35然後m大概你要走一百步才能終局。那，基本上 35的一百次方你這個花的時間實在是太多。以至於iii更不可能達成。 所以我們先簡單講問一個問題就是在MiniMax search裡面是不是每一個結點我都必須要探索。 好，那其實答案蠻明顯 就是其實不需要。好，我們先看一下 像下面這個例子。這是，這一層是 min啦，這一層min。好，這一層max. 這一層是min. 好，呃， 我們看一下這邊，我這邊有三個x,y,z. 好這三個，我沒有把數值寫出來。原因是什麼呢？ 原因是這三個數值不管是任意數字，都不影響 最後這個數字應該是三。也就是說mean應該會選擇走 左邊這一條。我們可以看一下，譬如說，x這個數字好了。 好，今天如果x是比二還大的數字。 因為這個是min嘛。還要記得一下這是min. 如果x大於二， 好，那左右兩隻。 因為這是min, 所以min一定會選擇這一個，所以這一隻是二，不變。 這個就沒有差別。但是如果今天x是小於二的話，那會發生的事情是， min當然在這個點會選擇這一隻，如果x比二還小。但是這造成的結果是這一個結點呢， 傳回左。我不知到會多少，但是小於二。 好比如假設負一百等等。那你這個結局就變負一百。問題是， 在上面這個結點，這個地方是換Max做決定，它會比較三和一個 小於二的一個數字。那三和一個小於二的數字，我根本不需要知道小於二的數字是多少。 我一定知道Max是三。 對不對？所以，這個數字三是不會變的，不管你的x是大於二還小於二。 ok? 這就是為什麼這一個結點不需要search的結果。那其實這個 pruning可以發生在很多更高一點的地方，pruning會砍得更凶。譬如那個地方， 這地方我不知到y,z是多少。那我甚至不care, 因為這邊如果回傳值， 這個回傳值如果大於十五。比十五還大的話，是，這邊會拿到比十五還大的值。 這是大於十五的值。那可是大於十五跟三來說, 上面一個是min來決定。那min會選擇三。 ok, 那你如果這邊回傳的值是小於十五的話，因為你這邊有個十五。所以這個結點呢，還是會- 是十五。 也就當我這邊寫十五的話，這個上面寫十五，你其實可以做個標記，它其實大於等於十五而已。 就我即使不知道這邊是個多少。這是個問號。 那它其實大於等於十五。所以就大家也會看到這整個部分是可以碰prun掉。 那這個例子我們好像七個結點我們只砍掉三個， 好像效能還好。可是實際上當我們搜尋深層一點的時候這邊代表的 可能是一整個非常大的一個tree. 那這個tree我是完全都可以不要搜尋。因為我不管它回傳值是多少我都不會影響我的決定。 那下面有列些例子，就是如果我們把 min, max, 就是用這manner寫下去的話你可以發現不管我的x,y,z 是多少你都可以直接算出來它其實就等於三。 Okay? 那這個，這個講法就是我們剛剛講的，就是你，比如說十五，你這個min, 這邊你當然是不知到你是個問號。但是跟十五取max以後它一定是， 它一定是一個，呃，大於等於十五的數字。就是這整個數字大於等於十五。你跟三取min, 你還是可以 取得出來，它就是三。
