kartikkukreja

if __name__ == '__main__':
  player = raw_input()
  boardSize = int(raw_input())
  grid = []
  for i in xrange(boardSize):
    grid.append(raw_input())
        
  IsPlayerBlack = player[0] == 'b'
  state = CheckersState([list(row.rstrip()) for row in grid], IsPlayerBlack, [])
  move = iterativeDeepeningAlphaBeta(state, piecesCount)

kartikkukreja

def iterativeDeepeningAlphaBeta(state, evaluationFunc):
  startTime = time()

  def alphaBetaSearch(state, alpha, beta, depth):
    def maxValue(state, alpha, beta, depth):
      val = -MaxUtility
      for successor in state.getSuccessors():
        val = max(val, alphaBetaSearch(successor, alpha, beta, depth))
        if val >= beta: return val
        alpha = max(alpha, val)

kartikkukreja

def piecesCount(state):
  # 1 for a normal piece, 1.5 for a king
  black, white = 0, 0
  for row in state.grid:
    for cell in row:
      if cell == 'b': black += 1.0
      elif cell == 'B': black += 1.5
      elif cell == 'w': white += 1.0
      elif cell == 'W': white += 1.5
  return black - white if IsPlayerBlack else white - black

kartikkukreja

from copy import deepcopy
from time import time

# Global Constants
MaxUtility = 1e9
IsPlayerBlack = True
MaxAllowedTimeInSeconds = 9.5
MaxDepth = 100

class CheckersState:

kartikkukreja

# alpha is the MAX's best option on path to root. Initialized to -infinity.
# beta is the MIN's best option on path to root. Initialized to +infinity.

def value(problem, state, player, alpha, beta):
  if problem.isTerminalState(state): return problem.getTerminalUtility(state)
  if player == "MAX": return maxValue(problem, state, player, alpha, beta)
  if player == "MIN": return minValue(problem, state, player, alpha, beta)
  
def maxValue(problem, state, player, alpha, beta):
  v = -infinity

kartikkukreja

def value(problem, state, player):
  if problem.isTerminalState(state): return problem.getTerminalUtility(state)
  if player == "MAX": return maxValue(problem, state, player)
  if player == "MIN": return minValue(problem, state, player)
  
def maxValue(problem, state, player):
  v = -infinity
  for successor in problem.getSuccessors(state):
    v = max(v, value(problem, successor, "MIN"))
  return v

kartikkukreja

class EightPuzzleProblem:
    # grid is 9-array of the 3x3 8-puzzle grid in row-major order
    # 0 represents empty block
    def __init__(self, grid):
        self.grid = list(grid)
        for i in xrange(len(grid)):
            if self.grid[i] == 0:
                self.pos0 = i
                break        

kartikkukreja

import heapq
class PriorityQueue:
  def __init__(self, priorityFunction):
    self.priorityFunction = priorityFunction
    self.heap = []
      
  def push(self, item):
    heapq.heappush(self.heap, (self.priorityFunction(item), item))
      
  def pop(self):

kartikkukreja

import heapq
class PriorityQueue:
  def __init__(self, priorityFunction):
    self.priorityFunction = priorityFunction
    self.heap = []
      
  def push(self, item):
    heapq.heappush(self.heap, (self.priorityFunction(item), item))
      
  def pop(self):

kartikkukreja

import heapq
class PriorityQueue:
  def __init__(self, priorityFunction):
    self.priorityFunction = priorityFunction
    self.heap = []
      
  def push(self, item):
    heapq.heappush(self.heap, (self.priorityFunction(item), item))
      
  def pop(self):