/*  POTM ENTRY:   KingKong            */
/*  Your Name:   Xinwei Kong             */
/*  Your email:  kong@triumf.ca          */
/*  Compile instructions: Save the email body as KingKong.c and then g++ KingKong.c   */

#include <stdlib.h>
#include <stdio.h>
#include <math.h>

#include <time.h>

#include <sys/times.h>  /* for the TMS structure */
//#define MAXTIME 600     /* 10 minutes worth of seconds */
#define CLK_TCK 100     
                          /* Note: this may be different on YOUR box, you
                           might find the value of HZ in YOUR param.h, but
                           it's gotta be 100 when you ship your entry! 
                           Alternatively, use sysconf to deduce CLK_TCK -
                           this approach should work on both systems!   */
int checktime()
{
        int seconds;
        static struct tms TMS;
        times(&TMS);
        /* add the elapsed system and user times                        */
        /* calculation comes out to the nearest second - rounded down   */
        seconds = (TMS.tms_stime + TMS.tms_utime);

        /*if (seconds >= MAXTIME)
        {
                // PRINT OUT YOUR SOLUTION BEFORE YOU GO! 
                exit(0);
        }*/
        return seconds;
}

static int start_time;
static int MAXTIME;

//Broadway  18:30 1177 RAGA
const int SC[8] = {0,0,0,3,10,25,56,119};


const double x=4;

const double K3SC[4] = {0, 1.5/x, 1.5,    0};
const double K4SC[5] = {0, 2.0/x/x,   2.0/x,      2.0,    0};
const double K5SC[6] = {0, 4.0/x/x/x,   4.0/x/x,  4.0/x,    4.0,    0};
const double K6SC[7] = {0, 8.0/x/x/x/x,   8.0/x/x/x,  8.0/x/x,  8.0/x,    8.0,  0};
const double K7SC[8] = {0, 16.0/x/x/x/x/x,  16.0/x/x/x/x, 16.0/x/x/x, 16.0/x/x, 16/x, 16.0, 0};

const double INFINITY = 1000.0;

const int MAXSUCC = 16;

const int MAXSUCC0 = 16;
const int MAXDEPTH0 = 8;
const int SUCCLIST0[8] = {2,2,2,4,8,8,16,16};

const int MAXSUCC1 = 10;
const int MAXDEPTH1 = 10;
const int SUCCLIST1[10] = {2,2,2,2,2,4,4,6,8,10};

const int MAXSUCC2 = 8;
const int MAXDEPTH2 = 10;
const int SUCCLIST2[10] = {2,2,2,2,4,4,4,4,6,6};

const int MAXSUCC3 = 8;
const int MAXDEPTH3 = 10;
const int SUCCLIST3[10] = {2,2,4,4,4,4,6,6,6,6};

static double SX[16384];
static double IMSX[16384];
static double SXO[16384];
static double IMSXO[16384];

static int IR[7];
static int IC[7];

static char Int2Char(int i)
{
  if (i==0) return '-';
  if (i==1) return '+';
  if (i==2) return 'X';
  if (i==3) return 'O';

  return -1;
}

static int Char2Int(char c)
{
  if (c=='-') return 0;
  if (c=='+') return 1;
  if (c=='X') return 2;
  if (c=='O') return 3;

  return -1;
}
inline static void Convert(char* b, int* a)
{
if (b[0] == '-') a[0]=0; else if (b[0] == 'E') {return;} else a[0] = 1;
if (b[1] == '-') a[1]=0; else if (b[1] == 'E') {return;} else a[1] = 1;
if (b[2] == '-') a[2]=0; else if (b[2] == 'E') {return;} else a[2] = 1;
if (b[3] == '-') a[3]=0; else if (b[3] == 'E') {return;} else a[3] = 1;
if (b[4] == '-') a[4]=0; else if (b[4] == 'E') {return;} else a[4] = 1;
if (b[5] == '-') a[5]=0; else if (b[5] == 'E') {return;} else a[5] = 1;
if (b[6] == '-') a[6]=0; else if (b[6] == 'E') {return;} else a[6] = 1;
} 

inline static int TransToInt(char c) 
{
  return (c=='+');
}


