围棋人工智能几个上限值的研究

摘要

当前围棋人工智能发展很快，继蒙特卡洛(Monte-Carlo)和UCT等方法运用到计算机围棋中取得一些成功后，围棋软件开发的核心就以这两个算法为主。本文简要分析了如何找到围棋本身和围棋对弈过程中的一些边界和上限值，详细讲解了如何对围棋的复杂度进行有效降解以及如何判定局部棋形的复杂深度类型。最后通过实例分析出了UCT和蒙特卡洛(Monte-Carlo)方法所存在的缺陷，得出了必须找寻围棋本身固有的规律的结论，对围棋复杂度进行降解的必要性。接着详细介绍了复杂度降解的一个基础，找出围棋的一些上限值，比如，证明了围棋活棋块在不含双活的情况下单方至多有20块活棋，双方活棋块之和不会超过33，围棋的嵌套层不会超过19层，并给出了一个强有力的猜想，在考虑双活下，围棋活棋块数不会超过71。

目录

声明

摘要

1 绪论

1．1 课题的选题背景和研究意义

1．2 国内外发展现状

1．3 围棋的基本知识

1．4 论文的组织结构

1．5小结

2 基于Alpha-Beta剪枝的搜索

2．1 极大-极小搜索(Min-Max Search)

2．2 Alpha-Beta搜索(Alpha-Beta Search)

2．3 负极大搜索(NegaMex Search)

2．4 迭代加深搜索(Iterative deepening search)

2．5 小结

3 围棋人工智能中几个关键问题的讨论

3．1 围棋的复杂度

3．1．1 围棋的状态空间的复杂度

3．1．2 围棋的博弈树复杂度

3．1．3 复杂度比较

3．2 蒙特卡洛方法(Monte-Carlo)和UCT算法

3．2．1 蒙特卡洛方法

3．2．2 从蒙特卡洛法发展到UCT

3．2．3 UCT搜索

3．3 围棋人工智能中复杂度降解的基础

3．3．1 如何找到围棋本身和围棋对弈过程中的一些边界和上限值

3．3．2 如何对围棋的复杂度进行有效降解

3．3．3 如何判定局部棋形的复杂深度类型

3．4 小结

4 围棋人工智能中几个上限值的讨论

4．1 围棋极限分析的重要性

4．2 围棋对弈过程中的极限分析

4．3 小结

5 总结与展望

参考文献

致谢