简单介绍一下MOGO

malaybear

MOGO的诞生

先从王一早说起吧。一早是北大数学00的学生，之后来Ecole Polytechnique学习应用数学硕士（Polytechnique是法国的清华）。看到他的名字，我总是不由自主地想起鲁迅刻在书桌上的那个‘早’字。事实上，一早很聪明也很勤奋，做事认真一丝不苟。事实上，mogo中他编写的代码可读性最强。2006年4月，他在lri（法国信息技术研究室）作了毕业实习，和Sylvain Gelly（当时还是在读博士）一起工作。因为一早他从小热爱围棋（我的围棋就是他教的，哈哈），就开始尝试计算机围棋的编写。

在我看来，计算机围棋和象棋相比，主要难点在于没有一个好的评估函数（Evaluate function）。在国际象棋中，如果一方损失了大子，如后，或者子力没有及时展开，那么形势很可能就一边倒了。所以评估函数往往是各个子的加权平均，加上每个子可以攻击到位置，再加上一些修正项。有了评估函数，就大大简化了搜索。如果评估函数是100%精确的，只要进行一次max min的搜索找最大值就可以了。即使评估函数只是近似，也可以省去很多无用的搜索。但是在围棋中，据我所知，还没有一个令人满意的评估函数。在这种情况下，大家就提出用MC模拟来代替评估函数。但是问题又出现了，MC模拟的收敛速度是1/sqrt(N)，走不能只模拟不搜索其他可能的棋步啊。这就是一个典型的Exploration vs Exploitation的问题。在Bandit问题中，UCT算法是相当不错的。当N(模拟次数)趋于无穷时，最好的分支和其他分支的模拟次数分别是N和LnN量级。MC和UCT的结合产生了MOGO的雏形。

在06年6月份，MOGO的雏形就完成了。一早邀请我们和MOGO对弈，来寻找bug。当时MOGO棋力很差，在9x9的棋盘上，连我这个只学了2个月围棋的菜鸟都下不过。（想想现在，我都已经没有和mogo下棋的勇气了）

MOGO的MC改进

在棋魂中，佐为，塔矢都在追求着神之一招。我不明白神之一招的确切含义，但是在电脑围棋这个领域里，大家确实是不断创新，不断改进，来挑战人对围棋的垄断。

Random MC部分
前面已经说过了，用MC模拟来代替评估函数，但是问题是好比两个高手下棋，下了一半，让两个不会下棋的门外汉来胡走一气，直至终局，来判断之前高手下棋的形势。这总是说不过去的。一早在这里做了一个关键的改进。

即使在高手下棋中，除了开局和突然投入对方阵地的棋，大家一般都是使用飞，长，断，连，尖，冲，立等围绕着自己已有棋子和对方的棋子做文章的棋，所以一早让MC模拟部分只能做这些固定的形。就好比是高手下棋之后让两个庸手下至终局，这样评判的效果比两人胡下，要好太多了。这个改进立竿见影，MOGO的棋力立刻可以和已有的电脑围棋程序一较高下了。

之后，就是对MC部分的微调了，可以想象，当MC部分越智能，他给出的终局结果越有意义，但是相应的运算时间就长，模拟次数就少了。为了找到这两者之间的平衡，光是我看到MC代码，就有45种，一早和sylvain以及之后的开发者，不停试验，不断改进。

UCT部分
事实上，在现在的MOGO程序中，已经不使用UCT算法了，而是代以很类似AMAF算法。之所以换算法，原因也很简单，使用AMAF算法的围棋程序对UCT的胜率超过50%。

基于MC的围棋程序相对于基于围棋知识的程序，最大的好处就是，随着电脑运算能力的提高，MC围棋的棋力也是水涨船高。大家都熟知的摩尔定律--CPU的性能每18个月提高一倍，价钱下降一半。我记得几年前，大家还热热闹闹的讨论摩尔定律是否能持续下去--因为随着IC尺度的缩小，散热，量子效应都成为难以逾越的瓶颈。但是现在看来，这个定律通过另一种方法持续下去了--多核技术。（插一句题外话，Playstation 3以他强大华丽的9核，令人乍舌的价格，不到4000人民币，出人意料的找到了除了游戏迷外新的粉丝--并行运算的实验室）

判断一个围棋程序优劣的最佳方法就是相互下棋看赢棋率，但是这很耗时间。所以大家选用了另一个紧密相关但可以实时监测的参数--每秒MC的次数作为一个优化的目标。在单CPU的优化有所突破之后，下一步自然是并行运算。事实上，MC是天然适合并行运算的。

在这一点上，mogo和其他基于蒙特卡洛算法的程序就显示出优于其它传统的基于定式的程序的优点了。如果只是向人类模仿，是永远赢不了的。

mogo运用了800cpu的cluster。今年在被让9子的情况下在19x19上战胜了八段韩国职业棋士MyungwanKim。当然，kim开始严重低估了mogo的棋力，开始下得很差。他输棋之后，当然大赞mogo，汗。

上个月，mogo在台湾向周俊勋挑战（在9x9上分先，持黑持白各一局，19x19被让7子）。在9x9的比赛中，周俊勋险胜，在19x19上，mogo下的很差（mogo的特点是如果能够领先，就能咬住，下出比较有质量的棋；但是一旦落后，就自暴自弃）。（也是上个月，在北京，mogo输给了many faces go，一个美国的围棋程序，原因据说是--位于荷兰的cluster遇上停电...）

MOGO最近又作了新的改进，现在单机版大概达到KGS上1k的水平。在kgs上MOGO的账号是mogobot1和mogobot3。