[音乐播放] 演讲嘉宾：欢迎回来，大家好。 这是CS50。 而今天，我们有很多的 有趣的东西可谈。 不过，首先我要提醒 你的一些管理的事情。 本周是测验之一，星期三 或为耶鲁部 在周二和周四，周四。 有测验点评 今晚在耶鲁大学，下午5:30到7:00。 在哈佛，他们1昨天录制。 每个人都可以观看，网上。 此外，本周末或下周初， 我们有我们的最后CS50讲座。 [呻吟]我知道。 它来了这么快。 耶鲁大学的学生将有一个活 讲座在这里的法学院 观众席上周五。 会有蛋糕。 哈佛的学生将有 桑德斯在最后一节课上周一。 也会有蛋糕。 此外，本周上周五，对于那些 你们谁是来纽黑文， 我们有CS50世博会。 我们有超过30 不同的组注册 告诉你一切 从自主帆船， 该识别系统 数码人像，计算机 音乐和电脑制作音乐。 所以，请加入我们的行列。 我认为这将是一个伟大的时刻。 但是，今天我们去 继续谈论AI， 关于人工智能。 和的事情之一 我们要拿到今天 是如何的想法 使用人工智能来解决问题。 现在，一如既往，让我们开始 简单的东西。 我们要开始 一个简单的想法。 这就是使用搜索。 所以，想象一分钟，我 有我需要执行的任务。 我想有该任务 通过一些软件代理的自动化。 想象一下，我想订一套 从航班，让我们说，波士顿 到旧金山。 我可以通过我可以使用 精彩的在线搜索之一 工具，这是要干什么 基本相同的过程，我们是 要穿行今天。 但是，如果你没有这种 工具，你会怎么办？ 好了，你可以看看和 看，说，我在波士顿。 哪些航班可以给我吗？ 现在，也许我有三个 可能的航班从波士顿 将适合的时间 当我需要离开。 我能飞芝加哥。 或者，我可以飞到迈阿密。 或者，我可以飞到纽约。 然后，我可以看看每个 这些目的地城市之一 想想什么位置 我可能达到 从每次个别城市。 因此，也许从芝加哥，我可以得到 直飞旧金山。 这是非常好的。 或者，我可以得到一个飞往丹佛的航班。 现在，也许该航班到旧金山 是一个完美的解决方案，对我来说， 但也许不会。 也许我寻找的东西 这是一个有点便宜 或者我的日程表更好一点。 因此，我可以寻找其他什么 可能性可能是在那里。 所以，我可以看看丹佛。 而从丹佛，好吧，也许 我可以得到一个飞行奥斯汀。 而从奥斯汀，也许我可以得到一个 飞往凤凰城，从凤凰城 到旧金山。 现在，我还没有完成。 因为也许有一个 从纽约直达航班 到旧金山，非常适合我。 或者，也许有来自迈阿密的航班 通过丹佛，这是一个便宜很多。 所以，我还是得去。 我仍然要看看所有这些 我还没有进行调查的城市。 我要彻底检查所有的 我可能有机会。 因此，从纽约，也许我可以得到一个 飞往纳什维尔，并从纳什维尔 奥斯汀。 然后，我知道我在哪里。 然后我知道，从奥斯汀，我可以 飞往凤凰城，从凤凰城 到旧金山。 如果我先飞到迈阿密，不过， 也许我可以从迈阿密的航班 纳什维尔，或从迈阿密到奥斯汀。 现在我已经尝试了所有 的可能性。 我已经建立了这个图， 我显示了所有可能的途径 我也许可以采取。 当我们表示这些 那样的问题， 我们不会代表 他们明确地为这个图， 因为该图没有表示 在这里，我们已经走了的历史。 知道我的飞 凤凰城到旧金山 不告诉我，我是否通过来 纳什维尔，或通过丹佛，或通过迈阿密。 因此，我会做的是 我要这个同样的问题， 我将它表示为一棵树。 并在树的根，在 顶，我会把我开始的地方， 波士顿。 并在波士顿，我将看看 所有的可能位置 我可以前往。 那么，在这种情况下，我有三个， 芝加哥，纽约和迈阿密。 然后，我将探讨各 这些孩子在树上。 从芝加哥，我看到了 我有两个航班。 我可以直接飞到 旧金山或丹佛。 现在旧金山，这就是我的目标。 这是我的目标。 这将是这棵树的叶子。 也就是说，我永远不会去 旧金山后的地方。 从丹佛，不过， 我可以从丹佛飞 奥斯汀，奥斯汀凤凰， 从凤凰城到旧金山。 而现在再说一次，我已经到了一个叶。 我可以再回到下一个 城市，我还没有充分开发。 这将是纽约，去 备份到我的树的顶端， 下来到纽约。 从纽约，我可以飞 纳什维尔，从纳什维尔到奥斯汀， 从奥斯汀到凤凰，和 从凤凰城到旧金山。 最后，一​​个城市我 还没有看呢，迈阿密。 那么，从迈阿密我说我有两个 可能性，纳什维尔和奥斯汀。 如果我飞到纳什维尔，那么好吧我飞 从纳什维尔，奥斯汀，凤凰， 到旧金山。 如果我飞到奥斯汀，我飞奥斯汀， 凤凰城，旧金山。 现在我有一棵树。 这是一个完整的树。 这是所有的可能性， 所有我可以采取的路径。 也就是说，如果我开始在 树的顶部根 我再往之一 叶，它告诉我，不仅 在这里我要 最终，旧金山， 但它告诉我的路线 我需要到那里。 现在，这些哪一个是最好的？ 好了，一无所知 问题还没有告诉我 其中哪些是最好的解决方案。 也许我关心最关心 我有多少时间是在空气中， 或距离是我飞。 在这种情况下，芝加哥圣 旧金山可能是最短的数 在航空里程。 也许我在乎成本。 我们都知道直达航班 通常更昂贵。 所以，如果我拿这个，也许 一种倒退路线 通过迈阿密，纳什维尔， 奥斯汀，凤凰，也许那时 我得到一个较低的价格。 但我可以优化任何 我关心的标准。 谁拥有最好的 飞机上的Wi-Fi无线，或 机场拥有最好的食物。 而且每个可能 给我一个不同的解决方案 我看到的是最好的。 这些种类的问题， 我们要去哪里 打造出了这棵树 可能性，然后 看看每那些 各个路径，并检查 其中那些满足了 一个标准对我们来说， 我们将调用 这些搜索问题。 我们有很多的 算法，其中一些 我们已经看到，去 探索那些树。 我们能做到这一点的方式，我 只是做了一个深度优先搜索， 下降尽可能我们可以直到我们 打叶，然后再回来了， 而要正确回落。 或者，我们可以做什么 所谓广度优先搜索。 我们可以扩大一切 在顶部，然后 一切一行 下方的是，然后 一切下方的一行。 这些搜索树 是十分重要的AI。 但他们并没有完全得到 它的权利所有的时间。 事实上，在很多情况下 我们真正关心的， 我们要建立一棵树， 但我们实际上并不 去决定一切的。 这些都是所谓的情况下， 对抗性搜索，也被称为 如何写玩游戏 系统和得到报酬。 但这些都是种 系统在哪里 可能会选择当我去从 波士顿，我去旁边哪个城市。 但在那之后，别人可能会 使在哪里我飞行的决定。 因此，要建立这些 种结构，我们 将不得不采取一种 不同的方法吧。 我们不打算要能够 只是通过搜索树 了，因为我们没有 一个是在控制 其中每个决策点的。 因此，让我们想象一下一个简单的 游戏像井字棋。 我可以从一个 完全空白板。 而在井字棋， x被打首发。 所以，我能想到的一切 可能的行动是X可以使。 如果我是一个打 在X，这是伟大的。 我有九个可能 移动，我可以做到的。 我可以把一个X中的任何一个 这些九个位置。 然后从每次的，我 可以想像接下来会发生什么。 那么，在这种情况下，其他 玩家将获得转一转。 Ø将获得转一转。 和从每次的，有 将八个不同的地方 其中O可能将他们的标志。 比方说，我决定，我是 打算把一个X在中心。 这似乎总是喜欢 良好的开放性举措。 我可以看看下面的是， 八种可能的举动，Ö使。 现在，如果我打X，这是美妙的。 我可以选择哪一个我 去，一个在中间。 但是，现在O与其选择。 而且我没有控制 在这一决定。 但是从每次的 可能的仓板， 还有接着又 设置的可能性。 当说到做到 我重新开机，我就 来挑，说，好， 如果可移动到了，好了， 中间点在左边，然后 我有一组的可能性 在那里我可以把我的下一步行动。 从这些，我可以考虑全部 他们下方的可能性。 然后与O将得到 在那些选择。 而且我可以继续建设这个 树，直到我到了点 在这里无论是有人 赢得game--那 得到了被认为是一个叶node-- 或董事会完全充满 也没有人赢了。 而这也将是一个叶节点。 这将是一个平局。 但棘手的事情与这 如果这只是一个常规的搜索 的问题，我能 比方说，好了，X应该去这里。 可是啊应该走的路那边。 然后X应该走在这里。 然后与O应该走的路那边。 然后X可以得到三个 在一排，我赢了。 而本场比赛将超过 在五个动作，三对我来说， 二为我的对手。 但我并不总是得到选择。 因此，不是，我们是 不得不做 是我们将有 有一个新的战略。 而战略 玩游戏的算法经常使用 是所谓极小。 的中心思想 极小的是，我们 会挑，让移动 我们的对手可能出现的最坏集 的动作，他们可以做到的。 它没有我好 选择一个移动的地方 我也许能取胜后 即，因为我的对手不是 要给我这样的机会。 他们会选择一些 可怕的结局对我来说。 所以我打算让 移动，迫使我的对手 做一些事情对我来说更好。 好吧。 让我们来看看这发挥出来。 因此，这里是我们的伪代码算法。 我们将产生 整个游戏树。 我们要打造 整个结构。 然后我们会去。 和在最底层，在每个 终端节点，在各叶片的， 我们将评估如何 可贵的是，在我身上？ 而我们要的价值的东西， 是为我好为阳性。 事情是不是为我好 将不太积极的，或零， 甚至为负。 因此，井字棋，也许 一场胜利对我来说是很好的。 这是一个。 而领带是零。 而东西是一个损失 我，也许这是一个消极的。 所有的事情是更好的 这对我来说，得分越高 它接收。 从这些可能性在 底部，然后我们会筛选向上。 而当这是我选择的机会 在一组备选的， 我会选择一个的 拿到了最高分。 每当这是我的 反对者转而选择， 我认为他们将 选择一个得分最低。 如果我做这一切的方式 到树的顶部， 我已经选择了一条路，让 我说，我能得到最好的结果， 假设我的对手 使所有正确的行动。 好吧，让我们看看 这个动作的第一。 然后我们将实际 看看它的代码。 所以，想象一下我这棵大树。 现在我不玩井字棋。 我想给你 东西一点点更丰富。 所以，我有一些游戏， 有许多不同的分数 我可以有结尾。 所以我建立这个完整的树。 而且我可以先移动。 我在树的根。 我能选择that--所以我得到 跨越该第一节点最大化。 然后我的对手随便去哪儿。 然后，我现在能去一次。 这样下来在底部，我有一组 可能性，我可以选择， 游戏中不同的终端状态。 如果我在那很沮丧 最左边的角落， 我看到，我有一个选择 八，七，和一个两者之间， 好了，我是一个得到选择。 所以我要选择 这其中的佼佼者。 我要选择的八个。 所以，我知道，如果我 下来到这一点， 我就可以拿到8分。 如果我最终的下一个点 并且，在接下来的节点， 九，一，或六，好了，我 要选择最好的那些。 我会选择九。 如果我有之间的选择 2，和四，和一， 我会选择四，最高的。 现在，如果我看水平 上面说，我的对手 是一个得到做出这样的选择。 所以，我的对手到达 选择，我想给他 的事情是怎么回事 让他八点， 还是我给他的东西，是 打算给​​他9分， 或东西是怎么回事 给他四点？ 而我的对手，是 理性的，是怎么回事 要选择那些最小的， 是要选择四个。 我能做到这一点 整个树。 我可以去到 中间套三。 我可以进行选择 一，三，五。 我能选择。 所以，我选择了五。 我可以选择三种，九两。 我能选择，所以我选择的九个。 六，五或二，我选择。 我能选择的六个。 在该水平之上，谁可以选择呢？ 谁可以选择呢？ 另外一个人，我的对手。 因此，他们选择5个， 九，六，哪一个？ 听众：五。 演讲嘉宾：他们选择的五个。 他们能选择的最低。 然后最后一个， 选择一个，两个或三个。 我能选择，所以我选择三种。 九，七，或两个，我选择九岁。 而11，六，或四个，我选择11。 我的对手则选择三， 9，或11，选择最小。 他给了我三个。 然后最后在顶部 树，我可以重新选择。 而我得到之间做出选择 四，五，或三。 所以，我把五。 如果我控制一切，我会 采取了导致11的路径。 但我不明白做出这样的选择。 如果我走这条路。 我的对手会强迫我进入 这导致了三个选择。 所以，我能做的最好的是 采取这一中间分支， 做出这样的选择这是最终 要带领我到五点。 这就是极小呢。 好吧。 让我们来看看这个。 因此，这里的CS50 IDE是一个程序， 实现极小玩井字棋。 我们要打造 向上的表示。 我们将有两个opponent-- 或者两个球员，我们的电脑 播放器和一个人的球员。 玩家头号将被打 在O.那将是机器的球员。 他们得到第二招。 而其他的球员，我们的 人类的球员，将是X. 而为了让我的生活 一点简单的，我要去 标记该玩家负值。 所以我只能乘 由负一换 之间的一个播放器和其他。 好吧，让我们来看看 我们实际上是要干什么。 我们要确定我们的董事会。 这将是，嗯，我们要去 以允许它有三个由三个， 或者，我们甚至可以玩 五经五天或七天 七井字棋，如果你想 像的基础上，一些尺寸D. 并且我们将有一对夫妇 辅助函数 那会做这样的事情 初始化screen--还是遗憾， 初始化我们的变量，清除 屏幕上，绘制电路板在屏幕上， 一个检查板 看是否 有一个赢家，一个 解析通过命令行， 只是助阵，一个读取 输入，以及一个函数调用极小。 这就是一个 我们最关心的。 但是，让我们先来看看主。 我们做什么？ 好了，我们要 分析我们的命令行， 只是读，看看 维板，我们希望有。 我们将初始化我们的董事会。 然后，我们会输入一个 野生大循环，反复 接受移动直到游戏 赢了，或者有没有向左移动。 每次我们去通过 循环中，我们将清除屏幕。 我们要开董事会在屏幕上。 我们是那种故意 这些抽象走为子程序， 所以，我们不必过于担心 他们是如何发生的细节。 你必须在代码后的今天。 如果你想看看通过 并找出，你可以看到他们所有。 但是，我们会得出一个板在屏幕上。 然后我们会检查并 看，我们有一个赢家？ 曾有人赢了这场比赛？ 如果他们有，我们将打印 出了胜利的消息。 并且我们将结束游戏。 我们还将检查和 看看有没有打领带。 这将是很容易，看看是否有一个平手。 这意味着，所有的位已满， 但还没有分出胜负呢。 我们可以声明领带和完成。 那么真正的meat--如果 它是一台机器的球员， 我们将允许 机播放器搜索 通过使用这种极大极小​​算法， 找到最好的招之能。 然后我们会把这个拉升。 否则，如果它是一个人的球员， 我们将阅读从人的一些输入。 然后，无论是人 玩家或机器播放器， 我们很少做一对夫妇 错误检查位， 以确保它保持的范围内 董事会的实际尺寸 我们有，要确保 这空间是空的， 没有人的放 片中出现了。 然后，我们就放 一块电路板上， 改变播放器到下一个层，和 增加了多少动作发生。 这对于主循环 我们井字棋游戏。 极小的话，是完全 该算法之前我们。 唯一的调整是 我们已经取得了让我们 可以播放高 维板是我们 保持这种所谓的深度额外的参数。 和深度只是说，如果我 通过树向下搜索 而我得到这么远了 超出一定水平的深度 我只是不希望 再往前走， 我会停下来，只是 评估委员会在这一点上。 我会检查，看看是否有一个赢家。 如果有一个赢家，我回报他们。 否则，我将经历一个循环。 我会说，所有的 可能位置 那我可能 拿我的举动，我会 建立一个假想的板， 包括我的举动上板， 然后递归调用极小。 如果这是我的举动，我可以找到 一个有足够快的最大比分。 如果是我的对手的举动，我们发现 那一定的最低分数的人。 和其他一切是 只是记录保存。 好吧，让我们看看这个运行。 其实，也许我们可以 找几个志愿者 拿出玩井字棋。 [听不清]之一，和一个 多，二，就在那里。 上来吧。 因此，让我们继续前进， 完全重新启动此。 所以，喜。 听众：你好。 演讲嘉宾：你叫什么名字？ 听众：Gorav。 演讲嘉宾：Gorav。 听众：我是莱拉。 演讲嘉宾：而且莱拉，和莱拉，对不起。 上来吧。 Gorav，我们将让你先走。 而我要问你是不是 非常良好的井字棋的球员。 好了，所有的压力是关闭你。 让我们来看看，虽然，我们的机器 玩家其实可以做一些聪明。 因此，继续前进。 你会在哪个坐标输入 你想将你的X研究。 A0，OK，机器已经 马上，把它的标记在A1中。 把O于董事会。 好了，现在继续。 您要在何处去？ C2。 我们的机器播放器已 广场中间，挡住你。 所以这是一个很好的， 聪明的为它做。 你阻止它。 这是非常好的。 它开出角球那里。 而且它会迫使你 取最后一个空间，B0。 而本场比赛以平局结束。 但它起到了合理的 游戏对你，对不对？ 好，非常感谢，Gorav。 [掌声] 好吧，莱拉，我们要去 她对你的游戏在这里。 听众：哦，太棒了。 演讲嘉宾：我们打算给 你四乘四井字棋。 现在，在四乘四，你必须要赢 四成一排，没有三连胜。 而这一切都属于你。 所以蕾拉了D1。 我们现在要遵循 我们在这里的电脑玩家。 三三井字棋是那种 东西，很容易对我们所有人。 但它仍然很好看 电脑玩家作出明智的举动。 四乘四到达 是有点棘手。 做得好。 好吧，让蕾拉的结束了。 哦，我们应该已经结束了在那里。 但是，让我们做一起来这里。 所以蕾拉，谢谢。 做得好。 [掌声] 因此，我们井字棋玩家进入 通过和发现的地点， 解决了他们使用这种极小。 而且我有一个深度设置 上，以便它 不会跑的太快， 这可能是为什么 蕾拉能够很好地向前走 她做到了，做得很好。 但是，这些系统只 经过和蛮力 走得更深，更深，更深， 并不断寻找解决方案 他们需要，那些类型的系统 在这些相当成功的，好了， 标准的棋盘游戏。 而事实上，如果我们看一下 三乘三井字棋游戏， 这基本上是一个解决的问题。 这是一个美妙的图 从兰德尔·门罗在XKCD， 显示哪些打动你应该 走，给你的对手的动作。 这是我们可以 随便指定时间提前。 但是，当我们得到更多的会发生什么 复杂的游戏，更复杂的游戏， 那里有更大的板，更 的可能性，更深层次的战略是什么？ 事实证明，这 强力搜索仍 确实相当不错，除了 当你到了点 其中，该树是如此之大 你不能代表一切。 当你无法计算整个树， 当你无法前进，并推 你自己，你已经点 得到整个树在内存中， 或者是否可以得到它 在内存中，它只是 带你太长时间进行搜索 它，你必须做一些更聪明。 为了做到这一点，你 必须做两件事情。 首先，你必须要找到一些 限制你的深度的方法。 嗯，这是确定。 我们可以找到一些不错的，最低限度 并说，你只能走这么深。 但是，当你这样做，这意味着你 有这些部分不完整的板。 而你要选择，我喜欢 这部分不完整的主板， 或者这部分不完整的主板？ 而在我们的四经 4井字棋游戏， 我们的电脑玩家得到了下来 的底部，它说， 我有两个不同的电路板。 没有一个是一个双赢。 没有一个是亏损的。 没有一个是一个平局。 如何选择它们之间？ 和它没有一个 这样做的聪明的办法。 我们看到这种 评估发生的事情 随着我们进入更复杂的游戏。 国际象棋是一个很好的例子。 在国际象棋中，我们有，第一 所有的人，一个较大的电路板。 我们有更多的作品。 与这些片的定位 和方式，这些棋子 是非常重要的。 所以，如果我想用极小， 我需要能够指定 并说，此板，其中， 没有人赢了还是输呢， 在某种程度上这比其他更好的 板，在那里没有人赢了还是输。 为了做到这一点，我可能会做 像我可能只是 算我多少块确实有 多少个，你呢？ 或者，我可以给不同 件的不同点。 我的皇后是20分。 你的棋子是一分不值。 谁拥有更多的积分总？ 或者，我可能会考虑一些事情，如， 谁拥有更好的板位置？ 轮到谁下一个， 什么我可以 做评估更准确​​地 其中这些可能性 是没有好 详尽考虑 一举一动都可能到来之后。 现在，使这项工作， 的事情的One 将成为非常重要的 对我们来说不只是直线运动 下降到特定深度 限制，但不能说， 这些想法一说我 已经是如此糟糕，它的 不值得考虑 所有的可能的方法 事情可以去每况愈下。 为了做到这一点，我们将添加到极小 一个原则叫做ALPH-β。 而α-β表示， 如果你有一个糟糕的主意， 不要浪费你的时间尝试 找出它究竟是如何糟糕。 因此，这里就是我们要做的。 我们将采取同样的 我们收到的原则， 同样极小极大类型 搜索，只是我们 要跟踪，不仅是 我们有实际价值，但我们会 跟踪的最佳可能 值，我能得到， 和最坏的可能 结果，我可以有。 而任何时候，最坏的可能 事情正在寻找可能的是， 我会抛弃树的一部分。 我不会甚至不屑 看它了。 好了，所以可想而知，我们开始 与此完全相同的博弈树。 而现在我们将去 再次回落，一路下行 到左下角。 而在这左下角，我们 看看我们评估这款主板。 也许这是一个四乘四井字棋 板，或者这是一个国际象棋棋盘。 但是，大家看看吧，我们评估 它，我们得到八的价值。 在这一点上，我们知道 我们将得到至少 八点从这个底部决定。 不要紧什么其他 两个是，这七有两个。 它们可以是任何的值 他们想要的。 我们要得到的 至少8分。 好吧，但是我们可以 继续检查。 也许其中之一是超过八个更好。 我们来看一下七个。 那是超过八个好？ 没有，这并不改变 我们的意见都没有。 我们看看两个。 那是超过八个好？ 没有，这并不改变 我们的意见都没有。 所以，现在我们知道我们已经用尽 所有存在的可能性。 我们不会得到 任何超过八个好。 我们将得到完全八强。 因此，我们改变节点 说了，就是现在是必然的。 我们去了一个级别上面。 现在我们知道的东西 有关最小化水平。 我们知道，我们永远不会得到 八个多百分点，如果我们再往 这个方向努力。 因为即使这些 其他两个部门转出 是梦幻般的，值得 成千上万的每一个点， 我们的对手会给我们 最低限度，并给我们八。 好吧，好吧，让我们来看看。 我们会继续走下去的道路。 我们再往左边的中间。 我们往下看，我们看到有一个九岁​​。 我们知道，我们将得到 至少有九个点按下去 这中间的道路。 而在这一点上，我们就可以暂停。 我们可以说，看，我 知道在水平以上， 我会得到不超过八个 通过走这方向点。 但是，如果我去拦腰 路径，而不是离开路径， 我会得到至少9分。 我的对手永远不会 让我走这中间道路。 他们开始选择。 而且他们会选择 路径向左朝8， 而不是下来，对中间 什么是至少9分。 所以在这一点上，我会停下来。 我会说，你知道吗？ 我没有看任何 比较下来这个方向努力。 因为我永远不会去那里。 我可以跳过那一个， 我可以跳过那六， 因为这是永远也不会发生。 所以，我会去，我会 考虑下一可能性。 我去那里，我说，我看到了两种。 我知道，如果我到了这里，我 将得到的至少两个。 好。 我继续下去。 我看到一个四。 我知道我会得到至少有四个。 仍然有很多的 四个和八个，虽然。 所以，我继续下去。 我低下头，我看到有一个。 好吧，我知道，如果 我走上这条道路， 我将能够选择的四个。 什么是我的对手会怎么做？ 东西之间给了我 八，东西给我四， 和东西 让我至少九个， 好了，他要给我四。 我现在知道了 最顶端，我要去 要能得到至少 四点了这个游戏。 α-β的整体思路 是切断部分树， 我不看他们了。 但它仍然看起来像我一直 看着很多树。 让我们继续下去。 现在，我们将下井下一个。 唐氏在底部，我找一个。 我知道我会得到至少一个。 我继续寻找。 我找了三人。 我知道我会得到至少有三个。 我继续下去。 我找了五位。 我知道我要送五 如果我在这条道路下不来。 而且我也知道再 我的对手，如果我 选择中间 三大选择， 他要给我 东西是五个或更少。 好。 我可以继续去那里。 我往下看，我 可以说，我该怎么 拿到如果我往下走中间路线？ 我要得到的，还有三个在那里。 我要得到的东西 这是至少三个。 目前仍然之间的事情 三和五，所以我一直在寻找。 哦，九，我肯定会 采取了三个。 我要拿到至少有九个 如果我走这中间道路。 现在，我的对手将停止，并说， 你看，有没有一点了。 我知道我的 最小的对手，他的 要给我的东西，是 小于或等于五， 而非件事是 大于或等于9。 我停下。 我不看任何更多的那个。 我继续下去。 我小看这一个。 下到谷底，我发现一个六人。 我知道我会得到至少六个。 而我能做些什么？ 我可以停止。 因为有之间的选择 东西是至少六个 而东西是 不到五年，他的 要给我的事 这是不到五年。 现在我知道我要去 要得到完全的选择。 我要拿到五次选择。 我回去到顶部。 我要去哪家 东西之间进行选择 这是大于或等于4， 或东西是等于五？ 我要带的东西 这至少五个。 我往下走过去的路，所有的 下到谷底的方式。 有一个。 好吧，至少我要拿到一分。 我继续下去。 二，哦，这是比一个好。 我要拿到至少两个。 我找了三人。 我知道我会得到三个。 和上面的一点， 我的对手是怎么回事 给我的东西的 小于或等于3。 现在我可以停止。 因为在我的选择是 能够得到一个五我的对手 给我的东西不到三年， 我总是会拿这五。 所以，我不评价说 树的底部都没有。 现在，这似乎很小。 但是，当算术一点位， 大于和小于 可以切掉整个地区 这种指数级增长的树， 这导致了巨大的 储蓄，储蓄量 这是足够大的，我 可以开始玩竞争力 在更复杂的游戏。 好吧，如果我们看一下尺寸 和不同的游戏的复杂性， 井字棋是我们简单的例子。 我们三个了小板，三。 我们得到的，最多，平均为 四种不同的选择 因为我们去通过游戏。 我们有地方约10至 第五个可能的不同叶子。 而建设一个井字棋 播放器，好了，我们只是做了它。 小菜一碟。 如果我们去到更多的东西 复杂，如连四。 你还记得这个游戏， 你把小的令牌？ 这是一个六七板， 不是更大，仍 有大约相同的分支 因素，因为井字棋。 我有四个选择 在那里我可以把事情研究。 但现在，我已经得到了很多 引出，10到21的功率。 在这个时候，很容易 以至于我们解决这个问题的时候了。 跳棋，更complex--您 八牌上看到一个八。 你只能在半 他们在任何时候，虽然。 你已经有了一个分支 因素是关于2.8。 好了，我们已经有一对夫妇 移动可以采取。 你得约10至31叶， 大，大，和更大的空间。 当我不得不通过搜索 那些越做越大的空间， 这时候，像α-β和 能够切掉整个分支 就显得至关重要。 现在，跳棋在1992年很容易。 一种称为计算机程序 奇努克击败世界跳棋 冠军马里昂·汀斯利。 从那以后，没有 人类高手玩家 之所以能够击败最好的 计算系统。 如果我们考察一下国际象棋，现在 再次，我们八板有八个。 但我们有更复杂 件，更复杂的动作。 我们有大约一个分支因子 35，35，平均可能的行动 我可以和状态 空间，若干叶 是的成长到10到123电源， 数量巨大的可能性。 即使如此，现代的处理器 能够成功地做到这一点。 1995年，然后在1997年，一台电脑 程序调用深蓝由IBM建造 可以运行在一个巨大的超级计算机 击败目前的世界冠军， 卡斯帕罗夫。 这是一个转折点。 今天，虽然，相同的处理 电力坐在我的MacBook。 处理速度保持 越走越快。 我们可以评估越来越多 板越来越快。 但更重要的是，我们有更好的 评价功能，更好地修剪 的方法。 所以，我们可以搜索 空间更加复杂地。 该板的最大 游戏，我们能想到的， 像围棋这 有一个19 19板， 现在突然，我们过去点 其中，计算系统可以赢得。 有没有计算 系统在那里 可以击败一个专业棋手。 关于最好的系统今天排名 排序好的业余水平。 所以还是有相当多的出 那里，你不能去还。 好吧，这些 传统的棋牌游戏， 这些类型的系统，其中，我们 建立这个极小，不管它有 α-β与否，这些算法的工作 因为有一定的限制。 我们有完善的信息 关于世界。 我们知道，所有的作品都是。 世界是静态的。 没有人获得移动 左右，而我是个 坐在那里想，采取轮到我了。 有一个动作空间的离散。 我可以把我的棋子在这里， 或者，我可以把我的棋子在这里。 我不能把我的棋子上 该行两个广场之间。 最后，操作 是确定性的。 我知道，如果我说， 车骑士三， 我的车是要结束了在骑士 三，只要它是一个有效举措。 有没有这方面的不确定性。 现在，当我去更多 不同类型的游戏， 我们必须打破这些假设。 如果我去的东西是什么 喜欢经典视频游戏？ 这里有一个选择的视频 游戏从雅达利2600。 我有什么了吗？ 我有青蛙，空间 入侵者，陷阱和Pac-Man的。 什么样的环境 我必须在这里吗？ 其中这些假设 我必须打破？ 嗯，这取决于游戏。 我会下棋的2600，和 它会成为像从前那样。 对于大多数这些系统的，有 关于世界的完整的知识。 有完全 确定性的行为。 但通常情况下，世界 不再是静态的。 也就是说，当我坐在那里 在等待的东西在移动。 鬼都来接我。 蝎子是继我的下方。 太空侵略者 越来越近。 我们如何能做到针对这些？ 几年前，谷歌 曾要求项目 DeepMind，他们培养了计算机 节目玩雅达利2600游戏。 如果你认为这是不严重 企业，他们的研究结果 发表在Nature，所以 只是好出版物 因为你所能得到的。 下面是他们如何执行。 他们有一个算法，坐 看着刚刚屏输入。 它任何没有得到指令 关于游戏的规则。 它本来是要弄清楚， 根据其成绩，以及它如何在做什么。 这是用什么系统 所谓强化学习。 也就是说，它看着它的得分。 如果它得到了一个不错的成绩，它说， 我应该记住这些事情。 我应该再做这些。 如果它有一个不好的分数，它说， 我不应该再这样做这些事情。 这是性能 这些训练有素的系统 允许一玩 几个小时的每场比赛， 相比较专业的玩家。 因此，对于所有的游戏的 这条线的左侧， 这个自学成才的电脑程序 跑赢了职业玩家。 而对于一切的 正确的职业玩家 仍然是最好的。 对于一些知道 一无所知的规则， 一无所知的结构 游戏，这是令人印象深刻的表现。 而这正是我们今天能够做到。 OK，你说的，但如果我们 想想AI在游戏中， 通常我们想到的 事情，我们实际上可以 坐下来对战。 如果我坐下来和我玩 星际争霸，还是我玩免费筛， 计算机对手是 人控制的虫族， 或控制其他文明。 如何做到这些的球员 很难找到他们的举动？ 那么，这些游戏的结构 大致相同的方式作为我们的下棋， 这些游戏，我们会 共同呼吁四个X游戏， 探索，expand--忘记的。 他们是什么？ 探索，扩张，并熄灭， 我认为这是最后一个。 但是，他们基本上 探索和征服的游戏。 通常，计算机对手 有有有限的信息。 他们不知道到底是什么 会在后面的战争的迷雾。 他们不明白，看看有什么 你有你的库存。 这里有一个环境是动态的。 一切都在不断地变化。 你不要坐下来， 迫不及待地把你的举动。 但大多数事情还是离散的。 我已经把我的城市在这里。 或者，我已经把我的城市在这里。 一切是确定性的。 当我说，把我的单位在这里，我单位 移动这里，除非障碍物突然 进场。 现在，这还不是全部电脑 今天比赛是在那里。 如果我去和我玩一款第一人称类型 游戏，像小偷或辐射 或者天际，或晕，现在 我的电脑对手 是在那里有 一个非常不同的情况。 他们再次，有限的信息。 他们只能看到一个 某些字段的图。 环境仍然是动态的。 事情正在发生变化所有的时间。 但现在我有一个更 连续动作的空间。 我可以只偷看一 点点出了门道。 而一些游戏，我 行动是随机的。 我去尝试跳过那道墙， 但我有一个失败的机会。 这些类型的游戏越来越近 和接近类型的控制器 我们建立的机器人。 在机器人技术，我们必须假设 我们有限制的信息。 我们有传感器 给我们介绍一下这个世界。 我们有一个不断更新的， 动态环境。 我们有一个世界中，空间 连续的，而不是离散的。 而且我们的行动，当我们试图 其中，有一个失败的机会。 而事实上，现代的游戏 控制器的最后一战的对手， 或用于在天际那些的NPC，基本上 经营小机器人的架构。 他们感知世界。 他们建造了世界的模型。 它们计算基于一组的 目标，他们希望实现的目标。 他们计划基础的行动 在他们所知道的。 而这些都是完全一样的种 对我们构建机器人系统。 因此，这些结构，以 把这个重新走到一起， 往往是相当一致的。 因此，让我们看看我们是否能够看到。 让我们回到我们 井字棋的例子。 而我要问我的几个 博士后上来帮我。 所以陈明，和Alessandro和 奥利维尔，如果你们会来。 而我会需要 一对夫妇的志愿者 好吧，我看到了一个手右上 中间有。 让我带一个，有人 进一步在后面可能。 好了，在那边。 上来吧。 好吧。 因此，让我们说盖了下来。 如果你们会来的权利 回来在这里对我来说太棒了。 所以这是一个叫百特的机器人。 和Baxter是一个机器人，这是一个 商业平台，设计 由一家名为反思。 而这个机器人被设计 对于小规模生产。 但今天我们要 用它玩井字棋。 现在，这个机器人也未尝 这是比较独特的。 因为如果我站在任何地方 接近标准的工厂自动化 系统，我会非常严重 危险受伤。 巴克斯特，但是，被设计成 相对安全进行交互。 所以，我可以把这个机器人。 你可以看到这是一个有点 位灵活，因为它到处移动。 我可以重新定位 在这里我想它去。 现在，在一个正常的机器人系统， 我们将有一组接头在这里 这将是直接 响应位置指令。 他们不一定会在意 如果他们通过户外运动， 或者，如果他们被感动 通过我的胸腔。 好。 并且通常，如果你 这里的工业体系， 你会去远不及它。 会有黄色 安全胶带周围的一切。 这个系统有一个 稍有不同的设计 要友好，更容易 人们互动， 中，在每一个关节，有一个春天。 而非控制 一个准确的位置， 我们控制一定量的 扭矩，一定量的力， 我们希望成为的那个春天。 好了，所以让我 在这里把我们的志愿者。 你好，你的名字是什么？ 听众：路易斯。 演讲嘉宾：路易斯。 很高兴见到你。 和？ 听众：大卫。 演讲嘉宾：大卫。 很高兴见到你。 如果你们会等 这里适合第二， 我想给你 有机会做到这一点。 所以这个机器人，如果你来了 如果你轻推就可以了， 你会看到， 它移动一点点。 如果你抓住它的权利 这里在手腕上刚 其中，以上这些按钮，它 看起来你应该抓住的按钮， 但抢正上方相反，你会 能够轻轻地操纵它 通过空间。 路易斯，你想给它一个尝试？ 所以给它一点点 推下手。 然后，如果你把你的手指 在那里，并抓住它， 因为它会动你呢。 好吧，你想给它一个尝试？ 上来吧。 所以给它只是一个温柔 推那里开始。 你可以感受到是什么感觉。 然后，如果你抓住它那里， 你就可以操纵左右。 好。 因此通常，这种机器人的会 用于小规模制造。 而且我要正义之举这个手臂 淘汰下来的方式一点点在这里。 但是今天，我们将使用 同样的井字棋播放系统 根据我们先前建立极小。 好不好？ 所以，你们是各 要玩游戏。 路易斯，你会是第一个。 让我抱起来这里进行了第二次。 我要你站在正确的 在这里，只是让每个人都可以看到你。 你们是不是在这里设置？ 机器人：欢迎。 让我们玩井字棋。 之前，不要抓住你的令牌 我说，这是轮到你了。 我开始游戏。 这是轮到我了。 演讲嘉宾：现在，如果你可以采取的一个 你的作品，并继续前进，并把它。 机器人：它是轮到你了。 [笑声] 这是轮到我了。 [笑声] [笑声] 轮到你了。 演讲嘉宾：人类是 你指望在这里，路易斯。 机器人：它是轮到我了。 演讲嘉宾：所以，巴克斯特 在这里成功地阻止。 机器人：它是轮到你了。 这是轮到我了。 轮到你了。 这是轮到我了。 演讲嘉宾：我们将让巴克斯特 在这里完成了它的最后一步。 [笑声] 机器人：这是一个平局。 我会赢得下一次。 [笑声] 演讲嘉宾：好的， 非常感谢，路易。 谢谢。 你可以走这条路。 机器人：我开始游戏。 演讲嘉宾：所以让我来解释一下 给你多一个小 前位，我们在这里得到了复赛。 究竟是怎么回事？ 因此，机器人有一个摄像头向上顶在这里。 而且它低头看着板。 而且它看到是否 它有一个红色的O或蓝色 白色X.由于这些获得放置在 板，这是基本相同的输入 我们将从读取 从我们的屏幕我们的数据结构。 它的运行相同 极大极小算法是 能够找到在哪​​里 把一个很好的象征。 然后我们给有关的命令 在这里我们想令牌放置。 手臂动了。 它采用真空夹具适用 一些吸引到木件， 把它捡起来，将其移动到右边 现货方面，然后释放抽吸 并把它。 好吧，我们要去 给它多一枪 一个稍微聪明的球员在这里。 你准备好了吗？ 好吧，如果你站在直到 这里为A--出现这样的局面 所以你可以看到大家。 然后[听不清]。 机器人：它是轮到我了。 演讲嘉宾：百特将启动。 轮到你了。 这是轮到我了。 轮到你了。 这是轮到我了。 [笑声] 演讲嘉宾：[WHISPERING]刚 让他继续前进，取得胜利。 机器人：它是轮到你了。 演讲嘉宾：这是确定的。 机器人：它是轮到我了。 [笑声] 我赢了。 [笑声] 我开始游戏。 演讲嘉宾：好的，非常感谢你。 好吧，我想我们还有时间 多了一个优秀的井字棋的球员， 谁可以把这个事情 匹配，谁知道他们在做什么。 [笑声] 谁是要在这里是我们的冠军吗？ 好吧，你的朋友自告奋勇你。 这对我来说不够好。 再告诉我你的名字。 听众：塔米尔。 演讲嘉宾：塔米尔，很高兴见到你。 好吧，再次，我们打算把你 直到这里，所以每个人都可以看到你。 你是我们的代表 在这场比赛了。 巴克斯特是哦，呵呵。 还是遗憾，一个OH和一个。 而它给你在这里。 百特将获得先动，虽然。 所以。 机器人：它是轮到我了。 [笑声] 轮到你了。 这是轮到我了。 轮到你了。 这是轮到我了。 轮到你了。 [笑声] 机器人：它是轮到我了。 演讲嘉宾：这是一个很大困难时， 你站在这儿，伙计。 [笑声] 机器人：你们人类是那么容易被击败。 [笑声及掌声] 演讲嘉宾：非常感谢。 机器人：我赢了。 我开始游戏。 演讲嘉宾：好的，十分感谢非常 太多的奥利维尔，并亚历山德罗， 和陈明。 [掌声] 我想提出最后一点。 所以巴克斯特在非常 到此为止，被骗。 这是出乎意料的。 一个梦幻般的 有关AI的事情是，我们 做工作，AI，使我们能够建立 真的很有趣，智能化 设备。 但是，我们也爱做的工作 因为它告诉我们什么 有关如何人类是聪明的。 人们所喜爱的 从我的实验室研究是 看会发生什么时 机器意外作弊。 我们这样做原本不 百特玩井字棋， 但有一个名为淖较小的机器人， 谁发挥剪刀，石头，布。 有时后 打很多很多 无聊的剪刀，石头，布的游戏， 机器人将抛出一个手势， 输了，然后突然改变 它的姿态，说，我赢了。 [笑声] 现在，有时我们也不得不机器人， 只是作为一个控制，抛出一个手势， 赢了，并改变其姿态 输了，丢了比赛， 作弊是为了减肥。 这是几乎没有引人注目。 该秘籍机器人 为了赢得人们 到，就好像它是响应 出去找他们，喜欢它 正在积极寻求他们的破坏。 [笑声] 它成为一个代理。 这就像一个人。 它有信念和意图。 而且这不是善意。 和机器人抛出 游戏只是故障。 这只是一个损坏的设备。 让我告诉你一些例子 的，从我们的一些参与者。 因此，这里的作弊是为了减肥。 [视频回放] - [听不清]获胜。 让我们玩。 -Wait，是什么？ - [听不清]获胜。 让我们玩。 [听不清]获胜。 让我们玩。 演讲嘉宾：这里的作弊取胜。 - 是的，我赢了。 让我们玩。 - 你不能这样做。 [笑声] - 是的，我赢了。 -你作弊。 现在，您被骗。 - 是的，我赢了。 - 嘿，你骗子。 你欺骗，超级骗子。 [结束播放] 演讲嘉宾：这些不同 反应迅速 改变我们的感知设备。 这是否意味着， 我们特意打造 该作弊，因为这是机器 我们能做的最好的工程？ 没有，但它告诉我们什么 真正有趣的人。 这件事欺骗了你和 偷了你的胜利，这是 东西是活的，这是 动画，那是出去找你。 它具有的精神状态。 它有信念。 它的意图。 这件事，手中的 游戏中你，那不是。 这只是发生故障。 这是在许多方面它为什么 易投掷游戏的孩子。 但是，如果你试图欺骗他们 和排序的取得胜利 如果，你知道的，只是为了缩短 比赛中，他们会抓住你的时候了。 这些种的效果是 我们看到走出来的AI， 他们教给我们很多关于自己。 好吧，这就是它的今天。 非常感谢大卫， 哈佛制作团队 对下来。 [掌声] 我们会看到你的测验之一， 然后一最后一次演讲。 祝你有美好的一天。 [掌声] [音乐播放] 大卫·马兰：好吧，我们可能需要 引入加密一些， 对？ 因为那么头 这些HTTP请求将 炒使任何人 试图嗅出你的流量 实际上不会能够看到它们。 那么，有什么办法解决这个问题？ 好了，我们需要真正引入 加密入公式， 这样，当该人是 从A发送数据给B， 我们可以安全地send-- [笑声] 在一个方式中的信息，该 攻击者无法，其实，看到它。