C++程设实验项目三：黑白棋与基于UCT算法的AI-程序员宅基地

在这篇博客里，我将总结一下在这次实验中学到的UCT算法实现原理。

 

首先是参考文章：

https://blog.csdn.net/u014397729/article/details/27366363 这是一篇用UCT算法实现四子棋AI的博客。这里给出了UCT的完整伪代码，而且有现成的可运行代码以供参考

https://blog.csdn.net/yw2978777543/article/details/70799799 这篇文章则用数学语言和伪代码进一步阐述了UCT算法的工作原理

https://jeffbradberry.com/posts/2015/09/intro-to-monte-carlo-tree-search/ 这篇英文文章则有一个清晰的图示，可以直观地认识UCT算法。

 

 

然后，让我唠叨一下本次黑白棋的具体实现和规则。

首先，每回合只有五秒的可用时间。这是为了防止有同学拿剪枝算法算太久。

同时，为了防止同学们写剪枝算法的时候直接抄网上的估值表，定义了如下规则：本方下棋时不可以下在上一回合落子的邻接点。

如图，黑色星是刚刚下的位置，X是不能下的位置，白方可下位置用♂标出（不要在意细节）。

 

那么具体的数据结构是这样设计的：

class Board {
    //记录了棋盘，以及上一子的颜色和位置
    int chessboard[8][8], latestColor;
    chesspos latestStep;

public:
    //棋盘的操控
    Board(); //初始化，在四角放上棋子
    bool isEnd();  //用对黑白子都算可下位置的方法计算是否终局
    bool notConj(chesspos a, chesspos b); //用于判断某点是否可下
    bool search(chesspos p, int color, int d); //判断某个方向上是否满足翻子条件
    void rev(chesspos p, int color, int d); //在search满足后翻棋子
    void oneMove(chesspos p); //确保合法的状态下给定位置，自动完成落子过程
    vector<chesspos> getValidPos(int, chesspos); //提供颜色和上一子的位置，返回可下位置

    //将会用于UCT算法的操作
    int calScore(); //计算分数
    chesspos randomMove(); //随机落子
    int simulate(); //用随机落子的方法完成棋盘

    //作业具体要求下的操作，可以无视之
    void graphBoard();
    void graphBoard(string path);
    void printScore(string path);
};

 

好了，让我们开始讨论UCT算法吧。

要写一个基于UCT算法的AI，首先就要弄懂UCT算法究竟在干什么。这是很重要，只有弄懂了怎么回事，才可以基于伪代码的框架实现，否则很可能实现的东西四不像，甚至为别人下棋。

 

黑猩猩算法——仅仅比随机落子好一点

在接触UCT之初，我曾一知半解地构想出这样一个解决方案：

• 我们在计算正方形内切圆面积时，可以随机播撒豆子。然后，数一数圆内的豆子数量，与所有豆子的数量比较，就可以知道圆的面积了。
• 基于同样的道理，我可以随机在所有的可下位置选一点，然后通过随机落子完成棋盘。只要模拟次数够多，那么不同位置的可能胜率就会有差异。选择胜率最好的那个位置，然后就可以一路走向成功喽！

 

尽管可能是我的估值设计有误（在没有理解具体含义的情况下使用UCT算法的估值公式），导致算法和随机落子没太大区别，但总而言之，黑猩猩不是一个好的算法。模拟是需要时间的，五秒钟随机的结果很难让优势显现出来，就好像一个一米的正方形，只播撒一百颗豆子去算内切圆的面积，当然算不准。那么如何去改进呢？

 

多臂赌博机问题，以及由此引出的UCB算法

现在不考虑黑白棋了，考虑我们去玩赌博机。现在面前有几台（不妨设为4台）相同的赌博机，它们的玩法是一样的：拉下拉杆，然后有几率获得一枚硬币作为奖励。不同的赌博机有不同的出奖概率，而你拉动拉杆的次数是有限的——比如233次。如何设计策略，让你这233次的拉动能获得最高的奖励呢？

 

