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

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

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

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

五子棋游戏[2] – 双人对战

五子棋游戏[2] – 双人对战
书接上回。时间间隔稍微有点远,但是我还是希望能够继续完结这一系列的文章。上一回我们已经建立了一个很标准的游戏框架,基于这个游戏框架我们只需稍加理解便可以完成这个五子棋软件的双人对战功能。 为什么要先讲解双人对战功能呢?因为其实AI vs. MAN的功能其实是MAN vs. MAN的一个子集,双人对战所完成的内容是包括游戏规则、游戏操作、胜负判定的一系列纯粹的游戏内容的实现,而加入AI只不过是将对战双方的其中一方的行棋改为了计算机自动计算。 在上一篇文章中我给出了一个类图,现在我再次给出。 其中Game类是我们这次的核心任务,因为整个游戏将如何进行基本上是由Game类来完成的,于是我们首先需要分析整个游戏的流程,由于我们要将分析的结果转换为程序逻辑,所以这个分析是必须逐步求精的,那么请跟着我一步一步的来把游戏的流程梳理清楚: 这是一个很标准的博弈类游戏的游戏流程,通常人们第一想到的就是这样的,但是这样的流程如果直接挪用到我们的游戏设计中就显得有些冗余了,现在回到我们之前的类图,之前我并没有解释

五子棋游戏[1] – 简介与设计

五子棋游戏[1] – 简介与设计
出于学校AI课程的设置,有一项可选的大作业是五子棋游戏,由于我比较倾向于实用主义,觉得做出来的东西可以玩才是王道,所以便选择了五子棋。由于之前的数据结构课程设计已经有了C#的使用基础再加之一个学期软件工程课程的锻炼,于是乎这次的设计我就想以非常标准化的方法来实现。 我这次并不会给出完整的游戏源代码,但整个游戏的结构我一定会力求完整的展现给大家,这样做也是希望大家能留有足够的思考空间,根据我自己的经验,看了别人的代码之后再自己写,多半也是循着那套思路在走,这样不利于学习。 五子棋大家都很熟悉,老少皆宜,规则相对比较简单,上手容易,但是要想成为高手,也是要下很大一番努力的。大家所熟悉的五子棋规则中主要分为“有禁手”,和“无禁手”两种,考虑到课程作业的简单性原则,以及其使用者(我?)五子棋水平有限,故在判断输赢方面,以“无禁手”的规则为标准。 五子棋的棋盘是一个15 * 15的方格棋盘,如下图所示: 由黑方执棋者先行,黑白两方交替放子,先使五个棋子连珠成线者获得当盘的胜利。 从这里我们就已经...

A*算法 – 八数码问题

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

A*算法 – 介绍

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