从国际象棋到中国围棋，人类与“机器”已经较上了劲。 看过那么多场对战，你是不是也想上手体验一把？ 来来来，简单五步，手把手教你撸一个缩减版的国际象棋AI。...首先，我们来看一些基础概念： 移动生成 棋面评估 Minimax算法 alpha beta剪枝 在每个步骤中，我们将通过一个国际象棋程序技术来改进算法。我将演示每个步骤是如何影响算法的。...https://en.wikipedia.org/wiki/Minimax 在此之后，我们向父节点返回子节点的最小或者最大值，这取决于黑子移动还是白子移动。...，我们的算法已经开始理解国际象棋的一些基础策略。...在线体验地址https://jsfiddle.net/q76uzxwe/1/ 总结 该算法的优势在于它不会犯一些愚蠢的错误，但同时它缺乏战略性的理解。
---- theme: fancy 原文链接 Minimax Improvements -- 作者 Ofek Gila 在上一篇文章中，我们讨论了在 AI 游戏（主要是五子棋）中，应用 Minimax...在本文中，我们将对该算法进行些改造。虽然它并不适用所有的游戏，但是它可能适用于一般的零和游戏，比如国际象棋，四子棋，跳棋等等...请注意，这些改进中的大部分都是针对特定的游戏。...在五子棋中，当一个玩家有四子相连并且只有一个开端，那么另一个玩家就要强迫关闭此开端。 2. 争取胜利 这个很简单 -- 当能争取到胜利，那就下该步。...在你的 minimax 函数执行这些动作之一后，你都可以简单结束游戏并返回游戏结果。不需要在该分支进一步搜索，因为游戏已经结束了。 争取胜利总是优先于防守。...强大的五子棋程序使用 Threat-Space Search 结合极大极小值算法实现。强大的国际象棋使用 alpha-beta 剪枝算法结合上述两种类型算法实现。
例如：玩井字棋 Maxine和Minnie是真正的游戏爱好者。他们只是喜欢游戏。特别是两人完美的信息游戏，例如井字棋或国际象棋。有一天他们在玩井字棋。Maxine或者简称为MAX使用X.。...有时候，也会有不管选择哪一个结果都一样的选择。 Minimax算法 我们可以利用上述游戏价值的概念来理解Minimax算法。它在理论上保证了任何确定性的、双人的、完全信息的零和博弈的最佳游戏玩法。...如上所述，Minimax算法可用于在任何确定性的、双人的、完全信息的零和博弈中实现最佳游戏玩法。...这类游戏包括井字棋，四子连珠，国际象棋，围棋等等（猜拳不属于这类游戏，因为它涉及隐藏于其他玩家的信息; 大富翁或西洋双陆棋也不是确定性的）那么，但这个主题已经结束了吗？...上面提出的minimax算法需要最小的变化来获得深度受限的版本，在给定深度受限法的所有节点上返回启发式搜索：深度时指的是在应用启发式评估函数之前游戏树被展开的步数。 练习7：Max为何悲观？
1928 年，John Vonn Neuman 发表了 Minimax（极小化极大）算法，而在 1949 年，Claude Shannon 将该算法重新组织，并用于解决国际象棋问题。...极小化极大算法（Minimax）是由 Claude Shannon 定义的用于解决国际象棋的算法，该算法最早在 1927 年被 John Vonn Neuman 发明。...深思采用了特殊的硬件设计用于搜索加速，并在此基础上引入了单步延伸（singular extensions）算法，其核心思想是：如果在逐层进行策略搜索时，发现某一步的结果显著好于其他步，则会进一步加深这一步棋的搜索以确认其中没有陷阱...在与 Kasparov 的比赛中，深蓝受益于专门设计的大型机的强大运算能力，能够每秒钟运算 2 亿步棋，且可搜索及估计随后的 12 步棋（在单步延伸的情况下可搜索 40 步棋）。...围棋 AI 完成进化，初步实现历史使命 相比较而言，围棋的状态远复杂于上述棋类游戏（每一步棋可选范围为 19*19 种），而且下棋的策略十分依赖于对于牌局的评估，因此围棋一直被认为是比国际象棋等更难的棋类游戏
话说最近DeepMind又搞了不大不小的新闻，他们使用了完全类似 AlphaGo Zero 的同一套算法框架，在完全没有人类下棋数据的情况下，解决了诸多困难的棋类问题，包括国际象棋，将棋以及围棋；在国际象棋...，将棋方面轻松碾压当前最强的框架（国际象棋甚至连续100局不败，并且很明显体现了先后手造成的巨大差距）。...Minimax 算法 (来源：wikipedia) 第 4 层是结果。 然后我们使用回溯的思想，反向推导。假如到了第3层，这是对手走棋，对手会怎么走？对手一定会走使得最后结果最小的那步对吧？...我们可以进一步对比一下在国际象棋中 MCTS 算法和 Alpha-beta 算法的搜索的节点数： AlphaZero 使用上文介绍的 MCTS 每步搜索了 80000 个节点 Stockfish(目前最强开源国际象棋软件...这个先验分布告诉我们走每步棋的先验概率，而求解这个这个概率的函数被称为 ”策略函数“。 我们当然可以把每一步都试试，然后用估值函数估计每步走后的 Minimax 值，然后反推出每一步的先验概率。
规则包括远程互动（例如，女王可能在一步之内穿过棋盘，或者从棋盘的远侧将死国王）。国际象棋的行动空间包括棋盘上所有棋手的所有符合规则的目的地；将棋也可以将被吃掉的棋子放回棋盘上。...搜索返回一个向量π，表示移动的概率分布。...下国际象棋，AlphaZero仅用了4小时（300k步）就超越了Stockfish；下将棋，AlphaZero仅用了不到2小时（110k步）就超越了Elmo；下围棋，AlphaZero不到8小时（165k...图1：训练AlphaZero 70万步。Elo 等级分是根据不同玩家之间的比赛评估计算得出的，每一步棋有1秒的思考时间。a....他们还使用完全训练好的AlphaZero与Stockfish、Elmo和AlphaGo Zero（训练了3天）分别在国际象棋、将棋和围棋中对比，对局100回，每下一步的时长控制在1分钟。
最近学校的课程设计自己做了个五子棋的游戏，今天就聊一聊五子棋游戏中用到的极小极大算法(The Minimax Algorithm)。...我们众所周知的五子棋、象棋等都属于这类程序，所以说Minimax算法是基于搜索的博弈算法的基础。...Minimax也不例外，它通过对以当前格局为根的格局树搜索来确定下一步的选择。而一切格局树搜索算法的核心都是对每个格局价值的评价。...Minimax算法基于以下朴素思想确定格局价值： Minimax是一种悲观算法，即假设对手每一步都会将我方引入从当前看理论上价值最小的格局方向，即对手具有完美决策能力。...，如图 重复这个步骤，我们最终可以发现第一步的最优选择，如图 以上就是极小极大算法（Minimax）。
《科学》杂志评价称，能够解决多个复杂问题的单一算法，是创建通用机器学习系统，解决实际问题的重要一步。...这些算法都是由强大的人类棋手和程序员构建，基于手工制作的功能和精心调整的权重来评估位置，并且结合了高性能的alpha-beta搜索。 而提到游戏树的复杂性，日本将棋比国际象棋还难。...日本将棋程序，使用了类似国际象棋的算法，例如高度优化的alpha-beta搜索，以及许多有针对性的设置。 ? AlphaZero则完全不同，它依靠的是深度神经网络、通用强化学习算法和通用树搜索算法。...此外，围棋的落子规则相对简单、平移不变，而国际象棋和日本将棋的规则是不对称的，不同的棋子有不同的下法，例如士兵通常只能向前移动一步，而皇后可以四面八方无限制的移动。...训练好的神经网络，用来指引一个搜索算法，就是蒙特卡洛树搜索 (MCTS) ，为每一步棋选出最有利的落子位置。 每下一步之前，AlphaZero不是搜索所有可能的排布，只是搜索其中一小部分。
前言 上篇文章，介绍了一下五子棋 AI 的入门实现，学完之后能用，就是 AI 还太年轻，只能思考一步棋。 本文将介绍一种提高 AI 思考能力的算法：极大极小值算法。...Minimax算法 又名极小化极大算法，是一种找出失败的最大可能性中的最小值的算法（即最小化对手的最大得益）。通常以递归形式来实现。 Minimax算法常用于棋类等由两方较量的游戏和程序。...，这个数字是特别庞大的，数字10后边要加432个0！！！这程序运行起来，电脑还要不要了？ 所以，我们只考虑2步棋或4步棋的情况。 如图所示，我只列举出了走4步棋所形成的部分情况。...minimax(0, 2); return this.bestPoint; } 测试一下，因为现在的 AI 可以思考两步棋了，所以比之前厉害了许多。...现在写的搜索算法，如果要让 AI 思考4步棋的话，我这普通电脑还是吃不消的，后续对搜索算法还有更多的优化空间。 源码：github.com/anlingyi/xe…
在本论文中，DeepMind 实现了类似但完全泛化的算法（fully generic algorithm）——在未输入游戏规则以外任何知识的情况下，其推出的全新算法 AlphaZero 在国际象棋和日本将棋上实现了和围棋同样的高水平...这些规则包含了远程互动（例如，后可以一步穿越整个棋盘，从远距离对王将军）。国际象棋的动作空间包含两名棋手棋盘上棋子的所有合法落子位置；而日本将棋甚至还允许被吃掉的棋子重返棋盘（加入另一方）。...国际象棋和日本将棋都允许胜负之外的其他结果；事实上，人们相信国际象棋的最优解是平局。 AlphaZero 算法是 AlphaGo Zero 的通用化版本，后者首先被应用在了围棋任务上。...这些动作是由其它空间平面或平面向量进行编码，且仅仅基于每个游戏的基本规则。 我们把 AlphaZero 算法应用到了国际象棋、日本将棋和围棋上。...在国际象棋中，AlphaZero 仅仅经过 4 小时（30 万步）就超越了 Stockfish；在日本将棋中，AlphaZero 仅仅经过不到 2 小时（11 万步）就超过了 Elmo；而在围棋中，AlphaZero
David Sliver、哈萨比斯等人亲自撰文解读这一棋类终极算法，以及实现通用学习系统的重要一步。 史上最强棋类AI降临！...日本将棋程序也是特定于游戏的，使用与国际象棋程序类似的搜索引擎和算法。...羽生善治，日本将棋棋士，获得七项头衔的“永世称号”，亦是日本将棋史上第一个达成七冠王与“永世七冠”的人，改写了将棋界多项历史纪录 训练后的网络用于指导搜索算法（蒙特卡罗树搜索，MCTS），选择游戏中最有有利的动作...所有的比赛都有时间控制，每场比赛3小时，外加每一步额外的15秒。...“过去的传统国际象棋软件已经非常稳定，几乎不会出现明显错误，但在面对没有具体和可计算解决方案的时，其行棋会发生偏差，”他说：“正是在这种时候，才是AlphaZero发挥其'感觉'、'洞察'或'直觉'的地方
日本将棋程序也是将棋专用的，使用类似于国际象棋程序的搜索引擎和算法。...它的独特走法预示着，日本将棋还存在其它的可能性。 已训练的神经网络被用于指导搜索算法（即蒙特卡洛树搜索/MCTS），来选择棋局中最有潜力的走法。...在每一步中，相比传统棋类引擎，AlphaZero 仅搜索很少的走法。例如在国际象棋中，它仅每秒搜索 6 万种走法，而 Stockfish 每秒要搜索 6 千万种走法。 ?...第一代 TPU 的推理速度和英伟达 Titan V GPU 大致相同，但两者的架构无法直接比较。 所有的比赛都采用了限时规则，每场比赛 3 小时，每一步棋限时 15 秒。...他还观察到 AlphaZero 从第一步开始就以「人类的一贯宗旨」用非常审慎的风格下棋。 「传统程序非常强悍，很少犯明显的错误，但是当面对没有具体、可计算解的位置时会慌乱。
有人无聊的时候会找电脑下国际象棋，但也有人无聊了会教电脑下棋。 ? 国际象棋可以说是最棒的棋盘游戏之一，它是战略战术和纯技术的完美融合。...评价函数流程图 移动选择 算法的最后一步是用 Minimax 算法中的 Negamax 实现进行移动选择，Minimax 算法是双人游戏（如跳棋等）中的常用算法。...之后使用 Alpha-Beta 剪枝进行优化，这样可以减少执行的时间。 现在让我们深入研究一下 minimax 算法。该算法被广泛应用在棋类游戏中，用来找出失败的最大可能性中的最小值。...简单来说，在游戏的每一步，假设玩家 A 试图最大化获胜几率，而在下一步中，玩家 B 试图最小化玩家 A 获胜的几率。 为了更好地理解 minimax 算法，请看下图： ?...维基百科中 minimax 树举例 为了得到更好的结果，使用 minimax 变体 negamax，因为我们只需要一个最大化两位玩家效用的函数。
原文链接 Minimax for Gomoku (Connect Five) -- 作者 Ofek Gila 回顾 不知道你是否还记得上一篇文章，我们使用深度优先搜索算法来解决井字棋游戏，递归所有可能的分支...因为我们是自底向上搜索，我们能够判断每一步棋是赢、输或者平局，为每位玩家下出最佳的一步棋。...这给 minimax 带来了额外的复杂性，因为需要一个评估函数 Evaluation Function 来评估这个位置的好坏。...你可能需要根据自己编写的启发式评估函数的输出返回 0.8, -0.25 或者 0.001，而不是根据游戏输赢或者平局来返回 1，-1 或者 0。 我要表达的是什么？...用下面的井字棋游戏作为例子： 不管现在轮到谁，X 将会赢下该局。分析函数 analysis function 应该为 X 返回一个正值。但是，玩家的回合在分析功能中仍然起着很重要的角色。
日本将棋程序也是特定的，使用与国际象棋程序类似的搜索引擎和算法。 AlphaZero则采用了一种完全不同的方法，用深度神经网络和通用算法取代了这些人类制定的规则，这些算法除了基本规则之外一无所知。...网络需要的训练量取决于游戏的风格和复杂程度，国际象棋大约需要9个小时，日本将棋大约需要12个小时，Go需要13天。...传统程序很强，几乎不会出现明显错误，但在面对没有具体和可计算解决方案的位置时会出现问题，而正是在这样的位置，AlphaZero能实现感觉，洞察或直觉。...Changer》中进一步探讨。...AlphaZero能够掌握三种不同的复杂游戏，并可能完成所有完美信息游戏，这是克服这一问题的重要一步。它表明单个算法可以学习如何在一系列设置中发现新知识。
AlphaGo 证明了世人对于虚拟和现实世界的怀疑是错误的。...简要介绍极小极大（minimax）算法和 alpha-beta 修剪算法 2 蒙特卡洛树搜索——基本概念 2.1 模拟——AlphaGo 和 AlphaZero 2.2 博弈树的展开节点、完全展开节点和访问节点...有时这样的游戏也被称为严格竞争博弈 我们可以轻易验证围棋、国际象棋或井字棋是有限两人零和回合制游戏。...什么是最有潜力的下一步行动？简要介绍极小极大（minimax）策略和 alpha-beta 剪枝算法 再次提醒，我们的最终目标是在给定博弈状态的前提下，利用博弈树寻找最有潜力的下一步行动。...这正是基础的极小极大算法的执行过程。 极小极大算法的最大弱点是它需要展开整个博弈树。对于有高分支因子的博弈（例如围棋或国际象棋），该算法将导致巨大的博弈树，使得计算无法进行。 那么有什么解救的办法吗？
文章还结合作者本人的经历对围棋算法与中国象棋算法的差异进行了比较。 本文原标题：AlphaGo的棋局，与人工智能有关，与人生无关 前言：人生如棋 回顾一下我的人生，似乎和棋是有一些关联的。...我第一步一般走中炮，电脑第一步总是走马，而当第二步我上马的时候，电脑不是走常见的屏风马，而是起横车，另外一侧的马都不动。从棋理的角度说，这种布局是有问题的，中路很空虚。...从入门的角度说，象棋的估值函数相对简单，因此入门应该更容易一些。 MiniMax搜索/Alpha-Beta剪枝和象棋 这个算法最早是冯诺依曼提出来的。...(from https://en.wikipedia.org/wiki/Minimax) 上面的“算法”用上图来说明。圆形的节点表示“你”面对的局面，而方块的节点表示对手面对的局面。...从这个角度来说围棋要比国际象棋复杂。但如果只是这一个因素的差别不可能导致最好的国际象棋程序超过人类而围棋只有13k的水平。
跳棋游戏很简单，但IBM 704是个很简单的机器。它不能通过试错法得出所有可能的棋步，从而得出最佳的移动方式，至少无法在合理的时间内完成。除非采用暴力算法，当中需要大量的数字计算。...一旦跳棋算法发现能够吃掉对手棋子的棋步，然后就停止了，就按这个棋步走。这种简单的启发法足以攻克跳棋。 扑克牌丨Poker 接下来，AI面对的是扑克牌游戏。...这些早期的机器中，最成功的是"沉思"(Deep Thought)。每秒能计算70万个棋步。 1988年，Deep Thought试图击败一名国际象棋高手。...总而言之，围棋中的棋步组合比宇宙中原子数量还多。 其次，围棋中每个棋子都同等重要。 这与国际象棋不同，比如国际象棋中，后就比兵要重要。这种关系是可以通过编程让AI理解的，比如输入生产系统。...甚至高水平的棋手有时也很难解释，他们是如何判断每个棋步和好坏。 计算机不擅长的领域就是主观性，以及计算万亿次的位置。因此深蓝的暴力算法对于围棋是完全不可取的。
领取专属 10元无门槛券
手把手带您无忧上云
云服务器
即时通信 IM
ICP备案
对象存储
实时音视频