1. 首先，凭我们的直觉，当然是每个赌博机都拉一次，先看看他们的表现如何。
2. 然后，如果A,B,C,D四个赌博机中，只有B赌博机给了你硬币，那么你要怎么选择呢？从当前的局面来看，当然是要继续拉B赌博机了——毕竟，从统计学上说，B赌博机的出奖概率是100%呢。
3. 然而，又两次的拉动，都没有出奖。即使B赌博机的出奖概率还是比A,C,D的高——33%对0%，但你有理由怀疑，A,C,D中有更好的选择，只是样本太少暂时没有显现出来。于是你就先放下了B，转而尝试其它赌博机。

 

这听起来的确很有道理，而也的确就是UCB算法处理博弈树的思想：

• 通过多次模拟的结果，寻找到概率最高的那一个节点。将自己的主要精力用在这一个节点上，避免不必要的浪费。这个过程叫利用（Exploitation）。
• 但是，也要照顾到那些被“冷落”的节点，避免失去机会。这个过程叫探索（Exploration）。

那么，我们如何确定选择哪一个节点呢？这就要使用UCB公式。针对像多臂赌博机这样的问题，可以设计这样的一个公式：

其中：

• Cw为节点分数。
• Cv为该节点总访问数。
• Pv为所有节点总访问数。
• C为比例系数。这个系数越大越注重探索，越小越注重利用。

这里的关键就在于如何调整比例系数了。一般需要用实验来确定，参考的文章中提供的一个可选的参数是1.38，也就是求解C*sqrt(2)==1.96得到的数值。至于为什么是1.96，我也说不清楚……

 

总之，在这个策略下，你可以记下拉动拉杆的总次数，以此作为Pv。针对单个赌博机，记得到的硬币为Cw，历史拉动次数为Cv，那么拉动前给每个赌博机计算UCB值，选择最大的那个去拉动就好了。当存在未拉动的赌博机，我们可以视为其UCB值无限大，这样我们总是优先地去尝试这些赌博机，毕竟它们有无限可能嘛。

 

将UCB算法与蒙特卡罗树结合的UCT算法——直观的解释

出于赌博机的封装机制，我们并不能看出拉动拉杆之后，赌博机内部如何进行运算。但是，黑白棋游戏中，我们是可以看到随机落子的模拟过程的。于是我们就可以对UCB算法做一些改进，使得我们的模拟过程能记录下来。这里就要用到树，树的节点代表一个棋盘的状态，同时也记录了这个状态下落子的一方以及落子方的胜率。可以推知，游戏开局的根节点是白色的，因为下一手是黑方行动，根节点是黑色的。

 

问题来了，UCT对模拟的记录是怎么样的呢？如果对算法理解不透彻就按伪代码搭代码，就可能对伪代码产生误解。我和舍友都曾经对其产生过误解，当时我们是这样认为的：UCT算法提到了模拟和备份的概念，那么是不是就意味着，模拟过程中，每一步落子前，我们都考察UCB值最大的点，若这个点不在树中，便生成一个胜率为0/0的节点。当我们经过约60多步的落子，完成棋盘，博弈树上就会有一条长长的枝。最后，根据模拟结果，给枝上的节点记分，得到一串胜率为0/1或是1/1的节点，以此算作所谓的备份过程。

上图是一个错误的理解，你可以看到，开局的首次模拟过程就开辟了一串节点，虚线指向的是还没有开辟的可行节点

但实际上并非如此。对于这个令人困扰的问题，我在观看了文首英文文献中的图片之后茅塞顿开。UCT的过程，实际上是这样的：

• 首先，我们从以当前棋盘状态对应的节点，作为博弈树的根节点。
  • 每次UCT搜索，看的是当前所到的节点，是不是尚未完全扩展的节点。这就好比在看，是否存在没有拉动拉杆的赌博机。
  • 如果这个节点是完全扩展的，那么我们就计算UCB值，选择最大的那个往下走。
• 最终可能出现两种可能：我们遇到了没有完全扩展的节点，或者遇到了终局节点。
  • 终局节点当然好说，就是直接沿着我们刚才来的路径，一个一个节点备份棋局结果。
  • 不然的话，我们就相当于发现了没有拉动的赌博机。这时候就选一个拉下去，即以一个可行状态出发，进行随机模拟。这个模拟过程就是随机在可行位置下不断下子，直到棋盘结束。这个随机过程中我们并不记录任何东西。模拟的结果，从刚才生成的0/0节点开始，依次向上备份结果。
     

