Решение минимакса для игры с нулевой суммой с использованием рекурсии Python - PullRequest
Новая
       54

Решение минимакса для игры с нулевой суммой с использованием рекурсии Python

0 голосов
/ 06 октября 2018

Я пытаюсь реализовать алгоритм Minimax для игры с нулевой суммой.У меня есть 3 функции: одна, которая выбирает лучший ход, одна, которая максимизирует полезность, и одна, которая минимизирует ее.get_moves() возвращает список кортежей со столбцами и строками в каждом кортеже.apply_move() делает ход и применяет его к текущему состоянию доски и генерирует новое состояние доски.utility_value возвращает разницу очков между текущим игроком и противником.

Метод MIN: 

def min_node(board, color):
sys.setrecursionlimit(100000)

# define player
player = 1 if color == 'dark' else 2

utility = math.inf

# get possible moves.
possible_moves = get_moves(board, player)

best_utility = math.inf
if len(possible_moves) > 0:
    for move in possible_moves:
        new_board = apply_move(board, player, move[0], move[1])
        max_color = 'dark' if color == 'light' else 'light'
        utility = max_node(new_board, max_color)
        if utility < best_utility:
            best_utility = utility

else:
    return utility_value(board, color)

return best_utility

Метод MAX: 

def max_node(board, color):

sys.setrecursionlimit(100000)
# define player
player = 1 if color == 'dark' else 2

best_utility = -math.inf

# get possible moves. 
possible_moves = get_moves(board, player)

if len(possible_moves) > 0:
    for move in possible_moves:
        new_board = apply_move(board, player, move[0], move[1])
        min_color = 'light' if color == 'dark' else 'dark'
        utility = min_node(new_board, min_color)
        if utility > best_utility:
            best_utility = utility
else:
    return utility_value(board, color)

return best_utility

ВЫБРАТЬ ЛУЧШИЙ ДВИГАТЕЛЬ: 

def select_move(board, color):

player = 1 if color == 'dark' else 2
best_move = (0,0)
best_utility = -math.inf
possible_moves = get_moves(board, player)
if len(possible_moves) > 0:
    best_move = possible_moves[0]
    print(best_move)

    for move in possible_moves:
        new_board = apply_move(board, player, move[0], move[1])
        utility = min_node(new_board, color)
        if utility > best_utility:
            best_move = move
            best_utility = utility

return best_move

После запуска кода я не получаю желаемого результата.Эта проблема может лежать где-то еще в программе, кроме методов, которые я выложил здесь, но мне было интересно, был ли вышеуказанный подход верным для решения минимаксной задачи.

...