人工智能基础实践教程 习题及答案 第4章 习题

第4章习题

4.1双方、动态、完美信息、确定性、零和的博弈问题具体是指什么？

答:双方是指博弈由两方参与;动态是指在博弈中，参与者所采取策略是有先后顺序的，

且参与者能够知道先采取策略者所选择的策略；完美信息博弈的每个参与者在做决策时都完

全了解曾经和正在发生的对弈过程的所有信息；确定性是指在博弈过程中，参与双方在采取

某种策略时，无其他非确定性因素的考虑；零和是指博弈双方收益之和为零。

4.2棋局的评估函数f(P)的设计原则是什么？

答：静态评估函数设计的基本原则是：当尸对MAX有利时，/'(P)取正值，并且值越

大表示对MAX越有利，当/(P)为+8时，表示MAX必胜；当P对MAX不利时，/(P)

取负值，并且绝对值越大表示对MAX越不利，当/(P)为—8时，表示MIN必胜；当双方

势均力敌时，/(P)取为零。

4.3请尝试说明为五子棋游戏设置静态评估函数的思路。

答：第一步，建立评分体系，将棋盘上的棋子分布化为具体的数值。评分依据两个核心

维度，即连子数和两端空位数。针对不同的连子数和两端空位数设计权重。具体示例如下：

(5,2)-连五：100,000分。游戏胜利，给予绝对高分。

(4,2)-活四：10,000分。两头皆空，下一步必成连五，等同于必胜。

(4,1)-冲四：1,000分。只有一头空，对手必须防守，具有强进攻性。

(3,2)-活三:500分。若对手不防守，下一手可变活四，威胁巨大。

(2,X)-活二等：低分。属于布局阶段的积累。

第二步，连子扫描。该步骤是评估逻辑的基础，对于给定的坐标(%,y)和方向(dkdy)(如

水平、垂直、对角)，沿正负两个方向延伸扫描，进而统计属于当前玩家(player)的连续棋

子数量，并检查连续棋子的两端是否为EMPTY(即是否被边界或对手堵死)，最后返回一

个元组(count,open_ends),用于在评分表中查找对应的分值。

第三步，局面估计。首先计算某一特定位置乂寸当前玩家的价值，汇总该点在水平、垂直、

主对角线、副对角线四个方向上的棋型得分总和。然后进行全局评估，局势分二(黑棋总得

分)-(白棋总得分)。结果为正，表示局面通过评分表判断对黑棋有利；结果为负，表示局面

通过评分表判断对白棋有利。

4.4为什么极小极大搜索算法的时间复杂度会随着搜索深度增加呈指数级增长？如何

缓解这个问题？

答：极小极大搜索需要遍历规定深度内的所有可能走步，若每个节点平均有b个分支

(分支因子)，博弈树深展为d,则节点总数约为bd,因此时间复杂度为O(bd),随深度

增加呈指数增长。

缓解方法包括：使用a剪枝剪掉不会影响最终决策的分支：使用启发式评估函数提

前终止无望分支；使用迭代加深搜索结合时间控制；使用蒙特卡洛树搜索在巨大搜索空间中

进行采样。

4.5在a剪枝中，为什么节点的搜索顺序会影响剪枝效果？如何优化？

答：a-B剪枝的效率高度依赖于子节点的访问顺序。如果先访问最优的子节点(即对

MAX节点先访问估值高的子节点，对MIN节点先访问估值低的子节点)，可以更早地更新

u/B值，从而剪掉更多分支。

典型的优化方法有：1）节点排序，使用启发式方法（如历史启发式、杀手启发式）对

子节点进行排序；2）置换表，缓存已评估过的局面，避免重复搜索；3）迭代加深，浅层搜

索获取节点顺序，用于深层搜索。

4.6蒙特卡洛树搜索由哪四个步骤组成？简述每一步的作用。

答：蒙特卡洛树搜索包括如下四个步骤：

1）选择：从根节点开始，使用UCB公式评估子节点，反兔选择最有潜力的节点，直到

找到一个未完全展开的节点。

2）扩展：为选中的节点添加一个未被访问过的新子节点，代表一个新的走法。

3）模拟：从新节点出发，使用随机策略快速对弈至终局，得到胜负结果（此过程不记

录在树中）。

4）回溯：将模拟结果沿路径反向回传，更新所有祖先节点的访问次数和胜率统计。

4.7采用a・B剪枝策略进行剪枝，在图中发生剪枝的分支处用“a剪枝”或“B剪枝”

进行标记（标记在满足剪枝条件的a值对应节点和B值对应节点之间的连线上），注意：搜

索过程中，同属一个父节点的多个子节点，优先扩展左侧子节点。

05-333-302-32-3

答:

05-333-302-32-3

4.8下图为井字棋的博弈搜索树,已知底层节点C、I）、I的静态评估值f。

1）使用极小极大搜索策略补全节点E、F、G、H的静态评估值，填入对应节点下方的

括号内，注意：静态评估值计算公式为f（P）=（能使MAX成三子一线的行、列和对角线数）

•（能使MIN成三子一线的行、列和对角线数），其中，P为棋局；

2）使用a-p剪枝策略补全节点S的a值、节点A的倒推评估值以及节点B的B值，填

