文档介绍：第六章对抗披索
-6剪枚技术
信息学院
0871501301
思年10月12日早期
博弈
博弈:如下棋、打牌、战争警一类智能活动。
·双人
人一步
双方信息完备:对垒双方任何一方都了解当前的格局及过
去的历史。
·零和:A胜B败,B胜A败,平局
非偶然:任何一方在采取行动前都要根据当前实际情况,
进行得失分析,选取对自己最为有利而对方最为不利的对
策,不存在“碰运气”的偶然因素。
信息学院
0871501301
思年10月12日早期
博弈树
初始状态:初始格局(是初始节点)
后续函数:(出招状态)
终止测试:判断游戏是否结束
目标函数(效用函数):对终止状态给出一个数值
信息学院
0871501301
思年10月12日早期
X口
MAX(X
xox区o
oxXO
TERMINAL□ OX OOX□
x xoo
Ulility
0
分钱币问题
(7)
61)
(52)(43)
5,1,1)(4,21)(3,22)(313)
(4111)(32,11)(2221)
(31111)
(22111)
(211111)
对方先走,我方必胜
信息学院
0871501301
思年10月12日早期
中国象棋
一盘棋平均走50步,总状态数约为10160
假设每秒搜索10个节点,约需10145年
结论:不能搜索整个状态空间
信息学院
0871501301
思年10月12日早期
最优策略一极小极大值过程
0
16
c093039-3-39-2919360
05-33333022-30-23541330689-3
信息学院
0871501301
思年10月12日早期
自己一方扩展的节点是或的关系。对方扩展的节点是与的关
系
在树中“或”节点和“与”节点交替逐层出现
所有能使自己获胜的终局都是本原问题,相应的节点是可解
节点;所有使对方获胜的终局都是不可解节点。
信息学院
0871501301
思年10月12日早期
最优策略一极小极大值分析法
对各种可能的后果进行比较,考虑实施后对方可能的所有
行动。并计算得分。
为计算得分,要定义一个估价函数,用来估算当前博弈树
端节点的得分。(静态估值)
当端节点的估算值出来后,再推算父节点的得分。
对或节点选其子节点中一个最大的得分作为父节点得
分,这是为使自己在可供选择的方案中选一个对自己最有利的
方案。
对与节点选其子节点中一个最小的得分作为父节点得
分,这是为使自己在可供选择的方案中选一个对自己最不利的
情况
信息学院
0871501301
思年10月12日早期
极小极大值算法
function MINIMAX-DECISION(state) returns an action
return the action in SuccESSORS(state) with value v
function MAX-VALUE(state)returns a talty value
if TERMINAL- TESr(state)then return UTiLIty( state)
fo
t∈MAx( MIN- VALUE(s)
turn u
function MIN-VALUE(state] returns a utility value
if TERMINAL- TESr(state)then return UTiLITY( state)
for a, s in SuccESSORs(state)do
t←MIN(, MAX- VALUE(s)
eturn U
信息学院
0871501301
思年10月12日早期