人工智能:学会学习

类型

计算机科学

年级

9^th年级

项目难度

需要技术知识

成本

这个项目没有成本。

安全问题

本项目不存在安全隐患。

完成项目所需的时间

完成该项目的总时间如下:

• 编程:147小时
• 木板制作:4小时
• 书面报告:18小时

客观的

这个项目的目的是确定策略游戏的最佳算法。

材料及设备

• 一个简单的文本编辑器，如记事本
• 一台电脑(Windows 7 Ultimate 64位，4GB RAM, Intel Core 2 Duo 3.00 GHz)
• 谷歌Chrome (8.0.552.237)

背景研究的介绍、术语和概念

将类人智能赋予无生命物体的目标由来已久。现代计算机每秒可以执行数百万次计算，但即使拥有如此惊人的速度，真正的逻辑还没有实现。每一年过去，计算机离实现这一目标越来越近，或者至少是模仿真正的逻辑。博弈策略是人工智能最常见的应用之一。算法是一组指令，计算机遵循它来完成一项任务或目标。游戏中有三种主要的智能算法:Alpha-beta，学习和混合。国际象棋是最早实现人工智能的游戏之一，1958年卡内基梅隆大学的科学家发现了Alpha-beta算法(Friedel, n.d)。Alpha-beta算法是第一个可用于游戏策略的可行算法。随着游戏中的人工智能不断进化并变得越来越复杂，人们开始采用更现代的“学习”方法。尽管“学习”式算法和Alpha-beta算法都取得了重大进展; a hybrid utilizing elements of both algorithms results in a stronger, more efficient, and faster program. On the forefront of the quest for artificial intelligence, these algorithms are playing vastly important roles.

Alpha-beta算法有着悠久的成功历史。第一次在游戏中使用算法是在70年代和80年代的“Belle”计算机。贝尔一直是计算机国际象棋的冠军，直到被克雷超级计算机取代(弗里德尔，n.d.)。Belle是第一台成功使用Alpha-beta算法早期形式的计算机。“深蓝”后来使用该算法击败了国际象棋大师加里·卡斯帕罗夫(Garry Kasparov);这是人工智能领域的一项重大进展，因为这是历史上计算机首次在标准比赛中击败国际象棋特级大师。随着时间的推移，算法已经被修订、更新和修改，以至于存在几个版本的算法，它们都使用相同的核心原则。

Alpha-beta算法使用蛮力计算(每秒数千个)来做出决策。Alpha-beta算法使用极大极小原则(一名玩家试图最大化他们的分数，而另一名玩家试图最小化它)和有效的评估技术来实现其逻辑。Alpha-beta是一个“游戏树搜索器”，换句话说，它形成了一个可能移动到定义级别的层次结构(即6步)。在一些变化中，消除对称性和旋转被用来减少博弈树的大小(Lin, 2003)。在树形成后，算法根据一组旨在使计算机发挥更强的规则继续评估树中的每个位置，这被称为启发式。Alpha-beta之所以快速而强大，是因为它忽略了游戏棋盘的某些部分。它会根据每个关卡(或移动)的最佳移动来决定忽略哪些部分，并忽略所有不是最佳的移动以及它们下面的移动。Alpha-beta可以在0.018秒内计算出2级900个位置的走法，0.54秒内计算出3级27000个位置的走法，16.2秒内计算出4级810000个位置的走法，等等。这些提高效率的技术可以减少计算时间，并改进算法提供的博弈策略。

学习式算法是另一种流行的游戏算法。学习风格的算法不一定是最近才出现的。它们已经使用了大约30年，但直到最近才取得有限的成功。在这种方法中，算法使用自己的经验，或预玩游戏的大型数据库来确定最佳走法。不幸的是，学习算法也包含了新手玩家使用的“坏”策略。随着时间的推移，算法的改进使得大多数动作游戏中的算法可能对中级玩家构成威胁;然而，学习算法在需要策略的游戏中通常是不成功的。支奴干计划使用了最著名的学习算法。该程序花了18年时间计算跳棋的每一步可能。但是支奴干的算法被一些人认为不是一个“真正的”学习算法，因为它已经知道每一步的所有可能结果(Chang, 2007)。 Chinook, however, does adjust its playing style for each player’s strategy; this is where its element of learning comes into play (Chang, 2007). Learning algorithms are considered closer to true intelligence than other algorithms that use brute-force calculations such as Alpha-beta. Compared to pure calculation algorithms, they play games more like humans and even show very limited aspects of creativity and self-formed strategy.

一种混合算法结合了Alpha-beta算法的蛮力风格和学习风格算法的灵活性。这种方法确保了计算机的全部能力被使用，同时它可以自由地适应每个玩家的个人游戏风格。奇努克成功地利用了这一技术，制作出了一个真正无敌的程序。因为支奴干计划，跳棋游戏被“解决”了。不管对手打得多好，他们能做的最好的就是以平局结束(Chang 2007)。

