经典中国象棋博弈原理(徐心和)

中国象棋

计算机博弈原理中国象棋计算机博弈原理棋局表示着法生成评估函数博弈搜索开局库与残局库系统建模根本约定立足红方向上进攻状态演化方程：

——棋谱(红方)(黑方)中国象棋棋局演化过程棋局状态展开示意图红方红方红方黑方黑方Depth1Depth3Depth4Depth2Depth0红方走棋时展开深度为4的博弈树

棋局表示

BoardRepresentation通常我们使用状态集合来表示n

时刻的棋局状态。即——棋局状态矩阵——棋子状态矩阵——棋子位置矩阵——比特棋盘矩阵棋盘表示与棋盘矩阵

矩阵元素为数偶，表示棋盘坐标值。行向路向棋子表示法国际象棋KingRookKnightQueenBishopPawn中国象棋KingRookHorseCannonGuardElephantPawn红子帅车马炮仕相兵Null字母代号krhcbep兵种编码12345670象棋明星兵种编码020408060c0a0e黑子将车(砗)马(码)炮(砲)士象卒字母代号KRHCBEP兵种编码－1－2－3－4－5－6－7象棋明星兵种编码121418161c1a1e黑子中的砗、码、砲将在不便区分车、马、炮的红黑方时使用初始棋局状态的表示兵种红帅红车红马红炮红士红相红兵无子编码１２３４５６７０兵种黑将黑车黑马黑炮黑士黑象黑兵编码－１－２－３－４－５－６－７行向路向初始棋子状态的表示编码12345678910111213141516棋子黑将黑车黑马黑炮黑士黑象黑兵编码17181920212223242526272829303132棋子红帅红车红马红炮红士红相红兵棋子位置矩阵表示法k12345678910111213141516黑将黑车黑马黑炮黑士黑象黑兵k17181920212223242526272829303132红帅红车红马红炮红士红相红兵第1行表示编号为k的棋子在棋盘矩阵中的行号，第2行表示编号为k的棋子在棋盘矩阵中的列〔路〕号。对于初始棋局比特棋盘表示法路向比特向量

