# FoolGo

**Repository Path**: ifquant/FoolGo

## Basic Information

- **Project Name**: FoolGo
- **Description**: A Go A.I. based on MCTS(AlphaGo and DeepZenGo's basic algorithm) WITHOUT Deep Learning
- **Primary Language**: C++
- **License**: MIT
- **Default Branch**: master
- **Homepage**: None
- **GVP Project**: No

## Statistics

- **Stars**: 0
- **Forks**: 0
- **Created**: 2021-07-31
- **Last Updated**: 2021-07-31

## Categories & Tags

**Categories**: Uncategorized

**Tags**: None

## README

基于蒙特卡罗树搜索的围棋A.I.

目前只有在9路棋盘上表现出入门级棋力。

底层的数据结构和算法相当高效，在我的MacBook Air上1秒钟能跑4万局蒙特卡罗对局（多线程）。

关键方法：

* 并查集实现的棋串（简单的链表实现，若改为树结构，加上路径压缩，会更高效些，但对整体的表现应该影响不大）。
* 位或运算实现棋串『气』的更新。
* 棋盘的哈希算法用Zobrist哈希，通过哈希表存放每个状态的胜率等信息

在面向对象设计上，这个项目高度可扩展（参考了刘知青教授的《现代计算机围棋基础》），介绍主要的几个类：

* FullBoard类，功能完整的棋盘类，提供高效的落子方法等。
* Player抽象类，提供可扩展的棋步选择方法，子类如RandomPlayer，就是Player类的随机落子的实现。
* Game类，Player类的组合，比如子类MonteCarloGame就组合了两个RandomPlayer。

C++编码指南

* 本项目遵循google的guideline中的多数条目。
* 出于性能的考虑，本项目大量使用模板类，在编译期确定棋盘的大小，以便尽可能多地使用静态数组。
* C + class + 模板，不使用模板元编程。
* 尽量用智能指针管理内存，极少数地方用了raw pointer（方法名New前缀），杜绝内存泄露。
* 用gtest做单元测试，用log4cplus打log

## TODO
如果你有兴趣模仿一下AlphaGo，并且也不喜欢python，那么基于这个项目，从实现论文中的rollout policy network开始，替换掉原来的RandomPlayer，是个非常好的选择。

有想过基于tensorflow，开始做这个事情，大致的步骤：
1. 只过一个隐层实现rollout policy network
2. 根据论文中罗列的特征，加特征，以期达到论文中rollout policy network的准确率（也有论文提到可以用CNN实现rollout policy network）
3. 用单层的CNN，实现policy network
4. 把policy network融合进蒙特卡罗树搜索
5. 尝试用多层CNN（估计不用指望能达到论文中的准确率）
6. 以上步骤都采用通过人类的棋谱有监督学习，至于value network和强化学习部分，我还不太会，欢迎邮件交流

本人实在是没时间继续写这个项目，欢迎有兴趣的同学pull request，或者邮件交流~

## Make
* 进入项目根目录
* cmake .
* make
* 不怎么会用CMake，所以第三方库的构建没有纳入CMake的管理，需要根据错误信息在特定的目录下放有相关依赖文件（这个项目目前只依赖gtest和log4cplus）

## 问题交流
* Send me an email : chncwang@gmail.com