最近人工智能很火，常常有各类新闻，做为一个程序员多少要懂一点吧，将来万一用得着呢。有心想去了解一下，奈何能力有限，皮毛都没学会。好吧，既然无法系统学，就无论那么多，就从如今开始动手，一步一步的往前走，遇到什么问题就查什么资料。虽然最后不必定能作成什么，起码作的过程遇到问题解决问题，总能学会点什么。
从最简单的五子棋游戏开始，先用普通的规则实现一个电脑下棋的算法，姑且叫作AI算法。做为一个只用过linux环境的C语言，作到这一步也仍是须要走很多的路，还要学习很多东西才能作好。此次算是我头一回认真学习并且还坚持这么久，因此记录一下所学和这个过程。本文适合像我同样的新手。linux
废话说完，正式开工。
五子棋基本规则：
一、棋盘大小15x15
二、五个棋子连成一条线即为赢
三、黑棋先下
四、黑棋禁手先不考虑程序员
棋型基本术语：
5连：5个子连成一条线，已经赢了。
活4：有4个子在一条线，并且连线的两端没有对方的子。
冲4：（也有说眠4）有4个子在一条线，连线的一端没有对方的子，另外一端有对方的子。
活3：有3个子在一条线，并且连线的两端没有对方的子。
相似的还有冲3，活2，冲2，活1。
其余更专业的术语就不考虑了。web
极大极小值算法须要两个条件：
一、 零和博弈，就是你死我活的游戏。
二、 彻底信息，玩家知道以前的全部步骤，象棋、五子棋都是交替落子在棋盘上，以前的步骤都一目了然。
若是把五子棋下子全部可能都列举出来，就能够看作一个树的结构。以电脑AI的视角看,每一步往下走均可以看作是树，树的根节点为0开始。奇数层表示电脑可能走法咱们称之为MAX层，偶数层是玩家的可能走法咱们称之为MIN层。
显然，
MAX层，电脑须要选择对本身最有利的节点。
MIN层，玩家会选择对本身最有利的节点，也就是对AI最不利的点。
这就是极大极小值算法。算法
这里有个很核心问题，什么叫最有利什么叫最不利呢？下面用源码一步一步详细讲解评估函数的由来，再用评估函数解释什么棋对电脑AI最有利和最不利。数组
(下面代码用C语言写的，linux下x86环境编译运行)
首先第一步：定义分值，其中score_e枚举就是分值定义
直接把头文件贴出来，方便后面的代码理解。svg
#ifndef __COBAND_MAIN_H
#define __COBAND_MAIN_H
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#define DEBUG 0 //打开调试信息
#define M_SIZE 15 //棋盘大小为15x15
#define DEEP 3 //最大搜索多少层
#define check(x) (((x)<0) || ((x)>=M_SIZE)) //棋子坐标是否溢出
//棋子状态颜色
#define SPACE 0
#define WHITE 1
#define BLACE 2
/*计分板
分数随意定的,只考虑了不让四个方向上的分数加起来超过更高一级的棋型*/
typedef enum score_e
{
WIN5 = 100000, //5连
ALIVE4 = 10000, //活4
ALIVE3 = 1000, //活3
DIE4 = 1000, //死4
ALIVE2 = 100, //活2
DIE3 = 100, //死3
DIE2 = 10, //死2
ALIVE1 = 10 //活1
}score;
//棋子
typedef struct chess_s
{
u8 x;
u8 y;
}chess_t;
//空子的序列
typedef struct chess_queue_s
{
chess_t chess[M_SIZE*M_SIZE];
u8 len;
}chess_queue;
#endif
第二步：依据连子个数计算分数函数
/*计分表,依据连子个数(bumber)和两端的空子个数(empty)*/
static u32 score_table(u8 number, u8 empty)
{
if (number >= 5)
{
return WIN5;
}
else if (number == 4)
{
if (empty == 2)
{
return ALIVE4;
}
else if (empty==1)
{
return DIE4;
}
}
else if (number == 3)
{
if (empty == 2)
{
return ALIVE3;
}
else if (empty == 1)
{
return DIE3;
}
}
else if (number == 2)
{
if (empty == 2)
{
return ALIVE2;
}
else if (empty == 1)
{
return DIE2;
}
}
else if (number == 1&&empty == 2)
{
return ALIVE1;
}
return 0;
}
第三步:把棋盘的一行数据存到n[15]，而后计算这一行的连子个数和两端空子个数，再用上面的API：score_table()计算出这一行的分数，最后返回分数。学习
/*正斜线、反斜线、横、竖，均转成一维数组来计算*/
static u32 count_score(u8 n[], u8 chessColor)
{
u8 i = 1; //n[0]已经提早计算
u8 empty = 0; //空的位子
u8 number = 0; //连子的个数
u32 scoretmp = 0;
if (n[0] == SPACE)
{
empty++;
}
else if (n[0] == chessColor)
{
number++;
}
while (i < M_SIZE)
{
if (n[i] == chessColor)
{
number++;
}
else if (n[i] == SPACE)
{
if (number == 0)
{
empty = 1;
}
else
{
scoretmp += score_table(number, empty+1);
empty = 1;
number = 0;
}
}
else
{
scoretmp += score_table(number, empty);
empty = 0;
number = 0;
}
i++;
}
scoretmp += score_table(number, empty);
return scoretmp;
}
第四步：重点来了，评估函数。评估整个棋盘的分值，分4个方向把棋盘数据存到一维数组用上面的API count_score()算出分值，并累加。AI和human都计算出总分数，最后AI分数减去human的分数，并返回这个分数。优化
下面代码中：
AIChessColor全局变量表示电脑AI棋子的颜色
humChessColor是玩家棋子颜色
gBoard[][]表示棋盘的二维数组。人工智能
/*把当前局势全部连线都存到一维数组,而后算一遍分数*/
static s32 evaluate_board (void)
{
u32 AIScore=0;
u32 humScore=0;
u8 i, j;
s8 x, y; //若是是u8,x--,y--运算时可能溢出
u8 n[M_SIZE];
memset(n, 0, sizeof(n));
//横排
for (i=0; i<M_SIZE; i++)
{
for(j=0; j<M_SIZE; j++)
{
n[j] = gBoard[i][j];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
//纵排
for (j=0; j<M_SIZE; j++)
{
for(i=0; i<M_SIZE; i++)
{
n[i] = gBoard[i][j];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
//上半正斜线(\)
for (i=0; i<M_SIZE; i++)
{
for(x=i,y=0; x<M_SIZE&&y<M_SIZE; x++,y++)
{
n[y] = gBoard[x][y];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
//下半正斜线
for (j=1; j<M_SIZE; j++)
{
for(x=0,y=j; y<M_SIZE&&x<M_SIZE; x++,y++)
{
n[x] = gBoard[x][y];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
//上半反斜线(/)
for (i=0; i<M_SIZE; i++)
{
for(y=i,x=0; y>=0&&x<M_SIZE; y--,x++)
{
n[x] = gBoard[x][y];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
//下半反斜线
for (j=1; j<M_SIZE; j++)
{
for (y=j,x=M_SIZE-1; y<M_SIZE&&x>=0; y++,x--)
{
n[y-j] = gBoard[x][y];
}
AIScore += count_score(n, AIChessColor);
humScore += count_score(n, humChessColor);
memset(n, 0, sizeof(n));
}
return AIScore-humScore;
}
到这里就能够解释什么是对电脑AI最有利，
简单说就是找到用评估函数evaluate_board()算出来的分值最高的下棋点。更具体的说，
在MAX层轮到AI下棋时，假设这一层有50个空位置能够下子。先尝试下一个子，而后用评估函数evaluate_board()算此时的棋局分值。50个点这样都试一遍，找到分值最高的点，即为对电脑AI最有利的点。（固然，这时电脑AI只考虑了一层的模型）
在实现上述思路以前先说另外两个相关API：
has_neighbors():是否有邻居，这个就没什么好说的，看代码。
/*是否有邻居:两步以内是否有子存在(不管是对手仍是本身的子均可以)*/
static Boolean has_neighbors(int x, int y)
{
int s = 2; //两步以内有子
u8 i = 0, j = 0;
for (i=(x-s>0?x-s:0); i<=x+s&&i<M_SIZE; i++)
for (j=(y-s>0?y-s:0); j<=y+s&&j<M_SIZE; j++)
if (i!=0 || j!=0)
if (SPACE != (gBoard[i][j]))
return TRUE;
return FALSE;
}
generate_point():空子序列，这是个很重要的API，咱们最开始设计，只是剔除了已经有子的地方和没有邻居的地方。剩余的空子位置做为能够下棋的地方保存到队列。后续还能够有很大的优化空间。
/*产生空子序列(能够下子的空位)*/
static void generate_point(chess_queue *queue)
{
int i,j,k = 0;
for (i=0; i<M_SIZE; i++)
{
for (j=0; j<M_SIZE; j++)
{
if ((gBoard[i][j]==SPACE) && has_neighbors(i,j))//有邻居的空子,作为可下子的队列
{
queue->chess[k].x = i;
queue->chess[k].y = j;
queue->len = k+1;
k++;
}
}
}
}
如今就按上述思路实现电脑AI下棋时的代码：
void chess_ai_minmax_alphabeta (chess_t *chess)
{
u8 i = 0, k = 0;
u8 x = 0, y = 0;
s32 tmp = 0;
s32 best = -WIN5; //找到的最高分,初始值赋一个最小值
chess_queue option_queue; //待选的空子队列
chess_queue sure_queue; //最合适的下子位置
generate_point(&option_queue); //生成可下子的空子队列
for (i=0; i<option_queue.len; i++) //一个一个子轮着试一遍
{
x = option_queue.chess[i].x;
y = option_queue.chess[i].y;
gBoard[x][y] = AIChessColor; //尝试下一个子
tmp = min_alphabeta(depth-1, option_queue.chess[i]);
if (tmp == best) //找到一个和当前最高分同样的分数,保存下来
{
sure_queue.chess[k].x = option_queue.chess[i].x;
sure_queue.chess[k].y = option_queue.chess[i].y;
sure_queue.len = k+1;
k++;
}
if (tmp > best) //找到一个更好的分,把之前存的位子所有清除
{
best = tmp;
k = 0;
sure_queue.len = 1; //清空终选队列
sure_queue.chess[k].x = option_queue.chess[i].x;
sure_queue.chess[k].y = option_queue.chess[i].y;
}
gBoard[x][y] = SPACE; //恢复成空子
}
k =(int)(rand()%sure_queue.len); //若是有多个最高分数,随机选择一个
chess->x = sure_queue.chess[k].x;
chess->y = sure_queue.chess[k].y;
}
其中有一个很重要函数没有讲到：
int min_alphabeta(s8 depth, chess_t chess);
先假设一个这个AI只看一步棋，即只考虑眼前的利益。就是尝试下了一个AI颜色的子基础上，用评估函数把当前局面分算出来返回便可，不用考虑两个参数的含义。以下：
static int min_alphabeta(s8 depth, chess_t chess)
{
return evaluate_board();
}
接着往下，若是AI考虑两步棋，即本身一步对手一步棋。min_alphabeta()目的是找到最小分数，由于玩家下棋会下AI最不利的棋，思路就是，先算res = evaluate_board()，若是上一步AI下完棋已经赢了，那直接返回res分数。不然，在当前局面再一次调用generate_point()生产可下子队列，而后每一个子尝试一遍，计算局面分数后找到最小值返回。
/*当min层（玩家）下棋时,考虑最坏的状况*/
static int min_alphabeta(s8 depth, chess_t chess)
{
s32 res = evaluate_board();
u8 i, x, y;
s32 tmpScore;
s32 best = WIN5;
chess_queue queue;
if ((depth <= 0) || (is_win(chess.x, chess.y, AIChessColor)))//上一步是AI下棋可能产生输赢
{
return res;
}
generate_point(&queue);
for (i=0; i<queue.len; i++)
{
x = queue.chess[i].x;
y = queue.chess[i].y;
gBoard[x][y] = humChessColor; //尝试下一个子
tmpScore = max_alphabeta(depth-1, queue.chess[i]);
gBoard[x][y] = SPACE;
if (tmpScore < best)
{
best = tmpScore;
}
}
return best;
}
显然，若是只考虑两步，和以前同样其中的 max_alphabeta()实现以下：
static int max_alphabeta(depth-1, queue.chess[i]);
{
return evaluate_board();
}
继续考虑，若是AI考虑3步棋。思路相似的：先算res = evaluate_board()，若是上一步玩家下完棋已经赢了，那直接返回res分数。不然，在当前局面再一次调用generate_point()生产可下子队列，而后每一个子尝试一遍，计算局面分数后找到最大值并返回。
/*当max层（电脑AI）下棋时,考虑最好的状况*/
static int max_alphabeta(s8 depth, chess_t chess)
{
s32 res = evaluate_board();
u8 i, x, y;
s32 tmpScore;
s32 best = -WIN5;
chess_queue queue;
if ((depth <= 0) || (is_win(chess.x, chess.y, humChessColor)))//上一步是玩家下棋可能产生输赢
{
return res;
}
generate_point(&queue); //生成能够下棋子的空子序列
for (i=0; i<queue.len; i++)
{
x = queue.chess[i].x;
y = queue.chess[i].y;
gBoard[x][y] = AIChessColor; //尝试下一个子
tmpScore = min_alphabeta(depth-1, queue.chess[i]);
gBoard[x][y] = SPACE; //恢复成空子
if (tmpScore > best)
{
best = tmpScore;
}
}
return best;
}
显然，若是只考虑三步，和以前同样，上述API其中的
tmpScore = min_alphabeta(depth-1, queue.chess[i]);应该替换成
tmp = evaluate_board();
若是须要考虑depth步，就须要用到递归的思想。加上depth参数,直到depth<=0或者某一方赢了，递归结束。不然一直依次调用min_alphabeta和max_alphabeta。
到此已经按极大极小值的思想，完整的实现了五子棋AI下棋的算法。固然这个算法还有很大的优化空间。接下来会用比较常见的alpha，beta剪枝，和启发式搜索优化generate_point()。
参考博客：
http://www.noobyard.com/article/p-ytipbncl-hm.html
代码下载地址：
连接：https://pan.baidu.com/s/1CefnVaoojTqonTtlBqIt1g 密码：qkyp