(Vertical）行向比特向量

(Horizon)注意：#表示计算比特向量〔二进制数〕对应的十进制整数行向路向比特棋盘与棋局的布尔条件比特棋盘用以记录棋局的某些布尔条件。如果比特棋盘中对应某一格的位是“1”，那么这一格上的条件就是“真”；如果是“0”那么对应的条件就是假。布尔条件就是在“哪些格子上符合你所定义的条件”。比方，“棋盘哪些位置有棋子？”“棋盘哪些位置有红棋棋子？”“棋盘哪些位置有车？”……这给计算机上的表示带来很大方便：12个字节，96位便可以表示一种条件〔高6位为0〕。比特棋盘预置表法在着法生成中具有重要的地位，而且在评估中可以方便地判断棋子相互的联系和威胁。初始行、路比特向量对应数值#B——比特向量索引值一个10位〔9位〕比特向量B可以表示一路〔行〕棋子的分布，它又可以有一个正整数#B作为索引，这将为今后的棋盘分析带来巨大方便；表示路向棋子全部可行分布情况的索引值范围为0—210-1=1023；表示行向棋子全部可行分布情况的索引值范围为0—29-1=511；这样通过索引值就可以找到相应棋子的分布情况。棋局的哈希数(H)与哈希变换黑将黑车黑马黑炮黑士黑象黑兵k12345678910111213141516kM-1-2-2-3-3-4-4-5-5-6-6-7-7-7-7-7红帅红车红马红炮红士红相红兵k17181920212223242526272829303132kM1223344556677777对应64位随机数哈希变换棋局的哈希数(H)与哈希变换为异或算符，H为64位数形成哈希数（值）由当前棋局PM生成64位随机数H

便构成当前棋局的索引值，与棋局形成单向对应， 即由P

可以生成H，但由H

无法产生P。

哈希变换没有反变换！着法生成原理

MoveGeneration着法生成是博弈树展开的关键环节着法的表示相对着法：马八进七，炮5平2——非完整信息，需要与当前局面结合着法算子的运算功能：提-动-落-吃提址——from即此着的出发位置；动子——moved〔chessmanmoved〕即走动的棋子；落址——to即着法的到达位置；吃子——killed〔chessmanCaptured〕即吃掉的棋子。对着法的要求：合法性、完整性、有序性着法生成的棋盘扫描法确定走动的棋子〔moved〕找到该棋子的当前位置〔from〕根据象棋规那么，扫描棋盘，逐个找到全部合理落址〔to〕〔考虑制约条件、有效区域、本方占位、对方占位等〕如果落址为本方棋子，那么不可行；假设为对方棋子，那么可以吃子〔Captured〕如果到达落址，构成“将军”〔叫杀〕，那么应该给对方以提示——“将！”着法生成的棋盘扫描规那么区域定义：定义棋盘有效区域定义红方半区定义黑方半区定义红方九宫定义黑方九宫

字符说明：A-area,R-red,B-black,P-palace提址(from)为(i,j)的动子着法生成规那么Captured提址(from)为(i,j)的动子着法生成规那么Captured提址(from)为(i,j)的动子着法生成规那么Captured棋盘扫描法遇到的问题虽然在着法的表达上，棋盘扫描法最为直观、简洁，但实战意义不强。因为扫描过程大量耗时：扫描动子、提址、制约条件、合理区域、双方占位、吃子等都是动态生成的，尤其区域判断和棋子种类检测等，时间开销巨大。对于吃子着法和非吃子着法无法分别生成，只能全部生成，再做筛选。模板匹配法

可以为某些动子设计“模板”，只要匹配到提址，便可以迅速找到落址。通过单项比特矩阵比对，实现“本方子那么止，对方子那么吃”，完成“提-动-落-吃”内容确实定。比较适合使用模板的动子为马和相〔象〕。走马匹配模板预置表法棋盘状态确定之后，各子的可行着法是确定的。预置表的思想是把某种棋子在棋盘每个合理位置上，所有可能的棋盘状态下的合理着法预先存储起来，生成一个小型数据表集合。在生成着法时，通过查询，取代各种计算。预置表的实质是用空间换时间，即牺牲一定的内存空间加速程序的运行速度。预置表初始化很费时，但只需在程序开始运行时初始化一次，而且占用内存空间不大。预置表法棋子布局的布尔行向量形式 [101000010]非吃子着法的落址为 [000110100]可能的吃子着法的落址为 [100000000]炮行着法预置表项举例动子为炮提址为〔i,6〕炮着法的预置表总的空间占用计算每一行棋子的可行排列数恰好对应于9位二进制数〔有子为1，无子为0〕，即29=512种情况〔项〕。考虑到炮在行向的9种可能位置，预置表的规模即为 9*512项。分别考虑吃子着法与非吃子着法〔2倍〕考虑路向情况，那么总表规模为2*9*512+2*10*1024=29696项每项占用4字节，那么总空间占用量为116k预置表的使用动子〔炮〕的提址〔i,j〕由第i行的比特向量和炮在第j位置查找对应的预置表项，分别得到吃子着法的比特向量和非吃子着法的比特向量；吃子着法仅为“可能”，还要判断“本方子那么止，对方子那么吃”；查找该行本方棋子比特向量，与吃子着法比特向量“与”，输出为1那么为非法着法；查找该行对方棋子比特向量，与吃子着法比特向量“与”，输出为1那么为合法吃子着法，得到落址；由该落址便可以得到“吃子”。评估函数在难以判断输赢的情况下识别棋局的好坏，可行的方法就是对局面进行量化通过为棋局“打分”，评判棋局的好坏。由于评估需要大量的象棋知识，仁者见仁，智者见智；评估函数的设计便成为机器博弈中最为人性化和模糊化的局部。目前对于评估函数取得共识的观点，应该包括如下局部：

固定子力评估值—e1(m)

车-600，炮-285，马-270相-120，士-125兵、卒-20帅、将无穷大值，具体数值可以给6000红方为正值，黑方为负值

棋子位置评估值—e2(m,i,j)

各兵种在棋盘的不同位置上权值不同可由三维数组给出：三维数组可以按兵种分解为假设干个二维数组，而且要区分红方和黑方x分别为各兵种代码红车位置评估值(m=r)车坐大堂分值最高！马窝心和马卧槽大不相同！红马位置评估值(m=h)当头炮分值较高！红炮位置评估值(m=c)红兵位置评估值(m=p)可见进入九宫的兵顶大车！棋子灵活度评估值—e3对各兵种而言，每多一个可走位置就加上一定分值。如设定：兵 15 士 1 象 1 车 6 马 12 炮 6 将 0

棋子配合评估值—e4重点是车马炮的配合与牵制。过河兵牵手可加120分。连环马、担子炮、霸王车等都可以考虑加分。将帅平安评估值—e5此项多从盘势上加以考虑。多子归边、空头炮、当头炮、沉底炮、将帅位置等，都要给予一定的惩罚或奖励分。评估函数的计算本方为正值，对方为负值，其代数和即为当前局面评估值。显然，总值为正对我方有利，负值对对方有利。绝对值的大小说明双方棋势的差距。不难看出，评估函数中涉及到的权值系数可能多达上千个，都需要认真选择与权衡。——系统开发难点。博弈搜索引擎

〔Gamesearchengine)博弈搜索引擎搜索策略—广度优先〔Breadth-firstsearch〕 深度优先〔Depth-firstsearch〕 迭代深化〔Iterativesearch〕搜索技巧—截断/剪枝〔cut-off〕 剪枝〔pruning〕 扩展/延伸〔extended〕搜索结果—返回值/倒推值/局面评估值最正确路径/当前着法〔Thebestmove〕广度优先搜索——近根为先深度优先搜索——远根为先博弈树分析博弈树上的每一个节点都代表一个棋局，棋手就是要在众多的叶子节点上挑选一个“最正确的路径与局面”作为自己的选择，从而反推到当前的着法。中国象棋博弈树的庞大是可以想象的。如果按照每一步平均有45种可行着法，每局棋平均走90步，那从开始局面展开到分出胜负，那么要考虑种局面。据说，这一天文数字要比地球上的原子数目还要多，即使用世界上最快的计算机进行计算，直到地球消灭也无法算出第一步的着法。搜索法是求解此类图模型的根本方法无法搜索到最终的胜负状态，只能靠评估。搜索的目标——如何在有限深度的博弈树中找到评估值“最正确”而又不剧烈波动的最正确棋局——目标状态。最正确路径〔Principalcontinuation〕——从当前状态出发到达最正确状态的路径，它代表着理智双方精彩对弈的系列着法。最正确着法〔Thebestmove——Rootmove〕——最正确路径上的第1步棋。所谓“不剧烈波动”就是说最正确棋局不是在进行子力交换与剧烈拼杀的过程当中。搜索策略的划分A类——穷尽搜索〔Exhaustivesearch〕B类——选择性搜索〔Selectivesearch〕C类——目标导向搜索〔Goaloriented search〕“一着不慎，满盘皆输”于是，看得远〔搜索的深〕，看得准〔真正找到指定深度内的最正确的平稳棋局〕，便成为搜索算法的根本着眼点。显然穷尽搜索成为人们首选的搜索策略。蛮力搜索〔Brutesearch〕一般采用广度优先搜索一层层展开，一层层搜索，因为“穷尽”而没有风险，不会漏掉展开深度内的最优解。假设计算机搜索节点速率为1M/秒，中国象棋B=45〔分枝因子B=40~50〕下表为在不同的给定时间内到达的搜索层数。给定时间1秒1分1小时1天1年10年100年搜索层数3.634.705.786.628.178.779.36出路在哪里？由于完整的博弈树过于庞大，盲目搜索所能到达的层数十分有限，在象棋博弈中几乎没有实用价值。假设想在指定时间内将搜索深度加以提高，一方面需要改进硬件与优化程序代码，提高单位时间内搜索的节点数；另一方面就需要像人类棋手一样有选择性地进行搜索，即对博弈树进行必要的裁剪〔cut-off/pruning〕。奠基者——香侬教授香侬(ClaudeShannon)教授早在1950年首先提出了极大-极小算法〔MinimaxAlgorithm〕，从而奠定了计算机博弈的理论根底。

