五子棋游戏[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的方格棋盘,如下图所示: 由黑方执棋者先行,黑白两方交替放子,先使五个棋子连珠成线者获得当盘的胜利。 从这里我们就已经...