博弈搜索

如果用计算机模拟两个人每一步的操作，理论上我们可以得到每一个棋局的必胜、必败信息。这是一种完美解决五子棋问题的算法。
但是考虑到搜索空间非常庞大，我们并不可能搜索到分出胜负，而是为了节约时间在仅仅几层之后不得不返回。
因此我们需要退而求其次，用不太稳定的估价函数大致判断棋局的好坏，在必要的时候直接返回这个棋局的估值。

估价函数

对于某个玩家，直接考虑该玩家在场上有多少个活着的 1,2,3,4,5 子棋。将这些棋的个数加权得到估价函数的值。
两玩家估价函数的差对应棋局的好坏。

当然，有了估价函数，我们就可以大致判断有哪些棋该下，有哪些棋不该下，每次只搜索那些该下的棋，以提高搜索效率。

Alpha-Beta 剪枝

有了估价函数，博弈搜索时对棋局的衡量就不再是简单的胜与负，而是一个数字。
因此，从博弈搜索的定义出发，我们可以定义每一个局面对于当前玩家的权值为
$$
val(x)=\begin{cases}
\max{(-val(y))} & (x\rightarrow y,dep\leq maxdep) \\
evaluate(x) & (x\gt maxdep)
\end{cases}
$$
因此不难看出，对于每一个 x，$val(x)$在搜索过程中是单调不降的。

根据这个性质，我们发现，如果 $val(x)$无限制的变大，当达到一个阈值时，它将不可能再更新其父状态的权值。因此当我们搜索到这个阈值的时候，直接返回，并不会影响最终的结果。所以这可以作为一种剪枝。

代码

所以实现非常简单。为了更高效，我把棋盘用二进制表示。

但是不知道为啥我的程序只能搜索 5 层，每层搜索接下来的 6 个最可能的状态。似乎还是非常低效。但是跟我这种新手下还是如鱼得水。

#include <algorithm>
#include <iostream>
#include <conio.h>
#include <cstring>
#include <cstdio>
#include <windows.h>
#define MX 19
#define S 0
#define B 1
#define W 2
#define U 3
#define MDEP 5
#define SRANGE 6
#define oo 1000000000
#define mov(x) (1LL<<(x))

using namespace std;

typedef long long ll;

struct position
{
    int x,y,v;
    bool operator < (const position& t)const{return v>t.v;}
};

ll game_x[4][MX+2];
ll game_y[4][MX+2];
ll game_u[4][MX*2+2];       //x-y+MX
ll game_d[4][MX*2+2];       //x+y
int cur_x,cur_y,cur_p,rob_p;

int line_value_count=31;
int line_value_base[40][6]={    //每一种棋型的估价函数
{+oo,B,B,B,B,B},
{1000,B,B,B,B,S},
{1000,S,B,B,B,B},
{1000,B,S,B,B,B},
{1000,B,B,S,B,B},
{1000,B,B,B,S,B},
{200,B,B,B,S,S},
{200,B,B,S,B,S},
{200,B,B,S,S,B},
{200,B,S,B,B,S},
{200,B,S,B,S,B},
{200,B,S,S,B,B},
{200,S,B,B,B,S},
{200,S,B,B,S,B},
{200,S,B,S,B,B},
{200,S,S,B,B,B},
{20,S,S,S,B,B},
{20,S,S,B,S,B},
{20,S,S,B,B,S},
{20,S,B,S,S,B},
{20,S,B,S,B,S},
{20,S,B,B,S,S},
{20,B,S,S,S,B},
{20,B,S,S,B,S},
{20,B,S,B,S,S},
{20,B,B,S,S,S},
{1,B,S,S,S,S},
{1,S,B,S,S,S},
{1,S,S,B,S,S},
{1,S,S,S,B,S},
{1,S,S,S,S,B}
};
int line_value[32];

int pos_value[MX+2][MX+2];

void gotoxy(int x, int y)
{
    COORD pos;
    pos.X=x-1;
    pos.Y=y-1;
    SetConsoleCursorPosition(GetStdHandle(STD_OUTPUT_HANDLE),pos);
}

