Mastering_Chess_and_Shogi_by_Self-Play_with_a_General_Reinforcement_Learning_Algorithm.ipynb · fork-out-project/cchess-zero

加入 Gitee

与超过 1200万开发者一起发现、参与优秀开源项目，私有仓库也完全免费：）

克隆/下载

Mastering_Chess_and_Shogi_by_Self-Play_with_a_General_Reinforcement_Learning_Algorithm.ipynb 34.06 KB

{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 用通用强化学习算法自我对弈，掌握国际象棋和将棋"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`程世东`](http://zhihu.com/people/cheng-shi-dong-47) 翻译\n",
    "\n",
    "[`GitHub`](http://github.com/chengstone)  [`Mail`](mailto:69558140@163.com)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "国际象棋是人工智能史上研究最为广泛的领域。最强大的象棋程序是基于复杂的搜索技术、适应于特定领域、和过去几十年里人类专家手工提炼的评估函数的结合。相比之下，通过自我对弈进行“白板”强化学习，在围棋游戏中AlphaGo Zero取得了超越人类的成绩。在本文中，我们将这种方法推广到一个单一的AlphaZero算法中，从“白板”开始学习，可以在许多具有挑战性的领域具有超越人类的表现。从随机下棋开始，除了游戏规则之外没有给予任何领域知识，AlphaZero在24小时内实现了在国际象棋、将棋（日本象棋）和围棋上的超人类水平，并击败了每一个世界冠军程序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "对计算机象棋的研究和计算机科学本身一样历史悠久。巴贝奇，图灵，香农和冯诺依曼都设计过计算机硬件、算法和理论来分析和指导下棋。国际象棋随后成为一代人工智能研究人员的挑战性任务，最终以高性能的超越人类水平的计算机国际象棋程序的出现而告终。然而，这些系统高度适应与它们的特定领域，不投入大量的人力是不能推广到其他问题的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "人工智能的长期目标是创造出可以从最初规则中自我学习的程序。最近，AlphaGo Zero算法通过使用深度卷积神经网络来表达围棋知识，只通过自我对弈的强化学习来训练，在围棋中实现了超人的表现。在本文中，我们应用了一个类似但完全通用的算法，我们将该算法[arXiv:1712.01815v1 [cs.AI] 5 Dec 2017]称之为AlphaZero，用来像围棋一样下国际象棋和将棋，除了游戏的规则外没有给予任何额外的领域知识，这个算法表明通用强化学习算法可以实现以“白板”方式学习，在多个具有挑战性的领域获得超人的表现。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "1997年，“深蓝”击败了国际象棋人类世界冠军，这是人工智能的一个里程碑。计算机国际象棋程序在那以后的二十多年继续稳步超越人类水平。这些程序使用人类专家的知识和精心调校的参数评估[`走子`](https://baike.baidu.com/item/%E8%B5%B0%E5%AD%90/97274)位置，结合高性能的alpha-beta搜索，使用大量启发式和领域特定的适应性来扩展巨大的搜索树。在[`方法`](#方法)一节我们描述这些增强方法，重点关注2016年顶级国际象棋引擎锦标赛（TCEC）世界冠军Stockfish，其他强大的国际象棋程序，包括深蓝，使用的是非常相似的架构。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在计算复杂性方面，相比国际象棋，将棋更难：它是在一个更大的棋盘上玩，任何被俘获的对手棋子都会改变方向，随后可能被放置在棋盘上的任何位置。最强大的将棋程序，如电脑将棋协会（CSA）的世界冠军Elmo，直到最近才击败人类冠军。这些程序使用与计算机国际象棋程序类似的算法，基于高度优化的alpha-beta搜索引擎，具有许多特定领域的适应性。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "围棋非常适合AlphaGo中使用的神经网络架构，因为游戏规则是平移不变的（匹配卷积网络的权值共享结构），是根据棋盘上的走子点之间的相邻点的自由度来定义的（匹配卷积网络的局部结构），并且是旋转和反射对称的（允许数据增强和合成）。而且，动作空间很简单（一颗棋子可以放在任何可能的位置），游戏结果只有二元结果赢或输，这两者都有助于神经网络的训练。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "国际象棋和将棋不太适合AlphaGo的神经网络架构。这些规则是与位置有关的（例如，兵可以从第二横线前进两步，在第八横线上升变）和不对称的（例如，兵只能向前移动，在王翼和后翼的王车易位是不同的）。规则包括远程交互（例如皇后可以一次穿过整个棋盘，或者从棋盘的另一边将军）。国际象棋的行动空间包括棋盘上所有棋手棋子的所有符合规则的位置；将棋允许将被吃掉的棋子放回棋盘上。国际象棋和将棋都可能造成平局；事实上，人们认为国际象棋最佳的解决方案是平局。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaZero算法是AlphaGo Zero算法的更通用的版本。它用深度神经网络和白板强化学习算法，替代传统程序中使用的人工先验知识和特定领域增强。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为取代手工制作的评估函数和启发式移动排序，AlphaZero使用参数为θ的深度神经网络$(p,v)= f_θ (s)$。这个神经网络使用局面（棋盘状态）s作为输入，输出走子概率向量p，它包含每一个走子动作a的概率分量$p_a  = Pr(a|s)$，同时输出一个标量值v（胜率）——从局面s估算预期结果$z，v ≈ Е[z|s]$。AlphaZero完全从自我对弈中学习这些走子概率和价值估计；然后将学到的知识指导其搜索。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为取代具有特定领域增强的alpha-beta搜索，AlphaZero使用通用的蒙特卡洛树搜索（MCTS）算法。每次搜索都包含一系列从根节点$s_{root}$到叶子节点遍历树的自我对弈模拟。每次模拟都是通过在每个状态s下，根据当前的神经网络$f_θ$，选择一个访问次数低、走子概率高和价值高的走子走法a（这些值是从状态s中选择的动作a的叶子节点状态上做平均）。搜索返回一个表示走子概率分布的向量π ，是在根节点状态下关于访问计数的概率分布（无论是按比例还是贪婪算法）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaZero深度神经网络的参数θ，从随机初始化参数开始，通过自我对弈强化学习进行训练。通过MCTS（$a_t$ ∼ $π_t$ ）轮流为两个棋手选择走子进行下棋。在棋局结束时，根据游戏规则计算游戏结果z 作为结束位置$s_T$的评分：-1代表失败，0代表平局，+1代表胜利。更新神经网络参数θ以使预测结果$v_t$与游戏结果z之间的误差最小，并且使策略向量$p_t$与搜索概率$π_t$的相似度最大。具体而言，参数θ通过在均方误差和交叉熵损失之和上的损失函数l上做梯度下降进行调整，"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "$(p,v)= f_θ (s),       l = (z - v)^2- π^T  log p + c||θ||^2$"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其中c是控制L2正则化水平的参数。更新的参数被用于随后的自我对弈中。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "本文描述的AlphaZero算法在几个方面与原始的AlphaGo Zero算法不同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaGo Zero在假设只有赢或输二元结果的情况下，对获胜概率进行估计和优化。AlphaZero会考虑平局或潜在的其他结果，对预期的结果进行估算和优化。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "围棋的规则是旋转和反转不变的。对此，在AlphaGo和AlphaGo Zero中有两种使用方式。首先，训练数据通过为每个局面生成8个对称图像来增强。其次，MCTS期间，棋盘位置在被神经网络评估前，会使用随机选择的旋转或反转变换进行转换，以便蒙特卡洛评估在不同的偏差上进行平均。国际象棋和将棋的规则是不对称的。AlphaZero不会增强训练数据，也不会在MCTS期间转换棋盘位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在AlphaGo Zero中，自我对弈是由以前所有迭代中最好的玩家生成的。每次训练迭代之后，与最好玩家对弈测量新玩家的能力；如果以55%的优势获胜，那么它将取代最好的玩家，而自我对弈将由这个新玩家产生。相反，AlphaZero只维护一个不断更新的单个神经网络，而不是等待迭代完成。自我对弈是通过使用这个神经网络的最新参数生成的，省略了评估步骤和选择最佳玩家的过程。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaGo Zero通过贝叶斯优化调整搜索的超参数。在AlphaZero中，我们为所有棋局重复使用相同的超参数，而无需进行特定于某种游戏的调整。唯一的例外是为保证探索而添加到先验策略中的噪声；这与棋局类型的典型合法走子的数量成比例。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "像AlphaGo Zero一样，棋盘状态仅由基于每个游戏的基本规则的空间平面编码。下棋的行动是由空间平面或平面向量编码的，而且仅仅基于每种游戏的基本规则（参见[`方法`](#方法)）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们将AlphaZero算法应用于国际象棋，将棋，还有围棋。除非另有说明，所有三个游戏都使用相同的算法，网络架构和超参数。我们为每一种棋单独训练了一个AlphaZero。从随机初始化的参数开始，使用5,000个第一代TPU生成自我对弈数据和64个第二代TPU来训练神经网络，训练进行了700,000步（mini-batches 大小是4096）。 [`方法`](#方法)中提供了训练步骤的更多细节。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "图1显示了AlphaZero在自我对弈强化学习期间的表现。在国际象棋中，AlphaZero仅仅用了4小时（300k步）就胜过了Stockfish；在将棋中，AlphaZero在不到2小时（110K步）就胜过了Elmo；而在围棋中，AlphaZero 8小时（165k步）就胜过了AlphaGo Lee。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![b1](assets\\b1.png\")\n",
    "图1:训练AlphaZero 70万步。国际等级分是在不同的玩家之间的比赛进行评估计算出来的，每一步棋有1秒的思考时间。a国际象棋中AlphaZero的表现，与2016年TCEC世界冠军程序Stockﬁsh比较。b在将棋中AlphaZero的表现，与2017年CSA世界冠军程序Elmo比较。c 在围棋中AlphaZero的表现，与AlphaGo Lee和AlphaGo Zero（20 block / 3天）比较。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们使用所有训练好的AlphaZero，分别在国际象棋、将棋和围棋中与Stockfish, Elmo和上一个版本的AlphaGo Zero（训练3天）进行了100场比赛，时间控制在每步棋1分钟。AlphaZero和之前的AlphaGo Zero使用一台带有4个TPU的机器。Elmo和Stockfish使用他们最强的版本，使用64个线程和1GB hash。AlphaZero击败了所有的对手，对Stockfish 零封对手，对 Elmo输了8局（见几个棋局的补充材料），以及击败以前版本的AlphaGo Zero（见表1）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "\n",
    "![b2](assets\\b2.png\")\n",
    "表1: 在国际象棋，将棋和围棋中评估AlphaZero，以AlphaZero的角度的胜平负，与Stockfish， Elmo，和训练了三天的AlphaGo Zero进行100场比赛。每个程序下一步棋有1分钟的思考时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们还分析了AlphaZero的MCTS搜索的表现，与Stockfish和Elmo使用的alpha-beta搜索引擎进行比较。AlphaZero在国际象棋中每秒只搜索8万个局面（positions），在将棋中搜索4万个，相比之下，Stockfish要搜索7000万个，Elmo搜索3500万个。AlphaZero通过使用其深层神经网络更有选择性地关注最有希望的[`变着`](https://baike.baidu.com/item/%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E6%9C%AF%E8%AF%AD/7549734?fr=aladdin)，补偿较低数量的评估- 可以说是像Shannon最初提出的那样，是一种更“人性化”的搜索方法。图2显示了每个玩家的思考时间，以国际等级分衡量，相对于Stockfish或者Elmo，思考时间为40ms。AlphaZero的MCTS的思考时间比Stockfish或Elmo更有效，这使得人们对普遍持有的观点认为alpha-beta搜索在这些领域本质上是优越的产生了质疑。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "最后，我们分析了AlphaZero发现的国际象棋知识。表2分析了最常见的人类开局（在人类国际象棋游戏的在线数据库中出现过超过10万次）。在自我对弈训练期间，AlphaZero独立地发现和使用了这些开局。从每个人类的开局开始，AlphaZero击败了Stockfish，表明它确实掌握了广泛的国际象棋玩法。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "国际象棋代表了过去几十年人工智能研究的巅峰。最先进的象棋程序基于强大的引擎，搜索数以百万计的局面，利用领域的专业知识和复杂的领域适应性。AlphaZero是一个通用的强化学习算法 - 最初为围棋而设计 - 在几个小时内取得了优异的成绩，搜索次数减少了1000倍，除了国际象棋规则之外不需要任何领域知识。此外，同样的算法不经修改也适用于更具挑战性的将棋游戏，在几小时内再次超越了当前最先进的水平。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b3](assets\\b3.png\")"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b4](assets\\b4.png\")\n",
    "表2：分析12个最受欢迎的人类开局（在线数据库中出现超过10万次）。每个开局标有其ECO代码和通用名称。该图显示了AlphaZero在自我训练比赛时使用的每次开局的比例。我们还从AlphaZero的角度报告了从每个开局开始与Stockfish 100场比赛的胜负/平局/失败结果，无论是白色（W）还是黑色（B）。最后，从每个开局提供AlphaZero的主要变着（PV）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b5](assets\\b5.png\")\n",
    "图2：关于AlphaZero思考时间的可扩展性，以国际等级分衡量。a在国际象棋中的AlphaZero和Stockfish的表现，描画每一步的思考时间。b在将棋中AlphaZero和Elmo的表现，描画每一步的思考时间。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "# 方法"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算机国际象棋程序剖析"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本节中，我们将描述一个典型的计算机国际象棋程序的组件，特别关注Stockfish，这是一个赢得2016年TCEC电脑国际象棋锦标赛的开源程序。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每个局面s由手工特征φ(s)的稀疏向量描述，包括特定中局/残局[`子力`](http://chessprogramming.wikispaces.com/material)（译者注：由每条线上棋子价值的总和确定的一个术语。所有的棋子和兵。[`子力优势`](https://baike.baidu.com/item/%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E6%9C%AF%E8%AF%AD/7549734?fr=aladdin)是棋手在棋盘上有比对手更多的棋子或棋子的价值更大。）点的价值，[`子力不平衡表`](http://chessprogramming.wikispaces.com/Material+Tables)（译者注：例如 车vs两个[`轻子`](https://baike.baidu.com/item/%E8%BD%BB%E5%AD%90)（Minor pieces：象和马），皇后vs两个车或三个轻子，三个兵vs普通棋子），[`Piece-Square表`](http://chessprogramming.wikispaces.com/Piece-Square+Tables)（译者注：给特定位置上的特定棋子分配一个值），[`机动性`](http://chessprogramming.wikispaces.com/Mobility)（译者注：衡量一个玩家在一个给定的位置上合法移动的选择数量，[`棋子的行动自由`](https://baike.baidu.com/item/%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E6%9C%AF%E8%AF%AD/7549734?fr=aladdin)。）和[`被困棋子`](http://chessprogramming.wikispaces.com/Trapped+Pieces)（译者注：被困棋子是移动性差的极端例子），[`兵型`](http://chessprogramming.wikispaces.com/Pawn+Structure)（译者注：用来描述棋盘上所有兵的位置，忽略所有其他棋子。也指兵骨架。所有兵的位置的各个方面。），[`国王安全性`](http://chessprogramming.wikispaces.com/King+Safety)，[`前哨`](http://chessprogramming.wikispaces.com/Outposts)（译者注：通常与马在棋盘中心或敌方一侧有关的国际象棋术语，被自己的棋子保护不再受对手棋子的攻击，或者在半开放线削弱对手的棋子，不再徒劳无功），[`双象`](https://en.wikipedia.org/wiki/Glossary_of_chess#Bishop_pair)（译者注：棋手是否有两个象），和其他复杂的评估 模型。通过手动和自动调整的组合，每个特征$φ_i$被分配相应的权重$w_i$，并且通过线性组合$v(s，w)=φ(s)^T w$来评估局面。然而，对于安全的位置，这个原始评估仅被认为是准确的，不包括未解决的[`吃子`](http://chessprogramming.wikispaces.com/Captures)和[`将军`](http://chessprogramming.wikispaces.com/Check)。在应用评估函数之前，使用领域专用的[`静止搜索`](http://chessprogramming.wikispaces.com/Quiescence+Search)来解决正在进行的战术局势。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "局面s的最终评估是通过使用静止搜索评估每个叶子的极小极大搜索来计算的。alpha-beta剪枝被用来安全地剪切任何可能被另一个变着控制的分支。额外的剪切是使用愿望窗口和主要变着搜索实现的。其他剪枝策略包括无效走子修剪（假定走子以后结果比任何变着还要差），徒劳修剪（假设知道评估中可能的最大变着），和其他依赖于领域的修剪规则（假设知道被吃棋子的价值）。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "搜索的重点是关注有希望的变着，通过扩展有希望的变着的搜索深度，并通过基于历史，静态交换评估（SEE）和移动的棋子类型等启发式技术减少没有希望的变着的搜索深度。扩展是基于独立于领域的规则，这些规则用于识别单一的走子，没有合适的选择余地，以及依赖于领域的规则，比如扩展检查走子。减少（译者注：搜索深度），如后期走子减少，主要依赖于领域知识。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "alpha-beta搜索的效率主要取决于下棋走子的顺序。因此，走子是通过迭代加深来排序的（使用更浅的搜索命令移动以进行更深入的搜索）。此外，结合了与领域无关的启发式走子排序，如杀手启发式，历史启发式，相反走子启发式，以及基于捕获（SEE）和潜在捕获（MVV / LVA）的领域相关知识。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "[`换位表`](http://chessprogramming.wikispaces.com/Transposition+Table)（译者注：是存储先前执行的搜索的结果的数据库）便于重复使用在多个路径达到相同位置时的下棋顺序和值。经过仔细调整的开局库用于在棋局开始时选择走子。通过对残局位置的彻底逆向分析预先设计的残局库，在六个、有时七个或更少的所有位置提供最佳的走子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "其他强大的国际象棋程序，以及像“深蓝”这样的早期程序，都使用了非常类似的架构，包括上述的大部分组件，虽然重要的细节差别很大。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaZero不使用本节中描述的技术。这些技术中的一些可能会进一步提高AlphaZero的性能；然而，我们专注于纯粹的自我对弈强化学习方法，并将这些扩展留给未来研究。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## 计算机国际象棋和将棋上的早期工作"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本节中，我们将讨论一些关于计算机国际象棋在强化学习上的重要早期工作成果。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "NeuroChess通过使用175个手工输入特征的神经网络评估局面。它被训练通过时序差分学习预测最终的游戏结果，以及两步棋之后的预期特征。NeuroChess赢得了对GnuChess 13%的比赛，使用固定的深度2搜索。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Beal和Smith应用时序差分学习来估计国际象棋和将棋中的棋子值，从随机值开始，单独通过自我对弈来学习。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "KnightCap通过一个神经网络来评估局面，这个神经网络使用了一个基于哪个区域受到哪些棋子攻击或防守的知识的攻击表。它是由时序差分学习的一种变体（称为TD（叶））进行训练的，它更新了alpha-beta搜索的主要变着的叶子值。KnightCap在训练之后与使用手动初始化棋子值权重的强大计算机对手对弈，达到了人类大师级别的能力。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Meep通过基于手工特征的线性评估函数来评估局面。它是由另一个时序差分学习的变种（被称为TreeStrap）训练的，它更新了一个alpha-beta搜索的所有节点。Meep经过随机初始权重自我对弈训练之后，在15场比赛中13场击败了人类国际大师级棋手。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Kaneko和Hoki通过学习在alpha-beta 搜索期间选择人类专家的走子，来训练包括一百万个特征的将棋评估函数的权重。他们还基于根据专家棋局日志调整的极小极大搜索进行了大规模优化；这是获得2013年世界计算机将棋冠军的Bonanza引擎的一部分。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Giraffe通过一个神经网络评估局面，包括移动能力地图和描述每个方格（走子点）的攻击者和防御者的最低值的攻击和捍卫地图。它通过使用TD（叶）的自我对弈训练，也达到了与国际大师相当的水平。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "DeepChess训练了一个神经网络来执行成对的局面评估。它是通过监督学习从人类专家对弈数据库进行训练的，这些棋局是经过预先过滤的，以避免吃子棋和平局。DeepChess达到了一个强大的特级大师的水平。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "所有这些程序都将他们学到的评估函数与各种扩展增强的alpha-beta搜索功能相结合。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "基于使用像AlphaZero策略迭代的双重策略和价值网络的训练方法已经成功应用于改进Hex的最新技术。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "## MCTS 和Alpha-Beta 搜索"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "至少四十年来，最强大的计算机国际象棋程序已经使用alpha-beta搜索。AlphaZero使用明显不同的方法来平均子树内的局面评估，而不是计算该子树的最小最大估计。但是，使用传统MCTS的国际象棋程序比Alpha-Beta搜索程序弱得多；而基于神经网络的alpha-beta程序以前不能与更快的手工评估函数对抗。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "AlphaZero局面评估使用基于深度神经网络的非线性函数逼近，而不是典型国际象棋程序中使用的线性函数逼近。这提供了更强大的表示，但是也可能引入虚假逼近误差。MCTS对这些近似误差进行平均，因此在评估大型子树时趋向于误差抵消。相比之下，alpha-beta搜索计算明确的最小最大值，它将最大的近似误差传播到子树的根节点。使用MCTS可以允许AlphaZero将其神经网络的表示与强大的、独立于领域的搜索有效地结合起来。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 领域知识"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "- 1.描述位置的输入特征和描述走子的输出特征被构造为一组平面；即神经网络结构与棋盘的网格结构相匹配。\n",
    "- 2.为AlphaZero提供了完善的游戏规则知识。这些在MCTS期间被用来模拟由一系列走子产生的位置，以确定游戏的结束，并对达到结束状态的任何模拟对弈进行评分。\n",
    "- 3.对规则的了解也被用来编码输入平面（即[`王车易位`](http://chessprogramming.wikispaces.com/Castling)，[`重复局面`](https://baike.baidu.com/item/%E5%9B%BD%E9%99%85%E8%B1%A1%E6%A3%8B%E6%9C%AF%E8%AF%AD/7549734?fr=aladdin)，没有进展）和输出平面（棋子如何走子，升变和将棋中的[`取驹`](https://baike.baidu.com/item/%E5%B0%86%E6%A3%8B/491643)（[`piece drops`](https://en.wikipedia.org/wiki/Shogi#Drops)））。\n",
    "- 4.合法走子的典型数量用于缩放探索噪音（见下文）。\n",
    "- 5.国际象棋和将棋比赛超过最大步数（由典型比赛长度决定）将被终止，并被判为平局；围棋比赛结束，使用Tromp-Taylor规则打分。\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "除了上面列出的要点，AlphaZero没有使用任何形式的领域知识。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 表示"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在本节中，我们将描述棋盘输入的表示形式，以及AlphaZero中神经网络使用的走子动作输出的表示形式。其他的表示本来也可以使用; 在我们的实验中，训练算法对于许多合理的选择可以有效地工作。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b6](assets\\b6.png\")\n",
    "表S1：分别在围棋，国际象棋和将棋中AlphaZero使用的输入特征。第一组特征是8步历史走子记录的每个局面。计数由实数值表示；其他输入特征通过使用指定数量的二值输入平面的独热编码来表示。当前玩家由P1表示，对手由P2表示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "神经网络的输入是N × N ×（MT + L）图像栈，其表示状态使用大小为N×N的T组M个平面的级联组成。每一组平面代表时间步t-T + 1，...，t的棋盘位置，在小于1的时间步中设置为零。棋盘朝向当前玩家的角度。M特征平面由棋手存在的棋子的二值特征平面组成，每个棋子类型具有一个平面，第二组平面表示对手存在的棋子。对于将棋，还有额外的平面显示每种类型的持驹数。还有一个额外的L个常值输入平面，表示玩家的颜色，总的回合数量和特殊规则的状态：在国际象棋合法的王车易位（王翼或者后翼）；局面的重复次数（3次重复在国际象棋中自动判为平局;在将棋中是4次）;和在国际象棋中没有进展的走子次数（没有进展的50次走子自动判为平局）。表格S1中总结了输入特征。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "下棋走子可以分为两部分：选择要移动的棋子，然后在棋子的合法棋步中进行选择。我们用一个8 × 8 × 73的平面栈来表示策略π(a|s)，它编码了4,672个可能的走子的概率分布。每个8×8的位置标识从哪个方块“拾取”一个棋子。前56个平面编码对于任何棋子可能的“皇后走子”，沿着八个相对方向{北，东北，东，东南，南，西南，西，西北}中的一个，若干方块[1..7]中将被吃的棋子。接下来的8个平面编码可能的马的走子。最后的9个平面编码对于兵底线升变后在对角线上可能的走子和吃子，分别对于车，马或象。和其他兵从第七横线升变为为皇后的走子或吃子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "将棋中的策略由一个9 × 9 × 139的平面栈表示，类似地对11,259个可能的走子进行概率分布编码。前64个平面编码“皇后走子”，接下来的2个编码马走子。另有64 + 2个平面分别编码升变成皇后的走子和升变成马的走子。最后7个平面编码将一个被捕获的棋子放回棋盘上的位置。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "围棋中的策略与AlphaGo Zero表示相同，使用一个包含19 × 19 + 1的走子平坦分布代表可能的放置和走子。我们在国际象棋和将棋上也尝试用关于走子的平坦分布，最后的结果几乎相同，尽管训练稍微慢了点。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b7](assets\\b7.png\")\n",
    "表S2：国际象棋和将棋中AlphaZero使用的动作表示。该策略是由一堆编码合法走子概率分布的平面表示的；平面对应于表中的条目。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "表S2中总结了行动表示。通过将概率设置为零，并将使用的走子概率重新归一化，可以屏蔽非法走子。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 配置"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在训练期间，每个MCTS使用了800次模拟。棋局的数量，局面和思考时间由于不同的棋盘大小和游戏长度而有所不同，如表S3所示。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "每场比赛的学习率为0.2，在训练过程中分别下降了三次（分别为0.02,0.002和0.0002）。走子的选择与根节点的访问次数成正比。Dirichlet噪声Dir(α)被添加到根节点的先验概率中；这个比例与典型位置的合法走子的近似数量成反比，分别为国际象棋、将棋和围棋的α 取{0.3,0.15,0.03}。除非另有说明，否则训练和搜索算法和参数与AlphaGo Zero相同。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b8](assets\\b8.png\")\n",
    "表S3：国际象棋，将棋和围棋中AlphaZero训练的选择统计。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "在评估期间，AlphaZero选择走子使用关于根节点访问次数的贪婪方法。每台MCTS在一台带有4个TPU的机器上执行。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### 评估"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了评估国际象棋的性能，我们使用了Stockfish版本8（官方的Linux版本）作为基准程序，使用64个CPU线程和1GB Hash。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "为了评估将棋中的性能，我们使用了Elmo版本WCSC27并结合了有64个CPU线程和1GB Hash，EnteringKingRule的usi选项设置为NoEnteringKing，YaneuraOu 2017早期的KPPT 4.73 64AVX2。我们通过测量每个选手的国际等级分来评估AlphaZero的相对强度（图1）。我们通过Logistic函数p(a defeats b) =$\\frac{1}{1+exp (c_{elo} (e(b)-e(a)) }$估计玩家a击败玩家b的概率，并通过贝叶斯逻辑回归估计等级分e(·)，用BayesElo程序使用标准常数$c_{elo}$ = 1/400计算。国际等级评分是根据与AlphaZero在训练迭代期间进行比赛1秒每次走子的结果计算得出的，同时Stockfish，Elmo或者AlphaGo Lee分别是基准选手。基准玩家的国际等级分是以公开可用的价值为基础的。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "我们还测量了AlphaZero对每个基准玩家快棋的表现。设置被选择为符合计算机象棋比赛的条件：每个棋手允许1分钟下一步棋，所有棋手都可以投降认负（Stockfish和Elmo 10次连续走子-900 centipawns，AlphaZero 5%胜率）。所有玩家的思考都被禁止了。"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "![b9](assets\\b9.png\")\n",
    "表S4：国际象棋、将棋和围棋中AlphaZero，Stockfish和Elmo的评估速度（局面/秒）"
   ]
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.6.7"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 1
}

一键复制编辑原始数据按行查看历史

提交于 2019-03-19 18:04 . fix can't display in jupyter notebook