Простейший возможный искусственный интеллект Tic Tac Toe на Python

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

• «Приятный» игровой опыт (возможность получать данные от пользователя и распечатывать доску после каждого хода)
• Обработка неправильных входных данных без сбоев.
• Иметь непобедимый ИИ в качестве противника.
• Возможность играть снова или выйти после окончания игры

В результате получился такой код:

def p(b):
    c = [' ' if i == 0 else 'X' if i == -1 else 'O' if i == 1 else i for i in b]
    [print(f'n{c[r*3:3+r*3]}') if r == 0 else print(c[r*3:3+r*3]) for r in range(3)]
def e(b, t):
    for p in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]):
        if b[p[0]] == b[p[1]] == b[p[2]] == t: return 1
def n(b, d, t):
    if e(b, t): return 0, (9+d)
    if e(b, -t): return 0, -(9 + d)
    if 0 not in b: return 0, 0
    x = -20
    for m in [i for i in range(9) if not b[i]]:
        b[m] = t
        s = -n(b, d - 1, -t)[1]
        b[m] = 0
        if s > x: x, y = s, m
    return y, x
def r():
    b, w = [0]*9, -1
    p(b)
    while 1:
        if w == -1 and not (e(b, w) or e(b, -w)) and 0 in b:
            while 1:
                u = input('nPlease enter your move (1-9): ')
                if u.isnumeric():
                    u = int(u)-1
                    if 0 <= u < 9 and not b[u]:
                        b[u], w = -1, w*-1
                        p(b)
                        break
        elif w == 1 and not (e(b, w) or e(b, -w)) and 0 in b:
            m, s = n(b, 8, 1)
            b[m], w = 1, w*-1
            p(b)
        else:
            f="You won!" if e(b, -1) else 'AI won!' if e(b, 1) else 'Game drawn!'
            if input(f'n{f} Do you want to play again (y/n)? ') != 'y': break
            r()
            break
r()

И с небольшими комментариями, чтобы легче понять, что происходит:

# Printing the board on the "standard" format with X:s and O:s instead of -1, 0, 1. 
def print_board(board):
    new_board = [' ' if i == 0 else 'X' if i == -1 else 'O' if i == 1 else i for i in board]
    [print(f'n{new_board[row*3:3+row*3]}') if row == 0 else print(new_board[row*3:3+row*3]) for row in range(3)]  # Print with new line to get nicer format
    
# Evaluates the board
def evaluate(boart, turn):
    for pos in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]):  # Go through all possible winning lines
        if board[pos[0]] == board[pos[1]] == board[pos[2]] == turn: return 1  # Return 1 if player turn has 3 in a row

# Recursive negamax function which goes through the entire game tree.
# Depth d is used in the returned scores to get shortest possible route to victory. 
def negamax(board, depth, turn):
    if evaluate(board, turn): return 0, (9+depth)  # Return positive score if maximizing player
    if evaluate(board, -turn): return 0, -(9 + depth)  # Return negative score if minimizing player wins
    if 0 not in board: return 0, 0  # Drawn game, return 0
    best_score = -20  # Initiate with less than smallest possible score
    for move in [i for i in range(9) if not board[i]]:  # Go through all empty squares on board
        board[move] = turn  # Make move
        score = -negamax(board, depth - 1, -turn)[1]  # Recursive call to go through all child nodes
        board[move] = 0  # Unmake the move
        if score > best_score: best_score, best_move = score, move  # If score is larger than previous best, update score
    return best_move, best_score  # Return the best move and its corresponding score

# Main game loop.
def run():
    board, turn = [0]*9, -1  # Initiate board and turn to move (-1 is human to start, 1 AI to start)
    print_board(board)
    while 1:  # Loop until game is over
        if turn == -1 and not (evaluate(board, turn) or evaluate(board, -turn)) and 0 in board:  # Human turn if game is not over and there are places left on board
            while 1:  # Loop until a valid input is given
                user_input = input('nPlease enter your move (1-9): ')  # Get input
                if user_input.isnumeric():  # Find if a number is entered
                    u = int(user_input)-1  # Get it on the right board format (square 1 corresponds to array[0])
                    if 0 <= u < 9 and not board[u]:  # Check if number is in the correct range and on an empty square
                        board[u], turn = -1, turn*-1  # Make move and change turn
                        print_board(board)
                        break
        elif turn == 1 and not (evaluate(board, turn) or evaluate(board, -turn)) and 0 in b:  # Ai turn if game is not over and there are places left on board
            move, score = negamax(board, 8, 1)  # Run Negamax loop to get a best move and the score
            board[move], turn = 1, turn*-1  # Make move and change turn
            print_board(board)
        else:  # This means the game is over or board is full
            text="You won!" if evaluate(board, -1) else 'AI won!' if evaluate(board, 1) else 'Game drawn!'  # Check who won or if there is a draw
            if input(f'n{text} Do you want to play again (y/n)? ') != 'y': break  # Ask to play again, break if answer is not 'y'
            run()  # Run game again if answer is 'y'
            break
