POJ 1568 极大极小搜索 + alpha-beta剪枝

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

主要算法依据就是根据极大极小搜索实现的。

苦逼的是，查了两个晚上的错，原来最终是判断函数写错了。。瞬间吐血！

ps. 据说加一句 if sum < 4 printf("#####\n")会变态的快，不过懒得加了

ps. 1表示胜利，0表示平局，-1表示失败。

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

#include <cstdlib>

#include <cmath>

#include <utility>

#include <vector>

#include <queue>

#include <set>

#define INF 0x3f3f3f3f

using 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.

.xxx

xooo

?

xxxo

oxox

....

xxxo

$

*/