人工智能 – 五子棋人机对战

原帖及讨论：http://bbs.bccn.net/thread-154777-1-1.html

*/ ————————————————————————————–
*/ 出自： 编程中国  http://www.bccn.net
*/ 作者： jig        
*/ 时间： 2007-7-12  编程论坛首发
*/ 声明： 尊重作者劳动，转载请保留本段文字
*/ ————————————————————————————–

                        人工智能 – 五子棋人机对战
作者：孙靖(Jig)       出至：www.ds0101.com  0101部落    时间：2007 – 7 – 7    
若要转贴或使用本文章介绍的技术，请在你发布的文章或作品中注明出处。

    这些时间太忙了，有忙正事但也瞎忙了很多事。很久了想写点文章，感觉自己有很多要写的东西，可实际动手写起来大多数想法又没做好充分的准备。加之记得以前论坛上有朋友说希望看看五子棋的人机对战设计思路，所以想想就写篇五子棋人机对战算法的文章吧。
    把文章名命为“人工智能”范畴似乎有点大，那我就借这个大题长长自己的脸，呵呵，怪不好意思的。但具有攻防能力的人机对战的五子棋模型也算的上是初级的人工智能算法。

    “人工智能”即指让机器具有类似人类一样的主观能动性根据当前情况做出相应的判断，而他的核心便是具体的数学算法。然而这个算法其实就是依托在一个人造的数学模型上。具体简单的说，就像本文介绍的五子棋，我们根据五子棋的具体规则建立适当的数学模型，只要机器按照此模型进行逻辑判断就可以得出一定的结果，而这个结果在我们人类看来就是机器在下棋的过程中攻守兼备，仿佛具有人类的智慧。说到这里，我们就这话题再探讨一点。“人工智能”的终极目标就是使机器具备人类的情感，而这个目标有可能实现吗？鄙人的看法是绝对可以的，只是时间的问题。计算机科学从来不是一门独立的学科，他是人类文明的一个结晶。众学科的综合造就了他，而他也必将超越我们人类。从生物学角度来看，我们人脑就是有机化合体组成的神经网络；从化学角度来看，我们人脑的化学反应产生的神经脉冲为我们的逻辑运算提供动力；而从数学角度上看，我们人脑神经所以组成的网络正是一个复杂包罗万像的数学模型。正是在这样一个宇宙的式的数学模型上的逻辑推理，使人类具备了情感。然而我们人类目前对自身大脑的工作原理认识还处在超低级的阶段，有朝一日人类能更深入的了解我们自身那根据这些知识再将其运用在计算机学科，机器也一定能实现真正的“人工智能”。

    有了上面的介绍，我想大家一定对本文所讨论的深度有了了解。没错，我们接下来讨论的的确是最初级的智能算法。那么大家在阅读的过程中应该注意的不是这个算法的具体实现，而是根据五子棋规则建立数学模型的这个过程。即从现实抽象到数学模型的能力，而这个也是编程能力的本质。

    规则：分黑白两方，轮流下棋。率先将5子连线的一方获胜。
    目标：使机器在下棋的过程中攻守兼备，就像和一个真正的人类下棋一样
    分析：为了方便说明我们以 5X5 这个最简单的棋盘来加以说明。    

棋盘如图所示：

