基于可编程片上系统的人机对弈系统外文翻译资料
2022-10-22 04:10
英语原文共 8 页，剩余内容已隐藏，支付完成后下载完整资料
基于可编程片上系统的人机对弈系统
摘要：基于可编程片上系统（SOPC）技术开发了人工智能人机对弈系统，有井字游戏[1]和五子棋游戏。与DE0开发板连接的触摸屏作为人机交互接口。人机对弈系统是一个算法集合，包括位置分析算法、搜索算法和棋步获取算法。该算法集可分析当前位置，并搜索下一个最佳的棋步。搜索算法从广度和深度上提高了对弈系统的分析能力。
关键词：DE0；触摸屏；人机对弈；五子棋；搜索算法
I. 引言
人机对弈在人工智能领域是一个重要且具有挑战性的课题。棋类游戏是人工智能的“试金石”，其中的搜索和模式识别算法提供了重要的方法。如今，嵌入式系统广泛出现在国民经济的各个方面，基于Nios II软核处理器的可编程片上系统（SOPC）技术也广泛存在于嵌入式系统中，其特点是设计模式灵活、开发周期短和可重构。在本文中，人机对弈游戏嵌入于SOPC系统中，来实现带有音频和视频效果的独特人工智能系统。
II. 总体设计
A.系统功能
对弈系统提供如下功能：
bull;液晶显示器（LCD），触摸屏控制。
bull;井字游戏和五子棋人机对弈。
bull;人机对弈和人人对弈两种可选的操作模式。
bull;初级和高级两种级别。
bull;红外提示音。
B.系统结构
如图1所示，该系统由三个模块组成：现场可编程门阵列（FPGA）开发板，触摸屏和音频模块。
bull;DE0 FPGA开发板：作为系统中心，CPU被设计在FPGA芯片上来运行算法程序并控制其它两个模块。
bull;触摸屏：显示用户界面，并收集用户控制信息。
bull;音频模块：播放提示音。
图1 系统结构
III.硬件设计
A. DE0开发板
DE0开发板是台湾友晶公司的产品，带有阿尔特拉公司Cyclone III 系列型号为EP3C16的FPGA，含15408个逻辑单元，346 I / O引脚和各种接口[2]。
B.控制模块
作为控制器芯片，FPGA是硬件设计的内核，在它上面，配置软核CPU Nios II来运行算法程序[3]和触摸屏驱动模块。红外提示音遥控和定时模块使用硬件描述语言（HDL）开发，用于控制连接到DE0开发板上的器件[4]。
C.触摸屏驱动模块
触摸屏是一种电子可视显示器，可以检测显示区域内触摸的存在和位置。触摸屏包括三个部分：液晶触摸面板，AD7843转换器和40引脚扩展连接器，如图2所示。
液晶触摸屏驱动模块执行两项任务。首先，它从触摸面板接收坐标信号，这些信号对于对弈算法分析棋位置很重要。其次，触摸屏驱动模块调整显示数据并将它发送到与触摸屏的接口[5]。
图2 触摸屏原理图
D.红外提示音遥控模块
播放提示音需要一个带有SD卡的MP3播放器和一个红外接收器。红外提示音遥控模块发送红外命令来控制MP3播放器播放提示音。
红外提示音遥控模块由载波发生器、码调制器和红外线发射管组成。载波发生器使用Verilog HDL语言，用于产生不同频率的方波。
IV. 软件设计
对弈算法函数是在Nios II软核处理器运行的C语言程序，实现了井字游戏和五子棋游戏的两种模式——人机对弈和人人对弈。五子棋游戏有初级和高级两种级别，是软件设计的重点和难点。图3是软件设计主要流程图。
图3 软件结构流程图
五子棋对弈软件设计的关键是设计出一个算法来分析当前位置，并计算下一步的最佳落子点，该算法由棋盘显示算法和分析算法构成。
A.棋盘显示
棋盘显示算法支持触摸屏以正确的方式显示对弈棋盘。该棋盘设计为15 *15的网格，白棋、黑棋和空点都用不同的代码标出。
B.分析算法
分析算法是一个算法集合，其中包括位置分析算法、搜索算法和棋步获取算法[6]。有两个级别供用户选择：初级水平和高级水平。
当用户选择初级水平，算法只分析当前位置，并且选择最佳点落子。下图为初级水平的算法流程。
图4 初级算法流程图
在高级水平中，系统将激活极大极小算法，可以像人一样思考，推理出几步之后的棋局，所以可以更早采取更合理的战术[7]。
高级算法流程图如图5所示。
极大极小算法是用于在二人游戏中选择下一步的递归算法[8]。设定一个值与棋盘上的每个位置相关。这个值由位置评估函数计算，它反映玩家落子到该处是否正确。对手接下来可能的棋步会使该位置有最小值，玩家将采取能使该位置的最小值增大的棋步。
该算法搜索对弈树的节点。树的有效分支数是每个节点的孩子的平均数量。节点的数目随层数成倍增加。因此，游戏分析所需搜索的节点数大约为分支数，即层数的幂次方。
图5 高级算法流程图[9]
极大极小算法建立对弈树来帮助系统推断出几步后的棋局并获取一些可能的位置；分析完这些可能的位置后再选择最佳策略。
实现极大极小算法的步骤如下[10] [11]：
1）设定搜索深度和宽度；
2）评估黑棋（机）；增大位置的最小值，并保存为根节点；
3）在虚拟棋盘中符合规则的每一步完成后，对玩家进行评估。每次取出N个节点（N由宽度设定）
4）重复步骤2和3，直到达到搜索深度。
5）选择最大数量并修改最佳棋步。
图6给出了一个例子。搜索的宽度和深度都被设定为3。第一层表示黑棋最佳的两个落子处，评估后得到最大值。在第二层中，基于上层中黑棋的每一步，得出白棋最好的两种棋步。最后，在第三层中，基于第二层中白棋的每一步，算法将获取黑棋最合理的两种棋步。
图6 搜索树的一个例子
V. 实验与结论
经过反复验证，基于SOPC的人机对弈系统可以实现有人机对弈和人人对弈两种模式的井字游戏和五子棋游戏。该系统可以作出合理的策略并正确判断结果。
选择五子棋游戏的高级水平时，搜索算法的计算时间与搜索深度和广度有关。表1列出了具有不同深度和广度的搜索算法的计算时间。
表1 不同深度和广度的搜索算法的计算时间
|
深度 广度 |
3 |
4 |
5 |
|
2 |
0.08571s |
0.11558s |
0.18688s |
|
3 |
0.22856s |
0.36167s |
1.11948s |
|
4 |
0.39589s |
0.71428s |
3.02133s |
|
5 |
0.90448s |
2.16256s |
11.1795s |
|
6 |
1.46283s |
3.42753s |
21.2331s |
从图中的数据，可以得出结论，更大深度和广度的搜索算法将消耗更多的计算时间，但更具智能。经过大量的实验发现，当深度为5、广度为3时，对弈算法可以在智能和计算性能方面取得最佳平衡。
参考文献
[1] Tictactoe[OL]. http://en.wikipedia.org/wiki/Tic-tac-toe
[2] DE0_User_manual_v1[1].3 .http://www.altera.com.
[3] Nios II Software Developerrsquo;s Handbook.http://www.altera.com.
[4] System Design Using SOPC Builder. http://www.altera.com.
[5] TRDB_LTM_UserGuide_v1.23[OL]. http://www.terasic.com.
[6] L. V. Allis, M. van der Meulen, and H. J. van den Herik, “Proofnumber search,” Artificial Intelligence, vol. 66, pp. 91 - 124, March 1994.
[7] A. Plaat, and J. Schaeffer, “F best-First fixed-depth minimax algorithms,” December 14, 1995
[8] Minimax. http://en.wikipedia.org/wiki/Minimax
[9] S. Bhattacharya and A. Bagchi, “Unified recursive schemes for search in game trees,” Technical Report WPS-144, Indian Institute of Management, Calcutta, 1990.
[10] M. Campbell and T. A. Marsland, “A comparison of minimax tree search algorithms” Artificial Intelligence, vol. 20, pp. 347- 367, 1983.
[11] A. Plaat, J. Schaeffer, W. Pijls, and A. de Bruin, “Nearly optimal minimax tree search,” Technical Report TR-CS-94-19, Department of Computing Science, University of Alberta, Edmonton, AB, Canada, December 1994.
用遗传算法解决五子棋博弈问题
摘要：五子棋，也被称为连珠棋或连五子，是一种流行的双人决策棋盘游戏。给定一个方形15times;15棋盘，两位玩家争先在水平方向、垂直方向或对角线方向连成五颗棋子。解决这类游戏的经典方法是基于博弈树理论，例如极小树。这些方法有一个明显的缺点：搜索的深度总是成为瓶颈。在本文中，我们提出了遗传算法来解决五子棋游戏。我们研究了将遗传算法应用于决策游戏的总体框架，从与游戏相关的各个方面来设计适应度函数。实验结果表明，所提出的遗传算法解决方案较传统博弈树解决方案能进行更深度的搜索，从而得到更好的解决方案，并且更高效地解决问题。
关键词：人工智能；五子棋；博弈；遗传算法；适应度函数
I. 引言
造出和人类一样智能的人工制品一直是人类永恒的梦想，这也促进了研究领域和IT界有了极大的发展。游戏是最广泛的研究领域之一，尤其是决策类游戏。研究人员研究能使电脑游戏问题的解决更智能、更高效地方法。博弈树已经成为主流方法，例如基于极大极小树搜索的国际象棋解决方案已成功地击败了人类最好的棋手[1]。从本质上讲，这些方法通过枚举所有可能的棋步然后选择一个最有利的解决方案，从而找到最佳的下一步方案。算法在博弈树中搜索得越深，就越有效。一般来说，三层结构接近人脑并足以作出简单的推理和响应：在决策类游戏中要么攻击要么防守。然而，时间和空间的复杂度随搜索深度而倍增，这限制了基于博弈树的求解算法的实时性能，尤其是一般人们所拥有的计算资源有限。
遗传算法（GA）是Holland提出的一种启发式搜索算法[2]，并广泛地应用于优化问题。 近年来，遗传算法已越来越多用于游戏研究。相比于基于树的算法，基于遗传算法的解算器不需要枚举所有的可能性。因此，他们可以搜索更深层次的步骤和并在更短的时间内这样做。换言之，它们比传统的解算器更智能、更高效率。在本文中，我们探讨将GA用于游戏的总体框架，并探讨五子棋游戏的重要组成部分，五子棋是经典的双人策略棋盘游戏的。本文设计的遗传求解算法采用了通用而有效的框架，在七级深度下能搜索到最佳棋步，并能与人类玩家对弈。
下一部分介绍相关工作，然后第三部分介绍我们基于遗传算法的五子棋对弈算法。第四部分介绍实验装置，并讨论结果。第五部分总结全文。
II. 相关工作
极大极小搜索和AlphaBeta搜索[3]可以说是解决策略类电脑游戏中最经典和众所周知的基于博弈树的方法。基本上，每一回合这些方法选择对己方最有利的棋步，为它的对手选择最不利的棋步。AlphaBeta修剪算法进一步提高了搜索效率，并已广泛应用到游戏。
遗传算法在执行类似于自然选择过程的方式搜索。每一个可能的解决方案是编码作为个体。个体
剩余内容已隐藏，支付完成后下载完整资料
资料编号：[152847]，资料为PDF文档或Word文档，PDF文档可免费转换为Word
