博文
人工智能在五子棋上的应用(2007-04-11 17:13:00)
摘要：人工智能也就是所谓的AI(Artificial Intelligence)，它是一门很抽象的技术，AI程序的编写不需要依据任何既定的思考模式或者规则。尤其是游戏中的AI可以完全依程序设计者本身的思考逻辑制作。我个人认为人工智能的核心应该是使计算机具有自动的处理事件的能力，而我们的所有的研究也应该围绕着这一方向。我们今天讨论的是策略类的人工智能。 策略类人工智能可以说是AI中比较复杂的一种，最常见的策略类AI游戏就是棋盘式游戏。在这类游戏中，通常的策略类AI程序都是使计算机判断目前状况下所有可走的棋与可能的获胜状况，并计算当前计算机可走棋步的获胜分数或者玩家可走棋步的获胜分数，然后再决定出一个最佳走法。下面我们先介绍一下五子棋的AI构想。 五子棋的AI构想 有句话叫“当局者迷，旁观者清。”，但这句话在由AI所控制的计算机玩家上是不成立的，因为计算机必须知道有那些获胜方式，并计算出每下一步棋到棋盘上任一格子的获胜几率，也就是说，一个完整的五子棋的AI构想必须： 1、能够知道所有的获胜组合； 2、建立和使用获胜表； 3、设定获胜的分数； 4、使电脑具有攻击和防守的能力； 一、求五子棋的获胜组合 在一场五子棋的游戏中，计算机必须要知道有那些的获胜组合，因此我们必须求得获胜组合的总数。我们假定当前的棋盘为10*10。 （1）计算水平方向的获胜组合数，每一列的获胜组合是：6，共10列，所以水平方向的获胜组合数为：6*10=60 （2）计算垂直方向的获胜组合总数，每一行的获胜组合是：6，共10行，则垂直方向的获胜组合数为：6*10=60 （3）计算正对角线方向的获胜组合总数，正对角线上的获胜组合总数为6+（5+4+3+2+1）*2=36 （4）计算反对角线方向的获胜组合总数，反对角线上的获胜组合总数为6+（5+4+3+2+1）*2=36 ，这样所有的获胜组合数为：60+60+36+36=192 二、建立和使用获胜表 我们已经计算出了一个10*10的五子棋盘会有192种获胜方式，这样我们可以利用数组建立获胜表，获胜表的主要作用是：1，判断当前的获胜方式是否有效；2，判断当前的获胜方式中到底有多少子落入该获胜组合中。详细的使用您将在后面的程序中可以看出。 三，分数的设定 在游戏中为了让计算机能够决定下一步最佳的走法，必须先计算出计算机下到棋盘上任一......
五子棋的核心算法(2007-04-04 22:34:00)
摘要：五子棋的核心算法五子棋是一种受大众广泛喜爱的游戏，其规则简单，变化多端，非常富有趣味性和消遣性。这里设计和实现了一个人机对下的五子棋程序，采用了博弈树的方法，应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。介绍五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程。一、相关的数据结构 关于盘面情况的表示，以链表形式表示当前盘面的情况，目的是可以允许用户进行悔棋、回退等操作。 CList StepList; 其中Step结构的表示为： struct Step { int m; //m,n表示两个坐标值 int n; char side; //side表示下子方 };以数组形式保存当前盘面的情况，目的是为了在显示当前盘面情况时使用： char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; 其中FIVE_MAX_LINE表示盘面最大的行数。 同时由于需要在递归搜索的过程中考虑时间和空间有效性，只找出就当前情况来说相对比较好的几个盘面，而不是对所有的可下子的位置都进行搜索，这里用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合： CList CountList; 其中类CBoardSituiton为: class CBoardSituation { CList StepList; //每一步的列表 char FiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE]; struct Step machineStep; //机器所下的那一步&......
我的数据结构课程设计-关键路径(2006-07-13 20:18:00)
摘要：#define max 20#include<iostream>#include<stdio.h>#include<malloc.h>using namespace std;typedef struct ArcNode//定义表结点{int adjvex;//该弧所指向顶点的位置 struct ArcNode *nextarc;//指向下一条弧的指针 int info;//该弧的权值}ArcNode;typedef struct VNode//定义头结点{int data;//顶点信息 ArcNode *firstarc;//指向第一条依附该顶点的弧的指针}VNode,AdjList[max];typedef struct//定义ALGraph{AdjList vertices; int vexnum,arcnum;//图的当前顶点数和弧数 int kind;//图的种类标志}ALGraph;typedef struct//定义栈 {int *base;//栈底 int *top;//栈顶}stack;
void initstack(stack &s)//建立空栈{s.base=(int*)malloc(max*sizeof(int)); s.top=s.base;}
int stackempty(stack s)//判断是否为空栈{if(s.base==s.top) return 1; else return 0;}
int stackfull(stack s)//判断是否为满栈{if(s.top-s.base>=max) return 1; else return 0;}
int pop(stack &s)//进行出栈{int e;//出栈先进行赋值，后移动指针 if(!stackempty(s)) {e=*(s.top-1); s.top--; return e; } else return NULL;}
void push(stack &s,int e)//进行入栈{if(!stackfull(s)){s.top++;/......