Skip to Main Content
算法技术手册(原书第2 版)
book

算法技术手册(原书第2 版)

by George T.Heineman, Gary Pollice, Stanley Selkow
August 2017
Intermediate to advanced content levelIntermediate to advanced
360 pages
8h 35m
Chinese
China Machine Press
Content preview from 算法技术手册(原书第2 版)
161
7
AI 寻路
如果一个问题没有明确的解决方案,那么我们就可以考虑使用寻路算法。本章介绍两种
寻路算法一种叫作
博弈树
,适用于两玩家之间的情况另一种叫作
搜索树
,适用于
单一玩家的情形。这两种方法本质上都是基于一种叫作“状态树”的通用结构。状态树
的根结点表示初始状态,边表示两个状态之间可以转换。这些搜索算法非常有挑战性,
因为状态数呈爆发性增长,从而导致无法完整地计算出底层结构例如,跳棋游戏中有
大约
5
×
10
20
个不同的棋局状态(
Schaeffer
2007
)。因此我们需要在搜索时按需逐
步构造树。上述两种寻路算法的特点如下
博弈树
两位玩家轮流交替动作,使游戏的状态从初始状态开始改变。每位玩家都有可能赢
得游戏但也有可能结果是“平局”,即没有人能够赢得游戏。优秀的寻路算法能
够帮助玩家最大化赢得比赛的机会,或者在不利的情况下帮助玩家保住平局。
搜索树
玩家从一个初始状态开始,不断进行有效的移动直至到所期望的目标状态。使
寻路算法能够得到从初始状态到目标状态所需的每一步策略。
7.1 博弈树
有一款叫作“字棋”的游戏,它需要一个
3
×
3
格的棋局,玩家在棋局上轮流画
X
或者
O
第一个将三个标记画在同一行的玩家将会赢得这次游戏,如果没有足够的空间画标记,
那么这场游戏就是平局。在井字棋游戏中,仅有
765
棋局状态(忽略掉那些对称的棋局
以及
26 830
不同的赛况(
Schaeffer
2002
)。为了重现一部分赛况,我们需要构建一
博弈树
(图
7-1
所示的是树的一部分),然后从玩家
O
的当前棋局 ...
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.
Start your free trial

You might also like

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

机器学习实战:基于Scikit-Learn、Keras 和TensorFlow (原书第2 版)

Aurélien Géron
Go语言编程

Go语言编程

威廉·肯尼迪
C++语言导学(原书第2版)

C++语言导学(原书第2版)

本贾尼 斯特劳斯特鲁普

Publisher Resources

ISBN: 9787111562221