Instructions
Requirements and Specifications
Source Code
"""
Tic Tac Toe Player
"""
import math
import copy
import random
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.
"""
xCounter = 0
oCounter = 0
for i in range(0, len(board)):
for j in range(0, len(board[0])):
if board[i][j] == X:
xCounter += 1
elif board[i][j] == O:
oCounter += 1
if xCounter > oCounter:
return O
else:
return X
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
possibleActions = set()
for i in range(0, len(board)):
for j in range(0, len(board[0])):
if board[i][j] == EMPTY:
possibleActions.add((i, j))
return possibleActions
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
# Create new board, without modifying the original board received as input
result = copy.deepcopy(board)
result[action[0]][action[1]] = player(board)
return result
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
# Check rows
if board[0][0] == board[0][1] and board[0][1] == board[0][2] and board[0][0] is not None:
return board[0][0]
elif board[1][0] == board[1][1] and board[1][1] == board[1][2] and board[1][0] is not None:
return board[1][0]
elif board[2][0] == board[2][1] and board[2][1] == board[2][2] and board[2][0] is not None:
return board[2][0]
# Check columns
if board[0][0] == board[1][0] and board[1][0] == board[2][0] and board[0][0] is not None:
return board[0][0]
elif board[0][1] == board[1][1] and board[1][1] == board[2][1] and board[0][1] is not None:
return board[0][1]
elif board[0][2] == board[1][2] and board[1][2] == board[2][2] and board[0][2] is not None:
return board[0][2]
# Check diagonals
elif board[0][0] == board[1][1] and board[1][1] == board[2][2] and board[0][0] is not None:
return board[0][0]
elif board[0][2] == board[1][1] and board[1][1] == board[2][0] and board[0][2] is not None:
return board[0][2]
else:
return None
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
if winner(board) is None:
return False
else:
return True
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
if terminal(board):
if winner(board) == X:
return 1
elif winner(board) == O:
return -1
else:
return 0
def minimax(board):
"""
the Minimax algorithm instead of selecting at random
"""
if terminal(board):
print('Nodes traversed:', 1)
return None
else:
best_result = minimax_step(board, X == player(board))
print('Nodes traversed:', best_result[2])
return best_result[0]
def minimax_step(board, maximizing):
if terminal(board):
return [None, utility(board), 1]
if maximizing:
value = -10
best_action = None
traversed = 0
for action in actions(board):
next_board = result(board, action)
next_result = minimax_step(next_board, not maximizing)
traversed += next_result[2]
if next_result[1] > value:
value = next_result[1]
best_action = action
return [best_action, value, traversed + 1]
else:
value = 10
best_action = None
traversed = 0
for action in actions(board):
next_board = result(board, action)
next_result = minimax_step(next_board, not maximizing)
traversed += next_result[2]
if next_result[1] < value:
value = next_result[1]
best_action = action
return [best_action, value, traversed + 1]
def minimax_alphabeta(board):
"""
the Minimax-alphabeta algorithm instead of selecting at random
"""
if terminal(board):
print('Nodes traversed:', 1)
return None
else:
best_result = minimax_alphabeta_step(board, -100, 100, X == player(board))
print('Nodes traversed:', best_result[2])
return best_result[0]
def minimax_alphabeta_step(board, alpha, beta, maximizing):
if terminal(board):
return [None, utility(board), 1]
if maximizing:
value = -10
best_action = None
traversed = 0
for action in actions(board):
next_board = result(board, action)
next_result = minimax_alphabeta_step(next_board, alpha, beta, not maximizing)
traversed += next_result[2]
if next_result[1] > value:
value = next_result[1]
best_action = action
alpha = max(alpha, value)
if value >= beta:
break
return [best_action, value, 1+ traversed]
else:
value = 10
best_action = None
traversed = 0
for action in actions(board):
next_board = result(board, action)
next_result = minimax_alphabeta_step(next_board, alpha, beta, not maximizing)
traversed += next_result[2]
if next_result[1] < value:
value = next_result[1]
best_action = action
beta = min(beta, value)
if value <= alpha:
break
return [best_action, value, 1 + traversed]