Shannon,ClaudeE.,Programmingacomputerforplayingchess[J],PhilosophicalMagazine, Vol.41:256-275,1950.博弈树特点分析博弈树不同于一般的搜索树，它是由对弈双方共同产生的一种“变性”搜索树。红方为走棋方，它在偶数层的着法选择是要在其全部子节点中找到评估值最大的一个，即实行“Max搜索”。红方称为MAX方。而其应对方——黑方在奇数层的着法选择那么是在其全部子节点中要找到评估值最小的一个，即实行“Min搜索”。黑方称为MIN方。红方红方红方黑方黑方Depth1Depth3Depth4Depth2Depth0红方走棋时展开深度为4的博弈树极大极小搜索〔Min-MaxSearch〕MAXMAXMIN1298765433213由此产生最正确路径和最正确着法MAXMAXMIN5298761431244MaxMin搜索〔2〕由此产生最正确路径和最正确着法α-β剪枝搜索一种基于剪枝〔α-βcut-off〕的深度优先搜索〔depth-firstsearch〕。将走棋方定为MAX方，因为它选择着法时总是对其子节点的评估值取极大值，即选择对自己最为有利的着法；将应对方定为MIN方，因为它走棋时需要对其子节点的评估值取极小值，即选择对走棋方最为不利的、最有钳制作用的着法。MAXMAXMIN45682434α剪枝〔1〕由此产生最正确路径和最正确着法

