/*------------------------------------------------------------
TEAM28
A
238
Target: MSVC9; Platform: Win32; Comment: MS Visual C++ 9
------------------------------------------------------------*/
// Random bot for "Breakthrough" game
// Ural Championship 2010 Game Tour
// Author: Igor Chevdar

#include <stdio.h>
#include <string.h>
#include <stdlib.h>
#include <time.h>
#include <algorithm>
#include <cmath>
#include <ctime>

#define BOARD_SIZE 8
#define MAX_MOVES (BOARD_SIZE*2*3)


using namespace std;

double mytime(){

	return 1.*clock()/1000;
}

enum {EMPTY,WHITE,BLACK};

double startgo;
int GO;
struct game_move {
  int sx,sy;
  int ex,ey;
  int is_capture;
  int good;
};

inline int op_color(int color) {
  return color==WHITE ? BLACK : WHITE;
}

char board[BOARD_SIZE][BOARD_SIZE];
char tboard[BOARD_SIZE][BOARD_SIZE];
int color;


void init() {
  memset(board,EMPTY,sizeof(board));
  for(int i=0;i<BOARD_SIZE;++i) {
    board[0][i]=board[1][i]=WHITE;
    board[BOARD_SIZE-1][i]=board[BOARD_SIZE-2][i]=BLACK;
  }
  color=WHITE;
}

void make_move(game_move &move) {
  board[move.ex][move.ey]=board[move.sx][move.sy];
  board[move.sx][move.sy]=EMPTY;
  color=op_color(color);
}

void make_move(char *str) {
  char sy,ey;
  int sx,ex;
  sscanf(str,"%c%d%c%d",&sy,&sx,&ey,&ex);
  game_move move={sx-1,sy-'a',ex-1,ey-'a',board[ex-1][ey-'a']!=EMPTY};
  make_move(move);
}

int gen_moves(game_move *moves) {
  int cnt=0;
  for(int i=0;i<BOARD_SIZE;++i) {
    for(int j=0;j<BOARD_SIZE;++j) {
      if(board[i][j]==color) {
        for(int dj=-1;dj<=1;++dj) {
          int ni=i+(color==WHITE ? 1 : -1);
          int nj=j+dj;
          if(ni>=0 && ni<BOARD_SIZE && nj>=0 && nj<BOARD_SIZE &&
             board[ni][nj]!=color && (dj || board[ni][nj]==EMPTY)) {
            game_move move={i,j,ni,nj,board[ni][nj]!=EMPTY};
            moves[cnt++]=move;
          }
        }
      }
    }
  }
  return cnt;
}

int check(int x,int y){
	if(x<8&&x>=0&&y<8&&y>=0) return 1;
	return 0;
}


int badpos(int x,int y){
	int r=0;
	if(check(x+1,y+1)&&board[x+1][y+1]==op_color(color)) r--;
	if(check(x+1,y-1)&&board[x+1][y-1]==op_color(color)) r--;
	return r;	
}


int eat(int x,int y){
	return board[x][y]==op_color(color);	
}


int dist(int x){
   if(color==WHITE){
      return x;
   }else{
      return 8-x;
   }
}





void make_b_move(game_move &move) {
  tboard[move.ex][move.ey]=tboard[move.sx][move.sy];
  tboard[move.sx][move.sy]=EMPTY;
  color=op_color(color);
}


int gen_b_moves(game_move *moves) {
  int cnt=0;
  for(int i=0;i<BOARD_SIZE;++i) {
    for(int j=0;j<BOARD_SIZE;++j) {
      if(tboard[i][j]==color) {
        for(int dj=-1;dj<=1;++dj) {
          int ni=i+(color==WHITE ? 1 : -1);
          int nj=j+dj;
          if(ni>=0 && ni<BOARD_SIZE && nj>=0 && nj<BOARD_SIZE &&
             tboard[ni][nj]!=color && (dj || tboard[ni][nj]==EMPTY)) {
            game_move move={i,j,ni,nj,tboard[ni][nj]!=EMPTY};
            moves[cnt++]=move;
          }
        }
      }
    }
  }
  return cnt;
}






int tr_color; 


int dx(int color)
{ if (color == WHITE) return 1;
  return -1;}

int sec(int color, int x, int y) 
{ int ret =0;
  for (int i = x; check(i,0); i+=dx(color))
    {
    for (int j = y; fabs(j-y+0.) < fabs(i-x+0.) && check(i,j); j++)
       ret+=(tboard[i][j] == op_color(color));
    for (int j = y; fabs(j-y+0.) < fabs(i-x+0.) && check(i,j); j--)
       ret+=(tboard[i][j] == op_color(color));
    }
 return ret;}