run()  # Run the game loop

У меня вопрос: есть ли другие подходы, более простые с точки зрения количества персонажей для работающей игры с указанными выше требованиями? Конечно, текст ввода / вывода на консоль может быть короче, но я думаю, это не в счет 🙂

Что касается удобочитаемости и стиля PEP 8, конечно, есть много вещей, которые нужно улучшить, я хотел свести код к разумному минимуму строк.

Я надеюсь, что этот тип вопросов здесь разрешен, в противном случае удалите его.

РЕДАКТИРОВАТЬ: Пример игры, предложенный пользователем «superb rain» в комментариях:

['  ', ' ', ' ']
[' ', ' ', ' ']
[' ', ' ', ' ']

Please enter your move (1-9): 5

[' ', ' ', ' ']
[' ', 'X', ' ']
[' ', ' ', ' ']

['O', ' ', ' ']
[' ', 'X', ' ']
[' ', ' ', ' ']

Please enter your move (1-9): 4

['O', ' ', ' ']
['X', 'X', ' ']
[' ', ' ', ' ']

['O', ' ', ' ']
['X', 'X', 'O']
[' ', ' ', ' ']

Please enter your move (1-9): 2

['O', 'X', ' ']
['X', 'X', 'O']
[' ', ' ', ' ']

['O', 'X', ' ']
['X', 'X', 'O']
[' ', 'O', ' ']

Please enter your move (1-9): 3

['O', 'X', 'X']
['X', 'X', 'O']
[' ', 'O', ' ']

['O', 'X', 'X']
['X', 'X', 'O']
['O', 'O', ' ']

Please enter your move (1-9): 9

['O', 'X', 'X']
['X', 'X', 'O']
['O', 'O', 'X']

Game drawn! Do you want to play again (y/n)? 

Твой

def evaluate(boart, turn):
    for pos in ([0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]):
        if board[pos[0]] == board[pos[1]] == board[pos[2]] == turn: return 1

может быть

def evaluate(boart, turn):
    for i, j, k in [0, 1, 2], [3, 4, 5], [6, 7, 8], [0, 3, 6], [1, 4, 7], [2, 5, 8], [0, 4, 8], [2, 4, 6]:
        if board[i] == board[j] == board[k] == turn: return 1

То есть для индексов одиночные буквы i, j и k обычны и совершенно нормальны. И для кортежа скобки не нужны.

Вы также можете определить каждую строку с двумя значениями вместо трех. Как и в моем, которое я написал недавно:

def show():
    for i in range(0, 9, 3):
        print(*board[i : i+3])

def possible_moves(board):
    return (i for i in range(9) if isinstance(board[i], int))

def move(board, p, i):
    return board[:i] + [p] + board[i+1:]

def won(board):
    for i, d in (0, 1), (3, 1), (6, 1), (0, 3), (1, 3), (2, 3), (0, 4), (2, 2):
        if board[i] == board[i + d] == board[i + 2*d]:
            return True

def value(board, p, q):
    if won(board):
        return -1
    return -min((value(move(board, p, i), q, p)
                 for i in possible_moves(board)),
                default=0)

def best_move():
    return min(possible_moves(board),
               key=lambda i: value(move(board, 'O', i), 'X', 'O'))

board = list(range(1, 10))
try:
    while True:
        show()
        board = move(board, 'X', int(input('your move: ')) - 1)
        if won(board):
            raise Exception('You won!')
        if board.count('X') == 5:
            raise Exception('Draw!')
        board = move(board, 'O', best_move())
        if won(board):
            raise Exception('You lost!')
except Exception as result:
    show()
    print(result)

Демо-игра:

1 2 3
4 5 6
7 8 9
your move: 5
O 2 3
4 X 6
7 8 9
your move: 3
O 2 X
4 X 6
O 8 9
your move: 4
O 2 X
X X O
O 8 9
your move: 8
O O X
X X O
O X 9
your move: 9
O O X
X X O
O X X
Draw!

Как я уже сказал, я написал свое недавно, вы просто дали мне повод бросить его сюда :-). Так что моя программа не является «проверяемой» по отношению к вашей, и она не обрабатывает неверный ввод и не запрашивает другую игру (пользователь может просто запустить программу снова), но, возможно, вы найдете в ней что-то полезное.