极小极大搜索 的个人理解（alpha-beta剪枝）

#include <cstdio>#include <cstring>#include <iostream>#include <algorithm>#include <cstdlib>#include <cmath>#include <utility>#include <vector>#include <queue>#include <set>#define INF 0x3f3f3f3fusing namespace std;int map[4][4], sum, winx, winy;char c;bool check(int otherplayer){    for(int i = 0; i < 4; i ++)    {        int tmp = 0;        for(int j = 0; j < 4; j ++)            tmp += (map[i][j] == otherplayer);        if(tmp == 4)            return 1;    }    for(int j = 0; j < 4; j ++)    {        int tmp = 0;        for(int i = 0; i < 4; i ++)            tmp += (map[i][j] == otherplayer);        if(tmp == 4)            return 1;    }    int tmp1 = 0, tmp2 = 0;    for(int i = 0; i < 4; i ++)    {        tmp1 += (map[i][i] == otherplayer);        tmp2 += (map[3-i][i] == otherplayer);    }    if(tmp1 == 4 || tmp2 == 4)        return 1;    return 0;}int alpha_beta(int depth, int alpha, int beta){    int nowplayer = depth&1;    if(check(1-nowplayer))        return -1;    if(sum == 16)        return 0;    for(int i = 0; i < 4; i ++)        for(int j = 0; j < 4; j ++)            if(map[i][j] == 2)            {                map[i][j] = nowplayer;                sum ++;                int tmp = -alpha_beta(depth+1, -beta, -alpha);                map[i][j] = 2;                sum --;                if(tmp >= beta)                    return beta;                if(tmp > alpha)                    alpha = tmp;                if(depth == 0 && alpha == 1)                {                    winx = i, winy = j;                    return alpha;                }            }    return alpha;}int main(){    while(getchar() != ‘$‘)    {        sum = 0;        getchar();        for(int i = 0; i < 4; i ++)            for(int j = 0; j < 4; j ++)            {                c = getchar();                switch (c){                    case ‘.‘:                         map[i][j] = 2;                        break;                    case ‘x‘:                        map[i][j] = 0;                        sum ++;                        break;                    case ‘o‘:                        map[i][j] = 1;                        sum ++;                }                if(j == 3) getchar();            }        if(alpha_beta(0, -INF, INF) == 1)            printf("(%d,%d)\n", winx, winy);        else            printf("#####\n");    }    return 0;}/*?.....xo..ox.....?o....ox..xxxxooo?xxxooxox....xxxo$*/