象棋算法入门（转）

1万 · 2013-8-31 00:31

象棋中的技术主要分为2类，一、蛮力搜索，二、象棋知识的表示。目前网上大量的文间论及蛮力搜索技术，这些技术都很先进，也很正确，本文不涉及此项内容。对于象棋知识的表示，则内容与**相对少得多，大家都只是说要用到浅层搜索，局面评价函数什么的，但是几乎谁也没给出具体的编程的例子，本人由于象棋水平实在差得可以，所以也无法给出局面评价函数的实例，不过本人致力于知识的表示的研究，相信对象棋的知识表示还有略有效果的。为了论述方便，我们先从残局入手，介绍一下什么是象棋知识。在残局中，大家都知道，由于待选的棋步较少，因此可以进行更深ply的搜索，并与此相应引入一些特殊的技术，故而最终出现专用于残局的搜索算法。很多象棋软件就是这样处理的，在主搜索函数搜索到各叶结点时，判定是否是残局，如果是则用残局专用搜索函数来评价。但是，这实际是对残局错误的处理方法，在残局我们为什么要用搜索算法呢？完全可以应用知识来解决问题。会下象棋的人都知道，象棋残局经历多年的发展，其实早就有必然的结论了，（本人以前不知，后来才知道~）对于五子，甚至是6子还是多少子，本人不清楚，反正就是必胜或必败的了。比如说，单车必胜单马。。。如果有此必然性的结论存在，我们为什么还需要蛮力搜索呢？我们只要判定给定的局面，是否是我方一车对方一马，即可立即给出必胜或必败的结论了！！这就是知识的应用！

1万 · 2013-8-31 00:31

写过象棋程序的人都知道这里可以省下多少时间了，在每个叶结点上都去蛮力一番，怎么可能比我应用知识利害，应用知识，我只需对特定的局面进行静态分析，即可给出同样的结果，而时间仅仅是查表的时间。可见，对于残局，我们仅仅需实现一个大型的知识库就能完成以前残局搜索的功能了，你搜索再利害，再有B*算法，也不及静态局面评价来得速度与正确。具体的残局评价函数可以这样实现，针对不同的残局，转入不同的分支，比如单车单马，则进入该分支，然后对单车单马中，什么情况下必胜，什么情况下可以守和进行具体的判定。如何判定下面再介绍，反正你的任务就是将残局书找出来，将必胜和必败的局面用程序写出来就OK了，当然有特例反例的也要写，否则知识就不正确~。好了，通过上面的介绍，我们已经大概知道象棋中的知识是如何起作用的了，剩下的难度就是如何对各种残局局面进行编程了，为了后面论述方便，这里先提出一个概念，模式，也许有人的喜欢叫特征吧，反正意思一样。所谓模式，就是一类具有特定特征的象棋局面的总称。刚才介绍的单车单马局面，其实就是一个模式，在这个模式中，我们只需计算车的数目与马的数目即可，而对该子出现的位置不加限制。可见，模式就是拓扑抽象下保持某属性不变的总称。算了，费话不多说，直接继续。模式还可以针对位置进行，比如，巡河车。。，也可以是相对位置，马前卒。。，也可以是某种形式，二鬼拍门。。。，本人对象棋了解不多，不过下面一个模式是我知道的，为了后面讨论方便，你也得将就我而掌握一下~，山前马。什么是山前马，我也说不太清楚，大家可以找出象棋残局书来看，好象就是敌方的马和将相对于士的位置，即将马相对于士同侧则是山前马，异侧则是山后马，这也是一种模式，高级程序员应该可以写出程序来实现这种模式的判定吧~。

1万 · 2013-8-31 00:31

