揭秘五子棋AI设备的炼成：wujian100 SoC助力人机对弈（下） |
您所在的位置：网站首页 › 博弈树五子棋原理 › 揭秘五子棋AI设备的炼成：wujian100 SoC助力人机对弈（下） |
|
编辑语： 技术解码栏目：是面向开发者详细解读芯片开放社区（OCC）上关于处理器、芯片、基础软件平台、集成开发环境及应用开发平台的相关技术，方便开发者学习及快速上手，提升开发效率。 作者介绍 王松：复旦大学微电子学院2020级直博生 陈布：复旦大学微电子学院2019级硕士研究生 上期我们简单介绍了五子棋AI设备的开发过程，讲解了基于博弈树的五子棋AI算法的原理，今天我们就带大家深入了解该实战案例的开发过程。 本文将分为五子棋AI核心算法的硬件实现、软硬件协同仿真两部分内容，为大家详细阐述基于wujian100 SoC设计开发五子棋AI设备的过程。 一、五子棋AI核心算法的硬件实现本次工作中，我们使用XILINX VIVADO HLS编写C++源程序，综合出硬件Verilog代码，封装成IP核，然后将其集成于wujian100 SoC平台之中。 1.1 极大极小值搜索算法的编程实现代码主体本质上是一个递归函数，但由于递归函数无法被综合（因为可能出现无穷无尽的迭代，硬件上无法实现），在考虑到最大搜索深度不会超过4层（否则，搜索时间太长）的前提下，实例化4个相同的函数，以供层层调用。 编程思路如下： 第一步，假设我方（或者对方）落子，更新棋盘状态；判断棋面输赢，如果已经输了或者赢了就没必要继续搜索下去了；否则，遍历棋盘上可落子的位置，假设对方（或者我方）落子，进入下一层搜索；得到上一步搜索返回的权值weight，更新下层上界max（或者下层下界min）；当前节点为MAX_Node时，如果max ≥ alpha（此处的max是在当前节点的子节点中已搜索出的最大值，在全部搜索完成前等价于当前节点的 α 值；此处的alpha是当前节点的父节点下的其它子节点中已搜索出的最小的 α 值，在全部搜索完成前等价为上层父节点的 β 值。即满足当前节点的α ≥ 父节点的β的条件），则可以直接返回至上一层，将当前节点及其子节点全部剪枝，即 α 剪枝；当前节点为MIN_Node时，如果min ≤ beta（此处的min是在当前节点的子节点中已搜索出的最小值，在全部搜索完成前等价于当前节点的 β 值；此处的beta是当前节点的父节点下的其它子节点中已搜索出的最大的 β 值，在全部搜索完成前等价为上层父节点的 α 值。即满足当前节点的β ≤ 父节点的α的条件），则可以直接返回至上一层，将当前节点及其子节点全部剪枝，即 β 剪枝；否则，返回已搜索出的下层节点中的最大值max（或者是最小值min）；搜索到限定层数之后，评估棋面，返回权值。相关参数定义如下： 参数定义ChessBoard用于存放棋盘状态的二维数组BOARD_SIZE棋盘规格，默认为15 × 15x, y当前节点的位置坐标type当前节点的类型（MAX_Node / MIN_Node）depth搜索深度（从0开始，递归一次，数值加1）alpha当前节点的父节点下的其它子节点中已搜索出的最小的 α 值，即当前层的下界beta当前节点的父节点下的其它子节点中已搜索出的最大的 β 值，即当前层的上界部分源代码如下： 1. for (j = 0; j < BOARD_SIZE; ++j) {2. for (i = 0; i < BOARD_SIZE; ++i) {3. if (ChessBoard[j][i] == EMPTY && canSearch(ChessBoard, i, j)) {4. weight = minMax3(ChessBoard, i, j, nextType(type), depth + 1, min, max);5. 6. if (weight > max)7. max = weight; // 更新下层上界8. if (weight < min)9. min = weight; // 更新下层下界10. 11. // alpha-beta12. if (type == MAX_NODE) {13. if (max >= alpha) {14. ChessBoard[y][x] = EMPTY;15. return max;16. }17. }18. else {19. if (min |
今日新闻 |
推荐新闻 |
| CopyRight 2018-2019 办公设备维修网 版权所有 豫ICP备15022753号-3 |