抽象地说（来自第一篇参考文章的注解），我们就是在找当前UCT树的主路径，然后取得主路径新生成的尾节点，从这个尾节点出发进行模拟，备份得分的对象是新的主路径。百度百科上有一张图，很直观地展现了什么是主路径。

 

刚才说的是单次的UCT搜索。一次完整的UCT算法求解，是要在限定的时间内进行多次UCT搜索的。每次UCT搜索，都会改变博弈树的结构，影响下一次UCT搜索的主路径走向。而搜索得越多，结果也就越准确。

如果主路径直达终局节点，那么当然就是直接备份结果。

这张图是最常见的情况。在主路径中发现了非全扩展节点，就为从可行节点中新开辟一个0/0节点（你可以看到，虚线还连着一个节点，如果下一次有主路径通往这里，就会开辟它）。

模拟的结果，假定是黑方胜利，那么沿着主路径从这个0/0节点回溯，一直到当前棋盘的根节点，都进行胜率的更新。

 

 

由此，就解释清楚了UCT算法的过程。那么，具体到代码，应该怎么写呢？

 

UCT算法在代码上的具体实现

先是数据结构：

class Node {
public:
    chesspos pos; //此状态的落子位置，如果上一回合没有落子，就是（-1，-1）
    int total, score; //节点的胜率信息
    int color; //落子的颜色
    Node* parent; 
    vector<Node*> child; 
    vector<chesspos> validPos; //生成每个节点的时，都保存了可下位置，这样方便判断是否完全扩展，也可以快速找到可扩展节点
    Node(chesspos p, int c, Node* par, vector<chesspos> v);
};

class Tree {
    Node *subroot, *tail; //一开始的时候想复用搜索树，所以还写了个root保存开局节点，但这实际上是不需要的，因为这个算法不复用搜索结果
    int ownColor; //本方的颜色，用于记录胜率
public:
    //下面这些在后面细讲
    Tree(int ownc); 
    Node* expend(Board board);//expend tail
    void nextnode(chesspos nextp, Board board); //includes nonexist node constuction
    Node* bestChild(Node * tarRoot, double cof);
    Board getTail(Board board);//tree policy
    void backup(int result);

    //下面的这两个都不用管，是作业特殊要求的函数。
    void printInfo(); 
    void newTurn();
};

除了这些UCT树用到的算法，还会用到Board类的simulate()。

 

关于初始化这样的基本操作我们就跳过不提了，先来看看UCT算法的主要部分是怎么工作的：

//到自己的回合了...
//树是Tree UCTtree
//当前棋盘是Board b
s = clock();
n = clock();
while ((int)(n - s)<4750) {
    UCTtree.backup(UCTtree.getTail(b).simulate());
    n = clock();
}
//根据搜索结果落子...

看起来有些简单，因为最重要的过程被抽象到了一条语句里。我们一步步地来看。

 

首先是getTail，由于我们不在节点中保存棋盘，所以这个函数接收一个棋盘，这个棋盘的状态等同于当前根节点代表的状态。

Board Tree::getTail(Board board) {
    tail = subroot;
    while (!board.isEnd()) {
        int vs = tail->validPos.size(), cs = tail->child.size();
        if (vs != cs) {
            tail = expend(board);
            board.oneMove(tail->pos);
            break;
        }
        else {
            tail = bestChild(tail);
            board.oneMove(tail->pos);
        }
    }
    return board;
}

你可以看到，如果主路径直达终局，那么就退出while，返回一个终局的棋盘。如果不是，也就是vs > cs的时候，就基于当前棋盘，扩展一个节点，然后根据这节点落子，最后返回棋盘。

 

getTail里有两个函数没有说，一个是expend，一个是bestChild。

Node* Tree::expend(Board board) {
    Node* newNode;
    vector<chesspos> possiblePos;
    bool matched;
    //以下的循环就是找出validPos中不在child的那些位置
    for (auto v : tail->validPos) {
        matched = false;
        for (auto c : tail->child) {
            if (v == c->pos) {
                matched = true;
                break;
            }
        }
        if (!matched) possiblePos.push_back(v);
    }
    int index = rand() % possiblePos.size();
    board.oneMove(possiblePos[index]);
    newNode = new Node(possiblePos[index], !(bool)tail->color, tail, board.getValidPos()); //你可以看到，节点在生成的时候就保留了可下位置。
    tail->child.push_back(newNode); //把新节点放入tail的子节点行列中。事实上，getTail里的tail = expend(board)是可以合并在expend里的，这就是具体实现细节的问题了。
    return newNode;
}

