Я программирую крестики-нолики, используя алгоритм минимакса с альфа-бета-обрезкой после приема Гарвардского CS-50. Моя логика работает отлично, за исключением времени возврата минимакса (особенно при первом вызове, когда играл только один игрок). Я думал заменить лишний рекурсивный вызов минимакса на значение max / min. Я хочу подчеркнуть, что минимакс выполняется относительно медленно для моих целей (около 0,5 секунды) и что я не могу использовать предварительно вычисленные данные.
import math
import copy
import time
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.
"""
if board == initial_state():
return X
X_counter = 0
O_counter = 0
for row in board:
for cell in row:
if cell == X:
X_counter += 1
elif cell == O:
O_counter += 1
return O if X_counter > O_counter else X
def actions(board):
"""
Returns set of all possible actions (i, j) available on the board.
"""
possible_moves = set()
for i in range(3):
for j in range(3):
if board[i][j] is None:
possible_moves.add((i, j))
return possible_moves
def result(board, action):
"""
Returns the board that results from making move (i, j) on the board.
"""
newboard = copy.deepcopy(board)
newboard[action[0]][action[1]] = player(board)
return newboard
def winner(board):
"""
Returns the winner of the game, if there is one.
"""
if board[0][0] == board[0][1] == board[0][2] != None: # 1, 2, 3
return board[0][0]
if board[1][0] == board[1][1] == board[1][2] != None: # 4, 5, 6
return board[1][0]
if board[2][0] == board[2][1] == board[2][2] != None: # 7, 8, 9
return board[2][0]
if board[0][0] == board[1][0] == board[2][0] != None: # 1, 4, 7
return board[0][0]
if board[0][1] == board[1][1] == board[2][1] != None: # 2, 5, 8
return board[0][1]
if board[0][2] == board[1][2] == board[2][2] != None: # 3, 6, 9
return board[0][2]
if board[0][0] == board[1][1] == board[2][2] != None: # 1, 4, 7
return board[0][0]
if board[0][2] == board[1][1] == board[2][0] != None: # 3, 5, 7
return board[0][2]
return None
def terminal(board):
"""
Returns True if game is over, False otherwise.
"""
def check_draw(board):
for row in board:
for cell in row:
if cell is None:
return False
return True
if winner(board) is not None or check_draw(board): # or someone won , or there is a draw
return True
return False
def utility(board):
"""
Returns 1 if X has won the game, -1 if O has won, 0 otherwise.
"""
temp = winner(board)
if temp == X:
return 1
elif temp == O:
return -1
return 0
def minimax(board):
"""
Returns the optimal action for the current player on the board.
"""
options = actions(board)
if player(board) == X:
vT = -math.inf
move = set()
for action in options:
v, count = minvalue(result(board,action), -math.inf, math.inf, 0)
if v > vT:
vT = v
move = action
else:
vT = math.inf
move = set()
for action in options:
v, count = maxvalue(result(board,action), -math.inf, math.inf, 0)
if v < vT:
vT = v
move = action
return move
def maxvalue(board,alpha,beta,count):
"""
Calculates the max value of a given board recursively together with minvalue
"""
if terminal(board): return utility(board), count+1
v = -math.inf
posactions = actions(board)
for action in posactions:
vret, count = minvalue(result(board, action),alpha,beta,count)
v = max(v, vret)
alpha = max(alpha, v)
if alpha > beta:
break
return v, count+1
def minvalue(board,alpha,beta,count):
"""
Calculates the min value of a given board recursively together with maxvalue
"""
if terminal(board): return utility(board), count+1
v = math.inf
posactions = actions(board)
for action in posactions:
vret, count = maxvalue(result(board, action),alpha,beta,count)
v = min(v, vret)
beta = min(v, beta)
if alpha > beta:
break
return v, count + 1