当前位置: 主页 > 365bet >

计算机围棋中的算法研究

时间:2020-07-06 09:21来源:原创 作者:admin 点击:

  【摘要】:

  博弈是人工智能的重要研究主题,人工智能的发展在很大程度上得益于博弈研究的发展。作为博弈研究的主要内容之一,棋类博弈得到了满意的解决,唯一的例外的是围棋,目前最优秀的围棋程序的水平还不及人类初级棋手。由于围棋的搜索空间太大、计算机难于处理模糊概念且难于设计学习算法,造成了计算机围棋程序的棋力难于提高。围棋是检验人工智能发展水平的良好环境,如何提高围棋程序的棋力是人工智能领域的一大难题。同时,开发出与人类棋手水平相当的围棋程序也有助于对人类认知能力的理解。所以计算机围棋研究具有重要的理论意义和实用价值。

  我们首先介绍了国内外计算机围棋研究现状,包括基础算法、搜索算法和学习算法三方面并介绍了部分计算机围棋程序,认为计算机围棋的搜索算法主要有minmax算法、alphabeta算法、failsoft算法、negmax算法、negscout算法和mtdf算法等等,涉及到的学习算法和理论基础主要有组合博弈理论、数学形态学、蒙特卡罗算法、模糊学习、分治法、强化学习算法、遗传算法、神经网络、支持向量机、贝叶斯模式分类、基于解释的泛化和并行算法等等,指出了目前研究中存在的主要不足主要表现为局面表示法欠完善、中盘策略欠完整以及学习算法欠成熟。

  然后,我们简述了本研究的相关理论基础,包括数学形态学、有限状态机、线性模型、感知机与遗传算法。

  接着,我们阐明了本研究提出的棋手思维模型、基础算法、搜索算法、学习算法及相应实验结果。具体说来,我们完成的主要工作与创新点包括以下几个方面:

  一、提出了一个完整的棋手思维模型。这是在提出了领土领海和领空等地域概念、提出了局面的层次表示法、归纳并分类了大量围棋术语、提取了目标概念、建立了目标图、总结了若干目标选择原则和走步属性并分析了棋风概念的基础上完成的。这个模型的特点在于它的完整性和围棋术语的分类、目标选择原则与走

  步属性的全面性。

  二、设计了基于数学形态学的局面层次表示法、棋群聚类算法和地域划分算法。这些有统一理论基础的算法计算简单,实验结果表明其效果良好。利用已有的数学形态学理论可以设计更多有意义的启发式策略。

  三、设计了PEMIS模式编码方法。它基于模式的邻近特征、行列特征和轮廓特征进行编码,其突出优点是与模式的黑白对称性、旋转与翻转对称性以及平移对称性均无关,实验结果表明这种模式编码方法性能良好。在基础算法方面,我们还设计了一种走步增量算法。

  四、设计了复合目标搜索算法。我们认为复合目标可看作是由“与”或“或”关系构成的单一目标的二维向量。复合目标搜索算法的优点是其调用的基本函数可由单一目标搜索算法的基本函数合成。我们还比较了经典搜索算法的性能。

顶一下
(0)
0%
踩一下
(0)
0%
------分隔线----------------------------
推荐内容