Run minimax and alpha-beta on the same tic-tac-toe position, counting nodes. Show they return the same move/value but alpha-beta visits fewer nodes.

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, counter): counter[0] += 1 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', counter); 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', counter); b[i] = ' ' if val < best: best, best_move = val, i return best, best_move def alphabeta(b, player, alpha, beta, counter): counter[0] += 1 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, _ = alphabeta(b, 'O', alpha, beta, counter); b[i] = ' ' if val > best: best, best_move = val, i alpha = max(alpha, best) if alpha >= beta: break return best, best_move else: best = 2 for i in moves: b[i] = 'O'; val, _ = alphabeta(b, 'X', alpha, beta, counter); b[i] = ' ' if val < best: best, best_move = val, i beta = min(beta, best) if alpha >= beta: break return best, best_move board = ['X', 'O', 'X', ' ', ' ', ' ', 'O', ' ', ' '] c1 = [0] v1, m1 = minimax(list(board), 'X', c1) c2 = [0] v2, m2 = alphabeta(list(board), 'X', -2, 2, c2) print(f"minimax: move {(m1//3, m1%3)} value {v1:+d} nodes {c1[0]}") print(f"alphabeta: move {(m2//3, m2%3)} value {v2:+d} nodes {c2[0]}") print(f"same result: {v1 == v2 and m1 == m2}, alpha-beta fewer nodes: {c2[0] < c1[0]}")