/*------------------------------------------------------------
TEAM43
A
225
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)

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

inline bool check_border(int i)
{ return i >= 0 && i < BOARD_SIZE; }

inline int direction()
{ return color == WHITE ? 1 : -1; }

bool is_attacked(int i, int j)
{
	int dir = direction();
	int op = op_color(color);
	for (int jk = j-1;jk <= j+1; jk+=2) {
		if (check_border(jk) && board[i + dir][jk] == op)
			return true;
	}
	return false;
}

	//static FILE *white_file = fopen("white.txt", "w");
	//static FILE *black_file = fopen("black.txt", "w");

int gen_moves(game_move *moves, game_move * & attack_move, bool check) {
  int cnt = 0;
  int dir = direction();
  static game_move six;
  static game_move five;
  bool has_six = false;
  bool has_five = false;
  static int safes[20];
  safes[0] = 0;
  int safe_max = -1;
  int safe_count = 0;
  for(int i = (color == BLACK ? 0 : (BOARD_SIZE - 1));i<BOARD_SIZE && i >= 0;i-=dir) {
    for(int j=0;j<BOARD_SIZE;++j) {
      if(board[i][j]==color) {
        for(int dj=-1;dj<=1;++dj) {
          int ni=i+direction();
          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};
			if (check) {
				if (color == WHITE ? (i == 6) : (i == 1)) {
					attack_move = 0;
					moves[0] = move;
					return 1;
				}
				if (!has_six && (color == WHITE ? (i == 5) : (i == 2))) {  
					if (!is_attacked(ni, nj)) {
						if (attack_move && (attack_move->ey == ni && !is_attacked(attack_move->ex, attack_move->ey)))
							attack_move = 0;
						six = move;
						has_six = true;
					}
				}
				if (!has_five && (color == WHITE ? (i == 4) : (i == 3))) {  
				}
				if (!is_attacked(ni, nj))
				{
					if (safe_max == ni || safe_max == -1) {
						moves[cnt++]=move;
						safe_max = ni;
						safes[safe_count]++;
					}
				}
			} else {
				moves[cnt++]=move;
			}
		  }
		}
	    if (check) {
		  if (safes[safe_count] > 0) {
			  safes[++safe_count] = 0;
		  }
	    }
      }
    }
  }
//  fprintf(black_file, "Next turn\n");
  if (has_six) {
	  moves[0] = six;
	  return 1;
  }
  if (has_five) {
	  moves[0] = five;
	  return 1;
  }
  if (check && cnt > 0) {
	  int cur = rand() % safe_count;
	  int min = 0;
	  for (int i = 0; i < cur; i++)
		  min += safes[safe_count];
	  for (int i = 0; i < safes[cur]; i++)
		  moves[i] = moves[min + i];
	  return safes[cur];
  } else {
	  return cnt;
  }
}

int gen_moves(game_move *moves, game_move * & attack_move) {
  int cnt = gen_moves(moves, attack_move, true);
  if (cnt == 0)
	  cnt = gen_moves(moves, attack_move, false);
  return cnt;
}

game_move *guess_attack()
{
	static game_move move;
	game_move *final_move = 0;
	bool has_move = false;
	int opponent = op_color(color);
	int dir = direction();
	for(int i = (color == WHITE ? 0 : (BOARD_SIZE - 1));i<BOARD_SIZE && i >= 0;i+=dir) {
		for(int j=0;j<BOARD_SIZE;++j) {
			if (board[i][j] == color) {
				if (check_border(j + 1) && board[i + dir][j + 1] == opponent) {
					game_move move_={i,j,i + dir,j + 1,true};
					move = move_;
					final_move = &move;
					if (!is_attacked(i+dir, j+1))
						break;
				}
				if (check_border(j - 1) && board[i + dir][j - 1] == opponent) {
					game_move move_={i,j,i + dir,j - 1,true};
					move = move_;
					final_move = &move;
					if (!is_attacked(i+dir, j-1))
						break;
				}
			}
		}
		if (final_move)
			return final_move;
	}
	return final_move;
}

void think(char *str) {
  game_move *move = guess_attack();
  bool attack = !!move;
  static game_move moves[MAX_MOVES];
  int cnt = gen_moves(moves, move);
  if (!move) {
	  move=&moves[rand()%cnt];
  }
  //FILE *file = color == WHITE ? white_file : black_file;
  sprintf(str,"%c%d%c%d",move->sy+'a',move->sx+1,move->ey+'a',move->ex+1);
	/*fprintf(file, "%d %d %s %d %d\n", color, direction(), str, attack ? 1 : 0, cnt);
	for (int i = 0; i < cnt; i++) {
		fprintf(file,"%c%d%c%d ",moves[i].sy+'a',moves[i].sx+1,moves[i].ey+'a',moves[i].ex+1);
	}
	fprintf(file, "\n");
	fflush(file);*/
  make_move(*move);
}

int main() {
  srand(time(0) ^ int((void*)&think));
  init();
  //color = BLACK;
  for(;;) {
    char str[100];
    gets(str);
    if(!strcmp(str,"Name")) {
      // Request for the bot name
      printf("Onyx\n");
      fflush(stdout);
    }
    else if(!strcmp(str,"Quit")) {
      // Game is over
      break;
    }
    else {
      if(strcmp(str,"Start")) {
        // Enemy's move
        make_move(str);
	  } else {
		  //color = WHITE;
	  }
      // Our move
      think(str);
      printf("%s\n",str);
      fflush(stdout);
    }
  }
	//fclose(black_file);
	//fclose(white_file);
  return 0;
}
