You are given a middle game situation of the game Tic Tac Toe. It is given that it is player "X's" turn and you need to give to most optimal position for the turn. The situation is given as a 3 x 3 character matrix board. '_' refers to the place is empty. 'o' refers that player O marked it in his turn at some time and 'x' refers that player X marked it in his turn at some time. It is player X's turn. Tell him the most optimal solution.(Assume player O played first). 
Example 1:
Input: board = {{o, _, _}, 
                {_, _, _}, 
                {_, _, _}}
Output: 1 1
Explaination: Placing a 'x' in the (1, 1) 
that is the center of the board is the most 
optimal approach for x.
Your Task:
You do not need to read input or print anything. Your task is to complete the function findBestMove() which takes board as input parameter and returns the best optimal move in a list where the first one is the row index and the second one is the column index.
Expected Time Complexity: O(2^{9})
Expected Auxiliary Space: O(1)
Constraints:
board[i][j] = 'o' / 'x' / '_'

Source: geeksforgeeks | Difficulty: MEDIUM_HARD

Starter code: #User function Template for python3

class Solution:
    def findBestMove(self, board):
        # code here

Solutions:
import math

class Solution:

	def findBestMove(self, board):
		tup = self.minimax(True, board, 1)[1]
		return (str(tup[0]), str(tup[1]))

	def minimax(self, is_max, board, depth):
		score = self.evaluate(board)
		moves = self.getMoves(board)
		if len(moves) == 0 or score != 0:
			return (0 if score == 0 else score - (depth if is_max else -1 * depth), None)
		if is_max:
			best_val = -math.inf
			best_move = None
			for move in moves:
				new_board = [[r[0], r[1], r[2]] for r in board]
				new_board[move[0]][move[1]] = 'x'
				(val, _) = self.minimax(False, new_board, depth + 1)
				if val > best_val:
					best_val = val
					best_move = move
			return (best_val, best_move)
		else:
			best_val = math.inf
			best_move = None
			for move in moves:
				new_board = [[r[0], r[1], r[2]] for r in board]
				new_board[move[0]][move[1]] = 'o'
				(val, _) = self.minimax(True, new_board, depth + 1)
				if val < best_val:
					best_val = val
					best_move = move
			return (best_val, best_move)

	def getMoves(self, board):
		moves = []
		for row in range(3):
			for col in range(3):
				if board[row][col] == '_':
					moves.append((row, col))
		return moves

	def evaluate(self, b):
		for i in range(3):
			if b[i][0] != '_' and b[i][0] == b[i][1] and (b[i][0] == b[i][2]):
				return -10 if b[i][0] == 'o' else 10
			if b[0][i] != '_' and b[0][i] == b[1][i] and (b[0][i] == b[2][i]):
				return -10 if b[0][i] == 'o' else 10
		if b[0][0] != '_' and b[0][0] == b[1][1] and (b[0][0] == b[2][2]):
			return -10 if b[0][0] == 'o' else 10
		if b[0][2] != '_' and b[0][2] == b[1][1] and (b[0][2] == b[2][0]):
			return -10 if b[0][0] == 'o' else 10
		return 0


class Solution:

	def isMovesLeft(self, board):
		for i in range(3):
			for j in range(3):
				if board[i][j] == '_':
					return True
		return False

	def evaluate(self, board):
		for row in range(3):
			if board[row][0] == 'o' and board[row][1] == 'o' and (board[row][2] == 'o'):
				return -10
			if board[row][0] == 'x' and board[row][1] == 'x' and (board[row][2] == 'x'):
				return 10
		for col in range(3):
			if board[0][col] == 'o' and board[1][col] == 'o' and (board[2][col] == 'o'):
				return -10
			if board[0][col] == 'x' and board[1][col] == 'x' and (board[2][col] == 'x'):
				return 10
		if board[0][0] == 'o' and board[1][1] == 'o' and (board[2][2] == 'o'):
			return -10
		if board[0][2] == 'o' and board[1][1] == 'o' and (board[2][0] == 'o'):
			return -10
		if board[0][0] == 'x' and board[1][1] == 'x' and (board[2][2] == 'x'):
			return 10
		if board[0][2] == 'x' and board[1][1] == 'x' and (board[2][0] == 'x'):
			return 10
		return 0

	def minimax(self, board, depth, isMax):
		score = self.evaluate(board)
		if score != 0:
			return score
		if self.isMovesLeft(board) == False:
			return 0
		if isMax:
			best = -1000
			for i in range(3):
				for j in range(3):
					if board[i][j] == '_':
						board[i][j] = 'x'
						best = max(best, self.minimax(board, depth + 1, not isMax))
						board[i][j] = '_'
			return best
		else:
			best = 1000
			for i in range(3):
				for j in range(3):
					if board[i][j] == '_':
						board[i][j] = 'o'
						best = min(best, self.minimax(board, depth + 1, not isMax))
						board[i][j] = '_'
			return best

	def findBestMove(self, board):
		bestVal = -1000
		bestMove = (-1, -1)
		for i in range(3):
			for j in range(3):
				if board[i][j] == '_':
					board[i][j] = 'x'
					moveVal = self.minimax(board, 0, False)
					board[i][j] = '_'
					if moveVal > bestVal:
						bestMove = (i, j)
						bestVal = moveVal
		return (str(bestMove[0]), str(bestMove[1]))


