资源描述：
《五子棋算法,学习算法的一个例子应用.pdf》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、基于人机对战的五子棋游戏页码，1/5VCKBASEOnlineHelpJournalNo.8基于人机对战的五子棋游戏浙江大学计算机系(310027)胡朝晖五子棋是一种受大众广泛喜爱的游戏,其规则简单,变化多端,非常富有趣味性和消遣性。这里我们设计和实现了一个人机对下的五子棋程序,采用了博弈树的方法,应用了剪枝和最大最小树原理进行搜索发现最好的下子位置。本文介绍了我们设计的五子棋程序的数据结构、评分规则、胜负判断方法和搜索算法过程这几个部分。一、相关的数据结构关于盘面情况的表示,以链表形式表示当前盘面
2、的情况,目的是可以允许用户进行悔棋、回退等操作。CListStepList;其中Step结构的表示为:structStep{intm;//m,n表示两个坐标值intn;charside;//side表示下子方};以数组形式保存当前盘面的情况,目的是为了在显示当前盘面情况时使用:charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];其中FIVE_MAX_LINE表示盘面最大的行数。同时由于我们需要在递归搜索的过程中考虑时间和空间有效性,我们只找出就
3、当前情况来说相对比较好的几个盘面,而不是对所有的可下子的位置都进行搜索,这里我们用变量CountList来表示当前搜索中可以选择的所有新的盘面情况对象的集合:CListCountList;其中类CBoardSituiton为:classCBoardSituation{CListStepList;//每一步的列表charFiveArea[FIVE_MAX_LINE][FIVE_MAX_LINE];structSte
4、pmachineStep;//机器所下的那一步CreatePDFwithGO2PDFforfree,ifyouwishtoremovethisline,clickheretobuyVirtualPDFPrinterfile://C:Documents%20and%20SettingsxiongweiLocal%20SettingsTemp...2004-6-24基于人机对战的五子棋游戏页码，2/5doublevalue;//该种盘面状态所得到的分数}二、评分规则对于下子的重要性评分,我们需要
5、从六个位置来考虑当前棋局的情况,分别为:图1实际上我们需要考虑在这六个位置上某一方所形成的子的布局的情况,对于在还没有子的地方落子以后的当前局面的评分,主要是为了说明在这个地方下子的重要性程度,我们设定了一个简单的规则来表示当前棋面对机器方的分数。基本的规则如下:1.判断是否能成5,如果是机器方的话给予100000分,如果是人方的话给予-100000分;2.判断是否能成活4或者是双死4或者是死4活3,如果是机器方的话给予10000分,如果是人方的话给予-10000分;3.判断是否已成双活3,如果是机
6、器方的话给予5000分,如果是人方的话给予-5000分4.判断是否成死3活3,如果是机器方的话给予1000分,如果是人方的话给予-1000分5.判断是否能成死4,如果是机器方的话给予500分,如果是人方的话给予-500分;6.判断是否能成单活3,如果是机器方的话给予200分,如果是人方的话给予-200分;7.判断是否已成双活2,如果是机器方的话给予100分,如果是人方的话给予-100分;8.判断是否能成死3,如果是机器方的话给予50分,如果是人方的话给予-50分;9.判断是否能成双活2,如果是机器方
7、的话给予10分,如果是人方的话给予-10分;10.判断是否能成活2,如果是机器方的话给予5分,如果是人方的话给予-5分;11.判断是否能成死2,如果是机器方的话给予3分,如果是人方的话给予-3分。实际上我们对当前的局面按照上面的规则的顺序进行比较,如果满足某一条规则的话,就给该局面打分并保存,然后退出规则的匹配。注意这里的规则是根据一般的下棋规律的一个总结,在实际运行的时候,用户可以添加规则和对评分机制加以修正。三、胜负判断实际上,我们是根据当前最后一个落子的情况来判断胜负的。实际上我们需要从四个位
8、置判断,以该子为出发点的水平,竖直和两条分别为45度角和135度角的线,我们目的是看在这四个方向是否最后落子的一方构成连续五个的棋子,如果是的话,就表示该盘棋局已经分出胜负。具体见下面的图示:图2四、搜索算法实现描述注意下面的核心的算法中的变量currentBoardSituation,表示当前机器最新的盘面情况,CountList表示第一层子节点可以选择的较好的盘面的集合。核心的算法如下:voidMainDealFunction()CreatePDFwithGO2P