static double ReScore(char* c, char mine)
{
    int s=0, n=0; 
     
     if (c[0]==mine) n++; 
     if (c[1]==mine) n++; else {n=0;}
     if (c[2]==mine) n++; else {s+= SC[n];n=0;}
     if (c[3]==mine) n++; else {s+= SC[n];n=0;}
     if (c[4]==mine) n++; else {s+= SC[n];n=0;}
     if (c[5]==mine) n++; else {s+= SC[n];n=0;}
     if (c[6]==mine) {n++; s+=SC[n];} else {s+= SC[n];n=0;}
    
    return (double)s;
}

static double K4;

static double EvalK4(int a0, int a1, int a2, int a3)
{
  int a=a0+a1+a2+a3;

  if ((a==1))
  {
    if ((a1==1)||(a2==1)) return K4;
  }  
  
  return K4SC[a];
}

static double K51;
static double K52;

static double EvalK5(int a0, int a1, int a2, int a3, int a4)
{
  int a=a0+a1+a2+a3+a4;

  if ((a==1)&&(a2==1)) return K51 + K5SC[a];
  if ((a==2)&&((a1+a2==2)||(a2+a3==2)||(a1+a3==2))) return K52 + K5SC[a];
  
  return K5SC[a];
}

static double SubScore(int* a, int j)
{ 
  int i;
  double s=0;
  
  if (j==3) s = K3SC[a[0]+a[1]+a[2]];
  else if (j==4) s = K3SC[a[0]+a[1]+a[2]] + K3SC[a[1]+a[2]+a[3]] 
		   + EvalK4(a[0],a[1],a[2],a[3]);
  else if (j==5) s = K3SC[a[0]+a[1]+a[2]] + K3SC[a[1]+a[2]+a[3]] + K3SC[a[2]+a[3]+a[4]]
                   + EvalK4(a[0],a[1],a[2],a[3]) + EvalK4(a[1],a[2],a[3],a[4])
                   +  EvalK5(a[0],a[1],a[2],a[3],a[4]);
  else if (j==6) s = K3SC[a[0]+a[1]+a[2]] + K3SC[a[1]+a[2]+a[3]] + K3SC[a[2]+a[3]+a[4]] 
                   + K3SC[a[3]+a[4]+a[5]]
                   +  EvalK4(a[0],a[1],a[2],a[3]) + EvalK4(a[1],a[2],a[3],a[4]) 
		   +  EvalK4(a[2],a[3],a[4],a[5])
                   +  EvalK5(a[0],a[1],a[2],a[3],a[4]) + EvalK5(a[1],a[2],a[3],a[4],a[5])
                   +  K6SC[a[0]+a[1]+a[2]+a[3]+a[4]+a[5]];
  else if (j==7) s = K3SC[a[0]+a[1]+a[2]] + K3SC[a[1]+a[2]+a[3]] + K3SC[a[2]+a[3]+a[4]] 
                   + K3SC[a[3]+a[4]+a[5]] + K3SC[a[4]+a[5]+a[6]]
                    +  EvalK4(a[0],a[1],a[2],a[3]) + EvalK4(a[1],a[2],a[3],a[4]) 
		   +  EvalK4(a[2],a[3],a[4],a[5]) + EvalK4(a[3],a[4],a[5],a[6])
                   +  EvalK5(a[0],a[1],a[2],a[3],a[4]) + EvalK5(a[1],a[2],a[3],a[4],a[5])
                   + EvalK5(a[2],a[3],a[4],a[5],a[6])
		   +  K6SC[a[0]+a[1]+a[2]+a[3]+a[4]+a[5]] 
		   +  K6SC[a[6]+a[1]+a[2]+a[3]+a[4]+a[5]] 
		   +  K7SC[a[0]+a[1]+a[2]+a[3]+a[4]+a[5]+a[6]];

  return s;
}



static double ImScore(char* c, char mine, char your)
{
  char b[8];
  int a[8];
  int i;
  int j=0;
  double score = 0.0;

  for (i=0;i<7;i++)
  {
    if ((c[i]!=your)&&(c[i]!='+')) 
    {
      b[j] = c[i];
      j++;
    }
    else if (j!=0)
    {
      b[j] = 'E';
      Convert(b, a);

      //for (i=0;i<j;i++){a[i] = (b[i] - '-')/(mine - '-');}

      score += SubScore(a,j);
      j=0;
    }     
  }
  
  if ((c[6]!=your)&&(c[6]!='+')&&(j!=0)) 
  {
    b[j] = 'E';
    Convert(b, a);

    //for (i=0;i<j;i++){a[i] = (b[i] - '-')/(mine - '-');}

    score += SubScore(a,j);
  }

  return score;
}

