AlphaGo 简单介绍

读了下2016年的 Mastering the game of Go with deep neural networks and tree search,本来想写个读后感,不过发现 Google DeepMind’s AlphaGo: How it works 其实已经做了相当全面的介绍了。

Untitled

围棋在博弈论上其实算是个非常简单的问题,非胜即负的零和游戏,同时也没有任何随机因素,和简单的井字棋游戏没什么大差。如果棋手是全知全能的话,5a 将只显示0或100,每步只需要在标明100的任何一个位置落子即可(下一步,在对手看来所有位置都将显示0)。

AlphaGo 首先利用的是已有的围棋知识库。如果对于一个棋局,已经有围棋大师如此落子的话,那这至少是个不错的选择。于是由 KSG Go 的数据训练了一个高准确率(57%)的策略网络,用来模拟大师的围棋策略;同时也训练了一个更快速(但较低准确率 24%)的策略网络,用来实时快速推演整个棋局。

策略网络的输出是一个落子的概率分布。因此可以将两个策略网络重复相互对弈,每次会得到有所不同的棋局进程。

接下来 AlphaGo 令高准确率的策略网络相互对弈,用 reinforcement learning 的方法继续优化策略网络。这时,优化的策略网络已经能够大概率战胜已有的围棋程序了。

最后,AlphaGo 利用策略网络对弈的棋局来训练价值网络。简单来说,对于任何棋局,有一个最优的价值(如前所述的0或100,但这需要不现实的完整树状搜索),这个最优的价值可以用反复用策略网络对弈的结果来近似(如果策略网络从该棋局开始对弈100局,80胜20败的话,可以近似认为其价值为80),然后这个近似的价值可以用价值网络的输出来近似。而显然价值网络在实时计算上优势明显。

在这些非实时的策略网络和价值网络训练完成之后,在和人类对弈中,AlphaGo 用基于 Monte Carlo tree search 的树状搜索算法来进行实时计算。在棋局 s,用策略网络的输出用来作为落子的初始价值(优先选择最有希望的落子),同时平衡仍未被探索过的落子选择。直到一定步之后的棋局 s’,平均价值网络的输出和快速策略网络的模拟结果来作为 s‘ 的价值,同时反过来更新之前每次落子的价值。在重复足够次数后选择有最高价值的落子。

这个流程基本是符合人类的直觉的,人类会从经验选择下一子的位置,并预想对手的反应,在一定步数后从经验判断此时棋局优势如何,从而修正开始的落子。

Advertisements
This entry was posted in Computer and Internet, Machine Learning, Science and tagged , . Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s