C/C++ 2009-11-30 18:03:17 阅读284 评论卡曼奇40 字号：大中小 订阅
摘要：本文就作者编写的井字棋程序进行了简要的介绍，并重点介绍了该程序采用的算法、程序设计方案、对算法的改进等内容。 关键字：井字棋，评估函数，极大极小值算法，α-β剪枝算法 1. 程序说明
本程序旨在完成一个具有人机博弈功能的井字棋程序，具有良好的用户界面、支持人机对弈和双人对弈两种模式，并具有悔棋、选择难易级别等功能。该程序是中科院研究生院2005年秋季学期《人工智能原理》课程的项目一。 2. 设计方案
天诛玉2.1 设计步骤
本程序最主要的任务是完成图形界面的井字棋的人机对弈模块的设计。在人机对弈过程中，计算机方所采用的算法，也就是博弈树的搜索技术是最重要的。所以，设计时，作者按照以下步骤进行：
(1) 选定博弈算法；
(2) 建立一个简单的应用程序（如字符界面程序）来测试算法；
(3) 选定图形界面中要实现的其他功能（如双人对弈、悔棋、难易级别选定、联机对战等）；
(4) 实现图形界面的井字棋程序。
所采用的核心算法将在第3节介绍。本程序要实现两个程序，一个是字符界面的算法测试程序，另一个是要正式提交的图形界面程序。下面是对这两个程序的设计方案的介绍。
2.2 字符界面的算法测试程序
该测试程序由标准C++编写，作者采用了极大极小值算法。除了主程序外，它还包括具有以下功能的函数：
(1) 棋盘初始化函数：void Init()；
ftc相变保温材料(2) 打印棋盘函数：void PrintQP()；
(3) 用户输入落子位置函数void UserInput()；
(4) 判断当前棋局是否有一方获胜，并判断哪一方获胜的函数：int IsWin(State s)；
(5) 评估函数值计算函数：int e_fun(State s)；
(6) 极大极小值算法主函数：int AutoDone()；
其中前三个函数是对程序中当前的棋局进行读写操作的函数，第4广西壮族自治区人口和计划生育管理办法
、5蛋白质晶体
个函数是对当前的棋局进行判断的函数，最后一个函数中包含了计算机决定在哪个位置落子所采用的核心算法，并且可以判断计算机落子前后棋局的状态，如果在搜索树的深度范围内能判断哪一方必胜，则可提前打印输赢信息，并结束本棋局。字符界面的测试程序的运行过程如图1所示。 2.3 图形界面的井字棋程序
图形界面的井字棋程序使用MFC（微软基础类库）来构建图形界面，同时将字符界面程序中的void Init()、int IsWin(State s)、int e_fun(State s)、int AutoDone()四个函数拿出来放
在一个独立的头文件中。棋盘绘制和显示对弈状态信息通过视图类CJzqView类来实现，而且所有的井字棋对弈功能的实现全部包含在CJzqView类中。作者定义的一些菜单消息如下所示，菜单消息包含了该程序实现的所有功能：
? ID_NEW_QP：新开一局
? ID_QP_HUI：悔棋
? ID_AUTO_GAME：人机对弈
? ID_TWO_MAN：双人对弈
? ID_MAN_FIRST：设定人先下
? ID_COMPUTER_FIRST：设定计算机先下
? ID_EASY、ID_MID、ID_HARDnetwork ntr：设定难易级别（容易、中等、困难）
此外，我还定义了ON_WM_LBUTTONUP消息的响应函数，以便于用户落子。此外，对弈结束后，用鼠标左键点一下棋盘就可以开始新的对弈，而以前的设定保持不变。
图1：字符界面的井字棋程序的运行过程
需要说明的是，在处理双人对战时，虽然程序不会调用AutoDone和e_fun函数，但是程序把参与对弈的第二个人当做“电脑”，即，用来标志电脑的变量被用来标识第二个人，这样可以减少变量的个数。比如ComputerFirst=1时，则表示第二个人先下，MansTurn=0时，则表示当前该第二个人落子。
3. 核心算法及源代码
3.1 定义的数据结构和变量
由于本程序采用的核心算法是极大极小值算法，所以，在实现算法之前，必须定义一些数据结构来保存生成的状态节点。因此，我定义了State结构：
struct State //该结构表示棋盘的某个状态，也可看做搜索树中的一个节点
{
int QP[3][3]; //棋盘格局
int e_fun; //当前状态的评估函数值
int child[9]; //儿女节点的下标
int parent; //双亲节点的下标
int bestChild; //最优节点（评估函数值最大或最小）的儿女节点下标
}States[MAX_NUM]; //用来保存搜索树中状态节点的数组
豫公网安备41160202000603
站长QQ:729038198
关于我们
投诉建议