static void SetXO()
{
  int i1,i2,i3,i4,i5,i6,i7;

  for (i1=0;i1<4;i1++){
  for (i2=0;i2<4;i2++){
  for (i3=0;i3<4;i3++){
  for (i4=0;i4<4;i4++){
  for (i5=0;i5<4;i5++){
  for (i6=0;i6<4;i6++){
  for (i7=0;i7<4;i7++){
    int n = i7 + i6*4 + i5*16 + i4*64 + i3*256 + i2*1024 + i1*4096; 
    
    char c[7];
    c[0] = Int2Char(i1);
    c[1] = Int2Char(i2);
    c[2] = Int2Char(i3);
    c[3] = Int2Char(i4);
    c[4] = Int2Char(i5);
    c[5] = Int2Char(i6);
    c[6] = Int2Char(i7);

    double imxscore = ImScore(c, 'X', 'O');
    double imoscore = ImScore(c, 'O', 'X');

    double xscore = ReScore(c,'X') + imxscore;
    double oscore = ReScore(c,'O') + imoscore;

    SX[n] = xscore;
    IMSX[n] = imxscore;

    SXO[n] = xscore - oscore;
    IMSXO[n] = imxscore - imoscore;
  }}}}}}}
}

inline static void Copy(int* c1, int* c2)
{
  c1[0] = c2[0];
  c1[1] = c2[1];
  c1[2] = c2[2];
  c1[3] = c2[3];
  c1[4] = c2[4];
  c1[5] = c2[5];
  c1[6] = c2[6];
}

inline static void Copy2D(int brd[7][7], int c[7][7])
{
  Copy(brd[0],c[0]);
  Copy(brd[1],c[1]);
  Copy(brd[2],c[2]);
  Copy(brd[3],c[3]);
  Copy(brd[4],c[4]);
  Copy(brd[5],c[5]);
  Copy(brd[6],c[6]);
}



class Board
{ 
public:
  int brd[7][7];

  double score;
  int next_move;

  int sx;
  int sy;

  Board() 
  {
  }

  Board(Board* b)
  {
    Copy2D(brd, b->brd);

    score = b->score;
    next_move = b->next_move;
    
    sx = b->sx;
    sy = b->sy;
  }

  Board(Board* b, int nx, int ny)
  {
    if (b->sx==-1) {sx=nx;sy=ny;}
    else {sx = b->sx; sy=b->sy;}

    Copy2D(brd, b->brd);

    if (b->next_move==2) next_move=3; 
    else next_move=2;

    brd[nx][ny] = next_move;
	IndexRow(nx);
	IndexColumn(ny);
    double nextscore = ScoreRow(nx) + ScoreColumn(ny);
	double nextXsc = ReXScoreRow(nx) + ReXScoreColumn(ny);


    brd[nx][ny] = b->next_move;
	IndexRow(nx);
	IndexColumn(ny);
	double rediff = (ReXScoreRow(nx) + ReXScoreColumn(ny) - nextXsc)/1000.0;
    score =  ScoreRow(nx) + ScoreColumn(ny) - nextscore + rediff;
  }
  
  ~Board()
  {
  }  

  Board* Clone()
  {  
    if (this != NULL) return (new Board(this));
    else return NULL;
  } 

  void SetScore()
  {
    score = 0;
  }

  void SetAllIndex()
  {
        IndexRow(0);IndexColumn(0);
	IndexRow(1);IndexColumn(1);
	IndexRow(2);IndexColumn(2);
	IndexRow(3);IndexColumn(3);
	IndexRow(4);IndexColumn(4);
	IndexRow(5);IndexColumn(5);
	IndexRow(6);IndexColumn(6);
  }
	
  void ScoreAll()
  {
	score =  ScoreRow(0) + ScoreColumn(0);
    score += ScoreRow(1) + ScoreColumn(1);
    score += ScoreRow(2) + ScoreColumn(2);
    score += ScoreRow(3) + ScoreColumn(3);
    score += ScoreRow(4) + ScoreColumn(4);
    score += ScoreRow(5) + ScoreColumn(5);
    score += ScoreRow(6) + ScoreColumn(6);
  }

