五子棋游戏[4] – 人机博弈 – α-β剪枝及改进与总结

五子棋游戏[4] – 人机博弈 – α-β剪枝及改进与总结
继续填坑。按照计划,剪枝和改进总结本应该分为两次写,但是经过整理,发现剪枝部分的内容并不丰富,而改进与总结其实和剪枝一样,都是为了更快的搜索到一个比较优秀的解,故此我就在这一篇文章中全部写完。 在上一次的文章中我写了博弈类算法中最为重要的工具 – 博弈树的构造方式,并且描述了对其搜索的算法。另一方面也写了博弈算法的核心 – 状态评价的一种方案。经过上一次文章的描述,你应该已经可以写出一个可以和你进行玩耍的AI了,但是你会发现,和这个AI下棋,每一步都会很慢很慢,这种情况就是在提醒我们就需要考虑到搜索的效率了。 上一篇文章的博弈树搜索算法可以用这样一句话来评价:简单粗暴。没错,短短几行代码就完成了整个博弈的智能,但是对于搜索而言,简单粗暴并不意味着非常有效。我们可以来分析一下: 假设棋盘上的正中心已经下有一个棋子,那么棋盘上还有224个可以放置的点位,那么博弈树搜索的第一层就需要扩展224个状态节点; 接下来,每个状态节点都剩余223个可放置棋子的位置,所以需要继续扩展223个状态节点,所以第二层会存

五子棋游戏[3] – 人机博弈 – 博弈树

五子棋游戏[3] – 人机博弈 – 博弈树
距离上次写这个系列已经过去很久了,非常抱歉,现在呢我重新拾笔来填我自己挖下的这个坑。 在上一次的文章中,我们已经制作了整个游戏的最核心的框架,也就是说我们得到一个可以进行游戏的交互界面并且对游戏规则进行掌控的一个游戏类,在此前的文章中,我尽可能的让大家回避我所写的代码,因为这样会限制大家对整个游戏架构的思考,毕竟构建一个游戏的方式是多种多样的,我所想的方法并不一定是最好的,所以我希望大家自己去构建游戏的核心部分,我的文章仅作为一些提示。不过从这一篇文章开始,情况将有所转变,在完成的游戏核心部分之后,我希望让大家了解到的是,让游戏获得智能本身是一件又简单但又不简单的事情。 简单,是因为我们其实只是需要一个算法,能够替代两个玩家中的其中之一,这个算法的框架显而易见: 算法的输入数据就是当前棋局,算法通过分析棋局来计算并得出一个最佳的行棋位置。算法的需求是明朗简单的,但是难点就在于如何实现这个算法。 好在,有无数的人身先士卒,已经研究出了一类算法来应对这种博弈类问题,而且这种方法易于理解和实现...

A*算法 – 八数码问题

A*算法 – 八数码问题
上一篇文章我介绍了A*算法,A*用于找到从起始状态到目标状态的一条最短路径,而且根据估价函数的不同,其搜索效率也会有所不同。其实我们只要找到一个估价函数h(s) > 0,那么这个A*算法最后至少要比BFS强。 我们今天来做一个A*算法的实战演练,借此来更透彻的理解A*算法。我们要解决的问题就如题目所述——八数码问题。 八数码问题其实非常容易理解,你我在儿时肯定都玩过这样的游戏。 这是一个九宫格,其中有八个格子有数字,还有一个格子是空位,和空位相邻的数字格子可以和空位相互交换,游戏的最终目的就是让这些数字形成一个有序的局面。假如说我们有左边这样一个初始状态,我们现在就是想找到一种最快捷的方法,使左边的初始状态转换为右边的最终状态。 如果按照BFS的思路,我们每次扩展四个节点,分别是空格上移、下移、左移和右移(当然,大多数节点是无法完全扩展这四个方向的),一层层搜索之后,若发现了目标状态,则从目标状态节点开始向父节点回溯,由此就可以得到一个步数最少的解法了。 在之前的文章中也提到了,BFS是

A*算法 – 介绍

A*算法 – 介绍
这学期学校开了人工智能课程,留了一项小作业,就是使用A*算法解决八数码问题,觉得挺有意思,于是就写下这篇文章来与大家分享。其实我很久很久以前就已经听闻过A*算法的大名了,但是鉴于当时的理解能力不足(懒?),就不了了之了。 记得当年第一次见到A*这个名字的时候,感觉非常的高端洋气,于是在气势上就输给了它,所以大家在继续阅读这篇文章的时候一定要放松,这个算法的确很著名,而且也的确非常的高效,但是它并不复杂,而且非常容易理解。 首先说下A*算法的作用:找到一条从起始状态到最终状态的最短路径。不知道大家看到这个作用有没有联想到什么?具有同样作用的一个算法“BFS广度优先搜索”在我之前的博客中介绍过,如果你不知道,可以点击这里回顾一下这个算法。 BFS通过“一层一层”地扩展节点,以此确保在发现目标状态的时候整个搜索树的深度最低,这是一种非常盲目的搜索方法,因为如果解的深度较深的话,我们有时候不得不搜索过所有的节点才能找到目标,而A*算法则不然,我编一个故事说明BFS和A*算法的区别: 王尼玛同学去食堂吃饭,但