好了，前面介绍了静态的必胜残局的判定，现在接着讨论如何将此局面转化为胜局了。对于残局知识来说，有些知识极其复杂，具有非常强的方法性与技巧性，这些必胜的方法，不是谁谁都能想出来的，大多数复杂的必胜局面，都是一代甚至是数代象棋大师长期钻研后的心血与成果，特别是那些5子6子残局，其中的技巧令人叹为观止，正是基于此原因，本人立即结束了象棋项目的~。不过大家也不用灰心，由于记住这些必胜的方法需要大量的脑力，即使是特级大师照样无法兑现很大比率的复杂必胜残局，谁有那么好的**力，记住成千上万的模式下是如何取胜的~。除了我们的象棋程序~。知识在象棋程序中，是如何引导并兑现必胜的残局的？复杂的残局取胜有一定的技巧与策略的，即使以单车必胜单马这种极简单的局面即可看出。如果是用搜索算法，对于一些特殊的单车单马局面，也需要超过40步以上的步骤方可完成，这已经超过很多垃圾象棋程序的搜索能力了，包括以前我写的那个程序~。那么程序是如果引导并兑现必胜局面的？1、赶马山前。2、闷宫捉马。3、单车少马必胜。

1万 · 2013-8-31 00:32

象棋中，我们有定式吗？当然有，只是以前没有人详细提而已，下面以当头**为例解释定式。首先在残局中我们曾提过模式引导，好了，中局中也一样，模式引导其实就是定式。当我方出现当头**这个模式时，并有助攻的处于**架的车马或其它子力时，我们即进入了模式引导的状态，首先，肯定是助攻子力试吃对方各个棋子，其次，对方肯定是逃跑或保护或阻挡你的助攻子力，或者是解决你的当头**，反正双方都以定式的行为，一来一回参予当前的战斗，最后在有限分枝的考虑下，结斗结束，谁也没有获益~。对了，当然是谁也没有获益，本来大家就势均力敌，任何局面下，都很难有一方很容易就获益的~。即使在模式引导下，情况也是一样，但是，我们还是在该模式引导下来搜索与评价局面，为什么呢？因为很少获利，并不代表不获利，并不代表没有意义，在该当头**的模式局面中，我们通过抽吃的方法来获益是必然的方法呀，难道不用定式，还去用蛮力搜索？对了，我们就是通过模式引导，来快速判定定式的双方，谁先不能通过考验，谁又将杀法进行到了最后，使得必吃一子或是必占一先机等成立。通过定式类的模式引导，使得我们有机会，可以快速在大范围内用知识进行局面的评价与剪枝。比如，我们抽吃的助攻子力无法抽身，或找不到对方的孤子，或我们当头**被灭。。。，反正模式引导随时应各种异常而中止，定式成功或失败，失败了，即使该局面有当头**，还是和普通的沉闷局面没有两样，我们根本不必因为有当头**就进行更深更多的搜索，该局面唯一与其它局面不同就是我们用了一下当头**的模式引导而已。定式模式引导下，判失败是很快的，判成功却不易，即使定式引导成功，我们还需要进行完全的搜索才能最终确定我方是可以在该局面获利的，即进行半边的完全搜索，无论对方如何应答，我们必可给出一步，使得最终我们获利一子。

1万 · 2013-8-31 00:32

所以说，在局面评价函数中，大量引入基于模式引导的象棋知识，并通过模式引导的方法来判定与检测，这就未必仅仅是‘静态’的模式识别与评价力所能及的了。下面再讨论一些比较抽象的模式，即常规意义下的子力分布与形态评价，由于本人棋力极差，下面讨论纯属糊说八道，如果这样你都能编出程序来，那你的编程能力就真的不是一般的OK了。关键位置，象棋和真实的战斗一样吧，地利是可以转化为形式的优劣的，而且，不同的子在该位置上，起作用的方式是不同的，并且谁先占领该山头又是不一样的，有些关键的点位，对局势的发展有重要影响，双方必须优先抢夺，比如巡河车。。。，谁先巡了，那对方肯定就被压制住了，即使占领了该位置，对于如何突破应该也是有一定的方法和技术的。这就象是攻坚，在你占领山头时，我该怎么攻，你会怎么守，是有模式可以引导的，并且通过不同的子力的实例最终展现出来。简单点说，地形的优势一定是通过压制，牵制，调度，攻击等一整系列的模式引导来最终获得收益的，我的巡河车，只要成功挡住你各个子力渡河，那我就有更多的空间用来运送后方的子力到前线，这样，我就将地利优势，转化为整体推进速度，或局部兵力集结速度上的优势，这就是模式引导。但是这个模式引导是通过实例展现的，换句话说，双方当时在此子区域内集结的子力不同，应变的方式不同，才是最终评价该位置是否值得占领的最终判断，而不能仅仅依赖我占领了就OK了，那根本就没把知识用完全。套用前面曾感概过的话就是，我要想获利，占领该位置一定是整个模式引导中的第一步，但是占领后未必获利，我还需要通过整个模式引导流程来确证确实可获益才行。简单的例子是，你占领了一个极挂的位置，但是对方在该地根本就没有一个子投入战斗，那你占领那个山头有屁用~。关键位置的评价，进而展开模式引导是一个极复杂的行棋指导，它往往无法给出一步步具体的行棋，而是从大范围内影响我们的战略布局，它的影响是通过多步，长期的行棋中展现的，但是，它还是展现出模式引导的特性，既，该模式获利的方式，就是成功转向另一种更接近于最终获利的模式。