  double TotalXScore()
  {
	double total_score =  ReXScoreRow(0) +  ReXScoreColumn(0);
    total_score    +=  ReXScoreRow(1) +  ReXScoreColumn(1);
    total_score    +=  ReXScoreRow(2) +  ReXScoreColumn(2);
    total_score    +=  ReXScoreRow(3) +  ReXScoreColumn(3);
    total_score    +=  ReXScoreRow(4) +  ReXScoreColumn(4);
    total_score    +=  ReXScoreRow(5) +  ReXScoreColumn(5);
    total_score    +=  ReXScoreRow(6) +  ReXScoreColumn(6);

	return total_score;
  }

  double FindImDiff()
  {
	  int i;
	  double imR[7], imC[7];
	  double maxim = -10000.0, maxim2 = -10000.0;

	  for (i=0;i<7;i++)
	  {
		imR[i] = ImScoreRow(i);
		imC[i] = ImScoreColumn(i);
		if (imR[i]>maxim) maxim=imR[i];
		if (imC[i]>maxim) maxim=imC[i];
	  }

	  for (i=0;i<7;i++)
	  {
		if ((imR[i]>maxim2)&&(imR[i]!=maxim)) maxim2=imR[i];
		if ((imC[i]>maxim2)&&(imC[i]!=maxim)) maxim2=imC[i];
	  }

	  double diff = maxim - maxim2;
	  
	  if ((diff>8.0)||(diff<-8.0)) return diff/1.5;
	  else if ((diff>4.0)||(diff<-4.0)) return diff/2.0;
	  else if ((diff>1.0)||(diff<-1.0)) return diff/3.0;
	  else return diff/4.0;
  }

  double FindImMinMax()
  {
	  int i;
	  double imR[7], imC[7];
	  double maxim = -10000.0, minim = 10000.0;
	  double maxim2 = -10000.0, minim2 = 10000.0;

	  for (i=0;i<7;i++)
	  {
		imR[i] = ImScoreRow(i);
		imC[i] = ImScoreColumn(i);
		if (imR[i]>maxim) maxim=imR[i];
		if (imC[i]>maxim) maxim=imC[i];
		if (imR[i]<minim) minim=imR[i];
		if (imC[i]<minim) minim=imC[i];
	  }
  
	  for (i=0;i<7;i++)
	  {
		if ((imR[i]>maxim2)&&(imR[i]!=maxim)) maxim2=imR[i];
		if ((imC[i]>maxim2)&&(imC[i]!=maxim)) maxim2=imC[i];
		if ((imR[i]<minim2)&&(imR[i]!=minim)) minim2=imR[i];
		if ((imC[i]<minim2)&&(imC[i]!=minim)) minim2=imC[i];
	  }
 
	  double diff = maxim + minim;
	  if (maxim2>-minim) diff = maxim - maxim2;
	  if (-minim2>maxim) diff = -minim + minim2;

	  if (diff<0) diff = -diff;

	  if (diff>4) return diff/2;
	  if (diff>1.5) return diff/4;
	  else return diff/8.0;
	  
	  //return diff/2.0;
  }


  void Evaluate()
  {
	SetAllIndex();

	ScoreAll(); 
	
	double total_score = TotalXScore();

	double imdiff12 = FindImMinMax();

	if (next_move==2) score += total_score/1000.0;
	else score += -total_score/1000.0;

    score = -score + imdiff12; 
  }

  Board* PlayFirstToEnd()
  {
    Board* succ=SingleSucc();
    Board* lastB = this;
    Board* oneB = succ;

    while (oneB!=NULL)
    {
       succ = oneB->SingleSucc();
       lastB = oneB;
       oneB = succ;	
       if (succ!=NULL) {delete lastB;}
    }

	lastB->SetAllIndex();

    lastB->ScoreAll();

    double total_score = lastB->TotalXScore();

	lastB->score += total_score/1000.0;

	if (next_move == lastB->next_move) lastB->score = - lastB->score; 

    return lastB;
  }

