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
寻路
｜
179
AI
寻路
return best;
}
}
虽然得到的结果和
Minimax
相同，但是由于从博弈树中剪掉了大量的状态，
AlphaBeta
的执行时间显著减少。
7.5.2 算法分析
可以从生成的博弈树的规模来观察
AlphaBeta
相对于
NegMax
的优点。但是这个任务非
常复杂，因为这和可行走法的评估顺序息息相关，如果对手的最优走法首先被评估，那
么
AlphaBeta
就能够节省大量的时间。当每个棋局状态有
b
个可行走法时，分支数深度
为
d
的
AlphaBeta
算法可能搜索的状态数大约为
b
d
。如果走法是按照某种顺序降序排列
（例如最优走法优先），那么仍然需要评估所有的
b
个子结点（因为要选择最优的走法）。
但是，最好的情况下我们只需要评估对手的第一种走法。在图
7-9
中，由于走法有序，
在评估了一些走法之后才能够进行剪枝，所以在这棵博弈树下，走法排序并不适用。
最好情况下，
AlphaBeta
会为每一级为玩家评估
b
个棋局状态，而只为对手评估一个棋
局状态。因此，在博弈树的第
d
级，
AlphaBeta
只需要评估
b*
1
*b*
…
*
b*
1
个
棋局状态（一
共
d
次乘法），而不是扩展出
b*b*b*
…
*b*b
个棋局状态（一共
d
次乘法）。所以棋局
状态的总数是
b
d/2
，节省了巨大的费用。
AlphaBeta
并不会试图简单地最小化状态的数目，它也可以扩展和
Minimax
一样多的状
态，但是这种情况下，
AlphaBeta
扩展的深度会变为
Minimax
的两倍。
为了从实践中比较
Minimax
和
AlphaBeta
，我们构建了一个 ...
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.