题解：P1917 三子棋II

· · 题解

本题非常适合作为 Minimax 算法的板子题。

什么是 Minimax？

Minimax（极小化极大）算法，是一种应用于零和博弈问题的决策算法，其本质是一种启发式搜索。Tic-tac-toe（井字棋/三子棋）是 Minimax 算法的一个经典应用场景。

如何实现 Minimax？

以一棵搜索数上的节点表示每一次决策。Minimax 的思路是，构建一个评估函数，计算一条决策路径（用搜索树上的叶子节点表示）的对己方的有利程度，然后分 Max 和 Min 两种节点对决策路径进行筛选。

Max 节点，即己方进行决策的节点，总会从子节点中选择评估值最大的一个进行决策，同时其评估值即为当前节点的评估值；Min 节点，即对方进行决策的节点，总会从子节点中选择评估值最小的一个进行决策，同时其评估值即为当前节点的评估值。

以上过程通常使用深搜，可以用递归实现。

一棵裸的 Minimax 搜索数的决策过程是 O(d^n) 的，所以我们需要对其进行减枝。

Minimax 经典的减枝算法称作 Alpha-Beta 减枝。对每个节点，称 \alpha 为每个节点的最大可行下界，\beta 为每个节点的最小可行上界。初始化根节点的 alpha 为 -\infin，\beta 为 \infin；每个节点将继承其父节点的 \alpha 和 \beta 作为初值。

对于每个 Max 节点应应用 \alpha 减枝，即每访问完一个子节点以后将当前节点的 \alpha 更新为 \alpha 和评估值的较大值。若 \alpha 在更新后满足 \alpha\ge\beta，则减枝，不再访问剩余的子节点。

对于每个 Min 节点应应用 \beta 减枝，即每访问完一个子节点以后将当前节点的 \beta 更新为 \beta 和评估值的较小值。若 \beta 在更新后满足 \beta\le\alpha，则减枝，不再访问剩余的子节点。

经过 Alpha-Beta 减枝后 Minimax 搜索的速度大大加快。

如何应用 Minimax？

现在为本题设计 Minimax 的解法。

首先考虑如何设计评估函数。我们设小 a 为“己方”，uim 为“对方”，则可以令小 a 胜利的评估值为 1，uim 胜利的估值为 -1，平局的评估值为 0。

输入当前局面，我们先判断轮到谁先手。由于初始时小 a 先手，所以小 a 的棋子多一颗即意味着现在是小 a 先手，棋子一样多即意味着现在是 uim 先手。

如果小 a 先手，我们令当前局面为 Max 根节点做一次 Minimax；如果 uim 先手，我们令当前局面为 Min 根节点做一次 Minimax。完成后根节点的评估值即为双方各取最优策略下最终的胜负。此时若平局则说明没有必胜策略，否则胜利方有必胜策略。

代码：

#include<climits>
#include<iostream>
#include<vector>
#include<ctime>
#include<cstdlib>
using namespace std;
int t[3][3];
int end()
{
    int e=0;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if(t[i][j]==0)e++;
        }
        if(t[i][0]==t[i][1]&&t[i][1]==t[i][2])
        {
            if(t[i][0]==1)return 1;
            else if(t[i][0]==2) return 2;
        }
        if(t[0][i]==t[1][i]&&t[1][i]==t[2][i])
        {
            if(t[0][i]==1)return 1;
            else if(t[0][i]==2) return 2;
        }
    }
    if(t[0][0]==t[1][1]&&t[2][2]==t[1][1])
    {
        if(t[0][0]==1)return 1;
        else if(t[0][0]==2) return 2;
    }
    if(t[2][0]==t[1][1]&&t[0][2]==t[1][1])
    {
        if(t[1][1]==1)return 1;
        else if(t[1][1]==2) return 2;
    }
    if(e==0)return 0;
    else return -1;
}
int minimax(int p,pair<int, int>&m,int a=INT_MIN,int b=INT_MAX)
{
    pair<int, int>mv(-1,-1);
    int e=end();
    if(~e)
    {
        return e==2?-1:e;
    }
    int di=0,dj=0;
    if(p==1)
    {
        int s=INT_MIN;
        for(int i=0;i<3;i++)
        {
            for(int j=0;j<3;j++)
            {
                if (t[(i+di)%3][(j+dj)%3]==0)
                {
                    t[(i+di)%3][(j+dj)%3]=1;
                    int x=minimax(2,mv,a,b);
                    if(x>s)s=x,m=make_pair((i+di)%3,(j+dj)%3);
                    t[(i+di)%3][(j+dj)%3]=0;
                    a=max(a,s);
                    if(b<=a)break;
                }
            }
        }
        return s;
    }
    int s=INT_MAX;
    for(int i=0;i<3;i++)
    {
        for(int j=0;j<3;j++)
        {
            if (t[(i+di)%3][(j+dj)%3]==0)
            {
                t[(i+di)%3][(j+dj)%3]=2;
                int x=minimax(1,mv,a,b);
                if(x<s)s=x,m=make_pair((i+di)%3,(j+dj)%3);
                t[(i+di)%3][(j+dj)%3]=0;
                b=min(b,s);
                if(b<=a)break;
            }
        }
    }
    return s;
}
int main()
{
    pair<int, int>m(-1,-1);
    char j;
    int n=0,k=0,e=0;
    for(int i=0;i<9;i++)
    {
        cin>>j;
        t[i/3][i%3]=((j=='O')?(n++,1):((j=='X')?(n++,2):0));
    }
    (n&1)?(k=2):(k=1);
    e=minimax(k,m);
    cout<<((e==1)?"xiaoa will win.":((e==2)?"uim will win.":"Dont know."))<<endl;
    cout<<n<<endl;
    return 0;
}