读[Seminal Ideas from 2007]

今天的google research 发布了ICML Test-of-Time Award 的一个视频介绍. 主要讲解了AlphaGo使用的算法和决策模型的建立.

使用的算法包括:

Monte-Carlo Tree Search

  • AlphaGo主体策略的数据结构, 其他的算法的输入, 输出, 都体现在这个数据结构基础上.
  • 每个node代表一个状态, 如果是围棋,就是当前的棋盘状态和那一方执棋, Node包含以下信息:
    • 来自于蒙特卡洛树的概率信息,比如4/5的意义是:4次取胜/5次当前状态
    • 来自于online(当前棋盘)的RAVE(rapid action value estimation)信息,用于快速进行树的探索
    • 来自于online(当前棋盘)的UCT(Upper Confident Bounder)信息,用于在subtree之间(Guess)跳转,避免local optimization.
    • 来自于offline信息,用来对于当前node进行初始化(这个非常重要, 因为棋盘足够大的时候, 如果没有初始化, 那么一切决策都来自于online的信息, 这样当前node的胜利概率在一开始的时候, 将会非常不可靠, 从而影响整个策略的选择)和再次策略验证(当online策略不确定时,需要offline的数据支持, 可以想象成一个选手对于当前棋局由于不决的时候, 他会想起以前看的棋谱中大师是怎么决策的, 从而进行下一步策略分析)
      • Reinforcement Learning: 用来训练机器对棋谱的认识, 从而记录大师的思路.
      • Convolutional Neural Network: 用来训练机器对整个棋局的认识, 从而让机器模糊的对黑白子进行图像化记忆, 这可以让机器对棋盘的布局有一个总体的分析.
  • 每个edge代表一个policy的使用. policy有两种层面:
    • Tree Policy: 一种greedy policy,建立MCTS树的基本使用方法.
    • Rollout Policy: 一种随机部分的policy,用来访问MCTS树的节点的policy.
    • (其实这两种policy已经涵盖在上面的learning机制中)

视频中还提到AlphaGo是一个12层的深度神经网络,里面已经涵盖了大部分已知高手的棋谱和思路,并且能通过修改策略参数, 自动进行训练……