int get_value(int *seq)         //获得一种棋型的估价函数
{
    int sum=0,f;
    for(int i=0;i<line_value_count;i++)
    {
        f=1;
        for(int j=0;j<5;j++)
        {
            if( (line_value_base[i][j+1]==B&&seq[j]==B)||
                (line_value_base[i][j+1]==S&&seq[j]==S));
            else {f=0;break;}
        }
        if(f)sum+=line_value_base[i][0];
    }
    return sum;
}

void init()                     //将每一种棋型预处理为二进制
{
    int now_seq[MX];
    for(int i=1;i<=MX;i++)
        for(int j=1;j<=MX;j++)
            pos_value[i][j]=min(min(i,j),min(MX+1-i,MX+1-j));
    for(int j=0;j<mov(5);j++)
    {
        for(int l=0;l<5;l++)
        {
            if(j&mov(l))now_seq[l]=B;
            else now_seq[l]=S;
        }
        line_value[j]=get_value(now_seq);
    }
    cur_p=B;
    cur_x=10,cur_y=10;
    gotoxy(cur_x*2+1,MX-cur_y+2);
}

bool place_seed(int x,int y,int p)  //在 (x,y) 处放置玩家 p 的棋
{
    int u=x+y;
    int d=x-y+MX;
    if((game_x[B][y]|game_x[W][y])&mov(x))return 0;
    game_x[p][y]|=mov(x);
    game_y[p][x]|=mov(y);
    game_u[p][d]|=mov(u>>1);
    game_d[p][u]|=mov(d>>1);
    return 1;
}

bool unplace_seed(int x,int y,int p)    //删除 (x,y) 处玩家 p 的棋
{
    int u=x+y;
    int d=x-y+MX;
    if(!(game_x[p][y]&mov(x)))return 0;
    game_x[p][y]^=mov(x);
    game_y[p][x]^=mov(y);
    game_u[p][d]^=mov(u>>1);
    game_d[p][u]^=mov(d>>1);
    return 1;
}

int get_x_line(int x,int y,int p)       //获得以 (x,y) 为左端点的水平连续的 5 个格子内的状态
{
    if(x<1||x+4>19||y<1||y>19)return 0;
    ll a,b;
    a=game_x[p][y]>>x;
    b=game_x[3-p][y]>>x;
    if((b&(mov(5)-1)))return 0;
    else return (a&(mov(5)-1));
}

int get_y_line(int x,int y,int p)       //获得以 (x,y) 为下端点的竖直连续的 5 个格子内的状态
{
    if(x<1||x>19||y<1||y+4>19)return 0;
    ll a,b;
    a=game_y[p][x]>>y;
    b=game_y[3-p][x]>>y;
    if((b&(mov(5)-1)))return 0;
    else return (a&(mov(5)-1));
}

int get_u_line(int x,int y,int p)       //获得以 (x,y) 为左端点的斜向上连续 5 个格子内的状态
{
    if(x<1||x+4>19||y<1||y+4>19)return 0;
    int u=x+y;
    int d=x-y+MX;
    ll a,b;
    a=game_u[p][d]>>(u>>1);
    b=game_u[3-p][d]>>(u>>1);
    if((b&(mov(5)-1)))return 0;
    else return (a&(mov(5)-1));
}

int get_d_line(int x,int y,int p)       //获得以 (x,y) 为左端点的斜向下连续 5 个格子内的状态
{
    if(x<1||x+4>19||y-4<1||y>19)return 0;
    int u=x+y;
    int d=x-y+MX;
    ll a,b;
    a=game_d[p][u]>>(d>>1);
    b=game_d[3-p][u]>>(d>>1);
    if((b&(mov(5)-1)))return 0;
    else return (a&(mov(5)-1));
}

int evaluate(int p)                     //估计整个棋盘内玩家 p 的权值
{
    int sum=0;
    for(int i=1;i<=MX;i++)
        for(int j=1;j<=MX;j++)
            sum+=
                line_value[get_x_line(i,j,p)]+
                line_value[get_y_line(i,j,p)]+
                line_value[get_u_line(i,j,p)]+
                line_value[get_d_line(i,j,p)];
    return sum;
}