这个代码应该很直观了，就是为搜索树扩展一个新的节点，然后棋盘相应地更新一下。

 

然后是bestChild。你可以看到比例系数cof是150，这个稍后会解释。

Node* Tree::bestChild(Node *tarRoot = NULL, double cof = 150) {
    double argmax = -99999999, ucb;
    Node* best = NULL;
    if (tarRoot == NULL) tarRoot = subroot;
    for (auto c : tarRoot->child) {
        ucb = 1.0 * c->score / c->total + cof * sqrt(log(tarRoot->total) / c->total);
        if (ucb > argmax) {
            argmax = ucb;
            best = c;
        }
    }
    return best;
}

要注意的是，无论是自己还是对方，UCT公式是一样的。如果在算对方的UCB值时加负号什么的，实测中发生的事，就是显示自己的胜率为99.98%，但是瞬间归零。因为在某些接近终盘的局面下，对方的选择可能就将决定胜负归谁。那么这个负号就是假设对手下在最坏位置，并且算出自己胜率。只要人家不傻，下在有利于他的位子，那么自己就绝对会输，胜率也就归零了。

 

以上就是getTail部分了，小结一下，getTail结束时候，我们就获得了一个棋盘，这个棋盘是这么得到的：从游戏当前的棋盘开始，根据UCT树的主路径落子，要么下到游戏结束，要么下到出现了非全扩展节点。如果是后者，就随机选一个之前没试过的位置落子，然后相应地在树上记录这个新的节点。

 

getTail之后就是simulate了，这是Board类的功能，简单看看就行：

int Board::simulate() {
    vector<pair<int, int>> aps;
    int score, tmpcolor = latestColor, tmpBoard[8][8];
    chesspos tmpStep = latestStep;
    memcpy(tmpBoard, chessboard, sizeof(chessboard)); //以上是备份当前棋盘。其实这个备份环节是出于调试的需要，实际上不会直接对本地棋盘这么调用，所以不备份或许也可以。
    while (!isEnd()) {
        randomMove(); 
    }
    score = calScore(); //保存分数
    memcpy(chessboard, tmpBoard, sizeof(chessboard)); //以下是恢复棋盘。
    latestColor = tmpcolor;
    latestStep = tmpStep;
    return score; //返回模拟结果
}

chesspos Board::randomMove()
{
    vector<chesspos> aps;
    int index;
    aps = getValidPos();
    index = rand() % aps.size();
    if (aps[index].first != -1) oneMove(aps[index]); //在oneMove里已经转换了颜色
    else latestColor = !(bool)latestColor; //说明一下，getValidPos在无子可下的时候会返回一个(-1,-1)的位置。
    latestStep = aps[index];
    return latestStep; //其实不一定要return，这里是调试需要
}

 

simulate之后就是backup。

void Tree::backup(int result) {
    //simulate的结果通过正负号来记录黑白子的胜利信息。
    int mod = result > 0 ? BLACK_WINS : WHITE_WINS;
    result = abs(result);
    while (tail != subroot) { 
        tail->total += 64;
        if (!(tail->color ^ mod)) tail->score += result;
        tail = tail->parent;
    }
    //由于之前的规划问题，这里还要再对subroot进行处理。如果每次转移搜索树的根节点的时候，都清除subroot的parent，那么就可以用while(tail)一步到位。
    tail->total += 64;
    if (!(tail->color ^ result)) tail->score += result; //这一行貌似可以不要，因为根节点的胜率不在计算的考虑范围内。
}

这里有必要说明一下记分规则。在我自己的实验过程中，设计了两种计算分数的规则，一种是计算胜负，一种是计算终局棋盘本方剩余子数。

• 如果是计算胜负，那么主路径的所有节点Cv+1，胜方颜色节点Cw+1，但负方不扣分。
• 如果是计算胜子，那么Cv+64，胜方Cw加棋盘上的本方子数，同样的，负方不扣分。注意，不能Cv+32，然后Cw考虑负方扣分，这会导致奇奇怪怪的情况。

两个记分规则会导致什么不同呢？

