/*------------------------------------------------------------
TEAM24
A
211
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>

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

//#define test

enum {EMPTY,WHITE,BLACK};

struct game_move {
  int sx,sy;
  int ex,ey;
  int is_capture;

};

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

char board[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;
}
#ifdef test
FILE* fp;
int cc=0;
#endif

void priority(double* prior, game_move* moves, int cnt)
{
	for (int i=0;i<cnt;i++)
		prior[i]=0.0;
//приоритет хода по близости к концу
	//double ar[7]={-20.0,0.0,10.0,30.0,1000.0,1e20,1e100};
	double ar[8]={-20.0,0.0,10.0,15.0,1000.0,1e20,1e100};
	if (cnt<=20) ar[0]+=20.0;
	for (int i=0;i<cnt;i++){
		prior[i]=ar[(color==WHITE)?(moves[i].sx):(7-moves[i].sx)];
		if (((color==WHITE)&&(moves[i].sx==6))||((color==BLACK)&&(moves[i].sx==1)))
			return;
	}
	//рубка опасных клеток
	for (int i=0;i<BOARD_SIZE;i++){
			if (board[(color==WHITE)?1:6][i]==op_color(color)){
				//поиск своей соседней клетки для рубки
				for (int j=0;j<cnt;j++)
					if ((moves[j].ex==((color==WHITE)?1:6))&&(moves[j].ey==i))
						prior[j]+=1e99;
			}
			if (board[(color==WHITE)?2:5][i]==op_color(color)){
				for (int j=0;j<cnt;j++)
					if ((moves[j].ex==((color==WHITE)?2:5))&&(moves[j].ey==i))
						prior[j]+=1e10;
			}
	}
	//приоритет рубки
	double pr[8]={100.0,100.0,100.0,100.0,1000.0,1e10,1e99};
	for (int i=0;i<cnt;i++){
		if (moves[i].is_capture)
			prior[i]+=pr[(color==WHITE)?(moves[i].ex):(7-moves[i].ex)];
	}
	//******************** РАНДОМ!!
	for (int i=0;i<cnt;i++){
		if (rand()%5==0)
			prior[i]+=10.0;
	}
	//кучкование
	double t_board[BOARD_SIZE][BOARD_SIZE];
	for (int i=0;i<BOARD_SIZE;i++)
		for (int j=0;j<BOARD_SIZE;j++)
			t_board[i][j]=0.0;
	for (int i=2;i<BOARD_SIZE-2;i++)
		for (int j=0;j<BOARD_SIZE;j++)
			if ((board[i][j]==color))
			for(int dj=j-1;dj<=j+1;++dj)
				for(int di=i-1;di<i+1;++di) {
					if (dj>=0 && dj<=7 && di>=0 && di<=7)
						if (board[di][dj]==EMPTY)
							t_board[di][dj]+=15.0;
				}
#ifdef test
	for (int i=0;i<BOARD_SIZE;i++){
		for (int j=0;j<BOARD_SIZE;j++)
			fprintf(fp,"%.2f	",t_board[i][j]);
		fprintf(fp,"\n");
	}
	fprintf(fp, "\n\n");
#endif
	for (int i=0;i<cnt;i++){
		prior[i]+=t_board[moves[i].ex][moves[i].ey];
	}
	//убираем ходы в битые поля
	for (int i=0;i<cnt;i++){
		if (color==WHITE){
			if (moves[i].ex<=6){
				if ((moves[i].ey<=6)&&(board[moves[i].ex+1][moves[i].ey+1]==BLACK))
					prior[i]-=5.0;
				else if ((moves[i].ey>=1)&&(board[moves[i].ex+1][moves[i].ey-1]==BLACK))
					prior[i]-=5.0;
			}
		}else{
			if (moves[i].ex>=1){
				if ((moves[i].ey<=6)&&(board[moves[i].ex-1][moves[i].ey+1]==WHITE))
					prior[i]-=5.0;
				else if ((moves[i].ey>=1)&&(board[moves[i].ex-1][moves[i].ey-1]==WHITE))
					prior[i]-=5.0;
			}
		}
	}

}

int move_number(double* prior, int cnt)//
{
	int maxi=0;
	for (int i=0;i<cnt;i++)
		if (prior[i]>prior[maxi])
			maxi=i;
	return maxi;
}

void think(char *str) {
  game_move moves[MAX_MOVES];
  double prior[MAX_MOVES];
  int cnt = gen_moves(moves);
  priority(prior, moves, cnt);
  game_move &move = moves[move_number(prior, cnt)];
  //game_move &move=moves[rand()%cnt];
  sprintf(str,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
  make_move(move);
}

int main() {
#ifdef test
	fp=fopen("test.txt","a");
#endif
  srand(time(0));
  init();
  for(;;) {
    char str[100];
    gets(str);
    if(!strcmp(str,"Name")) {
      // Request for the bot name
      printf("PSU 3\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;
}
