[讨论]黑白棋中的数学模型

qxfy

什么是黑白棋
黑白棋(Reversi、Othello)，也叫苹果棋，翻转棋，是一个经典的策略性游戏。它使用8x8的棋盘,由两人执黑子和白子轮流下棋，最后子多方为胜方。随着网络的普及，黑白棋作为一种最适合在网上玩的棋类游戏正在逐渐流行起来。目前国内主要的黑白棋游戏站点有Yahoo游戏、中国游戏网、联众游戏等。

一般的棋类，往往有功有守，攻守之间有一种平衡，而且随时可以转换，因此，先手一方即使先进行攻击也未必得胜。由此可以说，一般的棋类之所以变化无穷，根本原因在于其包含了攻与守这既对立又统一的两个方面。它们在胜负的天平上位置相同，相互抑制，一切取胜走法只不过是围绕着攻与守来进行罢了。

黑白棋也是这样。我们知道，任何事物的两个对立面之间的斗争都是围绕着事物的发展规律而展开的。象棋的两个对立面之所以是攻与守，无非是源于其取胜之道：即吃掉对方的将（帅），不进攻当然不行。因此，在确定黑白棋中的对抗的两种力量时必须意识到：这两种力量抗争的最终目的与黑白棋的目的应该是统一的：即最后子多方为胜方。


如果你玩过黑白棋这个游戏，应该知道每个边角乃兵家必争之的。用数学的语言来表达就是：设P1为角棋位的价值，P2为边边棋位的价值，P3为内棋位的价值，有，P1&gt2&gt3,这只是主观粗糙的判断，认真分析，我们便不难发现，每边
各个棋位的价值还是略有差别的，众多内棋位的价值也是有等级差别的；随着双方下棋，每个棋位的价值都按照一定的规律随着变化（价值规律）。显然，棋手们下棋都喜欢争取价值大的棋位，一旦占据价值大的棋位，并且力争保持它的价值增无减，那么，胜利便不远了。

我的问题是：如果能够建立一个数学模型来描述上述价值规律，那么我们就可以编写一个电脑黑白棋手程序（深蓝二代）。这个想法是不是很有诱惑力？如果你感兴趣的话，请加入讨论吧。这里提供一个类似的参考模型，见《数学模型》（第二版）任善强  雷鸣编著，重庆大学出版社。P219页《围棋中的数学模型》一文。


p.s. 《英雄》挺好看的，难得看到如此精彩的国产电影。画面洁净，古朴美观，情节一波三折，引人入胜，好看啊！



［此帖子已被 qxfy 在 2003-7-26 19:36:28 编辑过］

happy2003

嘿嘿，一下子又转到了《英雄》
大家一起来讨论呀

dcyu

我曾经做过黑白棋,我开始对棋盘的附值是这样的,
角900,内角-600,边150,内边-50,中间4*4的点0
后来改变了想法:角900,内角-600,其他0
这种估价也不是最好的,因为这是一种静态估价,还有动态估价的方法.
在不同行棋步数时,价值不一样,但是我刚开始的这种估价方法的智能就
已经相当高了,若不是专门下黑白棋的人输的可能性非常大,下载见:
<A TARGET=_blank HREF="http://www.csdn.net/cnshare/soft/12/12266.shtm">http://www.csdn.net/cnshare/soft/12/12266.shtm</A>(Dos版)
<A TARGET=_blank HREF="http://www.csdn.net/cnshare/soft/11/11147.shtm">http://www.csdn.net/cnshare/soft/11/11147.shtm</A>(Windows版)
(我和同学一起做的)
国内最好的黑白棋网站是http://blacwet.myrice.com
网站中yanwl的程序是最新版的,是采用后一种估价方法的,
其实黑白棋最重要的我觉得并不是估价,而是剪枝,还有方法,有两种方法
一种是考虑价值最大,另一种并不估价,而是计算下一步或下几步自己可走
的点或&quot;富裕手&quot;,这些方法都是不错的,但是后一种方法我们当时编的时候
测试效果并不好,而目前最强的黑白棋是用后一种方法的,还有就是模式识别
的方法,当时我们的程序进微软首届软件设计决赛时,知道的就是李开复博士
对黑白棋模式识别方法,将棋盘分为4个部分,每份4*4,进行对已有棋谱的
模式识别,据说这有助于进行图象识别的测试.此外我发现目前世界上第三
的黑白棋程序还用到了神经网络,因为它还有学习的功能,下一盘棋后可以学习,
将学习样本输入计算机,让它具有更高的智能.