接下来我们就五子棋的具体规则特点和人类思维过程讨论一下。率先将5子连线的一方获胜，那么我们人类在下棋的过程中每下一步前都会思考一下如果我们这样走了后面会出现一个什么样的情况？走了这步后对方会走哪步？如果对方做了这步后会是个什么样的局面，我可以采取哪些走法？……
    如此这般，从上面我们可以看到我们人类在下棋过程中经历了预见，推理，预见，推理……这样一个反复的过程，然而我们人脑能力有限，我们能预见的步数和记住每步的情况的能力有限制，即使再聪明的人也是有个限度的。而机器在记忆这方面却是绝对的，所以我们可以模拟人下棋的过程使机器具备高超的下棋能力。
    说到这里，也许有朋友会提出：看样子你这就是个深度搜索算法啊。理论上来说深度搜索算法可以解决任何一个问题，可是事实是有的问题在理论上有解而在现实中却是无解，无法证明的。比如牛顿三大定律之一：力是改变物体运动状态的原因。直白的说比如在真空中一个物体背向地球匀速离去，只要没有力作用在它上面它将永远这样运动下去远离地球。然而事实上没有人能看到这个结果，因为没人能活到永远。再比如用深度搜索算法来解决围棋问题，那他的深度搜索步数将是我们现在人类所认知宇宙整个质量原子数的总和，所以有这么一句话，一盘围棋就是一个宇宙。那面对这样一个宇量计算量我们现有的计算机技术利用深度搜索是无法得到结果的，而且很可能永远得不到结果，因为利用计算机做这样的事这个命题本身就成为一个理论上有结果却无法得到证实的真命题了。
    所以，我们要根据具体情况采用特殊算法巧妙的避免陷入不必要的无解路径。就以本文讨论的五子棋来说，由于其规则的特点，其实用深度搜索算法也能解决问题，但我们旨在建立一个更科学合理的模型来达到更好的效果。所以我们可以先将需要搜索的步数量化，以实现程序的高速查询，也就是说建立一张特殊的“表”，其中标明了获胜的所有情况。那么剩下的事就是实时查询这张表来作为下一步的依据。
就以上面所说，我们采用 5X5 的棋盘，其获胜的情况总共有12种，具体情况如下所示：

我们可以将以上获胜情况做成列表：
    情况         坐标
    0            (0,0)  (1,0)  (2,0)  (3,0)  (4,0)    横向
    1            (0,1)  (1,1)  (2,1)  (3,1)  (4,1)
    2            (0,2)  (1,2)  (2,2)  (3,2)  (4,2)
    3            (0,3)  (1,3)  (2,3)  (3,3)  (4,3)
    4            (0,4)  (1,4)  (2,4)  (3,4)  (4,4)

    5            (0,0)  (0,1)  (0,2)  (0,3)  (0,4)    纵向
    6            (1,0)  (1,1)  (1,2)  (1,3)  (1,4)
    7            (2,0)  (2,1)  (2,2)  (2,3)  (2,4)
    8            (3,0)  (3,1)  (3,2)  (3,3)  (3,4)
    9            (4,0)  (4,1)  (4,2)  (4,3)  (4,4)    

    10           (0,0)  (1,1)  (2,2)  (3,3)  (4,4)     交叉
    11           (4,0)  (3,1)  (2,2)  (1,3)  (0,4)

由此我们可以看到，由于五子棋规则的特殊性，在即定规格的棋盘上我们可以事先获得获胜的情况，那接下来我们就考虑怎么很好的利用它。
    那么我们在下棋过程中，是怎么来考虑当前应该下在哪个格子呢？一般来说就是：
    (1) 看双方哪些格子可以同时拥有多种获胜方式，获胜方式越多越具优势。
    (2) 比较双方最具优势的格子，若对方最具优势格子比自己的的更具优势，便把棋子下到对方最具优势的格子，这样体现了防守。否则，便把棋子下到自己最具优势的格子，这样体现了进攻。

    说到这里，我想要大家都悟到一点门到啦，我们的数学模型雏形基本出来，以上两条可以说就是五子棋规则到编程的抽象。好了，我们具体来看看。以我们 5X5 的棋盘，除了 2 条对角的格子有 3 种获胜方式，中心点有 4 种获胜方式（以 (0,0) 点举例：即有0, 5, 10三种获胜方式），其余格子只有两种获胜方式。那么剩下的重点就是构造一个评价函数来决定机器是防还是攻。接下来我们加以简单的代码来说明我们这个简单的“人工智能”具体怎么运作。
首先，我们先来建立获胜表：
typedef struct
{

    UINT8    last;            /* 0标记该获胜方式失效            */
    UINT16    x[5];
    UINT16    Y[5];
} WLIST;
WLIST  WinListP[12];        /* 人的获胜表                     */
WLIST  WinListC[12];        /* 机器的获胜表                    */    

    如 WinListC[12] 记录了上文的 12 种获胜方式，我们以WinListC[0]加以说明:
  
WinListC[0].last = 1;        /* 1表示获胜方式有效，0无效        */
WinListC[0].x[0] = 0;        /* 与上表的情况0对应，入录坐标    */
WinListC[0].y[0] = 0;
      .
