Spaces:
Sleeping
Sleeping
File size: 3,051 Bytes
14ebb49 |
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 |
"""
Tic Tac Toe Player
"""
import math
X = "X"
O = "O"
EMPTY = None
def initial_state():
"""
Returns starting state of the board.
"""
return [[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY],
[EMPTY, EMPTY, EMPTY]]
def player(board):
"""
Returns player who has the next turn on a board.
"""
x_count = sum(row.count(X) for row in board)
o_count = sum(row.count(O) for row in board)
return X if x_count == o_count else O
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
return {(i, j) for i in range(3) for j in range(3) if board[i][j] == EMPTY}
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
if board[action[0]][action[1]] is not EMPTY:
raise Exception("Invalid action")
new_board = [row[:] for row in board]
new_board[action[0]][action[1]] = player(board)
return new_board
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
for line in board: # Check rows
if line[0] == line[1] == line[2] and line[0] is not None:
return line[0]
for col in range(3): # Check columns
if board[0][col] == board[1][col] == board[2][col] and board[0][col] is not None:
return board[0][col]
if board[0][0] == board[1][1] == board[2][2] and board[0][0] is not None: # Check diagonal
return board[0][0]
if board[0][2] == board[1][1] == board[2][0] and board[0][2] is not None: # Check anti-diagonal
return board[0][2]
return None
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
return winner(board) is not None or all(cell is not EMPTY for row in board for cell in row)
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
win = winner(board)
if win == X:
return 1
elif win == O:
return -1
else:
return 0
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
if terminal(board):
return None
turn = player(board)
def max_value(board):
if terminal(board):
return utility(board), None
v = -math.inf
best_move = None
for action in actions(board):
val, _ = min_value(result(board, action))
if val > v:
v = val
best_move = action
return v, best_move
def min_value(board):
if terminal(board):
return utility(board), None
v = math.inf
best_move = None
for action in actions(board):
val, _ = max_value(result(board, action))
if val < v:
v = val
best_move = action
return v, best_move
if turn == X:
_, move = max_value(board)
else:
_, move = min_value(board)
return move
|