• 计算胜负，可以直观地看到胜率信息，但是最终只是能赢，不能考虑赢多。此时的比例系数c照常为1.38
• 计算胜子，就根据胜子数量细分了胜率，可以追求更多的胜子。然而，Cv+64导致增长过快，1.38的比例系数会导致极为不平衡的利用，所以必须把c调大。我尝试过从88.32到180的比例系数，但是由于时间上的限制，没办法清晰地展现出这些系数的不同。最终我采用了150，当然小一点也是没问题的。

 

至此，UCT算法的主要过程就结束了。之后就是一些操作上的设计了。

//...搜索结束
//要获得最佳节点，就把比例系数设为0，即完全利用，只看胜率了。
Node* best = UCTtree.bestChild(NULL, 0);
UCTtree.nextnode(best->pos, b);
//进行下一回合，轮到对手落子...

对了，nextnode是什么呢？

void Tree::nextnode(chesspos nextp, Board board) {
    for (auto c : subroot->child) {
        if (c->pos == nextp) {
            subroot = c;
            subroot->score = 0;
            subroot->total = 0;
            subroot->child.clear();
            return;
        }
    }
}

虽然nextnode很简单，就是向下转移根节点，但是注意到：

• 会不会出现我的目标节点并未被扩展出来？实际上不需要担心这个，一个局面的可下位置至多不超过30多，而5秒已经可以达到800多次的UCT搜索，所以并没有要为还没扩展的节点考虑在树上新生成节点。此外，bestChild也保证了只会在已扩展节点中选择位置。
• 注意subroot->child.clear()，也就是每次转移根节点，都不必要保存之前的搜索结果，因为这可能会妨碍最优子节点的判断。而且，实际上搜索结果的复用效率很低，即使保存了也不会有很大的能力提升。

 

UCT的实战效果怎么样？

你可能注意到了，我没有为动态申请的节点写清除的函数。这意味着会占用很多内存——实测一局大概15M左右。你要是想自己写清除的功能也没问题。

接下来的图片，都是与猴子（完全随机落子）对战的日志。

以上是计算胜负的情况下的结果。在第19步，就已经有1360步的搜索。在角位落子，显示出了高胜率，所以角位的搜索次数也相对较多。程序最终选择下在角位，而且胜率暂时为60%。

 

在计算胜负的策略中，算法在第47步确定自己将会胜利，胜率显示为了100%。

 

 

当采用计算剩子的策略时，计算的就是棋盘剩子的期望值了。47的剩子以为着极大的获胜可能，而且看AI的行为，已经逼得对方无棋可走，最终达成了完胜的局面。

 

 

甚至还出现了这样的局面：对阵的是同学的剪枝算法，UCT算法是白方。虽然UCT算法很难招架，但是由于对方的一些失误，UCT甚至在失去三个角位的情况下也达成了胜利！

 

关于UCT的总结

• 虽然UCT靠的是随机模拟，但是靠着模拟次数足够和UCB策略，也能有着很不错的表现。
• UCT算法是独立于游戏本身的算法，只要有接口，大部分相似的游戏都可以使用UCT，比如五子棋，象棋等。
• α-β剪枝是常用的算法，但是它需要针对游戏进行精细的估值。相比之下，虽然UCT算法可能打不过精细调参的剪枝算法，但是它只需要调一个比例系数，非常省事高效。
• 搜索次数也是限制UCT算法能力的一个因素。开局情况下只能搜索800次，只有到后期才可能上千上万。如果开局不好，UCT算法可能会无法给自己布好局，从而早早地给出低胜率。当然了，对付猴子还是绰绰有余的。

 

可以跑起来的代码

一个可以跑起来的代码会给我很大帮助，这在我研究UCT的时候就是这么想的。但是下面的代码是我自己本地调试，写的比较乱，很多没有使用的冗余功能，主函数也没有整理，而且整体代码不是最新版本，有兴趣的话看看就好，毕竟上面已经整理好相关代码了。

#include <cstdio>
#include <iostream>
#include <vector>
#include <ctime>
#include <string>
#include <fstream>
#include <omp.h>
//#include <cmath>
#define BLACK_WINS 0
#define WHITE_WINS 1
//#define TESTING
using namespace std;
typedef pair<int, int> chesspos;