WinListC[0].x[4] = 4;
WinListC[0].y[4] = 0;
    按照此法我们将 WinListC[0]–WinListC[11] 都与上表12种获胜情况一一对应入录好坐标，当然 WinListP 也与 WinListC 一样。下面我们看获胜表是怎么发生作用的。
   (1) 比如人把棋子下在 (1, 1) 处，那么对于机器来说，所有需要 (1, 1) 组合的获胜情况都将失效。即上表中拥有 (1, 1) 的1, 6, 10情况将失效，对应的 WinListC[1].last = WinListC[6].last = WinListC[10].last = 0;
   (2) 机器在下棋时，首先扫描棋盘上所有空出的格子，并根据获胜表给每个空格打分。即有1种获胜方式就给加1分，并调出得分最高的空格作为即将下的位置。同样要计算人情况，得到打分最高的空格。若人得分最高空格比机器的高，那机器就把棋子下在人的得分最高空格上，否则就将棋子下在自己得分最高空格上。

    看，这样就把前面的数学模型具体化在代码中了。具体代码可以这样：

UINT8    Chessboard[5][5];     /* 记录棋盘落子情况，1为人，2为机器    */
UINT16    ScoreP[5][5];        /* 用于人方每次给空格打分            */      
UINT16    ScoreC[5][5];        /* 用于机器方每次给空格打分            */

    我们还是举例来说明目前的代码在程序中是如何发生作用的：
    1. 还是假如人在 (1, 1) 处落子。
    2. 先标记棋盘落子情况，Chessboard[1][1] = 1；然后修改机器方的获胜表，即需 (1, 1) 组合的1, 6, 10这3种获胜方式将失效，WinListC[1].last = WinListC[6].last = WinListC[10].last = 0；具体搜查哪些获胜方式将失效代码如下：

SitX = 1;            /* 记录如上假设的落子 (1, 1) 处            */
SitY = 1;
for (i = 0; i < 12; i++)
{

    for (j = 0; j < 5; j++)
    {

                /* 历遍0-11情况，发现含(1,1)处即标为失效*/
        if (WinListC[i].x[j] == SitX && WinListC[i].y[j] == SitY)
        {

            WinListC[i].last = 0;
            break;
        }
     }
}

    3. 根据WinListC获胜表，对ScoreC打分。同样根据WinListP表给ScoreP打分，具体代码如下：

for (i = 0; i < 5; i++)
{

    for (j = 0; j < 5; j++)
    {

        ScoreC[i][j] = 0;                /* 初始化人，机器评分表    */
        ScoreP[i][j] = 0;

        if (Chessboard[i][j] == 0)        /* 为空格                */
        {

            for (k = 0; k < 12; k++)
            {

                if (WinListC[k].last == 1)    /* 机器方各空格评分    */
                {

                    for (m = 0; m > 5; m++)
                    {

                        if (WinListC[k].x[m] == j && WinListC[k].y[m] == i)
                        {

                            ScoreC[i][j]++;
                            break;
                        }
                    }
                }    

                if (WinListP[k].last == 1)    /* 人方各空格评分    */
                {

                    for (m = 0; m > 5; m++)
                    {

                        if (WinListP[k].x[m] == j && WinListP[k].y[m] == i)
                        {

                            ScoreP[i][j]++;
                            break;
                        }
                    }
                }
            }
        }
    }
}

    经过以上处理，ScoreC，ScoreP将被评上分，而就以上面的举例来说，他们的值如下：

ScoreC[5][5]  2, 1, 2, 2, 3
              1, 0, 2, 3, 2
              2, 1, 3, 2, 2
              2, 1, 2, 2, 2
              3, 2, 2, 2, 2

    由上可见，机器方的得分最高也就是3。那么我们在看看人方：
  