  void FindNextMove()
  {
    int i,j,d=0;

    for (i=0;i<7;i++)
     for (j=0;j<7;j++)
    {
      if (brd[i][j]==2) d++;
      if (brd[i][j]==3) d--;
    }
    
    if (d==0) next_move = 2;
    else next_move = 3;
  }

void IndexRow(int n)
{
	IR[n] = brd[n][6] + brd[n][5]*4 + brd[n][4]*16 + brd[n][3]*64 
    + brd[n][2]*256 + brd[n][1]*1024 + brd[n][0]*4096; 
}

void IndexColumn(int n)
{
	IC[n] = brd[6][n] + brd[5][n]*4 + brd[4][n]*16 + brd[3][n]*64 
    + brd[2][n]*256 + brd[1][n]*1024 + brd[0][n]*4096; 
}

double ScoreRow(int n)
{
  if (next_move==3) return SXO[IR[n]];
  else return -SXO[IR[n]];
}

double ScoreColumn(int n)
{
  if (next_move==3) return SXO[IC[n]];
  else return -SXO[IC[n]];
}

double ImScoreRow(int n)
{
  if (next_move==3) return IMSXO[IR[n]];
  else return -IMSXO[IR[n]];
}

double ImScoreColumn(int n)
{
  if (next_move==3) return IMSXO[IC[n]];
  else return -IMSXO[IC[n]];
}

double ReXScoreRow(int n)
{
  if (next_move==3) return SX[IR[n]];
  else return -SX[IR[n]];
}

double ReXScoreColumn(int n)
{
  if (next_move==3) return SX[IC[n]];
  else return -SX[IC[n]];
}


void Successors(Board* barray[], int nSucc)  //???????enemy's big point
{
  Board* thisB = this;
  double score[MAXSUCC];
  int i,j;
  Board* oneB;
  Board* saveB; 
 
  for (i=0;i<nSucc;i++)
  {
    score[i] = -10000;
    barray[i] = NULL;
  }

  for (i=0;i<7;i++)
   for (j=0;j<7;j++)
    {
      if (thisB->brd[i][j]==0) 
      {
	oneB = new Board(thisB, i, j);
        int k;
	double one_score = (oneB->score);
	double save;

	for (k=0;k<nSucc;k++)
	{
	  if (one_score > score[k]) 
	  {
	    save = one_score; saveB = oneB;
	    one_score = score[k]; oneB = barray[k];
	    score[k] = save; barray[k] = saveB;
  	  }
	}
	if (oneB!=NULL) delete oneB;
      }
    }
}

Board* SingleSucc()  
{
  Board* bSucc;
  Board* thisB = this;
  double score;
  int i,j;
  Board* oneB = NULL;

  score = -10000;
  bSucc = NULL;

  for (i=0;i<7;i++)
   for (j=0;j<7;j++)
    {
      if (thisB->brd[i][j]==0) 
      {
	oneB = new Board(thisB, i, j);
	double one_score = (oneB->score);
	
	if (one_score > score) {score = one_score; bSucc = oneB; oneB=NULL;}
	else {delete oneB;}
      }
    }  

  return bSucc;
}

};


Board* AlphaBeta0 (Board* oneB, int depth, double alpha, double beta)
{
    if ((checktime() - start_time) > MAXTIME) {return NULL;}

    if (depth == 0) 
    {
      oneB->Evaluate();
      return oneB->Clone();
    }

    Board* bestB = NULL;
    double best = -INFINITY;
    double value;
    int num=0;

    Board* succ[MAXSUCC0];
    oneB->Successors(succ, SUCCLIST0[depth-1]);

    while ((num<SUCCLIST0[depth-1]) && (best < beta))
    {
        oneB = succ[num];
		num++;

        if (oneB!=NULL)
		{
			if (best > alpha) {alpha = best;}
			Board* valueB=NULL;
			valueB = AlphaBeta0(oneB, depth-1, -beta, -alpha);
	  
			if (valueB==NULL) 
			{ 
				for (int l=0;l<SUCCLIST0[depth-1];l++)
				{
					if (succ[l]!=NULL) delete succ[l];
				}
				return NULL;
			}

			value = - valueB->score;
			if (value > best) 
			{
				if (bestB!=NULL) delete bestB; 
				best = value;
				bestB = valueB->Clone(); 
				bestB->score = best;
			}
	  
			if (valueB!=NULL) delete valueB;
		}
    }

    for (int l=0;l<SUCCLIST0[depth-1];l++)
    {
        if (succ[l]!=NULL) delete succ[l];
    }


    return bestB;
}

