本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
5-6 Stochastic Games, Partially Observable Games
Loading...
Do curso por National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
140 ratings
Na lição
Adversarial search
Conheça os instrutores
于天立(Tian-Li,Yu)副教授（Associate Professor）
電機工程學系(Electrical Engineering)
好，那我們最後再來談一下那個 stochastic Games，就是如果這個game，
這個遊戲裡面有一些隨機，比如說你是像大富翁你要擲個骰子，沒有人知道擲骰子出來 結果是怎麼樣，好，那這樣的話，我們在
search 的過程，我們就必須要 introduce 一個新的叫chance node 來 好，那這 chance node
就是，比如說，在這邊你必須要，如果 0.5 0.5 你可能是丟個硬幣嘛
那如果是正面的話，往這就是這一支，那反面就是這一支，等等，那 我們如果今天要做一樣，這裡
面我們甚麼叫做optimum decision，基本上我們可能不再是 原來的那個直接的值，而是我們要
minimax 是那個期望值哦，就是 expected minimax value。
OK，那它的寫出來式子其實還是一樣， 就是基本上就是
max 和 min 其實並沒有甚麼差別，這個 差不多，但是如果是你是 chance node
的話，我們就假想把 chance 也當作一個 player，當作一個 player，但是它做事情就是丟骰子，你就把它丟出來，然後決定要走哪
一條路，那這樣的話它基本上就是這個期望值嘛，就是直接 Summation 把它的 probility，然後乘上它的回傳這個值，
那同樣就是跟 minimax 的 Optimum 是一樣的意思，當你說
expected minimax 這個東西其他我們說是 perfect play，但是
perfect play 意思是甚麼呢？就是記得第一個 要套上 minimax Optimum 就是你的對手也是
絕對不會出錯，就是一樣要最大化他的期望值的情況下，那我們盡量最大化期望值， 意思就是說你在
多次 play 下，你的拿到的總 pay off 是最高的。
你要夠多次，那原則上其實講嚴重一點，就是無窮多次，也就是一樣嘛，就是這種運氣成分
即使用你所謂最佳策略，你可能運氣很差，所以這一次打的很低，但是 long term 來說，你應該是 OK 的。
好，這是所謂的我們 perfect play 的意思。
好，那你的整個 search 呢基本上跟 minimax 一樣，但是我們現在必須多一個就是 chance node。
那在 minimax 裡面， 你如果加了 chance node
這個機率進去，其實有一個比較困擾的，是你的 我們要提醒一下，就是 heuristic
是需要特別設計的，要設計的小心一點，因為 原本來說我們大部分的情況下 heuristic
只是一個相對值，對不對，我們不需要絕對，就是對我們來說，譬如說，我們說 國王比皇后重要對不對，那國王你給一千分，皇后給十分，和你
國王給一萬分，皇后給一千分，對我們來說沒有甚麼差別。理論上還是一樣。
你只要是同樣的，某層上放大或 調整，一般來說不見得，在 minimax 上不見得會有甚麼差別。
可是，今天我在加入 chance node 以後其實會有不一樣，譬如說像我們像
下面這兩個例子，那這邊左邊跟右邊唯一的差別就是我們把 1、2、3、4 把
它改正，就是你原本這邊是一 的，你如果今天換另外一個 heuristic，它的相 對沒有變，它就變得 1、20、30、400。
OK，它就不同的用，一種非線性放大 的情況下，那你去看一下這邊，這蠻明顯的，這邊是
一一大於一，三三大於三，那你一跟三這邊 chance node 你要做的是，它們相，期望值嘛，1 乘上 0.2
加上 3 乘上 0.8 結果是 2.6 好，你可以去算這個數字，這就是 chance node 算的數值的方法，那
你可以同樣去算一下這邊，那主要問題是在左邊這張圖，因為這邊 2.6
比 2.4 最後你會選擇往這邊走，但是右邊這張圖，因為值很明顯就是 400 放太大 400 相對是放很大，那你有一個機率往這邊走
的情況下，你這個加乘加的很多，所以最後算出來是 96 比 24.2，所以 在右邊這張圖，你會決定要走
A2 這一個，也就是說如果在原來的 minimax search 的情況下，我們
heuristic 只要是 iii 的變化，意思就是說原本小的還是比較小，相對 order 沒變，原本比較差的還是比較差，原本比較好的還是比較好的情況下。
你 minimax 決定不會更改，對吧，往左邊，左邊這條路好還是左邊這條路好，但是這件事情在
expected 的 minimax 是不會成立的，不一樣，就是它可以會變化。
就是這兩個 heuristic 一個往左走好一個往右走好，所以你在設計 heuristic 的時候
也就是說它的不僅相對的值有意義，這 heuristic 絕對的值是有意義的。
這是一定要小心，所以你在設計 heuristic 的時候，必須要把它絕對的那個值必須一並考慮進去。
好，那我們看一下它的 performance，如果今天 如果我們想要把 α-βpruning
把它 apply 到 expected minimax 其實它很大困難 因為其實你如果看我們剛剛的那個圖，你會發現它不再
apply 在 minimax node 上，因為你在 minimax node 上面你一定要丟骰子，而骰子要 往哪邊走你不能控制，那你可以
appy 在 chance node 上，因為 chance node 上最後就是 min 可以選擇嘛，譬如說，我如果是
min， 那我可以選擇我要走這一個的 chance node，還是走這一個的 chance node，這個我可以選擇，但是
chance 這邊你不能選擇我要走 max，你不能選擇我要走這個 max，還是這個 max，還是這個 max，因為到這邊你就得丟骰子，很單純。
好，所以其實 α-βpruning apply 在，你看我們有三種類型的 node，min
node ，max node 和 chance node，結果它是 apply 在 chance node 也就是說。同理的效率會比原來的差很多，那另外一點，它的
branch factor 呢 你 introduce chance node 之後，branch factor
從原來的 b 變成 bn b 變成 bn，那 bn 是甚麼呢，就是你 可能走的不同的，哦，不同的
iii，假設你是由六面骰的話 我不管那個機率是不是六分之一，不是六分之一也沒關係，因為我 search
還是要 branch 六支， ，將有可能非零的，機率非零的我都要 search 下去 OK，所以這蠻慘的，基本上這個，你如果是，如果大部分就是等於說你
branch factor，有印象吧，基本上 branch factor 只要大一倍，就非常慘，你的
service space 會呈 iii 成長 簡單講就是，你直接
用 expected minimax 去做 search 不管你加不加，第一個是它的 本身 search 就變得非常非常龐大，第二個是你的，之前我們剛剛提的
pruning 的技巧在這邊很多都 不太適用，所以這些去這樣做，簡單講就是在大部分的問題你都不能這樣解，那
有很多技巧來解決這個問題，那我們這邊沒有細講，但其中一種很著名的是蒙特卡洛 叫
Monte Carlo simulation， 好，那怎麼蒙特卡洛概念是怎麼樣呢，就是你現在面對是非常大樹，
非常龐大的樹，可是在這種情況下你沒辦法去真的去 search ，因為這個樹太大，
太誇張，你如果要去做 search，你的深度可能只能一層兩層，那我們 不願意，那蒙特卡洛想法就是那我乾脆不要
不要全走這個樹，我是譬如說根據我的時間假設說，我的時間容許我 search 一 百萬條，10 的 6 次方，search
一百萬條 path，那你這個蒙特卡洛就好像是丟骰子，遇到 chance node 呢那你就 真的根據那個chance 的機率丟骰子，丟出來哪一個你就走哪一個。
我就走一條，也就在這邊我就走一百萬條，10 的
6 次方，走這個 走這裡走這邊，然後你走，你如果時間容許，你做一百萬次一樣的事情，你就
真的去丟骰子走一百萬次，然後把這個一百萬次的結果平均起來當作最後最後這個回傳的- 這個值。
好，那這個稱為蒙特卡洛搜尋，那它就是基本上深不夠。
當然它有很多，這上面有很多地方你都沒 search 但是 在機率上來說也是還蠻不錯的，那基本上蒙特卡洛不僅適用在
iii，那基本上像 最近幾年，像圍棋這個東西，圍棋因為 iii，如果 我不加任何限制的話，它的
branch 基本上就300多，一開始就 361 每一個點都可以放。就是 你的 branch factor
那麼大的情況下，我面對一個那麼大的樹，其實蒙特卡洛還是蠻有用的，那最近幾年比較好的 生效不錯的 iii 大致上都是一種蒙特卡洛
situation 的一些辨析，那有興趣的同學可以在讀一下 最近幾年的一些 paper，那最後我們再談一個就是
partially observable Game，那 partially observable 跟 stochastic 它有蠻大不一樣，stochastic
就是一個機率，但你也不知道骰子丟出來 會怎麼樣，但是我們這邊講，partially observable
意思是說你不能觀察部分是 對手決定，它現在沒有甚麼機率，即譬如說我們剛講 Bingo 嘛，對不對，我們畫一張
Bingo 這 個圖，你不知道你的對手把擺成甚麼樣子，好那 在這種情況下你有不同的
situation，所謂的 optimum 其實是很 arguable 的。
因為你有地方觀察，那對方也是一樣，你不能完全觀察到所有的 information，所以
甚麼是 optimum 呢，很難講清楚，那 這部分通常研究都通常涉及
iii 理論，那在這 iii 理論其中有一個蠻著名的東西叫做平衡點，那平衡點，有各種平衡點。
那其一種蠻著名是納什平衡，那一般而言有一種
大家公認的就是如果在一個遊戲，如果納什平衡存在的話，一般我們會把
納什平衡稱為最佳最佳。這是一般一種講法。
好，我們這邊很簡單介紹一下 Nash
的觀念。那比較詳細的觀念其實那像 賽局裡面的coursera課上其實也有。也有這樣的課程。那大家有興趣可以去看看。
那大家再去，網絡上還有其他資源。那在這門課本的話其實有提到，在chapter 17.
第17章會提到。那我們這邊是，略過，我們只講一下。
那 Nash equilibrium，提出就是這個 Nash 就是John Nash。那 John Nash 有 部片就是拍他的電影啦。A
Beautiful Mind。那2001年的電影，那 呃，講
Nash 的一生。不過他那裡面並沒有對 Nash 一生講太多啦。你如果對他一生有興趣的話
可以看一下。有一種，它是一個蠻不，就 informal 的 introduction.
好，那這邊我也是很簡單的講，他的 Nash
平衡意思就是說如果在一個，在，一個 賽局裡面，如果當我，每，當我一個player如果我知道其他player的所有他們
呃，所要出的strategy ，所要，所要運行的。所以這我都知道的 在這種情況下，如果我不更，不會更改我的策略，
好，不會更改我的策略，就我認為我的策略對我來說是最好的。那這個情況，如果這同樣情況- apply
對每個 player 都 apply 也就每個 player 都知道其他所有 player 的策略而他不會更改他的策略。
就他一樣選擇這個策略對他最有利。那如果這件事對每一個player 都成立的話，那這，這個點我們稱為 Nash 的平衡點。
那，Nash 平衡有些是存在有些是不存在。那它也分成所謂pure equilibrium 還有 mixed equilibrium
那以 pure 來講的話就是你的 招數就只能出一種。那譬如我舉個例子像剪刀石頭布這樣的遊戲裡面。
剪刀的單純，就是純粹Nash平衡是不存在的嘛。對不對？比如說我就兩個人來好了。好，- 那你如果，如果我知道你會出剪刀的話我一定會出石頭。
反過來一樣，你如果對手知道我會出石頭的話那他就不會繼續 keep出剪刀。他會應該會改出布。所以你可以看出這裡面
呃，純粹，就pure的Nash平衡是不存在的。那你如果考慮 mixed strategy 的話，那
Nash 平衡存在。然後存在的地方就是出剪刀石頭布的機率都是三分之一。好。
那 Nash 平衡其實有解釋，又，很容易來解釋一個像囚犯兩難困境。
那，這是一個例子。就是你想像有兩個罪犯，就 A 跟B 那他們，呃，就是被，被詢，被警方尋問。
那他們可以考，考慮就是，就是承認犯罪。那，就是，等於，簡單說背叛啦。
等於說背叛對，對方把，呃，罪情招認。就是幫助警方 找這些罪證。那另外個可能就是他可以
keep silent 就是打死不招這個樣子。
那這邊是，這個 table 是他的，呃，utility 就是如果兩個人都不招，A B 兩個人都不招的情況下， 那，警方就拿不到夠多證據，那每個人都最多只能被關一年。
好那相對來說如果一個人打死不招。好，可一個人，B 背叛他，就甚麼都講清楚。那警方就，
都會拿到證據嘛。那A 就領很重的罪，被關五年。那同時 B 可能污點證人就，你就不用被關，你就直接free
那 Nash equilibrium 蠻能解釋囚犯困境這個問題哦。那囚犯困境這個問題是在描述
說有兩個罪犯。那他們，呃，基本上就警方在詢問他們。他們可以有兩個選擇，一個就是招供。
就是把他們的犯罪都招出來。一個就是他抵死不從，就是不跟警方合作。
那這邊這個 table 所列出來的是他們的 pay off.
就是或 utility,
那也就說如果兩個 罪犯他們都不和警方合作那結果就是， 警方沒辦法找到足夠的證據所以他們每個人都只能被關一年。
那另外一個可能是。就是，呃，一個罪犯都不 合作。那另外一個罪犯招了。就是等於說他背叛了
A， 這個 背叛 A 這個朋友。那結果就是罪證很明顯所以他們被關五年。那 B
因為可能是就 協助警方，當作污點證人他就直接釋放，都沒事。那另外有可能就是
兩個人都搶著認罪，那結果就是沒有人需要當污點證人因為警方不需要他們， 所以罪證簡單，明顯地，每個人都被
serve 三年。好，那如果我們用fair wear
的情況下來看。就是兩人合起來所要serve 的年數最少的話。似乎應該是在這個位置對不對？
加起來嘛，兩個就加起來。就兩年。一人一年，兩人加起來。可是實際上呢， 依照Nash
equilibrium來講的話，這件事會發生。這不是平衡點。會發生是在這個位置。
原因是因為這樣。你 A 會這樣想，A ok
想要在這邊。可是他會想說 如果我背叛他的話。我背叛 B 的話，我現在就馬上出獄。因為他只
care 他自己的。而且他會， 正常 rational 的想法他會覺得，ok B 應該也會這樣想，對不對？就是
B 應該也會想如果 這樣的話他就可以free所以他應該也會馬上背叛我。所以這樣的話還不如我也背叛他。
所以最後結果就是你會發現從這個 column 到這個 column 基本上有這樣的效果，就是，呃，這樣。
這裡到這裡，然後在這個點會移到這裡。在這個點會移到這邊。所以基本上這不是一個，這邊- 不是一個平衡點，而這邊是最後的一個平衡點。
就兩個人都被關三年。好，這是用 Nash equilibrium 來討論，解釋
囚犯兩難困境。所以最後得到平衡點在這邊。那如果在電腦賽局中有類似的情況下，有一些 uncertain
state那基本上馬上都跟賽局的研究有關。或是，呃，賽局，就是賽局裡面有超過兩個- 人以上。
比如說，三人以上。那基本上都跟賽局有關。因為你可能要在某一個時間點跟另外一個 player 合作來對抗第三個player.
那以上是我們這裡講的整體的內容。首先我們主要在探討怎麼。主要 focus在zero
sum player 的這些 term base, perfect information again.
那在這裡面，所謂的 optimal condition 基本上就是一個MiniMax 的manner
好，那我們當然有介紹各種，介紹各種不同 pruning 的技術。就包含alpha beta pruning.
那譬如說我們，這是一種非失真的，那我們也講mega scout.
Mega scout那基本上把alpha beta window縮到最小。那如果 search 的結果不行，
就是代表你可能有多坎。那，不安全的多坎，那我們可能就背叛這個 結果再
search 一次。那我們有介紹失真的方法，比如說你可以用beam search
你可以用probable count就機，用統計來算。你被砍的機率多少。那只要夠高你乾脆就直接把它砍掉。
那再大部分的電腦賽局裡面你都不太可能 search 到最下面。
因為 時間的關係，那所以我們會用，用 heuristic 來做。那如果是對stochastic game 的話，那再整個search
過程你必須要增加一個 就chance node 那chance node 增加蠻慘的就是你 alpha beta pruning 會不太有效率。
而且整個樹的 branch
factor會長得非常的龐大。那比較常用的方法我們是用蒙立卡羅的simulat- ion.
來就是在夠深的，你還是要search 到夠深的，呃，搜尋的結果才有品質的保證。
那可是我不能沒辦法整個這麼深的樹全部搜尋完。我們用蒙立卡羅就是， 在我時間可以容許的範圍random
地去挑我夠大的數量來做平均，來做統計。
那如果針對limited，呃，就是你observation 沒辦法 對整個遊戲有些地方你是看不到的。然後這些看不到的地方是
hold 在你的對手身上的 那這部分，呃，大部分研究都會跟 game theory 有關。那這部分相關的可能要看賽局的一些課程。
以上的是我們這一講的內容。
Explore nosso catálogo
Registre-se gratuitamente e obtenha recomendações, atualizações e ofertas personalizadas.
O Coursera proporciona acesso universal à melhor educação do mundo fazendo parcerias com as melhores universidades e organizações para oferecer cursos on-line.
© 2018 Coursera Inc. Todos os direitos reservados.
