Multi-Agent System
涉及到多人之间的博弈，但是数量不会特别多，否则应该使用经济学中的原理而非人工智能。同时多智能体系统要有明确的行动规则，比如说篮球比赛现在想要建模还比较困难，因为规则太复杂了。
A Special Case
现在只考虑只有两个智能体 开展零和博弈 的情形，两个玩家轮流行动 ，都默认采取最佳策略 。同时环境确定且可观测。(Two-Player Sequential Zero-Sum Complete-Information)
Tic-Tac-Toe
Solution Concept
我们在玩这个游戏的时候总是会想如何阻止对方连成一条线，这里可以显示出玩家总是会认为对方会做出最优的策略。
Game as Search Problem
对于一棵搜索树，一个状态后面会有许多后继状态，这和两个人的博弈是类似的。
定义：
S 0 S_0 S 0 Players(s)：在状态 s s s
Action(s)：一个合法的行动
Result(s,a)；状态 s s s a a a
Terminal-Tests(s)：表示游戏是否在状态 s s s
Utility(s,p)：表示某个终止状态状态 s s s p p p p ∈ { M A X , M I N } p \in \left\{ MAX, MIN \right\} p ∈ { M A X , M I N }
Game：在游戏数(搜索树)中搜索
因此我们需要找到一条路径，从初始状态到终止状态。并且对于 MAX 玩家而言，希望终止状态效用函数能最大化；对于 MIN 玩家而言，希望终止状态效用函数能最小化。而在玩家每一步的行动中，他们都会采取对自己最有利的策略。
Minimax Algorithm
Brute force
该算法是为了找出上面提到的路径。算法的执行顺序为：假如知道某个节点 s s s s s s
假如 Player(s)=MAX，那么节点 s s s
假如 Player(s)=MIN，那么节点 s s s
即：
M I N M A X ( s ) = { U T I L I T Y ( s ) if T E R M I N A L − T E S T ( s ) max a ∈ A c t i o n ( s ) M I N M A X ( R E S U L T ( s , a ) ) if P L A Y E R ( s ) = M A X min a ∈ A c t i o n ( s ) M I N M A X ( R E S U L T ( s , a ) ) if P L A Y E R ( s ) = M I N MINMAX(s)=
\begin{cases}
UTILITY(s) & \text{if } TERMINAL-TEST(s)\\
\max_{a\in Action(s)} MINMAX(RESULT(s,a))& \text{if } PLAYER(s)=MAX\\
\min_{a\in Action(s)} MINMAX(RESULT(s,a))& \text{if } PLAYER(s)=MIN\\
\end{cases}
M I NM A X ( s ) = ⎩ ⎨ ⎧ U T I L I T Y ( s ) max a ∈ A c t i o n ( s ) M I NM A X ( RES UL T ( s , a )) min a ∈ A c t i o n ( s ) M I NM A X ( RES UL T ( s , a )) if TERM I N A L − TEST ( s ) if P L A Y ER ( s ) = M A X if P L A Y ER ( s ) = M I N
因此这种算法相当于对整棵树进行搜索。
比如下面这颗搜索树，使用 minimax 算法的结果如下：
Properties of minimax algorithm
是完备的(只要搜索树是有限的)
是最优的(只要对手同样采取最优策略)
时间复杂度为 O ( b m ) O(b^{m}) O ( b m ) b b b m m m
空间复杂度为 O ( b m ) O(bm) O ( bm )
可以看出该算法对于一些比较大型的游戏而言是不可行的，比如下棋时 b ≈ 25 , m ≈ 100 b\thickapprox 25, m\thickapprox 100 b ≈ 25 , m ≈ 100
Minimax Algorithm
为了实现较快的计算，可以限制搜索树的深度，比如限制为 d d d e ( s ) e(s) e ( s )
对于一个评估函数
评估函数对于终止状态的排序应当和效用值对终止状态的排序应当是相同的。
因为评估函数需要多次计算，所以为了节约时间，应当便于计算
评估函数的值应当与获胜的概率密切相关
比如对于象棋而言，我们可以依据棋盘上棋子的数量和种类来定义一个评估函数。
Example
比如对于 Tic-Tac-Toe 游戏，我们定义 × 是 MAX 一方，而每种状态的评估函数定义为 e ( s ) = e(s)= e ( s ) =
假如考虑从头开始，第一步为 × 玩家先走，那么得到的限制深度 d = 2 d=2 d = 2
对各个叶节点使用评估函数估算，然后逐层推回根节点，就能知道 × 玩家应当先走哪一步。假如是从中间某一部开始，那么可以同理计算。
α − β \alpha-\beta α − β 之前的算法是限制搜索树的深度，于此同时我们还可以对搜索树进行剪枝，减小其复杂度。这就是 α − β \alpha-\beta α − β
Example
首先从一个例子入手
我们希望得到根节点的最优解，那么
首先看最左边的B节点，得到值为 3 3 3 3 3 3
然后再看C节点，C的第一个子节点为 2 2 2 2 2 2
所以C的其他子节点都直接不用考虑
α − β \alpha-\beta α − β
Why is it called α − β ? \alpha-\beta? α − β ?
α \alpha α v v v α \alpha α
β \beta β
pseudo code
function ALPHA-BETA-SEARCH ( s t a t e ) returns an action v ← MAX-VALUE ( s t a t e , − ∞ , + ∞ ) return the a c t i o n in ACTIONS ( s t a t e ) with value v \begin{aligned}
& \textbf{function ALPHA-BETA-SEARCH}(state)\text{returns an action}\\
& \quad v\leftarrow\text{MAX-VALUE}(state,-\infty,+\infty)\\
& \quad \textbf{return the }action\text{ in ACTIONS}(state)\text{ with value }v
\end{aligned}
function ALPHA-BETA-SEARCH ( s t a t e ) returns an action v ← MAX-VALUE ( s t a t e , − ∞ , + ∞ ) return the a c t i o n in ACTIONS ( s t a t e ) with value v
function MAX-VALUE ( s t a t e , α , β ) returns a utility value if TERMINAL-TEST ( s t a t e ) then return UTILITY ( s t a t e ) v ← − ∞ for each a in ACTIONS(state) do v ← MAX ( v , MIN-VALUE ( RESULT ( s , a ) , α , β ) ) if v ≥ β then return v α ← M A X ( α , v ) return v \begin{aligned}
& \textbf{function MAX-VALUE}(state,\alpha,\beta)\textbf{ returns }a\textit{ utility value} \\
& \quad\textbf{if TERMINAL-TEST}(state)\textbf{ then return UTILITY}(state) \\
& \quad v\leftarrow-\infty \\
& \quad \text{for each a in ACTIONS(state) do} \\
& \quad \quad v\leftarrow\operatorname{MAX}(v,\operatorname{MIN-VALUE}(\operatorname{RESULT}(s,a),\alpha,\beta)) \\
& \quad \quad \textbf{if }v\geq\beta\textbf{ then return }v \\
& \quad \quad \alpha\leftarrow\mathrm{MAX}(\alpha,v) \\
& \quad \text{return } v
\end{aligned}
function MAX-VALUE ( s t a t e , α , β ) returns a utility value if TERMINAL-TEST ( s t a t e ) then return UTILITY ( s t a t e ) v ← − ∞ for each a in ACTIONS(state) do v ← MAX ( v , MIN-VALUE ( RESULT ( s , a ) , α , β )) if v ≥ β then return v α ← MAX ( α , v ) return v
function MIN-VALUE ( s t a t e , α , β ) returns a utility value if TERMINAL-TEST ( s t a t e ) then return UTILITY ( s t a t e ) v ← + ∞ for each a in ACTIONS(state) do v ← M I N ( v , M A X − V A L U E ( R E S U L T ( s , a ) , α , β ) ) if v ≤ α then return v β ← MIN ( β , v ) return v \begin{aligned}
&\textbf{function MIN-VALUE}(state,\alpha,\beta)\textbf{ returns }a\textit{ utility value} \\
&\quad \textbf{if TERMINAL-TEST}(state)\textbf{ then return UTILITY}(state) \\
&\quad v\leftarrow+\infty \\
&\quad\text{for each a in ACTIONS(state) do} \\
&\quad \quad v\leftarrow\mathrm{MIN}(v,\mathrm{MAX-VALUE}(\mathrm{RESULT}(s,a),\alpha,\beta)) \\
&\quad \quad\textbf{if }v\leq\alpha\textbf{ then return }v \\
&\quad \quad \beta\leftarrow\operatorname{MIN}(\beta,v) \\
&\quad \text{return } v
\end{aligned}
function MIN-VALUE ( s t a t e , α , β ) returns a utility value if TERMINAL-TEST ( s t a t e ) then return UTILITY ( s t a t e ) v ← + ∞ for each a in ACTIONS(state) do v ← MIN ( v , MAX − VALUE ( RESULT ( s , a ) , α , β )) if v ≤ α then return v β ← MIN ( β , v ) return v
在上述伪代码中，if v ≥ β then return v \textbf{if }v\geq\beta\textbf{ then return }v if v ≥ β then return v
conclusion
MAX玩家更新 α \alpha α β \beta β
节点 α , β \alpha, \beta α , β
节点的效用值 v v v
α − β \alpha-\beta α − β 后继节点出现的顺序会很大的影响算法的效率，在最好的情况下，时间复杂度为 O ( b m / 2 ) O(b^{m / 2}) O ( b m /2 ) b b b m m m O ( b m ) O(b^{m}) O ( b m )
Iterative Deepening Search
α − β \alpha-\beta α − β