Board* AlphaBeta1 (Board* oneB, int depth, double alpha, double beta)
{
    if ((checktime() - start_time) > MAXTIME) {return NULL;}
   
	if (depth == 0) 
    {
       oneB->Evaluate();
       return oneB->Clone();
    }

    Board* bestB=NULL;
    double best = -INFINITY;
    double value;
    Board* valueB;
    int num=0;

    Board* succ[MAXSUCC1];
    oneB->Successors(succ, SUCCLIST1[depth-1]);

    while ((num<SUCCLIST1[depth-1]) && (best < beta))
    {
        oneB = succ[num];
		num++;

        if (oneB!=NULL)
		{
			if (best > alpha) {alpha = best;}
			valueB = AlphaBeta1(oneB, depth-1, -beta, -alpha);

			if (valueB==NULL) 
			{ 
				for (int l=0;l<SUCCLIST1[depth-1];l++)
				{
					if (succ[l]!=NULL) delete succ[l];
				}
				return NULL;
			}

			value = - valueB->score;
			if (value > best) 
			{
				if (bestB!=NULL) delete bestB; 
				best = value; 
				bestB = valueB->Clone(); 
				bestB->score = best;
			}
		  if (valueB!=NULL) {delete valueB;}
		}
    }

    for (int l=0;l<SUCCLIST1[depth-1];l++)
    {
        if (succ[l]!=NULL) delete succ[l];
    }

    return bestB;
}




Board* AlphaBeta2 (Board* oneB, int depth, double alpha, double beta)
{
    if ((checktime() - start_time) > MAXTIME) {return NULL;}
   

    if (depth == 0) 
    {
      Board* b =  oneB->PlayFirstToEnd();
      return b->Clone();
    }

    Board* bestB=NULL;
    double best = -INFINITY;
    double value;
    Board* valueB;
    int num=0;

    Board* succ[MAXSUCC2];
    oneB->Successors(succ, SUCCLIST2[depth-1]);

    while ((num<SUCCLIST2[depth-1]) && (best < beta))
    {
        oneB = succ[num];
	num++;

        if (oneB!=NULL)
	{
	  if (best > alpha) {alpha = best;}
	  valueB = AlphaBeta2(oneB, depth-1, -beta, -alpha);

	  if (valueB==NULL) 
			{ 
				for (int l=0;l<SUCCLIST2[depth-1];l++)
				{
					if (succ[l]!=NULL) delete succ[l];
				}
				return NULL;
			}

          value = - valueB->score;
          if (value > best) 
	  {
	    if (bestB!=NULL) delete bestB; 
	    best = value; 
	    bestB = valueB->Clone(); 
	    bestB->score = best;
	  }
	  if (valueB!=NULL) delete valueB;
	}
    }

    for (int l=0;l<SUCCLIST2[depth-1];l++)
    {
        if (succ[l]!=NULL) delete succ[l];
    }

    return bestB;
}

Board* AlphaBeta3 (Board* oneB, int depth, double alpha, double beta)
{
   if ((checktime() - start_time) > MAXTIME) {return NULL;}
   
   if (depth == 0) 
    {
      Board* b =  oneB->PlayFirstToEnd();
      return b->Clone();
    }

    Board* bestB=NULL;
    double best = -INFINITY;
    double value;
    Board* valueB=NULL;
    int num=0;

    Board* succ[MAXSUCC3];
    oneB->Successors(succ, SUCCLIST3[depth-1]);

    while ((num<SUCCLIST3[depth-1]) && (best < beta))
    {
        oneB = succ[num];
	num++;

        if (oneB!=NULL)
	{
	  if (best > alpha) {alpha = best;}
	  valueB = AlphaBeta3(oneB, depth-1, -beta, -alpha);

	  if (valueB==NULL) 
			{ 
				for (int l=0;l<SUCCLIST3[depth-1];l++)
				{
					if (succ[l]!=NULL) delete succ[l];
				}
				return NULL;
			}

          value = - valueB->score;
          if (value > best) 
	  {
	    if (bestB!=NULL) delete bestB; 
	    best = value; 
	    bestB = valueB->Clone(); 
	    bestB->score = best;
	  }
	  if (valueB!=NULL) delete valueB;
	}
	
    }

    for (int l=0;l<SUCCLIST3[depth-1];l++)
    {
        if (succ[l]!=NULL) delete succ[l];
    }

    return bestB;
}




