Implement minimax for tic-tac-toe (X = MAX, O = MIN). Return the optimal move and game value for a winning board, and confirm the empty board is a draw.

Answer

WINS = [(0,1,2),(3,4,5),(6,7,8),(0,3,6),(1,4,7),(2,5,8),(0,4,8),(2,4,6)] def winner(b): for a, c, d in WINS: if b[a] != ' ' and b[a] == b[c] == b[d]: return b[a] return None def minimax(b, player): w = winner(b) if w == 'X': return 1, None if w == 'O': return -1, None moves = [i for i in range(9) if b[i] == ' '] if not moves: return 0, None best_move = None if player == 'X': best = -2 for i in moves: b[i] = 'X'; val, _ = minimax(b, 'O'); b[i] = ' ' if val > best: best, best_move = val, i return best, best_move else: best = 2 for i in moves: b[i] = 'O'; val, _ = minimax(b, 'X'); b[i] = ' ' if val < best: best, best_move = val, i return best, best_move board = ['X', 'O', 'X', ' ', ' ', ' ', 'O', ' ', ' '] val, move = minimax(board, 'X') rc = (move // 3, move % 3) outcome = {1: '(X wins)', 0: '(draw)', -1: '(O wins)'}[val] print(f"best move: {rc} value: {val:+d} {outcome}") drawn = [' '] * 9 val2, _ = minimax(drawn, 'X') print(f"empty board value: {val2:+d} 0 = draw with optimal play")