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.
174
｜
第
7
章
图 7-7：NegMax 示例探测
7.5 AlphaBeta
在考虑到对手的可能走法之后，
Minimax
算法能够较为恰当地找出玩家的最优走法。但
是，我们却不会使用这个信息来生成博弈树！我们看看早先介绍的
BoardEvaluation
评
分函数，并且回忆一下图
7-5
——这是从初始状态开始，玩家
X
走了两步，玩家
O
走了
一步之后，生成的博弈树的一部分。
可以注意到，即使接下来每一次搜索得到的结果都是要输掉，
Minimax
仍然孜孜不倦地
将每次搜索进行到底，这样总共有
36
个结点需要评估。
Minimax
并不会利用玩家
O
第
一步走在左上角避免被秒杀这个事实。而
AlphaBeta
算法却会使用固定的策略来从搜索
树中“剪除无效”的搜索。
当需要评估图
7-8
中以
❶
为根的子树时，
AlphaBeta
算法可以在知道对手最好情况下得
到
3
分，即不可能在比
-3
更坏的位置。当
AlphaBeta
到
❷
时，第一个子结点
❸
的得分是
2
。
也就是说，如果选择走步
❷
，那么对手不可能让玩家进入一个比
❸
还要好的选择中，所
以无须考虑
❹
。
若使用
AlphaBeta
，则其博弈树的等效扩展如图
7-9
所示。
AlphaBeta
算法也会为玩家寻找最好的走法，它能够记住如果玩家
O
走在左上角，那么
玩家
X
的得分不会超过
2
这样的信息。对于玩家
O
的后续每一步，
AlphaBeta
会决定是
否玩家
X
有至少有一步能够比玩家
O
第一步要好（即玩家
X
能赢的每一种走法）。因此，
AI
寻路
｜
175
AI
寻路
博弈树只扩展了
16
个结点，相比
Minimax
节省了
50%
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.