五子棋人工智能的分析与实现
摘要：机器博弈是人工智能的一个重要研究分支，本文通过设计一个五子棋智能博奕程序，采用传统的博弈树算法，利用剪枝和极大极小树搜索最佳位置，从而实现人机智能博弈。并对现有算法存在的问题进行探究改进，最后给出程序实例，结果表明效果比较理想。关键词：五子棋；人工智能；博弈；
1主要传统算法
11博弈树传统的算法是采用博弈树法来设计程序。以甲乙两人下棋为例，甲有很多种落子方式，乙也有多种应对走法，如果把所有的走法列出来，自然就构成了一棵树，即为搜索树，也称博弈树。树的根结点为先手的第一步走法，下面的走法构成了树的子结点，直至棋局结束。显然，如果棋盘足够大，子结点数会以几何级数上升，而我们的任务是从这些子结点中寻找一个对己方最有利的结点，从而得到棋局的最佳走法。这必然是一个指数复杂度的过程，费时低效，无法搜索到最终结果（除了棋局结束），通常只能达到一个有限的深度，在有限的范围内来判断走法的好坏，得到一个局部最优解。23因此，有必要做一些调整改进，以提高算法的效率和质量。12极大极小算法极大极小搜索算法就是在博弈树在寻找最优解的一个过程，这主要是一个对各个子结点进行比较取舍的过程，定义一个估值函数F
来分别计算各个终结点的分值，通过双方的分值来对棋局形势进行分析判断。还是以甲乙两人下棋为例，甲为max，乙为mi
。当甲走棋时，自然在博弈树中寻找最大点的走法，轮到乙时，则寻找最小点的走法，如此反复，这就是一个极大极小搜索过程，以此来寻找对机器的最佳走法。其中估值函数通常是为了评价棋型的状态，根据实现定义的一个棋局估值表，对双方的棋局形态进行计算，根据得到的估值来判断应该采用的走法。棋局估值表是根据当前的棋局形势，定义一个分值来反映其优势程度，来对整个棋局
f形势进行评价。本程序采用的估值表如下：
状态眠二假活三眠三活二冲四假活三活三活四连五
分值
2
4
5
8
12
15
40
90
200
一般来说，我们采用的是15×15的棋盘，棋盘的每一条线称为一路，包括行、列和斜线，4个方向，其中行列有30路，两条对角线共有58路，整个棋盘的路数为88路。考虑到五子棋必须要五子相连才可以获胜，这样对于斜线，可以减少8路，即有效的棋盘路数为72路。对于每一路来说，第i路的估分为EiEciEpi，其中Eci为计算机的i路估分，Epi为玩家的i路估分。棋局整个形势的估值情况通过对各路估分的累加进行判断，即估值函数：
13r