class Node {
public:
    chesspos pos;
    int total, score; // long long?
    int color;
    Node* parent;
    vector<Node*> child;
    vector<pair<int, int>> validPos;
    Node(chesspos p, int c, Node* par, vector<chesspos> v);
};
class Board {
    int chessboard[8][8], latestColor;
    chesspos latestStep;
public:
    Board();
    int calScore();
    bool isEnd();
    bool notConj(chesspos a, chesspos b);
    bool search(chesspos p, int color, int d);
    void rev(chesspos p, int color, int d);
    void oneMove(chesspos p);
    vector<chesspos> getValidPos(int, chesspos);
    chesspos randomMove();
    int simulate();
    void graphBoard();
    void printScore();
};

class Tree {
    Node *root, *subroot, *tail;
    int ownColor;
public:
    Tree(int ownc, Board board);
    Node* expend(Board board);//expend tail
    void nextnode(chesspos nextp, Board board); //includes nonexist node constuction
    Node* bestChild(Node * tarRoot, double cof);
    Board getTail(Board board);//tree policy
    void backup(int result);
    void printInfo();
    void newTurn();
};
int dr[8] = { 0,0,1,1,1,-1,-1,-1 };
int dc[8] = { 1,-1,1,0,-1,1,0,-1 };

int main() {
    srand(time(NULL));
    int x, y;
    time_t s, n;
    Board b=Board();
    Tree UCTtree(0, b);
    Node* best;
    int res, searchCount ,total = 0;
    chesspos r;
    while (!b.isEnd()) {
        s = clock();
        n = clock();
        searchCount = 0;
        while ((int)(n - s)<4750) {
            //Board t = UCTtree.getTail(b);
            //res = t.simulate();
            UCTtree.backup(UCTtree.getTail(b).simulate());
            //printf("%d\n", i);
            n = clock();
            searchCount++;
        }
        n = clock();
        printf("time use:%d\nSearch times:%d\n", (int)(n - s), searchCount);
        UCTtree.printInfo();
        best = UCTtree.bestChild(NULL, 0);
        printf("win rate:%lf\n", 1.0 * best->score / best->total * 64);
        b.oneMove(best->pos);
        total++;
        printf("total:%d\n", total);
        b.graphBoard();
        if (!b.isEnd()) {
            UCTtree.nextnode(best->pos, b);
            UCTtree.printInfo();
            best = UCTtree.bestChild(NULL, 0);
            printf("win rate:%lf\n", 1.0 * best->score / best->total * 64);
            //cin >> x >> y;
            //b.oneMove(r);    //if you want to see how monkey moves, delete this two lines and use the next line
            r = b.randomMove();
            total++;
            printf("The monkey choose to move in (%d,%d)\n", r.first, r.second);
            printf("total:%d\n", total);
            UCTtree.nextnode(r, b);
            b.graphBoard();
        }
        system("pause");
    }
    b.printScore();
    system("pause");
    //take white as owncolor, monkey mode only
    total = 0;
    b = Board();
    UCTtree.newTurn();
    while (!b.isEnd()) {
        UCTtree.printInfo();
        best = UCTtree.bestChild(NULL, 0);
        printf("win rate:%lf\n", 1.0 * best->score / best->total * 64);
        r = b.randomMove();
        total++;
        printf("The monkey choose to move in (%d,%d)\n", r.first, r.second);
        printf("total:%d\n", total);
        UCTtree.nextnode(r, b);
        b.graphBoard();
        if (!b.isEnd()) {
            s = clock();
            n = clock();
            searchCount = 0;
            while ((int)(n - s)<4750) {
                res = UCTtree.getTail(b).simulate();
                UCTtree.backup(res);
                //printf("%d\n", i);
                n = clock();
                searchCount++;
            }
            n = clock();
            printf("time use:%d\nSearch times:%d\n", (int)(n - s), searchCount);
            UCTtree.printInfo();
            best = UCTtree.bestChild(NULL, 0);
            printf("win rate:%lf\n", 1.0 * best->score / best->total * 64);
            b.oneMove(best->pos);
            UCTtree.nextnode(best->pos, b);
            total++;
            printf("total:%d\n", total);
            b.graphBoard();
            system("pause");
        }
    }
    b.printScore();
    system("pause");
    return 0;
}

