人工智能原理复习5

Adversarial Search 对抗搜索

https://zhuanlan.zhihu.com/p/667251930

http://t.csdnimg.cn/fXNHW

游戏类型： 零和博弈 、一般游戏

零和博弈：人工智能领域中最常研究的博弈（例如国际象棋和围棋）是博弈论学者所称的确定性、双人、轮流、完美信息（perfect information）的零和博弈。“完美信息”是“完全可观测”的同义词，“零和”意味着对一方有利的东西将对另一方同等程度有害：不存在“双赢”结果。在博弈论中，我们通常用移动（move）作为“动 作”（action）的同义词，用局面（position）作为“状态”（state）的同义词。

【常见案例】：国际象棋、围棋

博弈

人工智能中“博弈”通常专指博弈论专家们称为有完整信息的、确定性的、轮流行动的、两个游戏者的零和游戏。

术语中，这是指在确定的、完全可观察的环境中两个Agent必须轮流行动，在游戏结束时效用值总是相等并且符号相反。正是Agent之间效用函数的对立导致了环境是对抗的。

在零和游戏中，代理具有相反的效用，他们必需争夺一个或者一组可用的资源。

对抗性搜索

o 状态：S（从 s 开始）
o 玩家：P={1...N}（通常轮流）
o 操作：A（可能取决于玩家/状态）
o 转换函数：SxA -> S
o 终端测试：S -> {t，f}
o 终端实用程序：SxP -> R

Solution for a player is a policy: S -> A

效用函数（utilities）

博弈中的优化决策

MAX想要找到通往胜利的动作序列，但MIN不希望MAX获胜。这意味着MAX的策略必须是一个条件规划——一个随机应变策略，指定对MIN的每个可能移动的响应。对于具有多个结果分数的博弈,即极小化极大搜索。

minimax

极小化极大值 （minimax value）

某一状态的极小化极大值是指，假设从该状态到博弈结束两个参与者都以最优策略行动，到达的终止状态对于MAX的效用值。

Alpha-Beta Pruning

Good child ordering improves effectiveness of pruning

With “perfect ordering”:
Time complexity drops to O(b^(m/2))
Doubles solvable depth!
Full search of, e.g. chess, is still hopeless…

Resource Limits

Expectimax Search

compute the average score under optimal play

Max nodes as in minimax search

Chance nodes are like min nodes but the outcome is uncertain

Calculate their expected utilities

I.e. take weighted average (expectation) of children