POJ1568 四子棋 博弈_反四子棋博弈

1. 必胜：无论对方走什么都可以必胜。
   即：轮己方走时，有true则true，轮对方走时，全true为true。
2. 竞赛中的题目通常是搜到底然后利用alpha-beta剪枝优化，根据兄弟节点的值及时剪枝。
3. 人工智能的算法中取max的最大值，min的最小值，再优化，相当于1和-1，这是极大极小值算法。
4. 充分不必要的bug最为隐晦。

题目链接：http://acm.hust.edu.cn/vjudge/problem/26288

#include<cstdio>
#include<cstring>
#include<algorithm>

using namespace std;
char str[5][5];
int X,Y,chess;
//判断一个局面是否结束
bool check(int x,int y){
    int tot=0;
    //横向判断
    for(int i=0;i<4;i++)
        if(str[x][i]=='o') tot++;
        else if(str[x][i]=='x') tot--;
    if(tot==4||tot==-4) return true;
    tot=0;
    //纵向判断
    for(int i=0;i<4;i++)
        if(str[i][y]=='o') tot++;
        else if(str[i][y]=='x') tot--;
    if(tot==4||tot==-4) return true;
    tot=0;
    //正对角线判断
    for(int i=0;i<4;i++)
        if(str[i][i]=='o') tot++;
        else if(str[i][i]=='x') tot--;
    if(tot==4||tot==-4) return true;
    tot=0;
    //反对角线判断
    for(int i=0;i<4;i++)
        if(str[i][3-i]=='o') tot++;
        else if(str[i][3-i]=='x') tot--;
    if(tot==4||tot==-4) return true;
    return false;
}
int MinSearch(int x,int y);
int MaxSearch(int x,int y);
int MaxSearch(int x,int y){
    //已经结束
    if(check(x,y)) return -1;
    //平局
    if(chess==16) return 0;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(str[i][j]=='.'){
                str[i][j]='x';chess++;
                int tmp=MinSearch(i,j);
                str[i][j]='.';chess--;
                //对方需要找的最差估价，如果当前比之前最差的高，剪枝
                if(tmp == 1) return 1;
            }
    return -1;
}
int MinSearch(int x,int y){
    //已经结束
    if(check(x,y)) return 1;
    //平局
    if(chess==16) return 0;
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            if(str[i][j]=='.'){
                str[i][j]='o';chess++;
                int tmp=MaxSearch(i,j);
                str[i][j]='.';chess--;
                //自己需要找的最高估价，如果当前比之前最差的低，剪枝
                if(tmp == -1 || tmp == 0) return -1;
            }
    return 1;
}
bool slove(){
    for(int i=0;i<4;i++)
        for(int j=0;j<4;j++)
            //枚举，然后搜索
            if(str[i][j]=='.'){
                str[i][j]='x';chess++;
                int tmp = MinSearch(i,j);
                str[i][j]='.';chess--;
                if(tmp == 1){
                    X=i;
                    Y=j;
                    return true;
                }
            }
    return false;
}
int main(){
    char ch[5];
    while(scanf("%s",ch)!=EOF&&ch[0]!='$'){
        chess=0;
        for(int i=0;i<4;i++){
            scanf("%s",str[i]);
            for(int j=0;j<4;j++)
                chess+=str[i][j]!='.';
        }
        //这一步直接从2S+到0ms，哭~~~
        if(chess<=4){
            printf("#####\n");
            continue;
        }
        if(slove()) printf("(%d,%d)\n",X,Y);
        else printf("#####\n");
    }
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105