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.
166
｜
第
7
章
7.2.3 最大扩展深度
在内存受限的情况下，一些搜索算法会限制搜索的深度和广度。这种策略也有它的缺点，
尤其是在那些需要考虑一系列走法的游戏中。例如在国际象棋中，我们经常会牺牲掉一
些棋子以换取将来的优势，如果这些棋刚刚处于最大的搜索深度处，那么就永远没有办
法发现这一步妙棋。一个固定的扩展深度可以扩展搜索本看不到的视野，但是却有可能
损害最终的搜索结果。例如在单人游戏中，固定搜索深度很可能让算法无法找到恰好在
深度外的全局最优解。
7.3 Minimax
任意给定开始位置，玩家都肯定希望搜索程序能够帮助最大化获得胜利的概率（或者至
少要保平）。程序不能仅考虑当时的棋局状态以及可行走法，还需要考虑对手会采取的
任何对策，并且假设对手会采取最完美的走法，并且不会犯错。它假设存在一个评估函
数
score(state
，
player)
，返
回一个整数，表示棋局状态的得分，分数越小（可以为负）
表示这个位置对玩家越不利。
扩展博弈树时也需要考虑
n
步之后的棋局状态。树的每一级轮流标注为
MAX
层级（目
标是最大化这一级棋局状态的得分，使得对玩家有利）和
MIN
层级（目标是最小化这一
级棋局状态的得分，使得对对手有利）。在每一级中，如果是玩家走，那么程序选择最
大化
score(state,initial)
的
走法；如果是对手走，那么程序将会假设对手足够聪明，
所以选择最小化
score(state,initial)
的走法。
当然，考虑到博弈树可能是无穷大，搜索程序也只会往前多看固定的步数。我们把这个
步数叫作
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.