当前所在位置： >
热门微信号：
棋类游戏背后的那些算法
作者： 浏览数：0 用手机扫描二维码
阅读，只需一秒。精彩，尽在掌握！日,国际象棋世界冠军卡斯帕罗夫在一场挑战赛中以2.5∶3.5输给了“深蓝”,特别是最后一局,卡斯帕罗夫只走了19步...
日，国际象棋世界冠军卡斯帕罗夫在一场挑战赛中以2.5∶3.5输给了“深蓝”，特别是最后一局，卡斯帕罗夫只走了19步就投子认输了。这个结果震惊了全世界，要知道“深蓝”并不是人类，它只是一台几吨重的计算机而已。卡斯帕罗夫之前曾经和“深蓝”的前辈“深思”过招几次，“深思”每次都输得很惨。就在一年前，卡斯帕罗夫还曾经以4∶2战胜过“深蓝”的一个初级版本。卡斯帕罗夫曾预言计算机在2010年之前不可能战胜人类，但是IBM的科学家让这个结果提前了13年。创新工厂的创始人李开复博士在学校期间，也曾开发过一个黑白棋（Othello）的AI算法，据说还战胜了当时美国黑白棋世界冠军。还是那句话：“外行看热闹，内行看门道”，作为程序员我们应该知道这“神奇”的现象的背后一定是某种算法在“作祟”。棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。设计一个棋类游戏的AI算法，棋盘和棋子的建模是相对比较简单的部分，而游戏规则的建模相对比较复杂。很多情况下，越是简单的规则越难以建模，比如围棋，目前还没有一种有效的理论能够对围棋的“形”和“势”进行建模，使得计算机能像人类一样理解一个围棋棋局。那么棋类游戏的AI到底是什么原理？除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢？1. 博弈与博弈树博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如“二人零和、全信息、非偶然”博弈，也就是我们常说的零和博弈（Zero-sum Game）。所谓“零和”，就是有赢必有输，不存在双赢的结果。所谓“全信息”，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的“非偶然”，是指参与博弈的双方的决策都是“理智”的行为，不存在失误和碰运气的情况。在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动（也可能是棋子落子）的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。假设两个棋手（可能是两个人，也可能是两台计算机）MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树（Game Tree）。2. 极大极小值搜索算法极大极小值（Min-Max）搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的最大利益（令对手的最大利益最小化）的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。3. 负极大值搜索算法博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：max(a,b) = -min(-a, -b)简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。4. “α-β”剪枝算法有很多资料将“α-β”剪枝算法称为“α-β”搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。“α-β”剪枝算法维护了一个搜索的极大极小值窗口：[α,β]。其中α表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值（也就是MAX的最坏的情况）。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比α大，则更新α值（用这个最小值代替α），也就是提高α这个下限。而β表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值（也就是MIN的最坏的情况）。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比β小，则更新β值（用这个最大值代替β），也就是降低β这个上限。当某个节点的α≥β时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。5. 估值函数对于很多启发式搜索算法，其“智力”的高低基本上是由估值函数（评估函数）所决定，棋类游戏的博弈树搜索算法也不例外。估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力（棋力）、双方棋子占领的空间、落子的机动性、威胁性（能吃掉对方的棋子）、形和势等。6. 置换表与哈希函数置换表（transposition table）也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找操作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找操作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。7.开局库与终局库所谓的开局库和终局库实际上就是一种存储了各种开局和终局棋局信息的数据库。以开局库为例，开局库一般要存储开局的棋局，该棋局对应的各种走法和评估分数，有些开局库还统计了该开局最终的胜局次数、平局次数和负局次数，给出开局棋局的权重等附加信息供搜索时选择。推荐阅读——技术新书畅销榜No.1书号：978-7-115-38537-6作者：王晓华页数：420定价：79.00 元CSDN超人气博主、算法专栏达人王晓华力作算法领域小百科，广泛涵盖常用算法结构及其应用淋漓尽致展现算法本质，一本书玩转算法，尽享算法乐趣算法之大，大到可以囊括宇宙万物的运行规律；算法之小，小到寥寥数行代码即可展现一个神奇的功能。《算法的乐趣》从一系列有趣的生活实例出发，全面介绍了构造算法的基础方法及其广泛应用，生动地展现了算法的趣味性和实用性。其中，既有各种大名鼎鼎的算法，如神经网络、遗传算法、离散傅立叶变换算法及各种插值算法，也有不起眼的排序和概率计算的算法。王晓华 2005年毕业于华中科技大学机械设计与CAD专业，在中兴通讯上海研发中心从事光纤接入网通讯设备开发，目前任职EPON（以太网无源光网络）业务软件开发经理。长期在CSDN写作专栏，被评为算法专栏达人。
手机版地址：
微信号：turingbooks
打造图灵品牌 出版精品图书
TA的热门文章
推荐互联网微信帐号
热门文章排行
(), All rights reserved 京ICP备号-12棋类游戏算法有哪些
棋类游戏算法有哪些
编辑:少芬&
　　棋类游戏通常包含三大要素：棋盘、棋子和游戏规则，其中游戏规则又包括胜负判定规则、落子的规则以及游戏的基本策略。设计一个棋类游戏的AI算法，棋盘和棋子的建模是相对比较简单的部分，而游戏规则的建模相对比较复杂。很多情况下，越是简单的规则越难以建模，比如围棋，目前还没有一种有效的理论能够对围棋的&形&和&势&进行建模，使得计算机能像人类一样理解一个围棋棋局。那么棋类游戏的AI到底是什么原理?
　　除了棋盘和棋子的建模，棋类游戏最重要的部分就是AI算法的设计。目前棋类游戏的AI基本上就是带启发的搜索算法，那么常用的搜索算法有哪些呢?
　　1. 博弈与博弈树
　　博弈可以理解为有限参与者进行有限策略选择的竞争性活动，比如下棋、打牌、竞技、战争等。根据参与者种类和策略选择的方式可以将博弈分成很多种，比如&二人零和、全信息、非偶然&博弈，也就是我们常说的零和博弈(Zero-sum Game)。所谓&零和&，就是有赢必有输，不存在双赢的结果。所谓&全信息&，是指参与博弈的双方进行决策时能够了解的信息是公开和透明的，不存在信息不对称的情况。比如棋类游戏的棋盘和棋子状态是公开的，下棋的双方都可以看到当前所有棋子的位置，但是很多牌类游戏则不满足全信息的条件，因为牌类游戏都不会公开自己手中的牌，也看不到对手手中的牌。所谓的&非偶然&，是指参与博弈的双方的决策都是&理智&的行为，不存在失误和碰运气的情况。
　　在博弈过程中，任何一方都希望自己取得胜利，当某一方当前有多个行动方案可供选择时，他总是挑选对自己最为有利同时对对方最为不利的那个行动方案。当然，博弈的另一方也会从多个行动方案中选择一个对自己最有利的方案进行对抗。参与博弈的双方在对抗或博弈的过程中会遇到各种状态和移动(也可能是棋子落子)的选择，博弈双方交替选择，每一次选择都会产生一个新的棋局状态。
　　假设两个棋手(可能是两个人，也可能是两台计算机)MAX和MIN正在一个棋盘上进行博弈。当MAX做选择时，主动权在MAX手中，MAX可以从多个可选决策方案中任选一个行动，一旦MAX选定某个行动方案后，主动权就转移到了MIN手中。MIN也会有若干个可选决策方案，MIN可能会选择任何一个方案行动，因此MAX必须对做好应对MIN的每一种选择。如果把棋盘抽象为状态，则MAX每选择一个决策方案就会触发产生一个新状态，MIN也同样，最终这些状态就会形成一个状态树，这个附加了MAX和MIN的决策过程信息的状态树就是博弈树(Game Tree)。
　　2. 极大极小值搜索算法
　　极大极小值(Min-Max)搜索算法是各种博弈树搜索算法中最基础的搜索算法。假如MAX和MIN两个人在下棋，MAX会对所有自己可能的落子后产生的局面进行评估，选择评估值最大的局面作为自己落子的选择。这时候就该MIN落子，MIN当然也会选择对自己最有利的局面，这就是双方的博弈，即总是选择最小化对手的最大利益(令对手的最大利益最小化)的落子方法。作为一种博弈搜索算法，极大极小值搜索算法的名字就由此而来。
　　3. 负极大值搜索算法
　　博弈树的搜索是一个递归的过程，极大极小值算法在递归搜索的过程中需要在每一步区分当前评估的是极大值节点还是极小值节点。1975年Knuth和Moore提出了一种消除MAX节点和MIN节点区别的简化的极大极小值算法，称为负极大值算法Negamax。该算法的理论基础是：
　　max(a,b) = -min(-a, -b)
　　简单地将递归函数MiniMax()返回值取负再返回，就可以将所有的MIN 节点都转化为MAX节点，对每个节点的搜索都尝试让节点值最大，这样就将每一步递归搜索过程都统一起来。
　　4. &&-&&剪枝算法
　　有很多资料将&&-&&剪枝算法称为&&-&&搜索算法，实际上，它不是一种独立的搜索算法，而是一种嫁接在极大极小值算法和负极大值算法上的一种优化算法。&&-&&剪枝算法维护了一个搜索的极大极小值窗口：[&,&]。其中&表示在搜索进行到当前状态时，博弈的MAX一方所追寻的最大值中最小的那个值(也就是MAX的最坏的情况)。在每一步的搜索中，如果MAX所获得的极大值中最小的那个值比&大，则更新&值(用这个最小值代替&)，也就是提高&这个下限。
　　而&表示在搜索进行到当前状态时，博弈的MIN一方的最小值中最大的那个值(也就是MIN的最坏的情况)。在每一步的搜索中，如果MIN所获得的极小值中最大的那个值比&小，则更新&值(用这个最大值代替&)，也就是降低&这个上限。当某个节点的&&&时，说明该节点的所有子节点的评估值既不会对MAX更有利，也不会对MIN更有利，也就是对MAX和MIN的选择不会产生任何影响，因此就没有必要再搜索这个节点及其所有子节点了。
　　5. 估值函数
　　对于很多启发式搜索算法，其&智力&的高低基本上是由估值函数(评估函数)所决定，棋类游戏的博弈树搜索算法也不例外。
　　估值函数的作用是把一个棋局量化成一个可直接比较的数字，这个数字在一定程度上能反映取胜的概率。棋局的量化需要考虑很多因素，量化结果是这些因素按照各种权重组合的结果。这些因素通常包括棋子的战力(棋力)、双方棋子占领的空间、落子的机动性、威胁性(能吃掉对方的棋子)、形和势等。
　　6. 置换表与哈希函数
　　置换表(transposition table)也是各种启发式搜索算法中常用的辅助算法，它是一种以空间换时间的策略，使用置换表的目的就是提高搜索效率。一般情况下，置换表中的每一项代表者一个棋局中最好的落子方法，直接查找置换表获得这个落子方法能避免耗时的重复搜索，这就是使用置换表能大幅提高搜索效率的原理。
　　使用置换表最大的问题是置换表的组织和查找的效率。一般来说，置换表越大，查找的命中率就越高。但这个关系不是绝对的，当置换表大小达到一定规模后，不仅不会再提高命中率，反而会因为耗时的查找操作影响算法的效率。所以置换表不是越大越好，需要根据计算机的性能以及搜索的深度选择一个合适的大小。此外，为了查找操作更高效，通常都会用可直接访问的哈希表方式组织置换表，哈希函数的性能就成为影响置换表性能的重要因素。棋类游戏普遍采用Zobrist哈希算法。
　　7.开局库与终局库
　　所谓的开局库和终局库实际上就是一种存储了各种开局和终局棋局信息的数据库。以开局库为例，开局库一般要存储开局的棋局，该棋局对应的各种走法和评估分数，有些开局库还统计了该开局最终的胜局次数、平局次数和负局次数，给出开局棋局的权重等附加信息供搜索时选择。
下页更精彩：1
本文已影响人
棋类游戏算法有哪些相关推荐&>&&>&&>&&>&常见娱乐棋牌游戏算法
常见娱乐棋牌游戏算法
上传大小：3.67MB
常见棋牌游戏算法
综合评分：3.9（30位用户评分）
所需积分：1
下载次数：170
审核通过送C币
创建者：zhangguo5
创建者：zhangguo5
创建者：zhangguo5
课程推荐相关知识库
上传者其他资源上传者专辑
开发技术热门标签
VIP会员动态
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
android服务器底层网络模块的设计方法
所需积分：0
剩余积分：720
您当前C币：0
可兑换下载积分：0
兑换下载分：
兑换失败，您当前C币不够，请先充值C币
消耗C币：0
你当前的下载分为234。
常见娱乐棋牌游戏算法
会员到期时间：
剩余下载次数：
你还不是VIP会员
开通VIP会员权限，免积分下载
你下载资源过于频繁，请输入验证码
您因违反CSDN下载频道规则而被锁定帐户，如有疑问，请联络:!
若举报审核通过，可奖励20下载分
被举报人：
liuxiaochakan
举报的资源分：
请选择类型
资源无法下载
资源无法使用
标题与实际内容不符
含有危害国家安全内容
含有反动色情等内容
含广告内容
版权问题，侵犯个人或公司的版权
*详细原因：简单介绍常见的五子棋算法
程序的引擎部分主要采用了以下技术:
2 历史启发
3 alpha-beta 或 MTD(f)
4 增量式棋盘
5 增量式估值
6 真假禁手识别
1,2,3大家很熟悉，就不说了，下面简单介绍4，5，6：
[棋盘结构]:
标准五子棋棋盘是15*15=225，为提高效率，
我用了256的数组基本棋盘，因为是最基本的棋盘，所以称之为第一层。其中的16行和16列没用到。
static uint8_t&
&&&_layer1[256];
这样就能用一个字节的unsigned char做索引，称之为Pos. 低四位是x, 高四位是y.
下面三个个宏可以快速在x,y坐标与一个字节的索引之间相互转换。
#define POSX(p) (uint8_t)((p)&0x0f)
#define POSY(p)
(uint8_t)((p)&&4)
#define MAKEPOS(x,y)
(uint8_t)(((y)&&4)+(x))
容易想到，可以用3个数字分别表示 黑子，白子和空位:
#define White 0
#define Black 1
#define Empty 2
由于经常要在黑方和白方之间转换，所以定义了OPP宏
#define OPP(side) (uint8_t)((~side) &0x01)
还需要经常遍历棋盘，以下两个宏可完成这个工作：
#define ESB(p) for(p=0;p&=(BW-1)*16+BW ;p++)
{if(POSX(p)&=BW)
#define ESE() }
这是程序中的一个实例:
& switch(_layer1[p])
& case Black: TRACE("[ X ]\t");
& case White: TRACE("[ O ]\t");
展开后是这样
& for(p=0;p&=(BW-1)*16+BW
if(POSX(p)&=BW)
continue；
& & switch(_layer1[p])
& & case Black: TRACE("[ X
& & case White: TRACE("[ O
光有基本棋盘还不能判断棋形，五子棋有四个方向， 所以我们还要用4个数组来储存这四个方向的棋形， 而且黑白双方要分开放,
所以这是个三维数组，称之为第二层
static uint8_t&
&&&_layer2[2][4][256];
假如在H8点放了一个黑子， 那么I8再落黑子就是2连， 记做 _layer[Black][横向][I8] = 2连
四个方向按"横竖撇捺"来排序， 0是横向.
单线各个棋形已经定义成了FSP_*系列宏， 如 FSP_d4p，d表示被堵了一半， p指plus,
表示除了冲四外，还有附加手段,见下图
&&&---&&a冲一次，还可再往外冲，所以是plus
四个方向分开的棋形最终要还是要合起来分析， 用另一个数组表示， 称之为第三层:
static uint8_t&
&&&_layer3[2][256];
各棋形也定义成了FMP_*系列宏， 如 FMP_43 表示 四三
这样棋盘就基本完整了， 下面介绍算法。
把四个方向棋形合成一个很简单， 一个3就是三，两个3就是三三，查表即可得到。
而把基本棋盘变为4个方向的基本形相对较难，对此我用了以查表为基础的算法:
单个方向不管有多少格， 最终总是成五, 即使成六也是包含了五(当然还有长连等例外，特殊处理)，
所以"五"可作为最小查表单位
上图在a,b两个空位是什么形？
答: 应这么查:
首先把这个图转成索引，容易想到 1表示有棋子，0表示没有， 上图即 11010 = 26, 查表得
_xl_gene[26] = {0,0,7,0,5}；
查看头文件， 有以下宏:
#define FSP_d4& &
#define FSP_4& &
把这个结果套上去， 得a是FSP_4活四， b是FSP_d4冲四
那么长一点的图如何处理？
答: 分成数段来查，然后合并， 如下图:
[a]&&OO_O_&&=&&{0,0,7,0,5}
[b]&&O_O__&&=&&{0,4,0,4,3}
[c]&&_0__O&&=&&{3,0,4,4,0}
[d]&&O__O_&&=&&{0,4,4,0,3}
合并时取数值大的
{0,0,7,0,5}
__{0,4,0,4,3}
____{3,0,4,4,0}
______{0,4,4,0,3}
{0,0,7,0,5,4,0,3}
检验一下， 这个结果是对的
问题来了, 上面是都是两边没有堵住的情况， 如果有一边被堵住呢？ 或者两边都被堵住呢？
答: 把表扩大4被， 分别储存"不堵"，"左堵"，"右堵"和"两边堵"
四种情况，索引上新增的第6,7位分别是"右堵标记"和"左堵标记":
_xl_gene[10
11010]&&=&&{0,0,5,0,5}
a,b都是冲四
那么，中间有对方的棋子呢？
答: 无需考虑这种情况， 单看这五个格已不可能出棋。
a,b,c 不用考虑， 单查d即可
其它注意事项:
1 注意同一条线上的44
2 注意长连
[秘籍]&&在查表时， "o_" 等价于左堵的"x",
同理"_O"等价于右堵， 如下图
XXXXXX__XXa__XXXXXX
黑a不是活三，而是左右被堵的形， 诸位可自行验证。
把基本棋盘变为4个方向的基本形的算法介绍完了， 很明显，这个算法很慢，所以我在程序中预先生成一些中间结果，以提高计算速度:
uint8_t *_cache[2][BW + 1];
取名cache, 但它并不是高速缓存， 叫预生成表更确切些，有了这个表，每次计算棋形只需查一下就行了，速度自然大幅度提高。
基本棋盘介绍完了，下面介绍"增量式棋盘"的概念。 实际上"增量式棋盘"就是上面介绍的 _layer2和_layer3.
因为估值时要知道各个点的棋形， 每次都计算将很慢，所以用了增量式计算的办法，
每次添加或移走棋子，都立即更新_layer2和_layer3，保证它们永远是最新。
[增量式估值]
增量式棋盘是增量式估值的基础， 原理是把估值用到的一些东西(比如冲三的个数)做成增量式的， 化整为零，
大大减轻估值的负担。
[真假禁手识别]
假禁手其实就是假三组成的禁手， 所以关键是如何判断假三。显然，假三就是表面上看来是三，但实际上不能成四的形。
这里"表面上看来是三"可以直接从_layer2中得到， 而在那一点落一子， 就能看出它到底能不能成四。
但是， 光这样判断是不完整的， 五子棋有高级禁手的情况: 两个相关的三， 其中一个是不是假三取决于另一个是不是假三.
这种情况实际对局中时有出现, 所以需要对假三进行递归判断。进一步还有利用禁手解禁手的下法，这就是搜索选点的问题了。
类似于象棋的连将胜， 五子棋有VCF(冲四连胜)。幸运的时，用置换表可以很好地解决VCF问题，
许多上百步的局面都可瞬间解出。
但即使如此，一些几十分钟也解不开的局面还是存在的，所以对VFC扩展要有一定的限制，否则碰到那些局面时程序就死在那里了。
作为VCF的延伸， 更像象棋残局的VCT是根难啃的骨头，
经常一个局面算几十分钟也没有结果，所以xl里没有VCT扩展。看前面的贴子里
有讨论活三是否该估值的问题， 其实活三问题是VCT问题的一种， 如果不能算尽棋变法， 完全的"活三不估值"将无法实现。
已投稿到：
以上网友发言只代表其个人观点，不代表新浪网的观点或立场。