企业官网建设流程全解析

南京 网站备案,成品短视频网站源码搭建免费,简单网站建设推荐,wordpress备案号放置一、核心概念与定义#xff08;填空/选择题高频#xff09;1. 对抗搜索#xff08;博弈搜索#xff09;定义#xff1a;在竞争环境中#xff0c;多个智能体通过竞争实现相反利益的过程典型场景#xff1a;两人对决、零和博弈常见算法#xff1a;最小最大搜索#xff0…一、核心概念与定义填空/选择题高频1. 对抗搜索博弈搜索定义在竞争环境中多个智能体通过竞争实现相反利益的过程典型场景两人对决、零和博弈常见算法最小最大搜索Minimax SearchAlpha-Beta 剪枝搜索蒙特卡洛树搜索MCTS2. 零和博弈一方收益 另一方损失总和为0不存在合作可能与“非零和博弈”对比3. 博弈树用于表示博弈过程中所有可能状态的树结构节点表示游戏状态边表示玩家的动作深度优先遍历常用二、算法原理与流程计算题与简答题重点1. 最小最大搜索Minimax基本思想MAX玩家希望最大化自身利益MIN玩家希望最小化MAX的利益交替进行递归计算每个节点的“效用值”算法流程从当前状态出发深度优先遍历博弈树在MAX层选择子节点中最大值在MIN层选择子节点中最小值叶子节点使用评价函数如胜负、得分2. Alpha-Beta 剪枝目的减少Minimax搜索的节点数提高效率剪枝条件α剪枝在MIN节点若父节点MAX的α值 ≥ 当前节点β值剪枝β剪枝在MAX节点若父节点MIN的β值 ≤ 当前节点α值剪枝α与β的含义α当前路径上MAX玩家的最佳选择下界β当前路径上MIN玩家的最佳选择上界效果不影响最终结果显著减少搜索节点三、典型例题与考点对应回忆卷题型1. 计算题示例类似回忆卷三.3题目会给出一棵博弈树叶节点有评价值要求1写出Minimax搜索后各中间节点的值2在图上标出Alpha-Beta剪枝的位置用“×”表示2. 简答题示例解释Minimax和Alpha-Beta剪枝的关系Alpha-Beta剪枝是对Minimax算法的优化通过剪去不影响最终决策的分支减少搜索空间但得到的结果与Minimax一致。为什么Alpha-Beta剪枝能提高搜索效率通过维护α和β值提前判断某些分支不会影响最终决策从而避免展开这些分支减少节点访问次数。什么是博弈树为什么对抗搜索常用深度优先博弈树是表示博弈过程中所有可能状态的树结构。深度优先节省内存适合递归实现便于进行Alpha-Beta剪枝。四、与试卷中其他章节的关联与启发式搜索对比启发式搜索用于单智能体寻优对抗搜索用于多智能体竞争与蒙特卡洛树搜索MCTS关联MCTS也常用于博弈通过采样代替穷举在非完全信息博弈中更常用与虚拟遗憾值最小化算法关联后者用于非完全信息博弈对抗搜索常用于完全信息博弈五、复习建议掌握算法流程能手动模拟Minimax计算过程能画出Alpha-Beta剪枝过程图理解剪枝原理明确α、β值的传递与更新规则能判断何时剪枝、剪哪一侧分支联系实际应用如井字棋、象棋、围棋等游戏的AI实现思路注意概念辨析零和 vs 非零和完全信息 vs 非完全信息Minimax vs MCTS对抗搜索 · 模拟练习题一、填空题每空1分对抗搜索也称为________搜索适用于________博弈环境。在最小最大搜索中MAX玩家希望________效用值MIN玩家希望________效用值。Alpha-Beta剪枝中α表示________玩家的最佳选择下界β表示________玩家的最佳选择上界。若在MIN节点处发现父节点的α值 ≥ 当前节点的β值则进行________剪枝。在完全信息、零和、两人轮流行动的博弈中常用________算法求解最优策略。博弈树中叶子节点常用________函数评估状态优劣。若博弈树分支因子为b深度为dMinimax算法的时间复杂度为________。Alpha-Beta剪枝最优情况下时间复杂度可降至________。二、选择题每题2分下列哪种情况一定会触发Alpha-Beta剪枝A) α βB) α βC) α βD) α ≤ β在Minimax搜索中某一层为MAX层其子节点返回值分别为[3, 5, 1]则该层节点的值为A) 1B) 3C) 5D) 9关于零和博弈的描述错误的是A) 一方收益等于另一方损失B) 总收益和为0C) 双方可能合作D) 常用于对抗搜索建模以下哪种算法通过随机采样代替穷举搜索A) MinimaxB) Alpha-Beta剪枝C) 蒙特卡洛树搜索D) A*搜索在Alpha-Beta剪枝中α和β的初始值通常设为A) α∞, β-∞B) α-∞, β∞C) α0, β1D) α1, β0三、计算与画图题10分给定如下博弈树叶节点为评价值MAX先手textAMAX / | \ B C DMIN / \ / \ / \ 3 5 2 9 1 8使用Minimax算法计算节点A、B、C、D的值。使用Alpha-Beta剪枝从A开始搜索在图上标出被剪枝的分支用“×”表示并写出α、β值更新过程。四、简答题每题5分简述Minimax算法的基本思想及其局限性。为什么Alpha-Beta剪枝能显著提升搜索效率剪枝是否会影响最终结果对抗搜索与启发式搜索如A*的主要区别是什么参考答案一、填空题博弈零和最大化最小化MAXMINα剪枝Minimax或Alpha-Beta剪枝评价或效用O(bd)O(bd)O(bd/2)O(bd/2)二、选择题BCCCB三、计算与画图题Minimax计算B max(3,5) 5C max(2,9) 9D min(1,8) 1A min(5, 9, 1) 1Alpha-Beta剪枝过程A: α-∞, β∞扩展B → 得值5A: α5扩展C → 第一个子节点2C: α2继续第二个子节点9C: α9返回9A: βmin(∞,5,9)5扩展D → 第一个子节点1D: β1此时α5 ≥ β1触发剪枝不再扩展第二个子节点D返回值1A最终值 min(5,9,1) 1剪枝位置D节点的第二个子节点值为8被剪枝。四、简答题Minimax思想MAX玩家最大化收益MIN玩家最小化MAX收益递归计算。局限性搜索空间大需遍历整棵树时间复杂度高。剪枝提升效率通过α、β值提前排除不影响最终决策的分支减少搜索节点。不影响结果剪枝仅去掉不会改变根节点值的分支结果与Minimax一致。主要区别对抗搜索多智能体竞争考虑对手行为如Minimax启发式搜索单智能体寻优利用启发函数如A*一、零和 vs 非零和维度零和博弈非零和博弈定义一方收益等于另一方损失总和为0各方收益与损失之和不等于0可能存在共赢或共损关系严格竞争对立可能存在竞争、合作或混合合作可能不存在可能存在合作典型例子棋类游戏象棋、围棋囚徒困境、资源分配谈判对抗搜索适用性常用如Minimax一般不用标准对抗搜索常用博弈论或谈判模型二、完全信息 vs 非完全信息维度完全信息博弈非完全信息博弈信息状态所有玩家均知道游戏全部历史与当前状态部分信息不公开如手牌、隐藏状态决策依据基于完整状态树需考虑信息集、概率推断常用算法Minimax、Alpha-Beta、MCTS确定性版本虚拟遗憾最小化、贝叶斯博弈、部分可观测MCTS典型例子象棋、围棋、井字棋扑克、麻将、星际争霸部分信息搜索树结构确定性树每个状态唯一信息集树多个状态归属同一信息集三、Minimax vs MCTS蒙特卡洛树搜索维度Minimax含Alpha-Beta剪枝MCTS搜索方式穷举或剪枝后的确定性搜索随机采样 逐步构建搜索树适用场景完全信息、零和、状态空间较小完全信息或部分信息、状态空间大、分支多是否需评价函数是叶节点需静态评价否通过模拟对局结果评估时间效率随深度指数增长可通过模拟次数控制时间内存使用需保存整棵树或部分路径仅保存构建的部分树结构最优性保证在完全搜索下最优渐进收敛至最优需足够模拟典型应用象棋、跳棋围棋AlphaGo、即时战略游戏四、辨析小结可用于简答题零和博弈一定是完全信息吗不一定。例如扑克是零和但非完全信息。Minimax能用于非完全信息博弈吗不能直接使用因为Minimax依赖完整状态树。非完全信息需扩展为信息集或使用随机化策略。MCTS在哪些方面比Minimax更灵活无需静态评价函数适合大规模状态空间可用于部分可观测环境支持实时决策可随时中断完全信息博弈是否一定可用Minimax求解理论上是但实际受状态空间限制。围棋等游戏状态数太多需结合剪枝、启发式或MCTS。