Игра "крестики нолики" на консоли python, алгоритм Минимакс

Взял алгоритм из интернета, но бот играет глупо. Помогите пожалуйста найти ошибку. Адаптировал код, написанный на C++: https://tproger.ru/translations/tic-tac-toe-minimax. Если человек выложил, то у него, вероятно, всё работает. Ошибка где-то у меня. Вот код:

import sys


sys.setrecursionlimit(1000000)  # увеличение глубины рекурсии

huplayer = 'X'
aiplayer = 'O'


class Move:
    index = -1
    score = 0


def get_empty_cells(board):
    # возвращает список пустых клеток
    l = []
    for i in board:
        if i != 'X' and i != 'O':
            l.append(i)
    return l

def check_win(board, player):
    # Проверяем, выиграл ли player
    if ((board[2] == player and board[4] == player and board[6] == player) or
            (board[0] == player and board[1] == player and board[2] == player) or
            (board[3] == player and board[4] == player and board[5] == player) or
            (board[6] == player and board[7] == player and board[8] == player) or
            (board[0] == player and board[3] == player and board[6] == player) or
            (board[1] == player and board[4] == player and board[7] == player) or
            (board[2] == player and board[5] == player and board[8] == player) or
            (board[0] == player and board[4] == player and board[8] == player)):
        return True
    else:
        return False


def minimax(new_board, player):
    global aiplayer, huplayer
    # доступные клетки
    avail_spots = get_empty_cells(new_board)

    if check_win(new_board, huplayer):
        return -10
    elif check_win(new_board, aiplayer):
        return 10
    elif len(avail_spots) == 0:
        return 0

    moves = []

    for i in range(len(avail_spots)):
        moves.append(Move())
        moves[i].index = new_board[avail_spots[i]]

        new_board[avail_spots[i]] = player

        if player == aiplayer:
            moves[i].score += minimax(new_board, huplayer)
        else:
            moves[i].score += minimax(new_board, aiplayer)

        new_board[avail_spots[i]] = moves[i].index

    best_move = -1

    if player == aiplayer:
        best_score = -10000
        for i in moves:
            if i.score > best_score:
                best_score = i.score
                best_move = i.index
    else:
        best_score = 10000
        for i in moves:
            if i.score < best_score:
                best_score = i.score
                best_move = i.index

    return best_move


def draw_board(board):
    # вывод игрового поля
    board4draw = []
    for j in board:
        if j in ('X', 'O'):
            board4draw.append(j)
        else:
            board4draw.append(' ')
    for h in range(3):

        print(f'|{board4draw[h*3]}|{board4draw[h*3 + 1]}|{board4draw[h*3 + 2]}|')


def game():
    board = [0, 1, 2, 3, 4, 5, 6, 7, 8]

    # main game loop
    run = True
    global aiplayer, huplayer
    player = aiplayer

    while run:

        if check_win(board, aiplayer): 
            print('bot win')
            run = False
            continue
        elif check_win(board, huplayer):
            print('you win')
            run = False
            continue
        empty_cells = get_empty_cells(board)
        if len(empty_cells) != 0:
            if player == aiplayer:
                print('bot made move:')
                bot_move = minimax(board, 'O')
                board[bot_move] = aiplayer
                draw_board(board)
                player = huplayer
                continue
            elif player == huplayer:
                human_move = int(input('ведите цифру: '))
                print('you made move:')
                board[human_move] = huplayer
                draw_board(board)
                player = aiplayer
                continue
        else:
            print('draw')
            run = False


game()

Пробовал менять аргументы функции минимакс при вызове в главном цикле - не помогло. Если будут вопросы - задавайте попробую ответить


Ответы (1 шт):

Автор решения: Роман Орлов

Закинул в программу поле с двумя пустыми клетками, дебагером прошел по программе и нашел наконец-то ошибку: последний return в функции minimax должен возвращать не только index, но и score, он нужен мне в этом цикле:

for i in range(len(avail_spots)):
    moves.append(Move())
    moves[i].index = new_board[avail_spots[i]]

    new_board[avail_spots[i]] = player

    if player == aiplayer:
        moves[i].score += minimax(new_board, huplayer)
    else:
        moves[i].score += minimax(new_board, aiplayer)

    new_board[avail_spots[i]] = moves[i].index

Здесь считываю не индекс, который может вернуть минимакс, а именно score.

Решил ее так: все return в minimax() переделал, чтобы они возвращали не int, а экземпляр класса Move. Когда надо - беру индекс, когда надо - score.

→ Ссылка