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
寻路
｜
165
AI
寻路
• +
∞
如果玩家
p
能够在当前棋局
gs
已经赢得游戏。
• -
∞
如果玩家在当前棋局
gs
下已经输掉游戏。
•
nc
(
gs
，
player
) -
nc
(
gs
，
opponent
)
，如果在当前棋局
gs
下仍然胜负未分。
一个好的评估函数不应当只局限于当前棋局状态，它还应当能够自动评估未来几步之后
的可能情况，从而找到最终能够获胜的走法。但是现实生活中这种评估函数并不多见，
原因有两个：做这些评估需要性能费用；搜索函数和评估函数可能需要共享代码，这么
做不方便进行代码维护。
7.2 寻路算法的概念
本节介绍的概念既适用于博弈树，也适用于搜索树。
7.2.1 状态表示
博弈树或者搜索树的每个结点都包含了当前棋局下的所有状态信息，例如在国际象棋中，
王和车易位的条件是：①两个棋子都没有移动过；②所经过的格子必须为空，而且不可
能被任何一枚敌方棋子攻击；③现在没有被将军。注意，条件②和③都可以通过对棋局
的观察得到，并不需要额外的计算，但是必须分开存储王和车是否被移动过。
如果树的规模呈指数级增长，那么必须非常紧凑地存储状态。如果状态有可能存在对称，
例如四子棋、黑白棋或者
15
数码游戏中，可以通过消除那些需要旋转或者左右互换的
状态来大幅减小树的规模。另外，还有更为复杂的数据结构
bitboards
可以专门应付这类
游戏，它能够很高效地管理大量的状态（
Pepicelli, 2005
）。
7.2.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,
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.