e-message

dcyu

黑白棋是我在大学阶段做的最得意的一个作品，智能方面已经非常高了，就是我自己对它的胜率也只有10%左右，但是令我自己感到惊奇的是我对黑白棋的算法仅仅用到了计算机算法中的回溯算法，而估值可以说是静态的，但是它对人的胜率都是如此之高，更不用说当今最强的黑白棋软件了。

其实棋类游戏是没有象我们今天所谈的数学建模这样确定的，因为本身是博奕游戏，不可能有所谓的什么最优方案，只有博奕算法，这些算法几乎都是按照一种模式去进行的，就是本方考虑让自己价值最高、而敌方价值最低的步去下，而考虑若干步后的情形则是交叉的进行这样的计算价值，这种方法称之为极大极小法，这个和数学建模中的一些优化问题非常类似，当你提出一个好的算法的时候，将会建立一个模型，就是计算价值的模型，而后通过设想今后的棋局进行计算价值，我在我的程序中用回溯算法实现了这一过程，效果非常不错。

dcyu

下面我贴一段网上摘下来的与棋类有关的算法基础的内容：

    现在有如图示的这样一个棋局，轮到电脑下棋。现在它发现有这样三个地方可以下：e3,c3,c5。这三种下法分别会形成三种局面：A、B、C。如果是人在下棋，就会思考：那一种下法更好呢？比如A被别人占角，B没什么变化，C占了别人的角。当然棋手会选择下C。电脑也是如此，它会对每一种棋局评一个分，比如它判断，如果被别人占角，就减80分，相反占别人的角就加80分。那么A=-80分,B=0分,C=80分。电脑会选择下C。电脑程序对棋局评分的部分，称为“估值函数”(Evaluation Function)。真正的估值函数当然不会这么简单。它会用到技巧篇提到的如行动力、潜在行动力、余裕手、边角判断、稳定子等综合因素来判断。具体的估值函数，我会在“估值函数”一节中详细讲述。

初始棋局(-1)

------------------+------------------

|                 |                 |

e3                c3                c5

(A)               (B)               (C)

    接下来，如果人就这么判断。那么它顶多也就是个初学者。为什么呢？因为它不会推理，碰到对手弃角之类的战术，如“边角判断”中示例的一些情况，就输得一塌糊涂了。当然，可以告诉电脑，碰到“边角判断”中的几种情况，就如何如何下。但是，真实的棋局是非常复杂的，电脑（也包括人脑）几乎不可能对动态的棋局给出静态的评估。因为实际对局总会出现这样那样的情况，是无法预先估计的。碰到这些情况，人就会向后推几步，看一看会是怎样的一个局面。一些棋类大师往往可以推十几步甚至更深。电脑也是如此。

    还是刚才那一幅图的演化。

-

-

-

电脑下棋

-

-

对手下棋

-

　
初始棋局

------------------+------------------

|                 |                 |

e3                c3                c5

-----+-----        ----+----        -----+-----

|  |  |  |  |      |  |  |  |      |  |  |  |  |

f2 f3 f4 f5 f6     c2 d3 e6 f5     b6 c6 d6 e6 f6