入对应节点旁边的括号内；搜索过程中，同属一个父节点的多个子节点，优先扩展左侧子节

点；

3）对该博弈树进行剪枝，在图中标注，剪枝标在a和p比较并满足剪枝条件的分支上。

S

MAXX|Q父=()

S

MAXX|_a父=()

4.9实现一个简化版的极小极大搜索算法，用于一个3x3的井字棋（Tic-Tac-Toe）。假

设AI为MAX（棋子，X，）,玩家为MIN（棋子。评估函数为：AI赢=1,玩家赢二・1,

平局=0。搜索深度为2。要求实现evaluatc（board）评估函数、minimax（board,depth,is_max）

递归函数，输出当前最优走步及其评估值。

答：以下是简化版井字棋极小极大搜索算法的完整实现。

importcopy

defevaluate(board):

评估当前棋盘状态

返回：1（AI赢）,-1（玩家赢）,0（其他）

#检查所有行

foriinrange(3):

ifboard[i][0]==board[i][l]==board[i][2]!='

return1ifboard[i][0]=='X'else-1

#检查所有列

forjinrange(3):

ifboard[0][j]==board[l][j]==board[2][j]!='

return1ifboard[Oj|jl=='X'else-1

#检查主对角线

ifboard[0]l0J==board[l][l]==board[2J[2J!='

return1ifbeard[01[01=='X'else-1

#检查副对■角线

ifboard[0][2]==board"]⑴==board[2][0]!='

return1ifboard[0][2]='X*else-I

return0#未分胜负

defis_full(board):

检杳棋盘是否己满

foriinrange(3):

forjinrange(3):

ifboard[i][j]=='

rctumFalse

returnTrue

defprint_board(board):

"""打印棋盘

print("-------------")

foriinrange(3):

print(“|”,end="H)

forjinrange⑶：

print(bcard[i][j]ifboard[i][j]!=1'else'end="|")

print("\n-------------")

defminimax(board,depth,is_max):

It

极小极大搜索算法

board:当前棋盘

depih:剩余搜索深度

is_max:True表示MAX层(AI),False表示MIN层(玩家)

IlltU

score=evaluate(board)

#如果已经分出胜负或平局，或达到搜索深度，返回评估值

ifscore==1orscore==-1oris_full(board)ordepth==0:

returnscore

ifis.max:#MAX层-AI的I可合，选择最大值

best=-float('inf)

foriinrange(3):

forjinrange(3):

ifboard[i][j]

board[i][j]='X'

best=max(best,minimax(board,depth-LFalse))

boardfil[j]="

returnbest

else:#MIN层-玩家的问合，选择最小值

best=floatC'inf)

foriinrangc(3):

forjinrange(3):

ifboard[i][j]==''：

board[i]|j]='O'

best=min(best,minimax(board,depth-1.True))

boardlij[j]="

returnbest

defget_best_move(board):

mm

获取AI的最佳走步

返回:(最佳行，最佳列，最佳评估值)

mm

bcst_val=-float('inf)

best_move=None

print("\n正在计算最佳走步..J)

foriinrange(3):

forjinrange(3):

ifboard[i][j]==":

#尝试在此位置落子

board[i][jl='X'

move_val=minimax(board,2,False)#搜索深度为2

buardliJUJ="

print(f,位置((i)»{j})的评估值:{movjval}”)

ifmovc_val>bcst_val:

best_val=move_val

best_move=(i,j)

returnbesl_move[0],best_move[I],best_val

defmain():

主函数-演示Al决策”加

#初始化空棋盘

board=[[''for_inrange(3)]for_inrange(3)]

print("="*40)

prim("井字棋极个极大搜索算法演示”)

printC'AI(X)vs玩家(O)")

print("搜索深度:2”)

print("=M*40)

#演示1:空棋盘

print("\n【场景1：空棋盘】")

print_board(board)

row,coLvalue=get_best_move(board)

print(f,\n最佳走步:({row}"col})”)

prini(「评估值：(value}")

print(f'解释：评估值{value}表示{‘AI必胜'ifvalue==1else'可能平局'ifvalue==

Oelse，不利}1)

#演示2:特定局面-AI有获胜机会

print("\n"+"="*40)

print("\n【场景2；AI有获胜机会】")

board2=[

['X','X',''L

[5'O','1

「='

1

print_board(board2)

row,cokvalue=get_best_move(board2)

print(f,\n最佳走步:({row),{col})”)

print(「评估值：(value}")

ifvalue==1:

printerAI可以直接获胜！”)

#演示3:需要防守的局面

print("\n"+”="*40)

print(M\n【场景3：需要防守】")

board3=[

[V,'O',"L

[XJ丁I

m

J

print_board(board3)

row,col,value=get_best_move(board3)

print(f,\n最佳走步:({row},{col})")

print(「评估值:{value}")

ifvalue==-I:

print("—如果不防守，玩家将获胜”)

if_name—=="_main_":

main()

运行结果如下:

井字棋极小极大搜索算法演示

AI(X)vs玩家(O)

搜索深度:2

【场景1：空棋盘】

正在计算最佳走步…

位置(0,0)的评估值:0

位置(0,1)的评估值:0

位置(0,2)的评估值:0

位置(1,0)的评估值:0

位置(1,1)的评估值：0

位