人工智能原理复习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