August 2017
Intermediate to advanced
360 pages
8h 35m
Chinese
Content preview from 算法技术手册（原书第2 版）
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.
AI
寻路
｜
171
AI
寻路
7.3.4 算法分析
当每个棋局状态都有固定的
b
个走法（即便每层都能减少一个可行走法）时，追寻深度
d
的
Minimax
算法需要搜索的棋局状态的总数大约是
O
(
b
d
)
，很明显是指数级增长。如
果博弈树足够小而且能够在合理时间内完成搜索，那么可以不加上追寻深度的限制。
来看图
7-5
的结果，是否有办法消除对无用棋局状态的计算呢？由于假设玩家和对手都
不会犯错，因此一旦发现整棵子树都没有办法得到一个更好的结果，就可以放弃继续扩
展。
AlphaBeta
可以很容易地满足这个要求。不过在这里，接下来先看
NegMax
算法是
如何简化交替使用
MIN
和
MAX
层的。
7.4 NegMax
NegMax
算法不再使用
Minimax
的
MAX
和
MIN
来标识层级，而是每一层都同样对待。
这种思想也形成了另外一种算法，即
AlphaBeta
。
在
Minimax
中，
棋局状态是一直从玩家的视角来观察，然后选择走法（需要存储玩家的
信息以供评估函数使用）。所以博弈树每一层会交替包含子结点的最大值（为玩家着想）
或者最小值（为对手着想）。相反，
NegMax
对走法采取一致的评估策略，即从最坏的
角度来评估子结点。
NexMax 算法小结
最好情况、平均情况和最坏情况：
O
(
b
ply
)
bestmove (s, player, opponent)
[move, score] = negmax (s, ply, player, opponent)
return move
end
negmax (s, ply, player, opponent) ...
Become an O’Reilly member and get unlimited access to this title plus top books and audiobooks from O’Reilly and nearly 200 top publishers, thousands of courses curated by job role, 150+ live events each month,
and much more.
Read now
Unlock full access
More than 5,000 organizations count on O’Reilly
O’Reilly covers everything we've got, with content to help us build a world-class technology community, upgrade the capabilities and competencies of our teams, and improve overall team performance as well as their engagement.Julian F.
I wanted to learn C and C++, but it didn't click for me until I picked up an O'Reilly book. When I went on the O’Reilly platform, I was astonished to find all the books there, plus live events and sandboxes so you could play around with the technology.Addison B.
I’ve been on the O’Reilly platform for more than eight years. I use a couple of learning platforms, but I'm on O'Reilly more than anybody else. When you're there, you start learning. I'm never disappointed.Amir M.
I'm always learning. So when I got on to O'Reilly, I was like a kid in a candy store. There are playlists. There are answers. There's on-demand training. It's worth its weight in gold, in terms of what it allows me to do.