Board::Board()
{
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            chessboard[i][j] = -1;
    chessboard[3][3] = 0;
    chessboard[4][4] = 0;
    chessboard[3][4] = 1;
    chessboard[4][3] = 1;
    latestColor = 1;//gameStartRoot is white, next and first move is black
    latestStep = make_pair(-1, -1);
}

int Board::calScore() {
    int c[2] = { 0 };
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            if (chessboard[i][j] >= 0) c[chessboard[i][j]]++;
#ifdef TESTING
    return c[0] - c[1];
#else
    if (c[0] == c[1]) return 0;
    else if (c[0] > c[1]) return c[0];
    else if (c[0] < c[1]) return -1 * c[1];
    //return c[0] > c[1] ? BLACK_WINS : WHITE_WINS;
#endif // TESTING

}

bool Board::isEnd() {
    if (getValidPos(1, make_pair(-1, -1))[0].first == -1 && getValidPos(0, make_pair(-1, -1))[0].first == -1) return true;
    return false;
}

bool Board::notConj(chesspos a, chesspos b) {
    if (abs(a.first - b.first) + abs(a.second - b.second) == 1) return false;
    else return true;
}

bool Board::search(chesspos p, int color, int d)
{
    int r = p.first + dr[d], c = p.second + dc[d];
    if (chessboard[r][c] == color) return false; //diff color should be in the middle
    while (0 <= r && r <= 7 && 0 <= c && c <= 7) {
        if (chessboard[r][c] == -1) return false;
        else if (chessboard[r][c] == color) return true;
        else {
            r += dr[d];
            c += dc[d];
        }
    }
    return false;
}

void Board::rev(chesspos p, int color, int d)
{
    int r = p.first + dr[d], c = p.second + dc[d], oppcolor = !(bool)color;
    while (0 <= r && r <= 7 && 0 <= c && c <= 7 && chessboard[r][c] == oppcolor) {
        chessboard[r][c] = color;
        r += dr[d];
        c += dc[d];
    }
}

void Board::oneMove(chesspos p)
{
    latestColor = !(bool)latestColor;
    if (p.first != -1) {
        chessboard[p.first][p.second] = latestColor;
        for (int d = 0; d < 8; d++) { //flip in 8 direction
            if (search(p, latestColor, d)) {
                rev(p, latestColor, d);
            }
        }
    }
    latestStep = p;
}

vector<chesspos> Board::getValidPos(int targetColor = -1, chesspos lstep = make_pair(233, 233))
{
    vector<chesspos> result;
    chesspos pos;
    if (targetColor == -1) targetColor = !(bool)latestColor; //next step is for the opp
    if (lstep == make_pair(233, 233)) lstep = latestStep;
    #pragma omp parallel for
    for (int k = 0; k < 64; k++) {
        int i = k / 8;
        int j = k % 8;
        if (chessboard[i][j] == -1) {
            pos = make_pair(i, j);
            for (int d = 0; d < 8; d++) {
                if (notConj(pos, lstep) && search(pos, targetColor, d)) {
                    result.push_back(pos);
                    break;
                }
            }
        }    
    }
    if (result.size() == 0) result.push_back(make_pair(-1, -1));
    return result;
}

chesspos Board::randomMove()
{
    vector<pair<int, int>> aps;
    int index;
    aps = getValidPos();
    index = rand() % aps.size();
    if (aps[index].first != -1) oneMove(aps[index]); //in this func color has been flipped
    else latestColor = !(bool)latestColor;
    latestStep = aps[index];
    return latestStep;
}

int Board::simulate() {
    vector<pair<int, int>> aps;
    int index, tmpcolor = latestColor, tmpBoard[8][8];
    chesspos tmpStep = latestStep;
    memcpy(tmpBoard, chessboard, sizeof(chessboard)); //backup
    while (!isEnd()) {
        randomMove();
#ifdef TESTING
        graphBoard(); //
#endif // TESTING
    }
    index = calScore(); //for temp use
    memcpy(chessboard, tmpBoard, sizeof(chessboard)); // reset to initial state
    latestColor = tmpcolor;
    latestStep = tmpStep;
    return index;
}