α=4在对博弈树采取深度优先的搜索策略时，从左路分枝的叶节点倒推得到某一层MAX节点的值，可表示到此为止得以“落实”的着法最正确值，记为α。显然此值可作为MAX方着法指标的下界。在搜索此MAX节点的其它子节点，即探讨另一着法时，如果发现一个回合〔2步棋〕之后评估值变差，即孙节点评估值低于下界α值，那么便可以剪掉此枝〔以该子节点为根的子树〕，即不再考虑此“软着”的延伸。此类剪枝称为α剪枝。MAXMAXMIN13682154α剪枝〔2〕7491224由此产生最正确路径和最正确着法

α=4剪枝效果差异很大不难发现，和最正确着法关系密切什么是最正确着法？怎样找到最正确着法？〔1〕〔2〕β-剪枝〔1〕174298MAXMINMIN77由此产生最正确路径和最正确着法β=7同理，由左路分枝的叶节点倒推得到某一层MIN节点的值，可表示到此为止对方着法的钳制值，记为β。显然此β值可作为MAX方无法实现着法指标的上界。在搜索该MIN节点的其它子节点，即探讨另外着法时，如果发现一个回合之后钳制局面减弱，即孙节点评估值高于上界β值，那么便可以剪掉此枝，即不再考虑此“软着”的延伸。此类剪枝称为β剪枝。β-剪枝〔2〕835791MAXMINMIN8426由此产生最正确路径和最正确着法448β=4β剪枝和α剪枝具有同样规律剪枝效果与最正确着法的位置密切相关 与博弈树展开的顺序密切相关〔1〕〔2〕需要指出的是α-β剪枝是根据极大-极小搜索规那么进行的，虽然它没有遍历某些子树的大量节点，但它仍不失为穷尽搜索的本性。α-β剪枝技巧的发现，一下便为博弈树搜索效率的提高开创了崭新的局面。Knuth和Moore重要奉献1975年给出了α-β算法正确性的数学证明。α-β剪枝算法的效率与子节点扩展的先后顺序相关。在最理想情况下〔极小树〕，其生成的节点数目为（D为偶数）（D为奇数）而蛮力搜索（D为搜索深度）可见不做任何剪枝仅能搜索到一半深度如何才能得到极小树？不难看出，如果最左路的分枝就是最正确路径，亦即理智双方最为精彩的对弈着法序列，那么就可以将右路各分枝陆续剪掉，从而使α-β搜索的节点数仅为极大树的。为了得到最好的节点扩展顺序，许多搜索算法在着法〔节点扩展的分枝〕排序上给予特别的关注。比方在着法生成〔节点扩展〕时，先生成吃子着法，尤其先生成吃分值高的“大子”着法，因为由此产生着法更有可能是最正确的。面向着法排序的算法围绕着法排序，已经出现许多优秀的搜索算法与举措。如：同形表法〔Transpositiontable〕吃子走法的SEE排序杀手走法〔Killerheuristic〕未吃子走法的历史启发排序〔Historicheuristic〕类比法〔Methodofanalogies〕等。有人将α-β剪枝作用延伸到多个回合之后，于是又出现了深层α-β剪枝〔Deepα-βcut-off〕算法。也取得很好效果。α-β窗口搜索

〔α-βwindowssearch〕从α-β剪枝原理中得知：α值可作为MAX方可实现着法指标的下界β值可作为MAX方无法实现着法指标的上界于是由α和β可以形成一个MAX方候选着法的窗口也便出现了各种各样的α-β窗口搜索算法。α-β窗口的搜索算法围绕如何能够快速得到一个尽可能小而又尽可能准确的窗口，也便出现了各种各样的α-β窗口搜索算法。如Fail-SoftAlpha-BetaAspirationSearch〔渴望搜索〕MinimalWindowSearch〔最小窗口搜索〕PrincipalVariableSearch〔PVS搜索〕Negascout搜索宽容搜寻〔Tolerancesearch〕等。迭代深化搜索

〔Iterativedeepeningsearch〕不难想像，深度为D－1层的最正确路径，最有可能成为深度为D层博弈树的最正确路径。Knuth和Moore分析说明，对于分枝因子为B的博弈树，利用剪枝搜索D层所需时间大约是搜索D-1层所需时间的倍。如果取B=36，每多搜一层就要花上原先的6倍时间。迭代深化搜索于是CHESS4.6和DUCHENSS课题组开始采用逐层加深搜索算法。先花1/6的时间做D-1层的搜索，找到最正确路径；同时记载同形表、历史启发表、杀手表等有价值的着法评估信息；以求到达D层最好的剪枝效果。目前机器博弈引擎普遍采用迭代深化搜索策略。迭代深化的时间复杂度深度优先的迭代深化搜索D层搜索的总结点数为所以深度优先的迭代深化的时间复杂度为值得关注的是，由于一系列剪枝算法的使用，使得此时的平均分枝度可以数量级地减小。许多算法已经做到

