开源围棋A.I. FoolGo

这几天把围棋A.I.最后的部分写好了，9路小棋盘上看上去运行得还不错，更名为FoolGo。先讲一下UCT博弈树的实现。

鉴于FoolGo的MC模拟速度和棋盘对象的大小，如果直接用树结构实现，用不了几分钟，我的MBP的4G内存就会被棋盘挤爆。所以要通过置换表实现博弈树。

哈希算法当然是zobrist哈希。如果哈希值的类型是uint32_t的话，不同棋局哈希冲突的概率就是1 / ~(uint32_t)0——可以认为不同的哈希值意味着不同的棋局。不用自己写哈希表，C++11新增有标准容器unordered_map，很含蓄的名字，就是哈希表。

zobrist哈希值可以增量计算，不过实现起来有些麻烦，暂不实现，因为FoolGo目前的性能瓶颈还是在落子动作上。

UCT搜索过程中多处要取到子节点的哈希值，如果为此落子很昂贵，因此置换表项须要携带子节点的哈希值，然后通过ChildKey函数取得哈希值：

template <BoardLen BOARD_LEN>
HashKey Engine<BOARD_LEN>::ChildKey(const BoardInGm<BOARD_LEN> &parent,
                                    PointIndex indx) const
{
    HashKey prnt_key = parent.HashKey();
    HashKey chldrn_key = table_[prnt_key].children_key_[indx];
    if (chldrn_key == NONE) {
        BoardInGm<BOARD_LEN> b;
        b.Copy(parent);
        PlayerColor color = OppstColor(b.LastPlayer());
        b.PlayMove(Move(color, indx));
        HashKey key = b.HashKey();
        table_[prnt_key].children_key_[indx] = key;
        return key;
    } else {
        return chldrn_key;
    }
}

有了这个置换表后，易实现UCT博弈树。只是刚写完时bug较多，这种海量计算的函数，debug起来比较头疼……

测试下来，在9路的初始棋盘上，模拟3w局MC对局用时大概9秒多，随着棋局的进行会加快。9秒一步还是比较愉快，就拿来和一个在线围棋A.I.单挑了一下 http://peepo.com/ 。FoolGo无耻地执黑先行：

棋盘上面的数值是FoolGo对该落子点的评估（即下在那里的话最后能占几子）

之前走成裂形了，可以看到FoolGo对局面的评估也持悲观，不过这串的滚打包收还不错。

双方地域基本确定，黑棋败势已定……

额操作失误了，我的测试程序没法悔棋，PK到此为止。

把模拟局数的参数设大一些应该会更强，不过人家的在线A.I.几秒种一步棋，我也不好意思再占便宜。

代码：https://github.com/chncwang/FoolGo

额对了，目前找工作中，之前做过iPhone开发，想转型做服务端的C++开发，比较向往的方向是推荐算法和搜索引擎开发。我还是比较感兴趣用C++高效实现一些东西。联系邮箱：chncwang@gmail.com，工作地点杭州。
原文链接: https://www.cnblogs.com/qswang/archive/2012/12/15/2818870.html

欢迎关注

微信关注下方公众号，第一时间获取干货硬货；公众号内回复【pdf】免费获取数百本计算机经典书籍