main()
{
  char c[7][7];
  scanf("%s\n%s\n%s\n%s\n%s\n%s\n%s", c[0], c[1], c[2], c[3], c[4], c[5], c[6]);

  start_time = checktime();
 
  Board* startB = new Board();
  int n_empty = 0;

  int i,j;
  for (i=0;i<7;i++)
    for (j=0;j<7;j++) 
     {
		startB->brd[i][j] = Char2Int(c[i][j]);
		if (c[i][j]=='-') n_empty++; 
     }

  if (n_empty==48)      {K4=0.3; K51=-0.0; K52=0.8;}
  else if (n_empty==46) {K4=0.4; K51=-0.1; K52=0.7;}
  else if (n_empty==44) {K4=0.5; K51=-0.2; K52=0.6;}
  else if (n_empty<=42) {K4=0.6; K51=-0.3; K52=0.5;}  

  SetXO();

  startB->sx=-1;
  startB->FindNextMove();
  startB->SetScore();
  int depth; 

  Board* sb = startB->Clone();

  int ix,iy, end=0;
 
  Board* bestB = NULL;

    if (bestB!=NULL) delete bestB;
    ////use iterative deepening
    /*if (n_empty > 42)
    {
      Board* saveB=new Board();
      depth = 2;
      while ((saveB!=NULL)&&(depth<=MAXDEPTH0))
      {
		 bestB = saveB->Clone(); 
		 delete saveB;
		 saveB = AlphaBeta0(startB, depth, -INFINITY, INFINITY);
		 depth = depth + 2;
      }
    }
    else if (n_empty > 26) 
    {
      Board* saveB=new Board();
      depth = 2;
      while ((saveB!=NULL)&&(depth<=MAXDEPTH1))
      {
		bestB = saveB->Clone(); 
		delete saveB;
		saveB = AlphaBeta1(startB, depth, -INFINITY, INFINITY);
		depth = depth + 2;
      }
      if (saveB!=NULL) {if (bestB!=NULL) delete bestB; bestB = saveB;}
    }
    else if (n_empty > 16)
    {
      Board* saveB=new Board();
      depth = 2;
      while ((saveB!=NULL)&&(depth<=MAXDEPTH2))
      {
		 bestB = saveB->Clone(); 
		 delete saveB;
		 saveB = AlphaBeta2(startB, depth, -INFINITY, INFINITY);
		 depth = depth + 2;
      }      
      if (saveB!=NULL) {if (bestB!=NULL) delete bestB; bestB = saveB;}
    }
    else if (n_empty > MAXDEPTH3)
    {
      Board* saveB=new Board();
      depth = 2;
      while ((saveB!=NULL)&&(depth<=MAXDEPTH3))
      {
		 bestB = saveB->Clone(); 
		 delete saveB;
		 saveB = AlphaBeta3(startB, depth, -INFINITY, INFINITY);
		 depth = depth + 2;
      }
      if (saveB!=NULL) {if (bestB!=NULL) delete bestB; bestB = saveB;}
    }
    else
    {
		depth = ((int)n_empty/2)*2;
		bestB = AlphaBeta3(startB, depth, -INFINITY, INFINITY);
    }*/

    MAXTIME = 908; 

    if (n_empty > 42)
    {
		depth = MAXDEPTH0;
		bestB = AlphaBeta0(startB, depth, -INFINITY, INFINITY);
    }
    else if (n_empty > 30) 
    {
		depth = MAXDEPTH1;
		bestB = AlphaBeta1(startB, depth, -INFINITY, INFINITY);
    }
    else if (n_empty > 20)
    {
                depth = MAXDEPTH2;
		bestB = AlphaBeta2(startB, depth, -INFINITY, INFINITY);
    }
    else if (n_empty > MAXDEPTH3)
    {
		depth = MAXDEPTH3;
		bestB = AlphaBeta3(startB, depth, -INFINITY, INFINITY);
    }
    else
    {
		depth = ((int)n_empty/2)*2;
		bestB = AlphaBeta3(startB, depth, -INFINITY, INFINITY);
    }
		
	if (bestB==NULL) 
	{
	    MAXTIME = 998;
	    bestB = AlphaBeta1(startB, 4, -INFINITY, INFINITY);
	    if (bestB==NULL) bestB  = startB->SingleSucc();
	}

    sb->brd[bestB->sx][bestB->sy] = sb->next_move;
  
    for (i=0;i<7;i++)
    {
      for (j=0;j<7;j++) printf("%c", Int2Char(sb->brd[i][j]));
      printf("\n");
    }

  return 0;
}