论文部分内容阅读
计算机围棋一直以来都是计算机博弈和人工智能领域关注的焦点。计算机围棋虽然规则简单,但其棋面变化多端,也由此造成了计算机围棋博弈的高复杂度,纯粹地靠暴力搜索去计算围棋的落子点是现代计算机根本无法完成的任务,因此必须引入人工智能的方法去解决这一问题。从计算机围棋研究至今,大量的人工智能算法应用于计算机围棋,例如模式匹配、UCT算法、神经网络、K-means算法等机器学习的算法都在不同程度上促进了计算机围棋研究的不断发展。在9*9大小的棋盘上,经过海内外学者的不断研究,计算机围棋水平已经达到职业棋手的棋力水平,但通常在大型的正式比赛中,围棋棋盘大小多采用的是19*19大小的棋盘,在19*19大小的棋盘上,计算机围棋的棋力也已经达到专业棋手水平。本文主要通过最大熵算法对19*19大小的棋盘上的落子预测进行研究以及通过UCT算法对围棋死活题的求解进行研究,本文主要内容如下:1)对计算机围棋进行简单介绍,引出本文的主要研究工作以及解决方案,为研究工作的开展做出相应的准备。2)本文采用最大熵算法和 OWL-QN(Orthant Wise Limited-memory Quas i-Newton)算法对计算机围棋落子进行预测,通过使用不同大小的模式模板对棋盘进行模式匹配,为每个提取到的模式使用Zobrist哈希进行编码,通过最大熵算法和OWL-QN算法对提取到的模式数据进行训练得到模型,然后使用该模型在测试数据上进行测试。实验表明在500个棋谱上获得20.58%的正确率,训练所采用的时间和空间性能上均有很大的提升。3)在围棋死活问题的求解上,传统的求解只能处理封闭边界的死活题。本文提出了一种开放边界围棋死活题的UCT(Upper Confidence bounds for Trees)求解算法。首先根据给定阈值,通过计算棋盘上每一空点的隶属度来确定搜索区域,然后用包围色的搜索区域比被包围色大一圈的特殊UCT算法求解给定开放边界死活题。实验表明,该算法能够在不使用围棋专有知识,不添加额外棋子的条件下,正确求解《李昌镐精讲围棋死活》第一卷中全部123道死活题中的101道,正确率为82.1%,并且大部分死活题都能在较宽的阈值区间里求得正确解,只有一小部分死活题对阈值敏感,其求得正确解的阈值区间较小。