1万 · 2013-8-31 00:33

如果没有明显的证据证明，前一种模式，可以很高概率地转换为后继模式，那么，基于模式引导，即可判定该位置评价未必就是有效的占领了。当然，实际当中，由于这种高级抽象类型的模式比较难以通过模式引导的方式来验证的，因此，我们更多地借助于类似必胜残局评价的静态评价方式来评价。也就是大家熟知的对各种局面模式打分这种静态局面评价函数了，通过打分这种方式来对较复杂的非必然性的模式进行评价，这就是常规意义下的局面评价，也即虽然都是该位置的占领，但现在我们可以进行更细致的评价与预测，哪种模式更容易转化为未来的获利，而哪种又无法获利，都可在评价模式中详细列明。现在大家明白如何下手写评价函数了吗？不会还是什么子在什么位置就打多少分这么简单吧，那你的程序永远都写不大，别人的商业程序动则几W行，你得把位置的占领也用模式的方式来评价，就是多包含几个棋子进来，针对不同的子力配置或阵形配置来评价，这样才能更精准地评价关键位置的好坏，才能将程序写大~，当然威力也会更大。子力灵活度，很多**都说子力灵活度，我想子力的灵活度是依赖于具体的局面而判定的吧，所谓的子力灵活度，一定是以以多打少，或以更合适的局部棋形来展开获利的，没有地方投放战斗，子力灵活也没用。牵制，以少牵多，以小牵大，双方动掸不得，但是主动权在我方，我方随时可在需要时抽调出去，快速投入到其它可以获益的局部区域。分割、包围、以多打少、整体推进、前线攻击。。。，这些都是有模式识别的，并且都可以进行行棋引导的，反正老话一句，应用这些方法我们未必获利，但是，我们大多数行棋方案都是依据这些模式展开的，真正的人在下棋，没有谁会去蛮力搜索的，都是基于某种目的推荐各种可能的棋步，然后择优录取一步。反正谁的鬼点子多，谁识别的模式多，谁就更用能力把握复杂的局面，进行长远的预期。最重要的是，知识是我们可以在平时中掌握，然后在关键时应用的东东。台下几千年的功，台上1分钟。好了，本人棋力不佳，也举不出更多的例子来说局面评价函数该如何写，不过基本方法在这，相信各位高手肯定可以写出比本人好得多的程序出来。为了说明静态模式打分这种方法是怎样实现象棋知识的。下面将展开详细的说明，让大家对知识的应用有一些更深的感觉。我们先提一个概念，局部演化原理。人类生活中绝大多数过程都是局部演化的，大家也都适应这种原理，你仅仅是想拿一杯水的话，很显然你不会因为拿杯水，而将几十里外的情况考虑进来，所谓的蝴蝶效应，在智能计算中是不存在的。

1万 · 2013-8-31 00:33

