人机对弈围棋报告

基于人工智能理论的围棋人机对弈基于人工智能理论的围棋人机对弈 摘要 人工智能及搜索的基本概念 实现人机对弈围棋的基本理论与方法 关于人机对弈围棋的算法 包括 蒙特卡罗算法 UCT 算法 Prolog EBG 算法 MTD f 算法 Alpha Beta 算法 回溯法 深度优 先搜索 一 基本概念 一 基本概念 人工智能 Artificial Intelligence 是在计算机科学 控制论 信息论 神经生理学 心理学 哲学 语 言学等多种学科相互渗透的基础上发展起来的一门新兴边缘学科 1 搜索的基本概念 1 搜索的含义 根据问题的实际情况 不断寻找可利用知识 从而构造一条代价最小的推理路线 使 问题得以解决的过程称为搜索 2 状态空间法 状态空间法是人工智能中最基本的问题求解方法 它的基本思想是用 状态 和 操 作 来表示和求解问题 3 问题归约 是不同于状态空间方法的另外一种形式化方法 其基本思想是对问题进行解或变换 2 状态空间的盲目搜索 1 一般图搜索过程 2 广度优先搜索 也称深度优先搜索 它是一种先生成的节点先扩展的策略 3 深度优先搜索 是一种后生成的节点先扩展的策略 4 有界深度优先搜索 在深度优先策略中引入深度限制 即采用有界深度优先搜索 5 代价树搜索 在搜索树中给每条边都标上其代价 称为代价树 3 状态空间的启发式搜索 1 启发性信息和估价函数 启发性信息是指那种与具体问题求解过程有关的 并可知道搜索过程朝着 最有希望方向发展的控制信息 估价函数 f n 被定义为从初始节点 S0 出发 约束经过节点 n 到达目标 节点 Sg 的所有路径中最小路径代价的估计值 它的一般形式是 f n g n h n 2 A 算法 启发式搜索算法 3 A 算法 是对估价函数加上一些限制后得到的一种启发式搜索 4 与 或树的盲目搜索 与或树的搜索过程其实是一个不断寻找树的过程 其搜索过程和状态空间的搜索过程类似 只是在 搜索过程中需要多次强调用可解标记过程或不可解标记过程 5 与 或树的启发式搜索 与或树的启发搜索需要不断地选择 修正希望树 6 博弈树的启发式搜索 1 概述 博弈是一类富有智能行为的竞争活动 可分为双人完备信息博弈和机遇性博弈 若把双人完备信息博弈过程用图表示出来 就可得到一棵与或树 这种与或树被称为博弈树 博弈树具有以下特点 1 博弈的初始状态是初始节点 2 博弈树中的或节点和与节点是逐层交 替出现的 3 整个博弈过程始终站在某一方的立场上 2 极大极小过程 那些对 MAX 有利的节点 其估价函数取正值 那些对 MIN 有利的节点 其估价函 数取负值 那些使双方均等的节点 其估价函数取接近于 0 的值 3 剪枝 与极大极小过程相比 极大极小过程是先生成与或树 然后再计算各节点的估值 这 种生成节点和计算估值相分离的搜索方式 需要生成规定深度内的所有节点 因此搜索效率低 如果 能边生成节点边估值 从而可以剪去一些没用的分枝 这种技术称为 剪枝过程 二 实现人机围棋的基本方法 二 实现人机围棋的基本方法 1 求任一解路得搜索策略 1 回溯法 backtracking 2 爬山法 hill climbing 3 宽度优先法 breadth first 4 深度优先法 depth first 5 限定范围搜索法 beam search 6 好的优先法 best first 7 Prolog EBG 算法 8 蒙特卡罗算法 9 UCT 算法 2 求最佳解路的搜索策略 1 大英博物馆法 British Museum 2 分支界限法 branch and bound 3 动态规划法 dynamic programming 4 最佳图搜索法 A 5 MTD f 算法 3 求与或关系解图的搜索法 1 一般与或图搜索法 AO 2 大极小法 minimax 3 Alpha Beta 算法 4 启发式剪枝法 heuristic pruning 4 博弈树搜索 1 博弈中典型的人工智能方法是搜索博弈树以决定走哪一步 标准的博弈树搜索由四部分组成 1 状态表示 2 候选走法产生 3 确定目标状态 4 一个确定相对优势状态的静态评估函数 有 效的博弈树剪枝方法 比如 增强了程序的表现 2 状态表示 从完全信息的角度看 围棋盘面有 19 19 的 3 次方格 每个交叉点要么空 要么被黑子或白 子占据 状态空间的大小是 3 的 361 次方 或 10 的 172 次方 另外 博弈树的大小 例如可能 的博弈数 在 10 的 575 次方和 10 的 123 次方个 othello 棋的 10 的 55 次方 3 围棋局部死活搜索 围棋局部死活搜索时基于博弈树实现的 树中的结点对应于某个棋局 其分叉表示一步步棋 假设棋手先走 因为棋手可能有多种算法 对手走后得到棋局用 或 结点 表示 然后轮到对手 走 用 与 结点表示这样棋手与对手轮流走棋 从而形成一颗具有 与 或 结点的 4 形式判断与模糊决策 决策是针对某一问题 根据确定的目标及当时的实际情况指定多个候选方案 然后按一定标准 从中选出最佳方案的思维过程 围棋中的每一步棋都是棋手决策的结果 而这种决策又与形式判断 密切相关 三 算法 三 算法 1 蒙特卡罗算法 蒙特卡罗算法 Monte Carlo method 1 算法介绍 运用蒙特卡罗算法作为评估函数 并且试图运用这一评估函数 作为全局性的搜索 蒙 特卡罗方法主要理论基础是依据大数定理 在随机取样情况下 可以获得有误差的评估值 2 蒙特卡罗方法应用于围棋 其核心思想是 在于通过统计许多模拟棋局的结果 进行局面的优劣判 断 亦即将蒙特卡罗作为局面评估函数 以决定着手的好坏 1 将分布式计算应用于围棋人机对弈程序上 充分利用多台计算机的运算能力 将运算任务按 能 者多劳 的原则分配下去 大大缩短程序的 思考 时间 2 后台计算功能 人机对弈中 在用户思考的同时 计算机不会停止思考的脚步 引擎会将局面进 行深入的静态分析并只将对方最有可能落子的点传递给模拟实战的蒙特卡罗算法模块 这样模拟人类 在下棋时的思考方式 可以节省很多轮到自己落子时的用时 3 针对蒙特卡罗算法 提出各种改进方式和延伸算法 核心思想为 利用静态分析和搜索为蒙特卡 罗算法排除一些坏棋 也可利用改变蒙特卡罗模拟对局中双方落子所用的围棋知识 模拟特殊情况 改进后的蒙特卡罗算法可是具有更高的棋力 对局面的把握更精准 4 算法组合思想 细致深入地挖掘各个经典算法的内在联系 了解各种算法的优势和不足 通过将 各个算法模块进行有机的组合和互补 扬长避短 例如让稳定却战斗力不足的搜索和静态分析模块为 蒙特卡罗模块提供备选点 既保证程序落子有良好的棋感 也可以保证有强大的计算力为程序的落子 进行模拟实战检验 3 研究来源 篇名 蒙特卡罗方法在计算机围棋中的应用 程序员 2008 年 12 期 Sylvain Gelly 等 篇名 围棋与人工智能 中国体育科技 2005 年 06 期 师军 2 UCT 算法算法 又名 UCB for Tree Search 1 算法介绍 1 一个 mc 围棋程序随机地下棋 而且根据中国规则可以很容易地对双方结束后的态势 行估值 Mc 程序经过计算无数个棋局搜索那个取得最高胜率的走法 2 一个最基本的 mc 程序会简单地为第一个根节点统计数值 但是这些着法的 mc 估值不会趋向于一 个最佳着法 因此需要做更深的搜索 3 UCT 算法 树图置信 是对 mc 搜索自然的扩展 对每一盘棋 通过搜索一个在内存中生长的树来 确定最初的着法选择 4 当一个端节点出现时 再生长一个新的枝节点 余下的棋自由走下去 利用棋局最后的 5 估值更新对局树中所有走法的统计数据 而这些走法仅是棋局的一部分 6 UCT 算法解决了一个问题 就是在树中选择走法 重要的走法比那些看起来差点的走法更多地被 一个办法就是选择最高胜率高过 50 的 或者随机走法 2 应用于围棋的算法描述 Tree Search 开始时 UCT 会建立一颗 Tree 然后 1 从根结点开始 2 利用 UCB 公式计算每个子节点的 UCB 值 选择最大值的子节点 3 若此节点不是叶节点 则从此节点开始 重复 2 4 直到遇到叶节点 如果叶节点曾经被模拟对局过 为这个叶节点生成子节点 从此节点开始重复 2 5 否则对这个叶节点进行模拟对局 得到胜负结果 将这个收益按对应颜色更新到该节点及它的每一 级祖先节点上去 6 回到 1 除非时间结束或者到达预设循环次数 7 从根节点的子节点中挑选平均收益最高的 作为最佳点 此节点就是 UCT 的结果 3 UCT Tree 搜索流程总结如下 UCT 算法使用极大极小游戏树 minimax game tree 搭配节点选择公式 UCB 公式 选择树节点 展开要测试的节点 然后使用 Monte Carlo 方法执行模拟棋局 最后将模拟棋局的结果回馈更新 流程图如下 4 研究来源 计算机围棋相关问题研究 中国新技术新产品 3 Prolog EBG 算法 算法 1 Prolog EBG 是一种序列覆盖算法 其过程为 1 单个 Horn 子句规则 移去此规则覆盖的正例 2 在剩余正例上重复这个过程 直到覆盖所有正例为止 对任意的正例集合 Prolog EBG 输出的假设包含一组对应于领域理论的目标概念的逻辑充分条件 2 Prolog EBG 算法的具体过程如下 Prolog EBG TargetConcept TrainingExamples DomainTheroy 1 LearnedRules 2 Pos TrainingExamples 中的正例 3 对 Pos 中没有被 LearnedRules 覆盖的每个正例 做 解释 Explanation 以 DomanTheory 表示的解释 说明正例满足 TargetConcept 改进 SuffcientConditions 按照 Explanation 能够充分满足 TargetConcept 正例的最一般特征集合 LearnedRules LearnedRules NewHornClause 其中 NewHornClause 的形式是 TargetConcept SufficientConditions 4 返回 LearnedRules 例 最佳棋着 b n 非禁着点 b n 非劫争禁着点 b n 历史棋谱 立 b n 将对方分为两快棋 b n 若下子则整块气被杀 左边棋块 b n n color 若下子则整块气被杀 右边棋块 b n n color 效率最高 所有好着 值得注意的是 类似 非禁着点 b n 或 立 b n 这样的充分条件很容易在对弈时 而 效 率最高 所有好着 则很难判断 在这里 效率 指的是围棋中的子效 着子效率 针对这个问题 在本文所研究的围棋学习方法中 特别增加了一个评价函数 IGE LTE PTE 4 MTD f 算法 算法 1 算法介绍 1 通常试探值并不一定设成零 而是用迭代加深的形式由浅一层的 MTD f 搜索给出 2 局面评价得越粗糙 MTD f 的效率越高 围棋中可使一个棋子的价值由 100 降低为 10 其他子力也 相应比例降低 以提高 MTD f 的效率 但粗糙的局面评价函数却不利于迭代加深启发 因此需要寻 求一个均衡点 3 零宽度窗口的搜索需要置换表的有力支持 因此称为 用存储器增强的试探驱动器 Memory enhanced Test Driver 即 MTD 它只需要传递两个参数 深度 n 和试探值 f 故得名为 MTD n f 缩写 为 MTD f 4 MTD f 的一个大的优势在于我们可以简化 Alpha Beta 搜索 因为它只需要两个参数 深度和 Alpha 而 不是三个 2 算法的实现 Java 代码 1 int MTDF int test int depth 2 int score beta upperbound lowerbound 3 score test 4 upperbound INFINITY 5 lowerbound INFINITY 6 do 7 beta score lowerbound score 1 score 8 score alphabeta depth beta 1 beta 9 score beta upperbound lowerbound score 10 while lowerbound 3 那么返回的是 4 4 beta return val if val alpha alpha val return alpha 返回最好的值 3 研究来源 王晓春 上海理工大学计算机工程学院 棋类对弈人工智能算法研究 2006 12 6 回溯法 深度优先搜索 回溯法 深度优先搜索 1 回溯法的应用模式 1 设置初始化的方案 给变量赋初值 读入已知数据等 令 表示行变量 表示列变 量 2 变换方式去试探 若 则转 若 则 转 3 判断此方法是否成功 若 成功则 转 4 试探成功则前进一步再试探 5 正确方案 还未找到则转 6 已找到一种方案则记录并打印 7 退回一步 回溯 若为退到头则转 8 已退到头 则结束或打印无解 2 算法的实现 3 研究来源 专题性智能搜索研究与实现 昆明理工大学 2005 34 37 四 四 相关函数 类 相关函数 类 LoadString LoadAccelerators GetMessage TranslateAccelerator TranslateMessage DispatchMessage RegisterClassEx LoadIcon LoadCursor CreateWindow ShowWindow UpdateWindow FillRect GetStockObject GetDC GetClientRect InvalidateRect DialogBox DestroyWindow DefWindowProc BeginPaint Rectangle EndPaint PostQuitMessage EndDialog SetRect GetPath GetParent SetFocus Arc timeGetTime SwapBuffers Polygon ReleaseDC RegOpenKeyEx RegQueryValueEx RegCloseKey 五 程序 五 程序 void AstarPathfinder FindPath int sx int sy int dx int dy NODE Node BestNode int TileNumDest TileNumDest TileNum sx sy 生成 Open 和 Closed 表 EN NODE calloc 1 sizeof NODE CLOSED NODE calloc 1 sizeof NODE Node NODE calloc 1 sizeof NODE Node g 0 Node h dx sx dx sx dy sy dy sy should really use sqrt Node f Node g Node h Node NodeNum TileNum dx dy Node x dx Node y dy OPEN NextNode Node make Open List point to first node for BestNode ReturnBestNode if BestNode NodeNum TileNumDest if we ve found the end break and finish break GenerateSuccessors BestNode sx sy PATH BestNode GenerateSuccessors void AstarPathfinder GenerateSuccessors NODE BestNode int dx int dy int x y if FreeTile x BestNode x TILESIZE y BestNode y TILESIZE GenerateSucc BestNode x y dx dy Upper if FreeTile x BestNode x y BestNode y TILESIZE GenerateSucc BestNode x y dx dy Upper Right if FreeTile x BestNode x TILESIZE y BestNode y TILESIZE GenerateSucc BestNode x y dx dy if FreeTile x BestNode x TILESIZE y BestNode y GenerateSucc BestNode x y dx dy if FreeTile x BestNode x TILESIZE y BestNode y TILESIZE GenerateSucc BestNode x y dx dy Lower if FreeTile x BestNode x y BestNode y TILESIZE GenerateSucc BestNode x y dx dy Lower Left if FreeTile x BestNode x TILESIZE y BestNode y TILESIZE GenerateSucc BestNode x y dx dy Left if FreeTile x BestNode x TILESIZE y BestNode y GenerateSucc BestNode x y dx dy GenerateSucc void AstarPathfinder GenerateSucc NODE BestNode int x int y int dx int dy int g TileNumS c 0 NODE Old Successor g BestNode g 1 g Successor g BestNode cost of getting from BestNode to Successor TileNumS TileNum x y identification purposes if Old CheckOPEN TileNumS NULL if equal to NULL then not in OPEN list else it returns the Node in Old for c 0 c Child c NULL Add Old to the list of BestNode s C hildren or Successors break BestNode Child c Old if g g if our new g value is Parent BestNode Old g g Old f g Old h else if Old CheckCLOSED TileNumS NULL if equal to NULL then not in OPEN list else it returns the Node in Old for c 0 cChild c NULL Add Old to the list of BestNode s Chi ldren or Successors break BestNode Child c Old if g g if our new g value is Parent BestNode Old g g Old f g Old h PropagateDown Old Since we changed the g value of Old we nee d else Successor NODE calloc 1 sizeof NODE Successor Parent BestNode Successor g g Successor h x dx x dx y dy y dy should do sqrt but si nce we don t really Successor f g Successor h care about the distance but just whi ch branch looks Successor x x better this should suffice Anyayz it s faster Successor y y Successor NodeNum TileNumS Insert Successor Insert Successor on OPEN list wrt f for c 0 c Child c NULL Add Old to the list of BestNode s Ch ildren or Successors break BestNode Child c Successor 基于人工智能理论的围棋人机对弈基于人工智能理论的围棋人机对弈