其他冠军程序只使用一种算法来获胜。因此，没有特定的算法被测量或证明是占主导地位的。游戏开发者选择使用哪种算法主要是基于个人喜好，而人工智能社区对于哪种算法更优秀缺乏共识。有一些弱点可以用来确定哪种算法将被证明是较差的。例如，Alpha-beta算法不能从游戏的当前条件中生成所有可能的移动。Alpha-beta假设对手将采取可能的最佳走法。如果玩家做出了不符合自己最大利益的移动，算法将不知道如何回应，因为该移动的游戏树还没有计算出来。对手可以通过超常规的移动来欺骗算法，迫使它重新计算。同样重要的是要注意，Alpha-beta算法在计算不止几步移动时可能会花费大量的时间。学习算法也有它的缺陷。 If it encounters an unknown strategy, the algorithm will be helpless against its opponent’s moves. The most likely way to minimize these flaws is to combine these algorithms into a hybrid. If the hybrid encounters an unknown strategy, it can then use the Alpha-beta style game tree to determine the possible moves from that point. Likewise, if the opponent uses a move not calculated by the brute-force method, it can then use learned strategies to defend itself. The hybrid algorithm will be faster and have better winning strategies than either the Alpha-beta, or the learning style algorithms.

研究问题

• 哪种算法赢的最多?
• 哪种算法播放速度最快?
• 哪种算法在更少的移动中获胜?

过程

1. 为了比较算法之间的差异，必须进行三个测试(每个测试涉及3000个游戏):Alpha-beta vs.混合，Alpha-beta vs.学习，以及学习vs.混合。
2. 为了在合理的时间内运行测试，在几台相同的计算机上同时运行多个测试。总共进行了9000场比赛。
3. 每个游戏的结果都存储在一个巨大的HTML表格中，然后可以导入到Microsoft Excel中进行评估和分析。
4. 他们花了147个小时来编程跳棋游戏和包含人工智能的三个算法(alpha-beta、学习算法和两者的混合)。编程完成后，每个算法与其他算法对弈3000盘跳棋。该实验的测试结果总计为9,000次。测试在几台相同的计算机上进行，同时运行多个独立的测试。记录胜利前的移动次数，平均移动时间，以及每一轮的获胜者。测试结束后，对结果进行平均和合计。

结论

实验清楚地表明，alpha-beta算法赢得了更多的比赛，花更少的时间来生成一个动作，用更少的动作来赢得比赛。它明显优于混合算法和学习算法。

这个图表显示了每种算法在9000盘跳棋中获胜的百分比。Alpha-beta的胜率最高，混合算法次之，学习算法的胜率最低。

这个图表显示了每个算法生成一个移动所花费的平均时间。在这种情况下，得分最低的算法表现最好。

这个图表代表了每个算法赢得一场比赛的平均步数。与前面的图表一样，得分最低的算法表现最好。

从实验中收集的证据表明，Alpha-beta算法远远优于混合算法和学习算法。这可以基于三个不同的因素得出结论:胜利的百分比，每一步所花费的平均时间，以及为了赢得游戏而产生的平均步数。在这些类别中，Alpha-beta算法在每个类别中表现最好。杂交组的表现比学习组好，但比阿尔法-贝塔组差。学习算法表现最差。

实验误差

这个实验包括9000个试验;因此，实验误差最小。唯一需要考虑误差的测量值是每个算法生成一个动作所需的平均时间。计算机可以记录精确的时间，但是时间是四舍五入的，这样计时的过程就不会影响实验的结果。然而，平均值之间的差异并不显著，即使计算机以绝对精确的方式记录结果，结论也不会改变。关于结果需要考虑的另一个方面是递归循环的可能性(基本上，当算法陷入重复循环时)。尽管算法会打破循环，但这将导致在该游戏中花费在移动上的平均时间大幅增加。最后一个需要考虑的错误是算法编程中的低效率。如果一个算法以一种低效的方式被错误地编程，它显然会损害整体性能。

进一步研究的问题

• 学习算法如何改进?
• 算法能不能做得更快，以便进行更多的测试?

参考书目

Chang K.(2007, 7月19日)。电脑跳棋程序无敌。检索自http://www.nytimes.com/2007/07/19/science/19cnd-checkers.html

Frayn, C.(2005, 8月1日).计算机国际象棋编程理论。检索自http://www.frayn.net/beowulf/theory.html

弗里德尔，F.(未注明)。电脑象棋的简史。检索自http://www.chessbase.com/columns/column.asp?pid=102

林旸(2003)。游戏的树木。检索自http://www.ocf.berkeley.edu/~yosenl/extras/alphabeta/alphabeta.html

联系

该程序的演示电子邮件connerruhl在me.com