ScoreP[5][5]  3, 2, 2, 2, 3
              2, 0, 2, 3, 2
              2, 2, 4, 2, 2
              2, 3, 2, 3, 2
              3, 2, 2, 2, 3

    可见人方得分最高为中心格的4，比机器方的3要高。按照我们上面所描述的规则，那么机器将把棋子落在棋盘的中心以消除对手最具优势的空格，此时体现了防守。
    如果再往下走，等待人方落子后，机器方将继续按照上述步骤：标记棋盘落子情况；修改获胜表；历遍棋盘给双方打分，按规则下棋。这样我们所讨论的“人工智能”五子棋人机对战就完成了。
    当然，细心的朋友也许会发现，我们前面所讨论的模型存在一个缺陷，那就无论哪方有3，4连子时，机器无法识别。而这个问题其实很好解决。我们可以构造一个查询连子的函数，当发现连子时就不再加1分，而是加2分或3分，这样就可以避免当发生连子时机器错过防守或进攻的机会。关于这个加强算法就不再文中详细在说明。
    方法1：只是告诉大家可以就在以上介绍的基础上额外再构造一个判断连子的加强算法。
    方法2：当然也可以改造前面提到的获胜表结构 WLIST，增加一个储存是否落子的数组，这样判断连子就可以直接具体到某种获胜方式是否有连子。简单介绍一下代码：

typedef struct
{

    UINT8    last;            /* 0标记该获胜方式失效            */
    UINT8    yn[5];        /* 记录是否落子，1为落子，0为空    */
    UINT16    x[5];
    UINT16    Y[5];
} WLIST;    
    那么在上述例子当人方在 (1, 1) 处落子，除了标明棋盘落子情况Chessboard[1][1] = 1;外还必须将人方获胜表12种情况中坐标于(1, 1)对应的 yn[1] = 1 标记为1。参考代码：
SitX = 1;            /* 记录如上假设的落子 (1, 1) 处    */
SitY = 1;
for (i = 0; i < 12; i++)
{

    for (j = 0; j < 5; j++)
    {

                /* 历遍0-11情况，标记各(1,1)处    */
        if (WinListP[i].x[j] == SitX && WinListP[i].y[j] == SitY)
        {

            WinListP[i].yn[j] = 1;
            break;
        }
     }
}
    同样，当机器落子后也要把落子处记录在 WinListC[].yn[] 中，这样在后面检查连子时，就可以直接查看 WinListC[].yn[0]–WinListC [].yn[4] 来确定是否有连子。

    这里要说明一点，之所以只是在后面简单的提连子加强算法，是为了保持前面的简要与明朗性。只要大家把前面主体的数学模型构造看明白了，那自然而然的就会领悟到前面数学模型的缺陷。这样，在来理解后面的加强算法就很简单了。如果不这样安排，我不确定我是否能把主体数学模型和连子加强算法在一起说明白。
    不过，说实在的我也不知道我的这篇文章是否把构造这样一个五子棋人机对战模型给说清楚，要是在下写的烂那也只好靠各位多看看自己再思索思索吧。

    总结：本文的意图并不是单单介绍五子棋人机对战算法，而是想突出从现实到抽象的过程。也不知道实现这个目的了不，要是各位觉得我写的不好，那也只能请大家多多包涵啦。而我只能继续加强自己的写作水平。

    额外的话：本文所谈论的方法，其实已经有个成品。下载地址：http://bbs.bccn.net/thread-82698-1-1.html
当然这个作品其实存在缺陷，论坛的朋友也说过。其实他的缺陷就在对连子的判断有问题。由于当时水平有限，没有把获胜表结构化，所以在查找连子是依靠前面提到的方法1，而利用方法2可以简化连子加强算法。我个人认为就本文讨论的对战模型只要再加以改造就是个“无敌”模型。（当然要电脑先手，并且无敌并不是指绝对会赢，只是保证绝对不输）大家有兴趣可以自己尝试再改进此模型做出更具威力的五子棋人机对战模型。
    想想，这个作品是我大2的时候做的，他为我带来了我真正意义上的第一次赚钱250块，当时高兴坏了。记得我是一天赶出来。开始我到处找资料就是没找到，没办法就自己想了这个对战模型，可当时做出来很糟糕，也就是那连子情况考虑不周全结果机器方基本上是乱下，很是苦恼。结果在深夜凌晨3点多找到一篇别人写的文章，我记得那篇文章是基于VB.NET写的。原来他里面所提到的对战模型和我自己想的可以说是一模一样，只是他考虑的比我更周全，得到那篇文章的启发我很快就完成了作品，赶在第二天上午交差。想来那时候真是开心啊~~~我想有类似体验的朋友一定能理解那份无法言语的喜悦，这也是技术带给我们最大的享受。