class Solution:

	def __init__(self):
		pass

	def findBestMove(self, board):
		now_best = -99999
		best_move = (-1, -1)

		def pos_moves(board):
			moves = []
			for (row_num, row) in enumerate(board):
				for (col_num, item) in enumerate(row):
					if item == '_':
						moves += [(row_num, col_num)]
			return moves

		def score(board):
			ROWS = [[(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)]]
			COLS = [[(i, j) for i in range(3)] for j in range(3)]
			DIAGS = [[(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]]
			ALL = ROWS + COLS + DIAGS
			for posns in ALL:
				now = ''
				for (i, j) in posns:
					now += board[i][j]
				if now == 'ooo':
					return -10
				elif now == 'xxx':
					return 10
			return 0

		def minmax(board, player):

			def pos_moves(board):
				moves = []
				for (row_num, row) in enumerate(board):
					for (col_num, item) in enumerate(row):
						if item == '_':
							moves += [(row_num, col_num)]
				return moves

			def score(board):
				ROWS = [[(0, 0), (0, 1), (0, 2)], [(1, 0), (1, 1), (1, 2)], [(2, 0), (2, 1), (2, 2)]]
				COLS = [[(i, j) for i in range(3)] for j in range(3)]
				DIAGS = [[(0, 0), (1, 1), (2, 2)], [(0, 2), (1, 1), (2, 0)]]
				ALL = ROWS + COLS + DIAGS
				for posns in ALL:
					now = ''
					for (i, j) in posns:
						now += board[i][j]
					if now == 'ooo':
						return -10
					elif now == 'xxx':
						return 10
				return 0
			nowscore = score(board)
			if nowscore == 10 or nowscore == -10:
				return nowscore
			if pos_moves(board) == []:
				return 0
			if player == 'x':
				best = -9999
				for (i, j) in pos_moves(board):
					board[i][j] = 'x'
					best = max(best, minmax(board, 'o'))
					board[i][j] = '_'
				return best
			else:
				best = 9999
				for (i, j) in pos_moves(board):
					board[i][j] = 'o'
					best = min(best, minmax(board, 'x'))
					board[i][j] = '_'
				return best
		moves = pos_moves(board)
		for (i, j) in moves:
			board[i][j] = 'x'
			mov_val = minmax(board, 'o')
			board[i][j] = '_'
			if mov_val > now_best:
				best_move = (i, j)
				now_best = mov_val
		(i, j) = best_move
		return (str(i), str(j))


p = 'x'
op = 'o'

def moves(b):
	for i in range(3):
		for j in range(3):
			if b[i][j] == '_':
				return True
	return False

def find(b):
	for i in range(3):
		if b[i][0] == b[i][1] and b[i][1] == b[i][2]:
			if b[i][0] == p:
				return 10
			elif b[i][0] == op:
				return -10
	for j in range(3):
		if b[0][j] == b[1][j] and b[1][j] == b[2][j]:
			if b[0][j] == p:
				return 10
			elif b[0][j] == op:
				return -10
	if b[0][0] == b[1][1] and b[1][1] == b[2][2]:
		if b[0][0] == p:
			return 10
		elif b[2][2] == op:
			return -10
	if b[0][2] == b[1][1] and b[1][1] == b[2][0]:
		if b[0][2] == p:
			return 10
		elif b[0][2] == op:
			return -10
	return 0

def findScore(b, d, mx):
	sc = find(b)
	if sc == 10:
		return sc
	if sc == -10:
		return sc
	if moves(b) == False:
		return 0
	if mx:
		a = -1000
		for i in range(3):
			for j in range(3):
				if b[i][j] == '_':
					b[i][j] = p
					a = max(a, findScore(b, d + 1, not mx))
					b[i][j] = '_'
		return a
	else:
		a = 1000
		for i in range(3):
			for j in range(3):
				if b[i][j] == '_':
					b[i][j] = op
					a = min(a, findScore(b, d + 1, not mx))
					b[i][j] = '_'
		return a

class Solution:

	def findBestMove(self, board):
		bv = -1000
		bm = (-1, -1)
		for i in range(3):
			for j in range(3):
				if board[i][j] == '_':
					board[i][j] = 'x'
					mv = findScore(board, 0, False)
					board[i][j] = '_'
					if mv > bv:
						bm = (i, j)
						bv = mv
		l = []
		l.append(str(bm[0]))
		l.append(str(bm[1]))
		return l