人工智能:学会学习

类型

计算机科学

年级

9^th年级

困难的项目

需要技术知识

成本

没有与本项目相关的成本。

安全问题

没有与本项目相关的安全隐患。

时间来完成这个项目

花费的总时间完成这个项目如下:

• 编程:147小时
• 董事会建设:4小时
• 书面报告:18个小时

客观的

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

材料和设备

• 一个简单的文本编辑器,比如notepad
• 电脑(Windows 7旗舰64位,4 gb内存,英特尔酷睿2双核3.00 GHz)
• Google Chrome (8.0.552.237)

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

目标赋予人类智能的无生命的物体有着悠久的历史。现代计算机每秒能执行数百万的计算,但即使所有这些惊人的速度,真的逻辑尚未实现。每年,电脑越来越接近实现这一目标,或者至少模仿真正的逻辑。游戏策略是最常见的一种人工智能的应用。算法是一组指令计算机遵循实现任务或目标。有三个主要类型的算法智能游戏:α-β,学习,和混合动力车。象棋是第一个游戏来实现人工智能的发现α-β算法在1958年由卡内基梅隆大学的科学家(弗里德,无日期)。α-β算法是第一个可行的算法,可用于策略游戏。随着人工智能在游戏中发展和越来越复杂,一个更现代的“学习”的方法已被采用。虽然已经有了很大的进步在“学习”风格算法和α-β算法; 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.

成功的α-β算法有着悠久的历史。第一个在比赛中使用的算法是在70年代和80年代的“美女”电脑。美女仍然计算机国际象棋的冠军,直到被克雷超级计算机取代(弗里德,无日期)。美女是第一个计算机成功使用α-β的早期形式的算法。深蓝后使用该算法为了打败国际象棋大师卡斯帕罗夫;这是一个人工智能社区的主要发展是历史上第一次电脑击败象棋大师在标准匹配。随着时间的推移,该算法已修订,更新,修改,几个版本的算法存在,所有使用相同的核心原则。

α-β算法使用蛮力计算(每秒数千)作出决定。α-β算法使用极小极大原理(一个球员试图最大化他们的得分,而其他试图最小化)和高效的评估技术来实现其逻辑。α-β是一个“博弈树搜索者”,或者换句话说,它形成一个层次结构的可能向下移动到定义的水平(即六个动作)。在一些变化,消除对称和旋转是用来减少博弈树的大小(林,2003)。树后形成算法然后收益评价树中的每个位置根据一组规则旨在使电脑玩更强大,这就是所谓的启发式。α-β的原因是快,然而强烈的是,它忽略了部分游戏板(林,2003)。它决定哪些部分忽略基础上寻找最佳移动每级(或移动),忽略所有的动作,不是最好的举措。α-β可以计算两个级别的波动在0.018秒,900个职位三个级别的波动在0.54秒,27000个职位四个水平的波动在16.2秒内810000个职位,等等。这些效率提高技术负责小计算时间和改进算法提供的游戏策略。

学习风格算法是另一个流行的游戏类型的算法使用。学习风格算法不一定是最近的一个创造。他们已经使用了大约30年,但直到最近会见了有限的成功。在这种方法中,一个算法使用自己的经验,或大型数据库的演奏比赛来决定最好的举措。不幸的是,学习算法也将“坏”策略利用新手玩家。随着时间的推移,已经作了一些改进,这样一种算法可以威胁到中级玩家在大多数动作游戏;然而,学习算法通常是不成功的在游戏中需要战略的作用。奇努克程序使用最显著的学习算法。这个项目花了十八年计算每一个可能的跳棋游戏。但奇努克的算法被一些不是“真正”的学习算法,因为它已经知道的所有可能结果的一举一动(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.

一种混合算法结合了α-β算法的强力风格和学习风格算法的灵活性。这个方法确保完整的能力虽然是免费使用的电脑是适应每一个游戏玩家的个人风格。奇努克成功地利用这种技术使一个程序,就是不可战胜的。因为奇努克项目的跳棋游戏“解决。“不管对手如何,最好的他们所能做的就是以平局结束(2007张)。

其他冠军计划只使用一个算法为了赢得的风格。结果,没有特定算法测量或被证明是主导。游戏开发者选择使用哪种算法主要基于个人偏好和缺乏共识的人工智能社区算法优越。也有弱点,可以用来确定哪些算法会低人一等。例如,α-β算法并不生成所有可能的从游戏的现状。α-β假定对手会让最好的移动。如果一个球员让此举并不在他们的最佳利益,该算法将不知道如何回应,因为移动的博弈树还没有计算。对手能欺骗算法通过sup-par举措,并迫使它重新计算。同样重要的是要注意,α-β算法可以用大量的时间在计算多几个动作。学习算法都有其缺陷。 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场):α-β与混合,α-β与学习,学习与混合。
2. 为了在合理的时间内运行测试,同时运行多个测试几个相同的电脑上。总的来说,9000年奥运会了。
3. 每场比赛的结果存储在一个巨大的HTML表,可以导入到Microsoft Excel进行评价和分析。
4. 花了超过147小时的编程的游戏跳棋和三个算法(α-β、学习算法和混合的)的人工智能。编程完成后,每个算法出场3000场的跳棋。实验的测试结果的总数是9000试验。测试发生在几个相同的计算机同时运行多个单独的测试。移动,直到赢得的数量,平均移动时间,每一轮的获胜者被记录。测试结束后,结果是平均和总计。

结论

实验清楚地展示了α-β算法赢得更多的比赛,把更少的时间来生成一个移动,用的移动少赢了。这显然是优于混合和学习算法。

这个图表显示了算法分别赢得9000年奥运会的百分比跳棋。α-β得分获胜的比例最高,混合排在第二,学习算法得分最低的百分比。

这个图表显示了每个算法生成的平均时间。在这种情况下得分最低算法的最好的。

这张图代表了移动了每个算法的平均数量赢得一场比赛。与前面的图表,得分最低的算法表现最好的。

证据收集的实验表明,α-β算法远远优于混合和学习算法。这可以得出基于三种不同的因素:赢的比例,平均时间移动,和平均生成一系列举措,为了赢得一场比赛。在上述每个类别中α-β算法的最好的在每一个类别。混合比进行学习,但比α-β。学习算法表现最糟糕的。

实验误差

这个实验包括9000次试验;因此,实验误差是最小的。唯一的测量值,需要考虑错误的平均时间是每个算法用于生成。计算机可以记录精确的时间,但是时间是圆的所以计时过程不会影响实验的结果。然而,平均值之间的差异并不显著,即使计算机记录结果与绝对精确的结论将保持不变。另一个方面考虑的结果是一个递归循环的可能性(基本上,当算法陷入重复循环)。尽管该算法将打破循环的,它会导致的平均时间移动游戏大大上升。过去的错误,需要考虑是一种算法的低效的编程。如果一个算法是错误的编程的方式是低效的,显然将损害整体性能。

问题进一步的研究

• 如何学习算法变得更好吗?
• 算法可以使更快,以便更多的测试?

参考书目

常,k(2007年7月19日)。计算机跳棋程序是不可战胜的。从http://www.nytimes.com/2007/07/19/science/19cnd-checkers.html获取

弗莱恩,c(2005年8月1日),计算机国际象棋程序理论。从http://www.frayn.net/beowulf/theory.html获取

弗里德,f(无日期)。一个简短的计算机象棋的历史。从http://www.chessbase.com/columns/column.asp?pid=102获取

林,y (2003)。游戏的树木。从http://www.ocf.berkeley.edu/获取~ yosenl /配件/ alphabeta / alphabeta.html

联系

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