B=2~5启发式搜索〔Heuristicsearch〕具体问题的领域决定了初始状态、算符和目标状态，进而决定了搜索空间。因此，具体问题领域的信息常常可以用来简化搜索。此种信息叫做启发信息，而把利用启发信息的搜索方法叫做启发性搜索方法。利用象棋的领域知识〔启发信息〕设计博弈搜索的启发式算法或方法，在着法排序中就有许多成功的应用。这里需要特别提及的那么是平静搜索、空着搜索和兑子搜索等。平静搜索〔QuiescentSearch〕α-β搜索使用的是给定深度搜索，当局面变化剧烈的时候，虽然已经到达搜索的最大深度，但此时评估函数的返回值并不能准确地表示当前局面的情况。举个简单的例子，某个叶节点上红车吃掉了黑炮，但是下一步红车会被黑方吃掉。如果在此叶节点调用评估函数，返回值肯定对红方十分有利，但会引起判断失误。平静搜索判断局面是否剧烈振荡的准那么是走棋方是否还有吃子走法，一直延伸到走棋方无吃子走法，也就是相对平静的局面。将军延伸〔CheckExtension〕是指当本方受到对方将军时所进行的扩展。由于逃避对方对本帅攻击的解将着法不多，所以我们可以对当前节点的搜索深度增加一层，以更准确地评估攻击的危险性。唯一着法延伸〔One_ReplyExtension〕。当本方受对方将军的时候，并且解将着法只有一步，这时候由于搜索量不大，我们在将军延伸之外，还要对其进行额外的延伸。启发式搜索兑子延伸〔RecaptureExtension〕。搜索过程中，如果出现A棋子吃掉对方的B棋子，随即Ａ棋子又被对方吃掉，那么也要对这样的局面进行延伸，以保证对兑子进行准确的评估。空着搜索〔NullMove〕是在1993年由ChrillyDonninger最先提出的。NullMove的思想是放弃本方的走棋权利，让对方连续走棋，如果得到的分值还大于原先的值，说明对方没有“硬着”可施，于是在此分枝下搜索的意义已经不大，免于搜索。NullMove危险性比较小，实现较为简单，剪枝效果明显，现已被棋类博弈广泛采用。负极大值算法

〔NegaMaxalgorithm〕博弈搜索是一种“变性”搜索。在偶数层进行“Max搜索”，而在奇数层进行“Min搜索”。这无疑给算法的实现带来一大堆麻烦。Knuth和Moore充分利用了“变性”搜索的内在规律，在1975年提出了意义重大的负极大值算法。它的思想是：父节点的值是各子节点值的变号极大值，从而防止奇数层取极小而偶数层取极大的为难局面。MAXMAXMIN1298765433213Min-Max搜索由此产生最正确路径和最正确着法-3-2-1NegaMaxNegaMaxNegaMax搜索负极大值算法

〔NegaMaxalgorithm〕此时需要特别注意的那么是，如果叶节点是红方〔走棋方〕走棋，评估函数返回RedValue-BlackValue，如果是黑方〔应对方〕走棋，那么返回BlackValue-RedValue。另外，由于负极大值计算等价于“Min搜索”，所以这里只进行β剪枝，非常有利于编程实现和提高搜索速度。开局库设计〔Openingbook〕象棋博弈三大阶段：开局、中局、残局。虽然有时在中局就决出了胜负而没有残局，但所有的对局都必须有开局。开局是开始的10～20个回合，对战双方各自展开子力，占据棋盘的有利位置。中国象棋讲究的是快速出动子力，各棋子协调作战，并且尽早占据中心位置。从开始就进行搜索，容易犯战略性错误。借助成熟的开局棋谱，建立开局库。开局库设计开局库中通常存放了数以十万计甚至更多的棋局；如何能够快速准确地搜索到对应的棋局成为开局库设计的关键技术之一。国际象棋的成功经验说明，开局库最好是采用Zobrist哈希技术加以实现；开局库作为棋局的索引值，记载常用着法；可以采用的着法，常常不止一个，每个着法都对应有输赢统计比率、作者偏好权重等，以便使用时选择。一般还应该具有自学习的功能，将新的对弈结果补充进来，并且不断自行调整比率与权重值。为异或算符，H为64位数形成哈希数（值）残局库〔Endga