void display()                          //windwos 控制台下的显示函数
{
    gotoxy(1,1);
    for(int i=0;i<=20;i++)putchar('-'),putchar('-');
    putchar('\n');
    for(int i=19;i>=1;i--)
    {
        putchar('|'),putchar(' ');
        for(int j=1;j<=19;j++)
        {
            if(game_x[B][i]&mov(j))putchar('X');
            else if(game_x[W][i]&mov(j))putchar('O');
            else putchar(' ');
            putchar(' ');
        }
        putchar('|'),putchar('\n');
    }
    for(int i=0;i<=20;i++)putchar('-'),putchar('-');
    gotoxy(cur_x*2+1,MX-cur_y+2);
}

int dfs(int dep,int player,int top)     //博弈搜索
{
    position stk[MX*MX+2];
    int num=0;
    int ret=-oo,e1=evaluate(player),e2=evaluate(3-player);
    if(dep==MDEP||abs(e1-e2)>=+oo/2)return e1-e2;
    else
    {
        for(int i=1;i<=MX;i++)
            for(int j=1;j<=MX;j++)
                if(place_seed(i,j,player))
                {
                    stk[++num]=(position){i,j,evaluate(player)-evaluate(3-player)};
                    unplace_seed(i,j,player);
                }
        sort(stk+1,stk+num+1);
        for(int i=1;i<=SRANGE;i++)
        {
            place_seed(stk[i].x,stk[i].y,player);
            ret=max(ret,-dfs(dep+1,3-player,ret));
            unplace_seed(stk[i].x,stk[i].y,player);
            if(-ret<=top)return ret;
        }
        return ret;
    }
}

void play()
{
    if(cur_p==rob_p)
    {
        int mxval=-oo,nowval,nx=0,ny=0;
        position stk[MX*MX+2];
        int num=0;
        for(int i=1;i<=MX;i++)
            for(int j=1;j<=MX;j++)
                if(place_seed(i,j,cur_p))
                {
                    stk[++num]=(position){i,j,evaluate(cur_p)-evaluate(3-cur_p)+pos_value[i][j]};
                    unplace_seed(i,j,cur_p);
                }
        sort(stk+1,stk+num+1);
        for(int i=1;i<=SRANGE;i++)
        {
            int tx=stk[i].x,ty=stk[i].y;
            place_seed(tx,ty,cur_p);
            nowval=-dfs(1,3-cur_p,mxval-pos_value[nx][ny])+pos_value[tx][ty];
            if(nowval>mxval)nx=tx,ny=ty,mxval=nowval;
            unplace_seed(tx,ty,cur_p);
        }
        system("cls");
        place_seed(cur_x=nx,cur_y=ny,cur_p);
        cur_p=3-cur_p;
        display();
    }
    else
    {
        int ch=getch();         //获得按键 (上下左右与 WASD，空格回车落子)
        if(ch==224)
        {
            ch=getch();
            if(ch==77)cur_x++;
            else if(ch==75)cur_x--;
            else if(ch==72)cur_y++;
            else if(ch==80)cur_y--;
        }
        else if(ch==100)cur_x++;
        else if(ch==97)cur_x--;
        else if(ch==119)cur_y++;
        else if(ch==115)cur_y--;
        else if(ch==13||ch==32)
        {
            system("cls");
            if(place_seed(cur_x,cur_y,cur_p))cur_p=3-cur_p;
            display();
        }
        if(cur_x<1)cur_x=1;
        if(cur_x>19)cur_x=19;
        if(cur_y<1)cur_y=1;
        if(cur_y>19)cur_y=19;
        gotoxy(cur_x*2+1,MX-cur_y+2);
    }
}

bool win(int p)             //判断是否有人获胜
{
    for(int i=1;i<=MX;i++)
        for(int j=1;j<=MX;j++)
            if( line_value[get_x_line(i,j,p)]>=+oo||
                line_value[get_y_line(i,j,p)]>=+oo||
                line_value[get_u_line(i,j,p)]>=+oo||
                line_value[get_d_line(i,j,p)]>=+oo)
                    return 1;
    return 0;
}

int main()
{
    rob_p=B;
    init();
    display();
    while(1)
    {
        play();
        if(win(W))
        {
            gotoxy(6,23);
            printf("White Win!\n");
            break;
        }
        if(win(B))
        {
            gotoxy(6,23);
            printf("Black Win!\n");
            break;
        }
    }
    return 0;
}