void Board::graphBoard() {
    int markboard[8][8];
    vector<chesspos> aps = getValidPos();
    memcpy(markboard, chessboard, sizeof(chessboard));
    if (latestStep.first != -1) markboard[latestStep.first][latestStep.second] = 2;
    for (auto p : aps) markboard[p.first][p.second] = 3;
    printf("  0 1 2 3 4 5 6 7\n");
    for (int i = 0; i < 8; i++) {
        printf(" %d", i);
        for (int j = 0; j < 8; j++) {
            switch (markboard[i][j]) {
            case 0:printf("●"); break;
            case 1:printf("○"); break;
            case 2: {
                if (latestColor == 0) printf("★");
                else printf("☆");
                break;
            }
            case 3:printf("♂"); break;
            case -1: {
                if (notConj(latestStep, make_pair(i, j))) printf("  ");
                else printf("×");
                break;
            }
            }
        }
        printf("||\n");
    }
    printf("=======================\n");
}

void Board::printScore() {
    int c[2] = { 0 };
    for (int i = 0; i < 8; i++)
        for (int j = 0; j < 8; j++)
            if (chessboard[i][j] != -1) c[chessboard[i][j]]++;
    printf("BLACK %d : %d WHITE\n", c[0], c[1]);
}
Node::Node(chesspos p, int c, Node * par, vector<chesspos> v)
{
    pos = p;
    color = c;
    parent = par;
    total = 0;
    score = 0;
    validPos = v;
}

Tree::Tree(int ownc, Board board)
{
    root = new Node(make_pair(-1, -1), 1, NULL, board.getValidPos());
    subroot = root;
    tail = root;
    ownColor = ownc;
}

Node* Tree::expend(Board board) {
    Node* newNode;
    vector<chesspos> possiblePos;
    bool matched;
    for (auto v : tail->validPos) {
        matched = false;
        for (auto c : tail->child) {
            if (v == c->pos) {
                matched = true;
                break;
            }
        }
        if (!matched) possiblePos.push_back(v);
    }
    int index = rand() % possiblePos.size();
    board.oneMove(possiblePos[index]);
    newNode = new Node(possiblePos[index], !(bool)tail->color, tail, board.getValidPos());
    tail->child.push_back(newNode);
    return newNode;
}

void Tree::nextnode(chesspos nextp, Board board) {
    for (auto c : subroot->child) {
        if (c->pos == nextp) {
            subroot = c;
            return;
        }
    }
    //no child matched
    board.oneMove(nextp);
    Node *newNode = new Node(nextp, !(bool)subroot->color, subroot, board.getValidPos());
    subroot = newNode;
}

Node* Tree::bestChild(Node *tarRoot = NULL, double cof = 150) {
    double argmax = -99999999, ucb;
    Node* best = NULL;
    if (tarRoot == NULL) tarRoot = subroot;
    for (auto c : tarRoot->child) {
        ucb = 1.0 * c->score / c->total + cof * sqrt(log(tarRoot->total) / c->total);
        if (ucb > argmax) {
            argmax = ucb;
            best = c;
        }
    }
    return best;
}
Board Tree::getTail(Board board) {
    tail = subroot;
    while (!board.isEnd()) {
        int vs = tail->validPos.size(), cs = tail->child.size();
        if (vs != cs) {
            tail = expend(board);
            board.oneMove(tail->pos);
            break;
        }
        else {
            tail = bestChild(tail);
            board.oneMove(tail->pos);
        }
    }
    return board;
}

void Tree::backup(int result) {
    //if a subroot is avoidable, then use while(tail) for root node's parent is NULL
    int mod = result > 0 ? BLACK_WINS : WHITE_WINS;
    result = abs(result);
    while (tail != subroot) {
        tail->total += 64;
        if (!(tail->color ^ mod)) tail->score += result;
        //tail->score += result * mod;
        //mod *= -1;
        tail = tail->parent;
    }
    tail->total += 64;
    //tail->score += result * mod;
    if (!(tail->color ^ result)) tail->score += result;
}

void Tree::printInfo() {
    printf("subroot:(%d,%d)\n", subroot->pos.first, subroot->pos.second);
    for (auto c : subroot->child) {
        printf("-child:(%d,%d), score:%d, total:%d\n", c->pos.first, c->pos.second, c->score, c->total);
    }
    Node* n = bestChild(subroot, 0);
    chesspos p = n == NULL ? make_pair(8, 8) : n->pos;
    printf("bestchild:(%d,%d)\n",p.first,p.second);
}

void Tree::newTurn() {
    subroot = root;
    ownColor = !(bool)ownColor;
}