from __future__ import print_function
import sys
import random
import copy

directions = [ (-1, -1), (0, -1), (1, -1), 
               (-1,  0),          (1,  0), 
               (-1,  1), (0,  1), (1,  1) ]

board = [[0 for i in range(8)] for j in range(8)] # 8x8 two-dimensional array


def init_board():
  for r in range(8):
    for c in range(8):
      board[c][r] = 0
  board[4][3] = board[3][4] =  1 # black disks
  board[3][3] = board[4][4] = -1 # white disks


def print_board():
  print("\n  a b c d e f g h")
  for r in range(8):   # row
    print(r + 1, end = '')
    for c in range(8):   # column
      d = board[c][r]
      s = '.'
      if d ==  1:
        s = 'B' # black disk
      if d == -1:
        s = 'W' # white disk
      print(' ' + s, end = '')
    print()
  print()


def can_flip(side, square, direction): 
  n = 0
  c = square[0]
  r = square[1]
  while True:
    c += direction[0]
    r += direction[1]
    n += 1
    if c < 0 or c >= 8 or r < 0 or r >= 8:
      return False
    if board[c][r] != -side:
      break
  if board[c][r] == 0:
    return False
  if n <= 1:
    return False
  return True


def is_legal_move(side, square):
  if board[square[0]][square[1]] != 0:
    return False
  for i in range(8):
    if can_flip(side, square, directions[i]) == True:
      return True
  return False


def place_disk(side, square):
  n = 0
  for i in range(8):
    d = directions[i]
    if can_flip(side, square, d) == False:
      continue
    c = square[0] + d[0]
    r = square[1] + d[1]
    while board[c][r] == -side:
      board[c][r] = side
      n += 1
      c += d[0]
      r += d[1]
  board[square[0]][square[1]] = side
  return n


def generate_legal_moves(side, legal_moves):
  nmoves = 0
  nempty = 0
  for c in range(8):
    for r in range(8):
      if board[c][r] != 0:
        continue
      nempty += 1
      square = (c, r)
      if is_legal_move(side, square) == False:
        continue
      legal_moves.append(square)
      nmoves += 1
  if nempty == 0:
    return -1
  return nmoves


def count_disks():
  sum = 0
  for r in range(8):
    for c in range(8):
      sum += board[c][r]
  return sum


def evaluate():
  sum = 0
  for r in range(8):
    for c in range(8):
      sum += board[c][r]
  return sum


def select_move(turn):
  global board
  board0 = copy.deepcopy(board)

  best_value = -99999
  legal_moves = []
  nmoves = generate_legal_moves(turn, legal_moves)
  for move in legal_moves:
    place_disk(turn, move)

    value = evaluate() * turn
    print("move =", chr(ord('a') + move[0]) + chr(ord('1') + move[1]), ", value = ", value)
    if value > best_value:
      best_value = value
      best_move = move
    
    board = copy.deepcopy(board0)

  return best_move


def negamax(depth, max_depth, turn):
  global board

  if depth == max_depth:
    return turn * evaluate(), (-1, -1) 

  legal_moves = []
  nmoves = generate_legal_moves(turn, legal_moves)

  if nmoves <= 0:
    score, dummy = negamax(depth + 1, max_depth, -turn)
    return -score, (-1, -1)

  board0 = copy.deepcopy(board)

  best_score = -99999
  for move in legal_moves:
    place_disk(turn, move)
    score, dummy = negamax(depth + 1, max_depth, -turn)
    score *= -1
    if depth == 0:
      print("move =", chr(ord('a') + move[0]) + chr(ord('1') + move[1]), ", score = ", score)
    if score > best_score:
      best_move = move
      best_score = score
    board = copy.deepcopy(board0)

  return (best_score, best_move)


def main():
  random.seed(12345)

  argvs = sys.argv
  human_side = 0
  if len(argvs) >= 2:
    human_side = int(argvs[1])
  
  init_board()
  print_board()

  passed = { -1:False, 1:False }
  turn = 1
  while True:

    legal_moves = []
    nmoves = generate_legal_moves(turn, legal_moves)
    if nmoves == -1: 
      break     # no empty square
    if nmoves ==  0: 
      print("turn =", turn, " move = Pass")
      passed[turn] = True
      if passed[-turn] == True:
        break   # pass x 2
      turn *= -1
      continue  # pass (no legal move)
    passed[turn] = False

    if turn == human_side:
      while True:
        print("Where? ", end = '')
        buf = input()
        c = ord(buf[0]) - ord('a')
        r = ord(buf[1]) - ord('1')
        move = (c, r)
        if is_legal_move(turn, move) == True:
          break
    else:
      #move = legal_moves[random.randint(0, nmoves - 1)]
      #move = select_move(turn)
      score, move = negamax(0, 3, turn)
      print("turn =", turn, " move =", chr(ord('a') + move[0]) + chr(ord('1') + move[1]))
    place_disk(turn, move)
    print_board()
    turn *= -1

  d = count_disks()
  if d > 0:
    print("The winner is Black.")
  elif d < 0:
    print("The winner is White.")
  else:
    print("Draw.")


if __name__ == '__main__':
  main()