/*------------------------------------------------------------
TEAM36
A
232
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 <vector>
#include <cmath>

using namespace std;

void ShowField();

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

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];
char or_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.ey][move.ex]=board[move.sy][move.sx];
  board[move.sy][move.sx]=EMPTY;
  color=op_color(color);
}

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

void make_move(char *str) {
  char sx,ex;
  int sy,ey;
  sscanf(str,"%c%d%c%d",&sx,&sy,&ex,&ey);
  game_move move={sx-'a',sy-1,ex-'a',ey-1,board[ey-1][ex-'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={j, i,nj, ni, board[ni][nj]!=EMPTY};
            moves[cnt++]=move;
          }
        }
      }
    }
  }
  return cnt;
}

bool IsWinning(game_move move)
{
	return move.ey == (color == WHITE) ? BOARD_SIZE - 1 : 0;			
}

bool deep_think2(game_move move)
{
	make_move(move);
	
	// our turn

	game_move moves[MAX_MOVES];
	int cnt=gen_moves(moves);
	for(int i = 0; i < cnt; i++)
	{
		if(IsWinning(moves[i]) == true)
		{
			unmake_move(move);
			return true;
		}
	}	
	unmake_move(move);
	return false;
}

bool deep_think(game_move move)
{
	//ShowField();
	char _board[BOARD_SIZE][BOARD_SIZE];
	for(int i = 0; i < BOARD_SIZE; i++)
		for(int j = 0; j < BOARD_SIZE; j++)
			_board[i][j] = board[i][j];
	make_move(move);
	//ShowField();
	//unmake_move(move);
	//ShowField();
	
	//enemie's turn

	game_move moves[MAX_MOVES];
	int cnt=gen_moves(moves);
	bool ok = true;
	for(int i = 0; i < cnt; i++)
	{
		if(deep_think2(moves[i]) == false)
		{
			ok = false;
			break;
		}
	}	
	unmake_move(move);

	for(int i = 0; i < BOARD_SIZE; i++)
		for(int j = 0; j < BOARD_SIZE; j++)
			if(_board[i][j] != board[i][j])
			{
				++*(int*)0;
			}

	return ok;
}

bool Without_Answer(game_move move)
{
	int i = move.ey;
	int j = move.ex;	
        for(int dj=-1;dj<=1; dj += 2) {
          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 && (board[ni][nj]!=EMPTY)) {
            return false;
          }
        }
		return true;
}

void ShowField()
{
	for(int i = BOARD_SIZE - 1; i >= 0; i--)
	{
		for(int j = 0; j < BOARD_SIZE; j++)
			if(board[i][j] == WHITE)
				printf("W");
			else if(board[i][j] == BLACK)
				printf("B");
			else
				printf(".");
		printf("\n");
	}
	printf("---------------\n");
}

void think(char *str) {
	for(int i = 0; i < BOARD_SIZE; i++)
	  for(int j = 0; j < BOARD_SIZE; j++)
		  or_board[i][j] = board[i][j];

	//ShowField();
 
	game_move moves[MAX_MOVES];
	int cnt=gen_moves(moves);
	game_move &move = moves[rand()%cnt];
	//game_move test[MAX_MOVES];	

	vector <game_move> vgm;

	//0. win-principle
	for(int i = 0; i < cnt; i++)
	{
		if(IsWinning(moves[i]))
		{
			move = moves[i];
			goto fin;
		}
	}
	//0.5 next-turns emulation
	/*for(int i = 0; i < cnt; i++)
	{
		bool flag = deep_think(moves[i]);
		if(flag == true)
		{
			move = moves[i];
			goto fin;
		}
	}*/

	
	//1. aggresive-principle	
	for(int i = 0; i < cnt; i++)
	{		
		if(moves[i].is_capture)
		vgm.push_back(moves[i]);		
	}
	//choise
	//1.1.kill without answer
	double _length = 0;
	for(int i = 0; i < vgm.size(); i++)
	{		
		if(Without_Answer(vgm[i]) == true)
		{
			if(fabs((double)vgm[i].ey - (color == WHITE)? 3.75 : 2.75) > _length)
			{
				_length = fabs((double)vgm[i].ey - (color == WHITE)? 3.75 : 2.75);
				move = vgm[i];
			}
		}
	}
	if(_length > 0)
	{
		goto fin;
	}
	//1.2. kill with answer
	_length = 0;
	for(int i = 0; i < vgm.size(); i++)
	{		
		if(fabs((double)vgm[i].ey - (color == WHITE)? 3.75 : 2.75) > _length)
			{
				_length = fabs((double)vgm[i].ey - (color == WHITE)? 3.75 : 2.75);
				move = vgm[i];
			}
	}
	if(_length > 0)
	{
		goto fin;
	}
	//2. save-principle
	_length = (color == WHITE) ? BOARD_SIZE + 1 : -1;
	for(int i = 0; i < cnt; i++)
	{
		if(moves[i].is_capture == false)
		{
			if(Without_Answer(moves[i]) && ( (color == WHITE) ? moves[i].ey < _length : moves[i].ey > _length))
			{
				_length = moves[i].ey;
				move = moves[i];
			}
		}
	}
	if(_length != (color == WHITE) ? BOARD_SIZE + 1 : -1)
	{
		goto fin;
	}

	

	//3. analyzer	
	move = moves[rand()%cnt];
fin:

  //sprintf(str,"%c%d%c%d",move.sy+'a',move.sx+1,move.ey+'a',move.ex+1);
  sprintf(str,"%c%d%c%d",move.sx+'a',move.sy+1,move.ex+'a',move.ey+1);
  
  make_move(move);
  //ShowField();
}

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