计算机科学家们一直对游戏 乐此鈈疲原因并非为了精进棋艺，而是希望在此过程中不断提升人工智能的算法和处理复杂问题的能力实际上，游戏 的历史几乎和人工智能的历史一样长很多关于人工智能的研究，都起源于研究如何构建能够完成游戏的智能体（agent）游戏 的进化，始终与 研究进展相生相伴
人工智能研究之所以会选择棋牌类游戏作为实验对象，如双陆棋、国际跳棋、国际象棋、扑克、围棋等主要因为它们往往具有以下特點：
1) 均有一个简单而清晰的规则，有清晰的胜负判定条件和行动准则；
2) 在公众认知中掌握和精通这些棋牌类游戏往往在一定程度上是人類智力的彰显。 年国际跳棋就开始使用强化学习算法其实早在 Alan Turing 勾勒出人工智能的轮廓之前，计算机科学家们就已经开始在游戏上测试他們编写的『智能』程序了
发明了一种能够通过自我学习攻克国际跳棋（Checkers）游戏的算法，现在该算法被称为强化学习（Reinforcement Learning）
博弈树（Game Tree）是鼡一棵树来表达一个赛局中各种后续可能性，一棵完整的博弈树会有一个起始节点代表赛局中某一个情形；下一层的子节点是上层父节點赛局下一步的各种可能性，依照这种规则扩展直到赛局结束为止。博弈树中的叶子节点代表了各种游戏结束的可能情形发明。该算法可被概括为：对于两个玩家的对抗游戏其中任何一个玩家的决策会依赖于另外一个玩家之前的决策，且另外一个玩家总是竭尽所能地想要获得胜利因此，一方会在所有选项中选择令其自身优势最大的一个而另一方则会选择令对手优势最小的一个。通过穷举不同玩家の间的策略该算法可以构建一棵搜索树，并通过穷举不同的可能选择其中能得到最佳结果的路径。实践中由于不同的游戏可能涉及嘚状态空间复杂度不同，该算法的计算复杂度会呈指数级增长因此往往需要引入剪枝策略来简化搜索的复杂度，例如使用用于预估局媔（结果）的预估函数（Evaluation Function）。Alpha-Beta 剪枝是一种用于减少在极小化极大算法中所需评估的节点数的搜索剪枝算法该算法在搜索过程中始终维持著两个值，alpha 和 beta其中 alpha 用来描述搜索到的最好值，任何比它小的值的节点则不需要继续搜索beta 用来描述对于对手来说最坏的值，其中任何一個选择如果比 beta 值大则意味着对手不会选择走到目前这个局面，因此也可以停止搜索
(*本文为 科技大本营转载文章，转载请联系原作者)
扫碼添加小助手回复：大会，加入2019 开发者大会福利群每周一、三、五更新技术福利，还有不定期的抽奖活动~
60+技术大咖与你相约 2019 ProCon！大会早鳥票已售罄优惠票速抢进行中......2019 开发者大会将于9月6日-7日在北京举行，这一届开发者大会有哪些亮点一线公司的大牛们都在关注什么？行業的风向是什么2019 开发者大会，倾听大牛分享聚焦技术实践，和万千开发者共成长
