本課程分為人工智慧（上）、人工智慧（下）兩部份，第一部分除了人工智慧概論外，著重在目標搜尋、meta heuristic、電腦對弈、演繹學習（包含證言邏輯、一階邏輯及 planning ）等技術。這些技術主要發展時機為人工智慧的第一波及第二波熱潮，也就是 1950 年代至 1990 年代附近的主流發展，即使到現在也在各個領域廣為應用。 課程教學目標： 使同學對人工智慧有基礎概念 同學能夠理解如何運用目標搜尋技術及演繹學習方式達成人工智慧 同學能將相關技術應用到自己的問題上
5-1 Type of Games - Symbols, Game Tree
Loading...
From the course by National Taiwan University
人工智慧：搜尋方法與邏輯推論 (Artificial Intelligence - Search & Logic)
145 ratings
From the lesson
Adversarial search
Meet the Instructors
于天立副教授（Associate Professor）
電機工程學系(Electrical Engineering)
好大家好，今天我們要講的是adversarial search，
那這個search搜尋技巧是我們大概是搜尋整個部分的最後一個單元。那這部分 之所以成為adversarial
search這是一個特殊的搜尋技巧，它主要是針對一個 multi agent的環境，那在這multi
agent的環境下，這我們是假設這些agent是出於一種相互競爭的 情況，那這樣的搜尋技巧當然大部分
被利用在電腦賽局中，也就是說computer game
playing的部分。那我們這一講的 內容主要對應是AIMA課本的第五單元，那其中我們
在這講中第5.6這部分是Partial Observable， 那我們只是會概略性的講，
不會講的非常的細。那有興趣的同學可以再看一下課本。那5.7是State-of-the-Art，
電腦賽局最近的一些競爭，那我們大家在Introduction的時候已經提過部分， 那我們在這一部，這一講，就跳，暫時跳過。
好那接下來這是我們今天要講的內容，那首先我們會對針對不同的game
來做各種探討。那game有很多類型我們等下會稍微講下，也會講它的， 我們在formulate一個game的時候，
我們需要哪些要素。其中我們針對的一種game是所謂的我們稱為 perfect information的game。
就是完美資訊，那在這一類的game裡面就是對手下的每一個動作每一步，你其實，這個資訊你- 都全部都有，如果是multi agent的話，
可能就包含若干個不同的對手，他們每一個人做的動作你都知道。 好那這一類的game其實還蠻多的，包括大部分的像
西洋棋，象棋，圍棋這一類都是屬於Perfect-Information的 Games。
好那在這裡面我們怎麼做search呢？我們會先從傳統的 Minimax search開始介紹。
那它其中有一種實作的方法我們稱為Negamax。那就是利用你如果只是
兩個對手，然後零和的情況下，也就是說，那零和的意思就是我贏就是你輸了，那我輸就是
你贏。這種情況下那我們可以把整個程式碼大大的簡化，簡化成一半，
那這種implementation我們稱之為Negamax。那接下來 在整個game
tree的search的過程中其實你不見得 每一個節點都需要去探索。那這一類的pruning的技巧我們稱為α—βpruning-
，那α—βpruning 可以在不失真的情況下，就是它的結果其實和Minimax的search結果是一模一樣的
情況下能夠大幅縮減所要探索的節點的數量。好那，我們接下來
還會再提這部分課本就沒有提到太多，就是如果你還要再加速你的搜尋的速度的話，我們還- 可以試著
再pruning更多的節點。好那就部分技巧也會談到，那這裡面我們分為，
有一些pruning的技巧會造成失真的結果，那有一些並不會。那我們會多探討一下- 。好那，
在大部分的game裡面，一個search tree其實原則上你要搜尋到這個game
終局，就是結束能定輸贏的時候，這樣的結， 這樣的decision我們稱為perfect
decision。那如果你不能做這樣的decision，因為大部分的game其實它深度，它的寬度其實都蠻
大的，因為記憶體它們時間的限制你可能沒辦法搜尋到底的情況下，那在我們就必須做 imperfect
decision，那不完美的決定這時我們需要一個heuristic來幫助我們做這件事情。
好那最後我們會介紹一個implementation的方式 叫做Zobrist hashing。 那Zobrist hashing這個技巧
是蠻好用的，那我在這邊特別介紹，主因也是反映到我們之前，前期講有講到 tree
search 和 graph search它們之間的差異是，graph search 是可以比較不同state它們之間的有沒有，
有沒有相，就是有沒有，我在搜尋過程中有沒有遇到重復的state。那tree search它就完全不做這件事那我們當然很清楚知道
graph search的效率上應該是比較好的，但是你一般面臨的問題 是你記憶體可能沒辦法沒有那麼大，沒辦法把所有的重復的
state全部都記錄下來。那Zobrist hashing可以達到在就是利用 hash table的技巧，在只要在近期內搜尋過的
state，它有蠻高的幾率可以抓到說它們其實是重復的，那它不保證， 因為你的記憶體限制的關係。
那這個技巧是蠻實用的，我們會介紹一下。那接下來一個單元我們會講Stochastic Games。 這也蠻常見的尤其是像，
就很多遊戲裡面其實有包含的幾率的因素在，比如說像撲克牌類的，一般來說你一髮牌，
每個人會拿到什麼牌其實你都不知道。那在Stochastic Games裡面， 你要做search的時候基本上我們第一步先從Minimax
做一個進化，就是我們在做Minimax的是它的期望值， 我們稱為EXPECTIMiniMax。
那在這，在Stochastic Games裡面其實最常用的技巧是蒙地卡羅 模擬法，
MonteCarlo-simulation那方法就是， 你遇到機率的地方你就真的丟個骰子，真的去
丟，然後利用幾率的方法來決定我接下來要搜尋哪一步， 那只要你在有限的時間內你盡量去多做這樣的模擬，
然後把它的結果平均起來，來當做它的期望值，那就種方法我們稱為蒙地卡羅。
那最後我們就是針對Partially Observable game我們會簡單的介紹一下。 那這部分其實跟
賽局理論有很大的關係，那我們這邊只做很簡單的簡介， 那我們也會提到一下何為，在賽局裡面，
在賽局理論中何為納什均衡。好那這是我們今天的內容。
好首先對於不同的，有很多很多game，那其實有些遊戲裡面其實它包含的要素
一方，有一種類型是競爭，有一種類型是合作，那當然有一些 遊戲是同時包含地遊戲和競爭裡面，那如果你有
合作和競爭都有關的話這一類的遊戲多半會牽涉到 Game theory的部分。 那可能就是我們這一講的最後我們會做很簡單的介紹，
那 Adversarial search如果照字面上來講主要就是只考慮競爭這一塊，
然後就是所有的agent，在一個multi agent的環境中 說我agent是彼此是互相競爭的。
那 在眾多的遊戲裡面最常見的就是我們這邊列的有包含，就是deterministic 然後turn-taking，
two-player，zero-Sum with perfect information，我這邊綠字還蠻多的，但是它每一個都很強烈的意義。
那deterministic的相對就是 Stochastic。那就我們剛剛講的就是如果你像撲克牌類的都是，
像橋牌啊，撲克啊，然後是這邊列的像大富翁這種遊戲， 你要擲骰子，好，那這樣都是Stochastic，那我們相對應就是deterministic
，像是 西洋棋啊，圍棋呀，黑白棋等等，那bingo其實也是，就是大家念數，
因為你一旦把12345678就是1到25數字寫下來以後它就固定的，那接下來只是看那個數字，
你決定畫哪一個。好那這是deterministic的game。你所謂turn-ta- king 應該也瞭解，就是有一種game是大家同時
可以進行動作，但turn-taking不是這樣，turn-taking就是 大家輪流下，其實這也是最常見的一種game，
就是我動作完換你動作，那相對應的，像現在大部分如果你說是實際上電腦的線上遊戲， 通常比較real time的
就是不屬於turn-taking，就是大家在同一個時間內大部分的每一個 agent都可以做它自己想要做的action。
好那另外一個就是two-player。那就是兩，就是字面上的意思就是兩人在玩。 那zero-sum是一個很重要，就是所謂的零和遊戲。
那零和遊戲就是我們剛剛講就是， 你如果把零當做當做正一，輸當做負一，然後平手你就當做
零的話，那這樣兩個人在玩這個遊戲的時候，
兩個人的這個數值相加一定是零。就是我贏的話我就正一，那代表你輸就是負一。
那合計兩個人都是零相加還是零，那這樣的遊戲我們稱為零和遊戲。
那perfect information我們就這樣講， 就是所有對手，所做的動作你全部都知道，這種情況下-
，我們稱為perfect information。
好那可以講一下像這邊有這邊列有一個例子像bingo
或是battleship，battleship我們大家可能各位有沒有玩過，是一個
一個格點上你可以把自己的，你可以決定自己的船艦要怎麼擺，
然後你可以決定打人家的哪個船，就大家都擺好，那個船艦就不能， 坐標就不能動了，然後你就，
說你要打對方的炮，打對方的哪裡，然後你battle如果達到一個程度 這一個船當然就會沈，那你的目的當然就是
最快把對方的船打掉。好那這樣這一類bingo和battleship裡面 它其實是deterministic，
因為你一旦船艦擺好，你就不能動了，它沒有什麼隨機的狀況在裡面， 但它不是一個perfect information。
因為你不知道對方的bingo卡的上面他是怎麼寫的，如果你要知道人家怎麼寫的，就很簡單，
偷看一下就知道，那我一定要不要喊什麼數字。那battleship也是一樣 你不知道對方的船的坐標在哪裡。
好那這是不同的類型的game。好接下來我們介紹一下把這整個game formulate的方式。
那我們介紹一些symbol。首先一樣我們還是用state來描述這個game。 那S0就是我們的initial
state。那我們用一個針對每一個state裡面我們會 用一個function，player（s），意思就是你把這個state傳進去，
這個player(s)就會跟你講現在是換誰來走，就是有不同的，因為turn-taking， 所以 有不同的player，這時候可以下。
那接下來就是action(s)跟之前一樣就是你給我這個state，我action就是把 所有合理
的move，legal move。我這，我們常用， 如果在電腦賽局我們常用的方法就叫legal move。
好也就是說合法的move全部抓出來，那如果是像象棋，中國象棋這種，
就針對不同的盤面，有可能有一些不同的move，比如說你的馬的跳法就如果前面有子的話
擋住，你就不能往另外一邊跳，那一樣象也被擋住，你就象就不可以走到一些地方。
那這是transition model跟這之前的一樣，就是你給我從一個state， 我take一個action-
(a)， 那接下來傳回一個state，我就resulting state，好這是這是一樣的東西。好那，
在game裡面我們會多一些就是包含了terminal test， 那之前我們是叫goal test，那現在 我們通常不叫它goal
test的原因是因為有不同的player有不同的目標，就兩個人下的話，我的目標是我贏， 那你的目標是你贏，所以這兩個人goal都不一樣，但是我們還是有稱為一個terminal
state呃test，terminal test就是這個遊戲 終止，那只要是false時候，就遊戲就繼續進行，然後true的時候就終止。
那終止的時候終止的情況下，我們會有一個 叫做utility
function。好那這utility function大家要記得只有在 終止，遊戲終止就是這個可以apply，這個function可以作用的情況只有在，
terminal test（s）是True的情況下，就是這個情況下， 你才可以apply utility，也就你不能遊戲進行到一半的時候你說，呃我現在
怎麼樣，這都還說不定。好那utility function有很多別名， 如果是在最佳化的領域我們通常稱它為目標函式，
就objective function，那如果是在經濟學的部分我們可能稱為 payoff。
在賽局里我們也稱為payoff這樣的metrics。好那這邊我們定義基本上通常是因為
你這個turn可能不一定是某player下的，而且這個utility針對不同的player， 就算同一個狀態，
不同的player可能拿到的分數是不同的，所以我們基本上是針對一個state， 這個state當然就是我們剛剛講的這個要為true的state。
然後你針對不同的player，不同的玩家，然後有不同的utility。那如果是針對- 我們剛剛講的就是我們forcus的是 two-player
零和的遊戲上，我們不需要這麼複雜的symbol，因為如果是two-player零和的情況下，
因為我們知道，我們只有兩個 player，P1和P2，那我的分數就是你的負分嘛，就是如果我是正三分，
就代表你是負三分，因為這要求就是零和兩個相加必須是零，所以我們習慣上，我們會
utility會寫成就把P直接拿掉，把P拿掉，那這個你要當然要講清楚就是iii對誰，
就是如果說是三的意思可能是說P1拿到三分，那你當然就很容易知道P2拿到的是負三分。
好那這所以我們會把symbol簡單化一點。
好那這個部分是一個井字棋的partial gampe search tree.
那井字棋大家應該都會下，就是一個圈圈一個叉叉，那誰先連成直橫斜
任意一個三個你就贏，那這是一個展開的部分，那大家可以看到就像
iii，原來是9個，9個你都可以下，那接下來是八個可以下，接下來是七個等等等等等。
這整個search space大概是就是九階，大致上九階，那我講大致上的原因是因為 有一些情況你還沒
把棋盤全部填滿就已經終局了，你的terminal test就已經是True了。
那如果你真的是terminal的情況下，你就可以對它做計分，你比如說像這個排名上- 的狀況，
叉叉已經連成一條直線了，所以我們就知道它是utility是正1，如果我們utility定義在
叉叉這個player，那同樣如果那我們當然知道叉叉是正1的意思，就圈圈是負1，
這是一樣的意思。好那就在最後在在terminal的情況下，
那我們可以對它applyutility。那在我們在目前的情況是叉叉贏就是正1，
然後和棋的話就是零分，然後叉叉輸的話就是負1，那我們就不再定義圈圈的分數。
Explore our Catalog
Join for free and get personalized recommendations, updates and offers.
Coursera provides universal access to the world’s best education,
partnering with top universities and organizations to offer courses online.
© 2018 Coursera Inc. All rights reserved.
