对抗搜索

最小最大定理？

如何对博弈树进行搜索

多玩家博弈？

效用函数？

Alpha-Beta剪枝？

启发式函数

随机博弈

蒙特卡洛方法

蒙特卡洛搜索树

人工智能中的博弈通常指完全信息、确定性的、轮流的两人零和博弈

博弈问题难以在有限时间内求解，因而博弈要求具备在有限时间内无法计算最优决策的情况下也能给出某种决策的能力。

剪枝允许我们在搜索树中忽略哪些不影响最后决定的部分，启发式的评估函数允许在不挖暖搜索的情况下估计某状态的真实效用值。

两人游戏的定义：

S_0 ：初始状态

PLAYER(s) ：定义此时该谁行动

ACTION(s) ：返回此状态下合法行动的集合

RESULT(s,a) ：转移模型，定义行动的结果

TERMINAL-TEST(s) ：终止测试，游戏结束返回真，否则返回假。游戏结束的状态称为终止状态

UTILITY(s,p) ：效用函数（也称为目标函数或收益函数），定义游戏者p在终止状态s下的数值

习题5.7：证明如下断言：对于每颗博弈树，MAX使用极小极大算法对抗次优策略的MIN得到的效用值不会低于对抗最优 策略的MIN得到的效用值。能否找到一颗博弈树使得MAX用次优策略对抗使用次优策略的MIN要好于使用最优策略？

对抗搜索

博弈

搜索与对抗搜索的对比

博弈要求在有限的时间内进行决策

博弈的特征：

两个或多个玩家（智能体）

轮流或同步行动

完全信息与不完全信息

确定性与随机性

合作与对抗

零和与非零和

例子：

例子：两玩家博弈

特点：确定性、完整信息、轮流、两玩家、零和

两玩家分别为MAX和MIN

问题形式化：

问题形式化定义为搜索问题：

S_0 ——Initial state, specifies how the game is set up at the start

PLAYER(s)——returns which player has the move in a state

ACTIONS(s)——returns the set of legal moves in a state

RESULT(s,a)——transition model, defines the result of a move

TERMINAL-TEST(s)——terminal test, true when the game is over and false otherwise

UTILITY(s,p)——utility function, defines the value in state s for a player p

博弈中的优化决策

α-β剪枝

不完美的实施决策

随机博弈

蒙特卡洛方法