poj 1568極小探索

質問:4 x 4 tic-tac-toeの局面を与えて、先手の“x”が次の一歩の中で探すことができるかどうかを聞きます
必勝局面を見つけ、あれば最初の落子位置(順番)を出力します.
極大極小検索戦略は一般的にいくつかのゲーム類のゲームで使用されています.  このようなポリシーは本質的に深さ探索ポリシーを用いるので、一般的に再帰的な方法を用いて実現することができる.検索の過程で、味方に有利な検索点には極大値を取るべきで、味方に不利な検索点には極小値を取るべきである.  極小値と極大値は相対的である.  検索中に検索深さを合理的に制御する必要があり、検索の深さが深いほど効率が低くなるが、一般的には歩き方が良い.

#include <iostream>
using namespace std;
#define inf 100000000
int state[5][5],chess,xi,xj;
char ch;
int minfind(int,int,int);
int maxfind(int,int,int);
bool over(int x,int y) {
     bool flag = false;
     int row[5],col[5];
     memset(row,0,sizeof(row));
     memset(col,0,sizeof(col));
     for (int i=0;i<4;i++)
         for (int j=0;j<4;j++) {
             if (state[i][j]=='x') {
                row[i]++;
                col[j]++;
             }
             if (state[i][j]=='o') {
                row[i]--;
                col[j]--;
             }
         }
     if (row[x]==-4 || row[x]==4 || col[y]==-4 || col[y]==4) 
        flag = true;
     int tot1 = 0, tot2 = 0;
     for (int i=0;i<4;i++) {
         if (state[i][i]=='x') tot1++;
         if (state[i][3-i]=='x') tot2++;
         if (state[i][i]=='o') tot1--;
         if (state[i][3-i]=='o') tot2--;
     }
     if ((tot1==4 || tot1==-4) && x==y)        flag = true;
     if ((tot2==4 || tot2==-4) && x==3-y)      flag = true;
     return flag;
} 
int maxfind(int x,int y,int mini) {
    int tmp, maxi = -inf;
	if (over(x,y)) return maxi;
	if (chess==16) return 0;
	for (int i=0;i<4;i++)
	    for (int j=0;j<4;j++)
            if (state[i][j]=='.') {
                       state[i][j]='x';
                       chess++;
                       tmp = minfind(i,j,maxi);
                       chess--;
                       state[i][j]='.';
                       maxi = max(maxi, tmp);
                       if (maxi>=mini) return maxi;
            }
    return maxi;
}
int minfind(int x,int y,int maxi) {
    int tmp, mini = inf;
	if (over(x,y)) return mini;
	if (chess==16) return 0;
	for (int i=0;i<4;i++)
	    for (int j=0;j<4;j++)
            if (state[i][j]=='.') {
                       state[i][j]='o';
                       chess++;
                       tmp = maxfind(i,j,mini);
                       chess--;
                       state[i][j]='.';
                       mini = min(mini, tmp);
                       if (mini<=maxi) return mini;
            }
    return mini;
}
bool tryit() {
     int tmp, maxi = -inf;
     for (int i=0;i<4;i++)
         for (int j=0;j<4;j++)
             if (state[i][j]=='.') {
                state[i][j] = 'x';
                chess++;
                tmp = minfind(i,j,maxi);
                chess--;
                state[i][j] = '.';
                if (tmp>=maxi) {
                       maxi = tmp;
                       xi = i; xj = j;
                }
	            if (maxi==inf) return true;
             }
     return false;
}
int main() {
	while (scanf("%c",&ch)) {
		if (ch=='$') break;
		scanf("%c",&ch);

		chess = -4;
		for (int i=0;i<4;i++)
			for (int j=0;j<5;j++) {
				scanf("%c",&state[i][j]);
				chess += state[i][j]!='.';
			}
		if (chess<=4) {  //     
                      printf("#####
");
                      continue;
        }
        if (tryit()) printf("(%d,%d)
",xi,xj);
        else printf("#####
");
	}
	return 0;
}