c语言蒙特卡洛树搜索代码,uct-gobang

UCT算法实现五子棋AI

环境

Java 1.8 (界面使用的是1.8内置的JavaFx)

运行方式

运行UI类 src.mcts.ui.GoBangUI.java

(目前UI类功能比较简单，仅仅实现AI对局功能)

UCT基本思想

(本图来自于维基百科[蒙特卡洛树搜索]页面)

大多数当代蒙特卡洛树搜索的实现都是基于UCT的一些变形。

[1] selection(选择)从根节点开始，选择连续的子节点向下至叶子节点，选择的方式使用UCB公式。

[2] expansion(扩展)除非任意一方的输赢使得游戏在叶节点结束，否则创建一个或多个子节点并选取其中一个节点。(本项目中选择创建多个子节点)

[3] simulation(模拟)在从选择的子节点开始，用随机策略进行游戏

[4] backPropagation(传播)使用随机游戏的结果，更新从选择子节点至根节点。

(以上说明部分借鉴于维基百科[蒙特卡洛树搜索]页面)

【UCB公式】

(本图来自于维基百科[蒙特卡洛树搜索]页面)

wi代表第i次移动后取胜的次数；

n_i代表第i次移动后仿真的次数；

c为探索参数—理论上等于 sqrt2 在实际中通常可凭经验选择(我的理解：C越大越倾向于那些分数不高，但是模拟次数少的，尽量去尝试更多也许看起来不好的下法)；

t代表仿真总次数，等于所有n_i的和。

(以上说明部分借鉴于维基百科[蒙特卡洛树搜索]页面)

总结

将模拟时间设置为5秒，大部分情况都可以赢我(我执黑棋的情况)，我的水平不是很高；

将模拟时间设置至30秒，勉强可以和网上一个五子棋高手模式战平(因为棋盘大小原因，没有模拟到最后，大部分情况没有输赢)，但是个人感觉处于落后状态；

如果仅仅使用树搜索，一直随机模拟对局，最后的结果并不理想，增加了形势判断，对三连子、四连子等情况的判断打分，大大增加了胜算；

特定情况(对方四连字或己方四连子)直接堵子，不进行模拟对局，缩短垃圾搜索时间。