围棋中的数学思想.doc

围棋中的数学思想李岩峻 （02010327）（东南大学 机械工程学院，南京 210096）摘要：围棋是一项起源于中国的古老的游戏，是对弈双方的策略竞争。在共361点的棋盘上，选择自己的落子方式中蕴含着或简单或高深的数学原理。借助于数学工具，我们能更加明白的理解围棋对弈中的种种现象。Abstract: weiqi is one of the oldest game originated in China.It is a competitive strategy between two sides. In a total of 361 points on the board, choosing their own stone contains simple or profound mathematical theory. With the aid of mathematical tools, we can understand various phenomena in the game of weqi.关键词：围棋、博弈论、化归、数列Keywords:weiqi,game theory,transformation,sequence of number1、 引言 围棋，起源于中国，可以说是最早产生的一种棋类。相传围棋为尧所造，已经有4000年的历史。最初围棋可能与天文有联系，后来逐步变为纯粹的策略游戏。围棋的规则很简单，可以理解为双方抢占棋盘上的空间，对弈双方谁围起的空间越大谁就获得胜利。这与如今的市场经济体系是有相似之处的。 博弈论是二人在平等的对局中各自利用对方的策略变换自己的对抗策略，从而达到取胜目的理论与方法。其最早期的研究对象就是象棋，桥牌，赌博等。所以也可以用博弈论中的方法来研究围棋。 在围棋的一些基本概念，如死活，围空，实地与势中都蕴含着数学的原理。本文将关注围棋本质、行棋技巧上的数学原理。二、围棋中的博弈论与计算机围棋 围棋虽然出现的早，规则也比较简单，但是由于棋盘的广阔与行棋过程中的变化，使这个问题非常复杂。可以说，即使是专业的棋手，也不可能通晓围棋中的每一招。 围棋的直接参与者有两人，双方要选择的战略必须是针对对手所选择战略的最优反应，双方都希望尽可能的比对手获得更多实空从而赢得胜利。运用博弈论的方法来研究围棋，是一种自然而然的想法。或者说，围棋是博弈论的一个很好的研究对象。 由于本人对围棋和博弈论的了解都很肤浅，所以在本文中只是进行一些大概的叙述。对于围棋的状态空间，我们可以这样分析。每一个格点可能的情况有3种，即有黑子，白子，或者没有子。棋盘格点格，当不考虑具体的围棋规则时，状态空间的大小为。这个数有多大呢？打个比方来说吧，假设全世界五十亿人者来下围棋，每人每天下一盘，要下完盘棋就得花年，而现在人类所知道的宇宙的历史也不过才200亿年，即年。一般来说，象棋，国际象棋与围棋相比较要小很多（当然也非常大）。这个数字与真实值相比是偏大，因为许多棋形根据围棋本身的规则是不可能出现的。对于围棋的行棋，如果考虑最简单的情况，第一手黑棋走有361种选择，第二手白棋走有360种选择，以此类推，行棋的可能性有361！种，这绝对是一个天文数字。与361！比起来，也只能算是小巫见大巫了，两者相比，相差竟达倍。即使动用一台每秒钟能够列出十亿种变化的电子计算机，要列完361！种变化也得花上年。不过这个值也是比真实值大的，因为根据围棋的规定有些地方不能走子，有些地方死子被提以后又能重复。正因为有这么多的行棋方式，所以围棋变化无穷，可谓千古无同局。相对来说，如象棋，国际象棋，他们本身的棋子数量是不变的（除非被吃），但是棋子本身可以运动。相对来说，象棋的行棋可能性要小一些。 以上数字表示围棋这个研究对象已经是很复杂了。那么评估函数更加凸显了这个问题的困难。在我们平时下棋的过程中，总会去尝试寻找所谓的“最大的一手”。也就是走在哪里获得的最多。这个问题在收官时可能还比较容易得出结论，但是在布局或者中盘时想要确定对棋力不是很高的人是困难的，即使对专业棋手，他们的意见往往也分歧很大。高手之所以这么下，是他在长期的实践与研究过程中总结得出的，是一种感觉。比如对于实地与势这对矛盾，下一手可以稳定获得一定的实地，也可以取外势放弃实地，此时外势就像股票，也是你的资源，但是它的利益不稳定，将来可能让你大赚一笔，也可能毫无用处。所以，我们很难得到准确的评估。其他的棋类，比如象棋、国际象棋等，他们的利益是集中的表现在子上的。比如车是最厉害的，兵与车相比不那么重要。这些棋类争夺的焦点是有限个棋子的吃与被吃，故每一手棋的利益比较好估计。 用理论方法来分析围棋是困难的。人类利用自己编写的程序和超级计算机，已经击败了国际象棋的世界冠军，但是，现在能够击败业余高手的计算机程序还没有出现。可以说，围棋是人类直觉胜利最后的坚固堡垒。现在围棋计算机程序大多是通过运用模式匹配和博弈树这两种在国际象棋计算中取得很好效果的算法，再加以细加工来进行计算、落子的。这样的算法对于围棋来说效率低，效果也不好。人们现在在寻找新的突破性的算法，但到目前为止仍没有太大的进展。三、围空效率的数学思想 有一句棋彦叫“多子围空方胜扁”，其意思是用多颗棋子围空的时候，棋型要尽量走成方形，也就是要有立体感，要把棋子的效率最大化，这样能围城大空。扁的棋型所占目数少，子效很低，弹性小。这其实是一个约束条件下的最优化数学问题。 下棋时我们总是希望用尽量少的子围出尽量大的空。当所用的子数一样时，围空越大越好。可以近似的把这个问题抽象为一个条件极值问题：矩形周长C为定值，求矩形面积S的最大值。即求，st。构造拉格朗日函数，则可以列出方程，解得，由于空的最大值在区间内一定存在，所以易得就是最大值取得的条件,也就是说矩形为正方形时围空的效率最高。有经验的棋手布局时就会注意这一点，将子下得高低错落有致，这样易于高效的围出空来，不至于下出扁平的臃肿的所谓“愚形”。 当然，关于围空效率的问题，还有很多的棋彦，比如“金角银边草肚皮”，“莫压四路，休爬二路”，“七子沿边活也输”等等，这些道理都较易明白，这里就不再赘述了。四、死活中的数学原理 围棋的死活是最基本的一项规则，可能也是唯一的规则了，所以死活的研究对于每一个棋手都是非常重要的。在下围棋时的计算主要就是死活和目数。对于一块棋的死活的计算，最一开始我们利用较多的就是穷举法，将可能的走法试一遍，来判断棋的死活。当然这种方法最适用于简单的死活，比如一些初学者做的死活题，因为此时可能性不多，能够穷举出来。对于一些复杂的死活问题，化归的思想是非常有用和自然的，如果能够试法将复杂问题转化为自己已经知道结论的简单问题，就能对自己的分析起到指导意义。比如我们一看到若干步之后能够构造出经典的活棋形式，就可以断定这片棋是活棋。 在对杀的过程中往往要判断自己单个眼内的内气是否满足需求。眼中内气的求法可用数列通项的递推方法来计算。若大小为的眼位有口气，则大小为的眼有口气，与满足的关系是,，通过逐项相消的方法，可求得的通项公式为。我们可以将该结论进行验证，当，当，当，结果均与人们平时所熟悉数据的一致。当然，时的大眼是公活的，讨论其气数在实战中意义不大，但是，这样的分析问题的方法却是值得借鉴的，因为这种递推的方法有助于我们化繁为简，加快计算速度。五、围棋盘上格点数为的数学原理 纵横十九道，迷煞多少人。围棋的规则现在已经基本定型。围棋的发展经理了一个漫长的过程。如今棋盘为，也是经历了历史的演变。当然，围棋盘为什么是现在这个样子一直还是有争议的。但我们可以通过实地与外势的平衡来分析这个问题。 围棋盘上三路线被称为地线，在地线上行棋容易将低路上的空地围住。四路线被称为势，虽然不能完全控制住低路，但是对高路的围空很有帮助。我们可以看一个极端的例子。对于N路棋盘（一般最小的棋盘为九路，即），若地线全部被黑棋占领，势线全部被白棋占领（如图1所示），则双方的围空效率之差为图1，其中这一项当时单调递增，这一项也单调递增，所以整个式子是单调递增的。将N=18和N=19代入式子中，我们得到，可见时取得最小值，即在十九路棋盘上行棋，双方的效率基本一致，使得取地与取势没有明显的优劣之分，这大大的拓宽了围棋的战术。所以围棋使用十九路棋盘不是没有道理的。6、 结语 通过本文以上的讨论，我们看到了围棋是异常复杂与有趣的。它本身就是双方博弈的一种典型情况。围棋的道理与现实生活其实是紧密相关的，比如弃子、脱先、以及取势取地。这些特殊境况下的决策其实我们都会遇到。当然，很多情况下每个人找到的“最大的一手棋