/*------------------------------------------------------------
TEAM52
A
231
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>

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

enum {EMPTY,WHITE,BLACK};

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

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

struct hz {
	int md;
	int mi;
	int ex;
	bool isc, isd;
	hz (int md=-1, bool isc=false, bool isd=true, int mi=-1, int ex=-1): md(md), isc(isc), isd(isd), mi(mi), ex(ex){}
};

bool operator< (const hz& h1, const hz& h2) {
	if (h1.mi==-1) return true;
	if (h1.isc!=h2.isc) return (h2.isc);
	if (h1.isd!=h2.isd) return (h1.isd);
	int di=(color==WHITE?1:-1), ni=(color==WHITE?7:0);
	int tt=(ni-h2.ex)*di;
	bool isgood;
	if (h2.isc)
		isgood = ((tt<4 && h1.md>tt) || (tt>=4 && h1.md>(8-tt)));
	else
		isgood = (h1.md>tt);
	return isgood;
}

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

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;
}


game_move& choose_move (int cnt, game_move *moves) {
	int i, j, k, di=(color==WHITE?1:-1), ni=(color==WHITE?7:0);
	int ecolor=(color==WHITE?BLACK:WHITE);
	hz ss;
	for (i=0;i<cnt;i++)
		if (moves[i].ex==0 || moves[i].ex==7)
			return moves[i];
	for (i=0;i<cnt;i++) {
		bool isdanger=false;
		for (j=-1;j<=1;j+=2) {
			int jj=moves[i].ey+j;
			if (jj<0 || jj>=8) continue;
			if (board[moves[i].ex+di][jj]==ecolor) isdanger=true;
		}
		hz tt=hz((ni-moves[i].ex)*di,moves[i].is_capture,isdanger,i,moves[i].ex);
		if (ss<tt) {
			ss=tt;
		}
	}
	if (ss.mi==-1) ss.mi=rand()%cnt;
	return moves[ss.mi];
}

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

int main() {
  srand(time(0));
  init();
  for(;;) {
    char str[100];
    gets(str);
    if(!strcmp(str,"Name")) {
      // Request for the bot name
      printf("Bot Strikes\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;
}
