AI 筆記14 - Adversarial Search

Adversarial Search又稱為Game

這是hard problem! 所以每次有突破都是令人興奮的新聞！

困難度在於除了有對手之外，通常search branching factor都相當高，例如西洋棋可能高達35，這讓完整的search是不可能的達成之事。所以我們需要發展approximation方法。

圍棋的話branching factor > 300。


Game的種類
包括以下：

我們（初學者）主要關注的是左上角較為簡單這塊。

零和遊戲

如果以打敗對方為目的的話，就是一個零和遊戲。每個game有不同outcomes，我方贏是一個outcome value，對方贏是一個outcome value，通常雙方會要最佳化自己的outcome value，最差化對方的outcome value。

所以可以看成一個objective function for each game: 一方要maximize，而一方要minimize。

Problem Formalization

• initial state
• 在每個state，players動作順序（通常是輪流）
• 合法的actions
• transition function: 每個state -> action -> new state的定義
• terminal test: 終局了沒？
• utility function(s,p): 對某個player p來說，他處於的state s的score，這也是就是每個player要最佳化的objective function。

舉tictactoe來說，如果只有一個player的時候（不考慮對手），就是一個單純的search problem，branching factor = 9:

找到utility = +1的state，基本上就是一個terminal state。

2-Players: Minimax Search

如果有兩個players，這時候雙方分別要達成想的utility function score，假設可能的outcome分別為：

max贏：+1
平手: 0
min贏: -1

所以可以看出, max就是要maximize score (所以稱它為max)，而min要minimize score。

當然不一定要這樣設定，不過如果是數值，當然還是會有大小之分，所以會有maxmize/minimize的對立。

這邊有一個假設：對手會採取optimal decision。


一個max先下手的可能search tree如下：

Minimax演算法概說

採用DFS，並且目的是讓max贏。演算法是recursive:

第一行是test s 是否為terminal state，如果是的話就回傳這個state的utility score。

第二行是如果目前是max ply，則search所有的actions產生的children states，回傳任何children能達到的最大utility score。

第三行跟第二行邏輯一樣，只是目前是min ply。