+84+36+12 +5 -1    +11 -1 +6 +6     +6 +0 -5 +3 +5 　

    电脑在自己下棋以后，把对手的下棋情况也推理出来。然后加以评分。（最下一排是电脑评估的得分）这一次电脑又如何下呢？这时电脑假设对手是高手。如果电脑下e3，对手就会下对电脑最不利的情况f6。同样，电脑下c3，对手就会下d3，电脑下c5，对手就会下d6。这三种情况，c5是最不好的(因为c5的下一步d6的得分最低)，c3与e3一样。因此电脑会下c3或者e3。用程序化的语言这样描述：

    电脑从棋盘初始状态出发，以后双方轮流下子，形成一种倒树状结构。树的层数就是电脑搜索的深度。在树状结构的叶子节点，对棋盘状态进行估值，即估计形式的好坏。得出一个分值。将此分值赋给叶子节点，之后，如果父节点该电脑下棋，则将子节点的最大节点值赋给其父，如果父节点该对手下棋，则将子节点的最小节点值赋给其父。（就是说，四级节点把最大值赋给三级节点，三级节点把最小值赋给二级节点，二级节点把最大值赋给根节点...）以此类推，得到根节点的值。具有和根节点一样值的二级节点即为电脑该下的位置。

    这里读者会有个疑问：电脑为什么要假设对手是高手？这是因为，如果你认为对手不是高手，但是不能说对手每一步都会下错。比如你送对手一个角吃。对手如果吃掉了，岂非损失惨重？当然，如果你确定对手不会吃你的角，你也可以下，但是前提就是“你确定对手不会吃你的角”。也就是你完全明白对手的战术。所以说如果一个程序完全了解另一个程序（或人）的下法，它也可以用针对性的下法，这将会更具成效。
　
   如图所示棋局，设电脑为白棋，推理深度为2，可以形成如下的树：（数字为节点值）

初始棋局

-

-

白棋下棋之后

-

-

黑棋下棋之后

估值
初始棋局(-1)

------------------+------------------

|                 |                 |

e3(-1)            c3(-1)            c5(-5)

-----+-----        ----+----        -----+-----

|  |  |  |  |      |  |  |  |      |  |  |  |  |

f2 f3 f4 f5 f6     c2 d3 e6 f5     b6 c6 d6 e6 f6

+84+36+12 +5 -1    +11 -1 +6 +6     +6 +0 -5 +3 +5

结果:应该下e3或c3

　
具体实现的伪算法:

类似于经典的八皇后问题

function MiniMax(depth:Integer; Position TPosition)ouble；//得到最佳位置的x，y坐标


begin

//根节点depth=depthmax；叶子节点depth=0；

if (depthmax-depth) mod 2=0 then       //电脑下棋的节点
    value：=-MaxInt；                  //节点赋初值,初始化为一个不可能达到的最小值         
else                                   //电脑下棋的节点
    value：= MaxInt；                  //节点赋初值,初始化为一个不可能达到的最大值         


if depth=depthmax then max:=-MaxInt；

如果是叶子节点,进行估值,result:=估值；exit；

对于每一个合法的可下棋的位置 do

begin

    保存棋局；

    下棋；

    s：=MiniMax(depth-1, Position)；    //递归调用

     //选择节点中最大或是最小的值

if ((deepmax-depth) mod 2=0) and (value &lt; s)then  value:=s;
else   if (value&gt;s) then  value:=s;

//如果值大于根节点值则赋值
if (depth=deepmax) and (value&gt;max)then  

begin
    max:=value;
    max_x:=i;        //x坐标
    max_y:=j;        //y坐标
end;


恢复棋局；

result：=value；

end；

qxfy

请教dcyu,你在上文中所配的图形好像和文章不匹配，我看不懂，能解释一下吗？

路过

要在论坛里用文本图形有转门的软件，论坛提供了下载，点这儿啊，呵呵
<A TARGET=_blank HREF="http://www.shumo.com/bbs/showtopic.asp?id=784&forumid=1&page=3">http://www.shumo.com/bbs/showtopic.asp?id=784&forumid=1&page=3</A>