Минимаксный алгоритм в Tic, Tac, Toe с использованием python: рекурсия не заканчивается - PullRequest
Новая
       51

Минимаксный алгоритм в Tic, Tac, Toe с использованием python: рекурсия не заканчивается

0 голосов
/ 03 декабря 2018

Я очень новичок в программировании и хотел запрограммировать Tic, Tac, Toe Solver, используя минимаксный алгоритм.Когда я тестировал свою программу, она возвращает: максимальная глубина рекурсии превышена в сравнении.Я понятия не имею, почему моя рекурсия не остановится.Может ли кто-нибудь помочь мне с этой проблемой?Не стесняйтесь дать мне несколько советов о том, как улучшить мой код.

# in the scores list the scores of the moves are kept
scores = []
# in the empty_spots list all indices of the empty cells in the grid are kept
empty_spots = []

# function, which prints the grid
def show_grid(grid):
    a = 0
    for cell in grid:
        a = a + 1
        if cell == 1:
            if a < 3:
                print("X", end="")
            else:
                print("X")
                a = 0
        elif cell == -1:
            if a < 3:
                print("O", end="")
            else:
                print("O")
                a = 0
        else:
            if a < 3:
                print("_", end="")
            else:
                print("_")
                a = 0

# function which checks if there is a victory or draw
def check_victory(grid, player):
    Victory_Combos = [[0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [6, 4, 2]]
    for victorys in Victory_Combos:
        if grid[victorys[0]] == player*-1 and grid[victorys[1]] == player*-1 and grid[victorys[2]] == player*-1:
            return -10 * player
    if 0 not in grid:
        return 0

# function which finds all empty spots
def find_empty_spots(grid):
    for cell in range(9):
        if grid[cell] == 0:
            empty_spots.append(cell)
    return empty_spots



# minimax function
def minimax(grid, player, best_score, depth):
    if check_victory(grid, player) != None:
        return check_victory(grid, player)
    list = find_empty_spots(grid)
    for cell in list:
        grid[cell] = player
        scores.append(minimax(grid, player*-1, 1000*-player, depth + 1))
        if player == 1:
            best_score = -1000
            for score in scores:
                if best_score < score:
                    best_score = score
        else:
            best_score = 1000
            for score in scores:
                if best_score > score:
                    best_score = score
        grid[cell] = 0
    if depth == 0:
        grid[scores.index(best_score)] = player
        show_grid()
    scores.clear()
    return best_score



# example
print(minimax([-1,1,-1,1,1,0,1,-1,0],-1,1000,0))

1 Ответ

0 голосов
/ 03 декабря 2018

Проблема с вашим empty_spots, вы никогда не очищаете его, поэтому вы всегда проверяете предыдущие (пустые) ячейки. 

def find_empty_spots(grid):
    empty_spots = []
    for cell in range(9):
        if grid[cell] == 0:
            empty_spots.append(cell)
    return empty_spots

Добавлен empty_spots = [] для очистки списка перед каждым вызовом,иначе вы просто добавляете ячейки к уже существующему списку.

И еще одна вещь - list = find_empty_spots(grid) очень-очень неправильно, не используйте ключевые слова для имен переменных, правильный путь будет lst = find_empty_spots(grid),или лучше какое-то значимое имя, empty_cells = find_empty_spots(grid).

...