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

第4章习题4.1双方、动态、完美信息、确定性、零和的博弈问题具体是指什么？答：双方是指博弈由两方参与；动态是指在博弈中，参与者所采取策略是有先后顺序的，且参与者能够知道先采取策略者所选择的策略；完美信息博弈的每个参与者在做决策时都完全了解曾经和正在发生的对弈过程的所有信息；确定性是指在博弈过程中，参与双方在采取某种策略时，无其他非确定性因素的考虑；零和是指博弈双方收益之和为零。4.2棋局的评估函数的设计原则是什么？答：静态评估函数设计的基本原则是：当对MAX有利时，取正值，并且值越大表示对MAX越有利，当为时，表示MAX必胜；当对MAX不利时，取负值，并且绝对值越大表示对MAX越不利，当为时，表示MIN必胜；当双方势均力敌时，取为零。4.3请尝试说明为五子棋游戏设置静态评估函数的思路。答：第一步，建立评分体系，将棋盘上的棋子分布化为具体的数值。评分依据两个核心维度，即连子数和两端空位数。针对不同的连子数和两端空位数设计权重。具体示例如下：(5,2)-连五:100,000分。游戏胜利，给予绝对高分。(4,2)-活四:10,000分。两头皆空，下一步必成连五，等同于必胜。(4,1)-冲四:1,000分。只有一头空，对手必须防守，具有强进攻性。(3,2)-活三:500分。若对手不防守，下一手可变活四，威胁巨大。(2,X)-活二等:低分。属于布局阶段的积累。第二步，连子扫描。该步骤是评估逻辑的基础，对于给定的坐标(𝑥,𝑦)和方向(𝑑𝑥,𝑑𝑦)（如水平、垂直、对角），沿正负两个方向延伸扫描，进而统计属于当前玩家(player)的连续棋子数量，并检查连续棋子的两端是否为EMPTY（即是否被边界或对手堵死），最后返回一个元组(count,open_ends)，用于在评分表中查找对应的分值。第三步，局面估计。首先计算某一特定位置对当前玩家的价值，汇总该点在水平、垂直、主对角线、副对角线四个方向上的棋型得分总和。然后进行全局评估，局势分=(黑棋总得分)-(白棋总得分)。结果为正，表示局面通过评分表判断对黑棋有利；结果为负，表示局面通过评分表判断对白棋有利。4.4为什么极小极大搜索算法的时间复杂度会随着搜索深度增加呈指数级增长？如何缓解这个问题？答：极小极大搜索需要遍历规定深度内的所有可能走步，若每个节点平均有b个分支（分支因子），博弈树深度为d，则节点总数约为bd，因此时间复杂度为O(bd)，随深度增加呈指数增长。缓解方法包括：使用α-β剪枝剪掉不会影响最终决策的分支；使用启发式评估函数提前终止无望分支；使用迭代加深搜索结合时间控制；使用蒙特卡洛树搜索在巨大搜索空间中进行采样。4.5在α-β剪枝中，为什么节点的搜索顺序会影响剪枝效果？如何优化？答：α-β剪枝的效率高度依赖于子节点的访问顺序。如果先访问最优的子节点（即对MAX节点先访问估值高的子节点，对MIN节点先访问估值低的子节点），可以更早地更新α/β值，从而剪掉更多分支。典型的优化方法有：1）节点排序，使用启发式方法（如历史启发式、杀手启发式）对子节点进行排序；2）置换表，缓存已评估过的局面，避免重复搜索；3）迭代加深，浅层搜索获取节点顺序，用于深层搜索。4.6蒙特卡洛树搜索由哪四个步骤组成？简述每一步的作用。答：蒙特卡洛树搜索包括如下四个步骤：1）选择：从根节点开始，使用UCB公式评估子节点，反复选择最有潜力的节点，直到找到一个未完全展开的节点。2）扩展：为选中的节点添加一个未被访问过的新子节点，代表一个新的走法。3）模拟：从新节点出发，使用随机策略快速对弈至终局，得到胜负结果（此过程不记录在树中）。4）回溯：将模拟结果沿路径反向回传，更新所有祖先节点的访问次数和胜率统计。4.7采用α-β剪枝策略进行剪枝，在图中发生剪枝的分支处用“α剪枝”或“β剪枝”进行标记（标记在满足剪枝条件的α值对应节点和β值对应节点之间的连线上），注意：搜索过程中，同属一个父节点的多个子节点，优先扩展左侧子节点。答：4.8下图为井字棋的博弈搜索树，已知底层节点C、D、I的静态评估值f。1）使用极小极大搜索策略补全节点E、F、G、H的静态评估值，填入对应节点下方的括号内，注意：静态评估值计算公式为f(P)=（能使MAX成三子一线的行、列和对角线数）-（能使MIN成三子一线的行、列和对角线数），其中，P为棋局；2）使用α-β剪枝策略补全节点S的α值、节点A的倒推评估值以及节点B的β值，填入对应节点旁边的括号内；搜索过程中，同属一个父节点的多个子节点，优先扩展左侧子节点；3）对该博弈树进行剪枝，在图中标注，剪枝标在α和β比较并满足剪枝条件的分支上。答：4.9实现一个简化版的极小极大搜索算法，用于一个3×3的井字棋（Tic-Tac-Toe）。假设AI为MAX（棋子‘X’），玩家为MIN（棋子‘O’）。评估函数为：AI赢=1，玩家赢=-1，平局=0。搜索深度为2。要求实现evaluate(board)评估函数、minimax(board,depth,is_max)递归函数，输出当前最优走步及其评估值。答：以下是简化版井字棋极小极大搜索算法的完整实现。importcopydefevaluate(board):"""评估当前棋盘状态返回:1(AI赢),-1(玩家赢),0(其他)"""#检查所有行foriinrange(3):ifboard[i][0]==board[i][1]==board[i][2]!='':return1ifboard[i][0]=='X'else-1#检查所有列forjinrange(3):ifboard[0][j]==board[1][j]==board[2][j]!='':return1ifboard[0][j]=='X'else-1#检查主对角线ifboard[0][0]==board[1][1]==board[2][2]!='':return1ifboard[0][0]=='X'else-1#检查副对角线ifboard[0][2]==board[1][1]==board[2][0]!='':return1ifboard[0][2]=='X'else-1return0#未分胜负defis_full(board):"""检查棋盘是否已满"""foriinrange(3):forjinrange(3):ifboard[i][j]=='':returnFalsereturnTruedefprint_board(board):"""打印棋盘"""print("-------------")foriinrange(3):print("|",end="")forjinrange(3):print(board[i][j]ifboard[i][j]!=''else'',end="|")print("\n-------------")defminimax(board,depth,is_max):"""极小极大搜索算法board:当前棋盘depth:剩余搜索深度is_max:True表示MAX层(AI)，False表示MIN层(玩家)"""score=evaluate(board)#如果已经分出胜负或平局，或达到搜索深度，返回评估值ifscore==1orscore==-1oris_full(board)ordepth==0:returnscoreifis_max:#MAX层-AI的回合，选择最大值best=-float('inf')foriinrange(3):forjinrange(3):ifboard[i][j]=='':board[i][j]='X'best=max(best,minimax(board,depth-1,False))board[i][j]=''returnbestelse:#MIN层-玩家的回合，选择最小值best=float('inf')foriinrange(3):forjinrange(3):ifboard[i][j]=='':board[i][j]='O'best=min(best,minimax(board,depth-1,True))board[i][j]=''returnbestdefget_best_move(board):"""获取AI的最佳走步返回:(最佳行,最佳列,最佳评估值)"""best_val=-float('inf')best_move=Noneprint("\n正在计算最佳走步...")foriinrange(3):forjinrange(3):ifboard[i][j]=='':#尝试在此位置落子board[i][j]='X'move_val=minimax(board,2,False)#搜索深度为2board[i][j]=''print(f"位置({i},{j})的评估值:{move_val}")ifmove_val>best_val:best_val=move_valbest_move=(i,j)returnbest_move[0],best_move[1],best_valdefmain():"""主函数-演示AI决策"""#初始化空棋盘board=[[''for_inrange(3)]for_inrange(3)]print("="*40)print("井字棋极小极大搜索算法演示")print("AI(X)vs玩家(O)")print("搜索深度:2")print("="*40)#演示1:空棋盘print("\n【场景1：空棋盘】")print_board(board)row,col,value=get_best_move(board)print(f"\n最佳走步:({row},{col})")print(f"评估值:{value}")print(f"解释:评估值{value}表示{'AI必胜'ifvalue==1else'可能平局'ifvalue==0else'不利'}")#演示2:特定局面-AI有获胜机会print("\n"+"="*40)print("\n【场景2：AI有获胜机会】")board2=[['X','X',''],['O','O',''],['','','']]print_board(board2)row,col,value=get_best_move(board2)print(f"\n最佳走步:({row},{col})")print(f"评估值:{value}")ifvalue==1:print("→AI可以直接获胜！")#演示3:需要防守的局面print("\n"+"="*40)print("\n【场景3：需要防守】")board3=[['O','O',''],['X','',''],['','','']]print_board(board3)row,col,value=get_best_move(board3)print(f"\n最佳走步:({row},{col})")print(f"评估值:{value}")ifvalue==-1: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位置(1,2)的评估值:0位置(2,0)的评估值:0位置(2,1)的评估值:0位置(2,2)的评估值:0最佳走步:(0,0)评估值:0解释:评估值0表示可能平局========================================【场景2：AI有获胜机会】-------------|X|X|