int evr(){ 
 int i,j;
 int ans =0;

 for (i=0;i<8;i++)
 for (j=0;j<8;j++)
  

  {

   if (tboard[i][j]==op_color(tr_color)) ans -= 7 * sec(op_color(tr_color),i,j);
   if (tboard[i][j]==tr_color) ans += 5 * sec(tr_color,i,j);
                                                    
  
   }
 return ans;
        	
}

int brute(int h, game_move &best){

	if(h>8 || (mytime()-startgo>2.7)){
	  return evr();	
	}
	game_move d;
	game_move b_moves[MAX_MOVES];
        int n = gen_b_moves(b_moves);
	int max = -10000000;
	int i;
		
	for(i=0;i<n;i++){
     		b_moves[i].good+=5*dist(10-b_moves[i].ex)*eat(b_moves[i].ex,b_moves[i].ey);

	        b_moves[i].good+=3*dist(b_moves[i].ex)+1;

	        b_moves[i].good+=badpos(b_moves[i].ex,b_moves[i].ey)*10;
         }
	 int maxi=0;

	 for(i=0;i<n;i++){
	       if(b_moves[maxi].good<b_moves[i].good) maxi=i;
	  } 


 	for (i=0;i<n;i++){
 	 
	  if ((b_moves[maxi].good +0.)/ (b_moves[i].good +0.) <=1.1){
	 
 	  char end = tboard[b_moves[i].ex][b_moves[i].ey];
 	  char start = tboard[b_moves[i].sx][b_moves[i].sy];
 
	  int col = color;
	  make_b_move(b_moves[i]);

//	  color = op_color(color);
	  int u= brute(h+1,d);
	  if (u > max) max = u,best=b_moves[i];
// 	  del_b_move(b_moves[i]);
          color=col;
//	  color = op_color(color);

	  tboard[b_moves[i].ex][b_moves[i].ey] = end;
 	  tboard[b_moves[i].sx][b_moves[i].sy] = start; 
 	  }

	}

 	return max;
}






























int shielded(game_move u)
{
int ret = 0;
if (check(u.sx,u.ey-1)&& board[u.sx][u.ey-1]==color && u.ey-1!=u.sy) ret++;
if (check(u.sx,u.ey+1)&& board[u.sx][u.ey+1]==color && u.ey+1!=u.sy) ret++;
return ret;
} 

void think(char *str) {
  int i,j,k,n;
  game_move moves[MAX_MOVES];
  n=gen_moves(moves);
  GO++;
  int u;
  int z;
  int num=0;
/*  for(i=0;i<n;i++){
     moves[i].good+=3*dist(8-moves[i].ex)*eat(moves[i].ex,moves[i].ey);
     moves[i].good+=3*dist(moves[i].ex)+1;
     moves[i].good+=badpos(moves[i].ex,moves[i].ey)*2*dist(moves[i].ex);
  }
  int maxi=0;
  for(i=0;i<n;i++){
     if(moves[maxi].good<moves[i].good) maxi=i;
  }                           */
  //game_move &move=moves[maxi];
  for (i=0;i<8;i++)
  for (j=0;j<8;j++)
    num+=board[i][j]!=EMPTY;

  if(num>24){
    z=100;
    game_move move;
    for(i=0;i<n;i++){
      if(eat(moves[i].ex,moves[i].ey)){ 
	move=moves[i],z=0; 
	break;
      }
    }
    while(z){
      u=rand()%n;
      z--;
      if( (dist(moves[u].ex)<3 && z<90) || (z==0) 
	 || (check(moves[u].ex, moves[u].ey+1) && board[moves[u].ex][moves[u].ey+1]!=EMPTY)
         || (check(moves[u].ex, moves[u].ey-1) && board[moves[u].ex][moves[u].ey-1]!=EMPTY)
	 || ((dist(moves[u].ex)<4) && (shielded(moves[u])==2 || (shielded(moves[u])==1 && z<=80)))  ) {move=moves[u],z=0;}
    }         
   sprintf(str,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
    make_move(move);	
  }else{
    startgo=mytime();
    game_move move;
    for (i=0;i<8;i++)
    for (j=0;j<8;j++)
    tboard[i][j] = board[i][j];
    tr_color=color;
    brute(0,move);
 // sprintf(stderr,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
    sprintf(str,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
    make_move(move);
  }
}








int main() {
  srand(time(0));
  init();
  for(;;) {
    char str[100];
    gets(str);
    if(!strcmp(str,"Name")) {
      // Request for the bot name
      printf("This is Refrigerator\n");
      fflush(stdout);
    }
    else if(!strcmp(str,"Quit")) {
      // Game is over
      break;
    }
    else {
      if(strcmp(str,"Start")) {
        // Enemy's move
        make_move(str);
      }
      // Our move
      think(str);
      printf("%s\n",str);
      fflush(stdout);
    }
  }
  return 0;
}