绝大多数的过程，都是在局部的范围内展开的，在相对封闭的小范围内，显现定式性的演化，这就是局部演化原理。有时也称为独立演化原理。在人类生活中，人类很善于区分局部演化的范围，有时虽然2个对象很近，但我们也很容易识别出它们是分别参予不同的演化过程的，因此，如何提高独立演化区域的判定，就是人工智能必须实现的重要技术之一。好了，具体的智能理论比较复杂，大家也没必要参和，下面来看局部演化原理在象棋中的应用。局部战术，在局部范围内，双方有限参予子力的情况下，定式的发展。比如双车抓双马，车**抓双马等等，有一些技巧可以引用的，塞马腿，车驱马，最后同抓双马而获利等等。这些获利的模式可以从实战中自动总结而来，通过摈弃不必要的子力而简化局面，然后在实战局面中用该模式引导来检测，成功引导，再展开详细的评价与搜索。当然，实战中是否采用该局部战术，可以通过双方在子区域内投入的子力来判断。反正引导未必成功，但是要成功，这就是一些必然或很高概率下会采用的方法，这就是象棋知识的一种，是独立演化原理下基于知识的应用。当然实战中，也可直接利用独立演化原理，比如快速对当前局面进行划分，清除在子区域内因被挡，被封，被牵等无法参战的子力，在子力相对较少，范围较小的局面下，快速寻找一种获利的行为模式。一但找到某种获利的方法，再利用前面介绍过的模式引导的方式来验证该方法确实可行，再进一步进行大范围的全面的蛮力计算与评价。有了局部战术的观念后，我们可以展开更多的基于知识的描述，这些描述虽然未必可以通过模式引导的方式来验证，但是却是对我们获利是有效帮助的。进一步论述之前，我们先提一下什么是智能。所谓智能就是按照**所总结的模式，对未来进行预测的能力。因此预测能力是关键，而是否可引导又是另外的问题，只要我们有预测能力，即使无法引导到最终获胜，我们还是使用了知识。就以前面那个无法兑现必胜残局的象棋大师为例，他掌握的XXX必胜XXX，就是一种预测，一种知识。这就是各种静态局面评价函数的基本理论。

1万 · 2013-8-31 00:33

所以有人说，象棋人工智能中没有智能，只有技术，是错误的，程序员的工作，就是将象棋专家的知识表示出来。在某种模式下，预测将来必然获胜，这是知识，实际上，还有另一种较隐含的知识，那就是感觉，即在某种模式下，我们虽然无法预测必胜或是必败，但是，此种模式却可以对应较高的获胜概率，这已经就是一种知识了。为什么会有这种现象呢？每次出现了猫叫，小儿很大概率就要拉尿，但是我们却暂时无法知道其原因，但我们不知道其原因也没关系呀？只要能把握这种预测能力，就已是部份掌握了客观世界必然性的演化规律了。每次和隔壁的小王下棋，只要他去拉尿了，那我肯定就能赢他，怎么赢我也说不清楚，反正我每次都赢了，这就是预测能力~。另外特别要注意的是，预测能力不是凭空想象出来的，是通过实战演练，从实践中出总结出来的，如何准确地提出各种预测模式，正是各位特级大师长期实战演练的原因之一。当然，尽可能将各种不太可靠的获利预测能力（感觉），细化到必胜式的取胜模式与步骤，也是各位象师技术研究人员努力工作的方向。但是不论精确化的努力是否成功，模式预测能力已经是人类展现智能的能力了。好了，将预测能力与模式引导这两个概念分离后，我们即可展开基于模式的静态局面评价了。我们尽可能地准确划分整个局面中各自独立演化的子区域，然后根据各个子区域，分别按模式感觉与评价其最终获益的能力大小，这就是感觉~。可见，基于模式的评价中，不一定可被引导的模式才是有用的模式，只要该模式可预测将来获益，即是可用的知识。而这种模式如何获益，则由于各种原因我们暂时无法知道，但是我们就是知道双车抓双马，比车**抓双马来得高效与成功率高些，抗干扰能力强些。这种根据各种不同的模式，预测将来获利成功率及获利大小的能力，就是知识。现在大家明白静态的局面评价函数该如何编写了吧，首先你一定得是象棋高手，越是专家里手，这种按模式预测未来获益的能力就越精准，而整个的静态评价，就是针对各种不同的子区域模式，分别展开与评价的，这也是那些商业程序越来越大的主要原因。对了，忘了提为什么要用局部演化原理了~，用它就是为了限定真正固定演化的区域，进而减少计算量并提高模式复用率而已。