text: import random
  
  piceScore = {"K": 0, "Q": 10, "N": 3, "R": 5, "P": 1, "B": 3}
  CHECKMATE = 1000
  STALEMATE = 0
  DEPTH = 2
  
  
  def findRandomMove(validMoves):
      return validMoves[random.randint(0, len(validMoves)-1)]
  
  
  def findBestMoveMinMax(gs, validMoves):
      global nextMove
      nextMove = None
      findMoveMinMax(gs, validMoves, DEPTH, gs.whiteToMove)
      return nextMove
  
  
  def findMoveMinMax(gs, validMoves, depth, whiteToMove):
      global nextMove
      if depth == 0:
          return scoreMaterial(gs.board)
      if whiteToMove:
          maxScore = -CHECKMATE
          for move in validMoves:
              gs.makeMove(move)
              nextMoves = gs.getValidMoves()
              score = findMoveMinMax(gs, nextMoves, depth-1, False)
  
              if score > maxScore:
                  maxScore = score
                  if depth == DEPTH:
                      nextMove = move
              gs.undoMove()
          return maxScore
      else:
          minScore = CHECKMATE
          for move in validMoves:
              gs.makeMove(move)
              nextMoves = gs.getValidMoves()
              score = findMoveMinMax(gs, nextMoves, depth-1, True)
  
              if score < minScore:
                  minScore = score
                  if depth == DEPTH:
                      nextMove = move
              gs.undoMove()
          return minScore
  
  
  def scoreBoard(gs):
      if gs.checkMate:
          if gs.whiteToMove:
              return -CHECKMATE
          else:
              return CHECKMATE
      elif gs.staleMate:
          return STALEMATE
      score = 0
      for row in gs.board:
          for square in row:
              if square[0] == 'w':
                  score += piceScore[square[1]]
              elif square[0] == 'b':
                  score -= piceScore[square[1]]
      return score
  
  
  def findBestMove(gs, validMoves):
      turnMultiplier = 1 if gs.whiteToMove else -1
      opponentMinMaxScore = CHECKMATE
      bestPlayerMove = None
      random.shuffle(validMoves)
      for playerMove in validMoves:
          gs.makeMove(playerMove)
          opponentMoves = gs.getValidMoves()
          if gs.checkMate:
              score = -turnMultiplier * CHECKMATE
          elif gs.staleMate:
              score = STALEMATE
          else:
              opponentMaxScore = -CHECKMATE
              for opponentMove in opponentMoves:
                  gs.makeMove(opponentMove)
                  gs.getValidMoves()
                  if gs.checkMate:
                      score = CHECKMATE
                  elif gs.staleMate:
                      score = STALEMATE
                  else:
                      score = scoreMaterial(gs.board) * -turnMultiplier
                  if score > opponentMaxScore:
                      opponentMaxScore = score
                  gs.undoMove()
          if opponentMaxScore < opponentMinMaxScore:
              opponentMinMaxScore = opponentMaxScore
              bestPlayerMove = playerMove
          gs.undoMove()
      return bestPlayerMove
  
  
  def scoreMaterial(board):
      score = 0
      for row in board:
          for square in row:
              if square[0] == 'w':
                  score += piceScore[square[1]]
              elif square[0] == 'b':
                  score -= piceScore[square[1]]
      return score
  