CCF_201803_4_棋局评估_极大极小搜索法

极小极大搜索方法

五子棋看起来有各种各样的走法，而实际上把每一步的走法展开，就是一颗巨大的博弈树。在这个树中，从根节点为0开始，奇数层表示电脑可能的走法，偶数层表示玩家可能的走法。

假设电脑先手，那么第一层就是电脑的所有可能的走法，第二层就是玩家的所有可能走法，以此类推。

我们假设平均每一步有50种可能的走法，那么从根节点开始，往下面每一层的节点数量是上一层的 50被，假设我们进行4层思考，也就是电脑和玩家各走两步，那么这颗博弈树的最后一层的节点数为 50^4 = 625W 个。

先不考虑这么多个节点需要多久能算出来。有了对博弈树的基本认识，我们就可以用递归来遍历这一棵树。

那么我们如何才能知道哪一个分支的走法是最优的，我们就需要一个评估函数能对当前整个局势作出评估，返回一个分数。我们规定对电脑越有利，分数越大，对玩家越有利，分数越小，分数的起点是0。

我们遍历这颗博弈树的时候就很明显知道该如何选择分支了：

电脑走棋的层我们称为 MAX层，这一层电脑要保证自己利益最大化，那么就需要选分最高的节点。

玩家走棋的层我们称为MIN层，这一层玩家要保证自己的利益最大化，那么就会选分最低的节点。

这也就是极大极小值搜索算法的名称由来。

一般应用在博弈搜索中，比如：围棋，五子棋，象棋等。结果有三种可能：胜利、失败和平局。暴力搜索，如果想通过暴力搜索，把最终的结果得到的话，搜索树的深度太大了，机器不能满足，一般都是规定一个搜索的深度，在这个深度范围内进行深度优先搜索。

假设：A和Ｂ对弈，轮到Ａ走棋了，那么我们会遍历A的每一个可能走棋方法，然后对于前面A的每一个走棋方法，遍历B的每一个走棋方法，然后接着遍历A的每一个走棋方法，如此下去，直到得到确定的结果或者达到了搜索深度的限制。当达到了搜索深度限制，此时无法判断结局如何，一般都是根据当前局面的形式，给出一个得分，计算得分的方法被称为评价函数，不同游戏的评价函数差别很大，需要很好的设计。

在搜索树中，表示A走棋的节点即为极大节点，表示B走棋的节点为极小节点。

//http://118.190.20.162/view.page?gpid=T70
#include<bits/stdc++.h>
using namespace std;
int mp[3][3];


bool isv(int k)
{
    for(int i=0;i<3;i++)
    {
        if(mp[i][0]==k&&mp[i][1]==k&&mp[i][2]==k) return true;
        if(mp[0][i]==k&&mp[1][i]==k&&mp[2][i]==k) return true;
    }
    if(mp[0][0]==k&&mp[1][1]==k&&mp[2][2]==k) return true;
    if(mp[0][2]==k&&mp[1][1]==k&&mp[2][0]==k) return true;
    return false;
}

int dfs(int k) //轮到k下棋
{
    int t=0;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
          if(mp[i][j]==0) t++;
    if(k==1&&isv(2)) return -t-1;
    if(k==2&&isv(1)) return t+1;
    if(t==0) return 0;
    int mn=0x3f3f3f3f,mx=-0x3f3f3f3f;
    for(int i=0;i<3;i++)
        for(int j=0;j<3;j++)
    {
        if(mp[i][j]==0)
        {
            mp[i][j]=k;
            if(k==1) mx=max(mx,dfs(2));
            if(k==2) mn=min(mn,dfs(1));
            mp[i][j]=0;
        }
    }
    if(k==1) return mx;
    if(k==2) return mn;
}

int main()
{
    int T;
    cin>>T;
    while(T--)
   {
       for(int i=0;i<3;i++)
         for(int j=0;j<3;j++)
           cin>>mp[i][j];
       cout<<dfs(1)<<endl;
   }
   return 0;
}