[Python] Tic-Tac-Toe: Minimax algorithm

틱-택-토

틱택토는 3*3 보드 위에 3칸 1줄(가로, 세로, 대각선 중 하나)을 먼저 완성하는 쪽이 이기는 보드게임입니다. 

따라서 모든 경우의 수는 9! = 362_880

이 정도라면 가지치기를 하지 않고 퓨어한 미니 맥스 알고리듬으로 돌릴 수 있습니다. 

*막대기게임처럼 max에서 score==1, min에서 score==-1을 찾으면 break 했습니다. 
이것만 하더라도 반응 속도가 상당히 빨라집니다. 

game_board: str = '_' * 9

AI = True
HUMAN = False

AI_MARK = 'X'
HUMAN_MARK = 'O'


def main():
    player: bool = AI
    # player: bool = HUMAN
    print('initializing ...')
    if player == HUMAN:
        print("\nBRD KEY\n___ 789\n___ 456\n___ 123")
    while find_empty(game_board) and not is_end(game_board):
        if player == AI:
            position, _ = minimax(game_board, 9, AI)
            place(position, AI_MARK)
            player = HUMAN
        else:
            position = input_num()
            place(position, HUMAN_MARK)
            player = AI
        draw()
    ending()


def find_empty(board: str) -> tuple[int, ...]:
    return tuple(x for x, cell in enumerate(board) if cell == '_')


def is_end(board: str) -> bool:
    return is_win(board, AI_MARK) or is_win(board, HUMAN_MARK)


def is_win(board, player):
    for (x, y, z) 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[x] == board[y] == board[z]:
            if board[x] == player:
                return True
    return False


def minimax(board: str, depth: int, max_player: bool) -> tuple:
    position = -1
    if depth == 0 or not find_empty(board) or is_end(board):
        return -1, evaluate(board)
    if max_player == AI:
        value = float('-inf')
        for each in find_empty(board):
            _, score = minimax(board[:each] + AI_MARK + board[each + 1:], depth - 1, HUMAN)
            if score > value:
                value = score
                position = each
            if score == 1:
                break
    else:
        value = float('inf')
        for each in find_empty(board):
            _, score = minimax(board[:each] + HUMAN_MARK + board[each + 1:], depth - 1, AI)
            if score < value:
                value = score
                position = each
            if score == -1:
                break
    return position, value


def evaluate(board: str) -> int:
    if is_win(board, AI_MARK):
        score = 1
    elif is_win(board, HUMAN_MARK):
        score = -1
    else:
        score = 0
    return score


def place(x: int, player: str) -> bool:
    if is_valid(x):
        global game_board
        game_board = game_board[:x] + player + game_board[x + 1:]
        return True
    return False


def is_valid(x: int) -> bool:
    return x in find_empty(game_board)


def input_num() -> int:
    num = -1
    while num not in find_empty(game_board):
        input_str = ''
        while not input_str.isdecimal():
            input_str = input('\n1~9?')
        num = int(input_str) - 1
    return num


def draw():
    print(f'\nBRD KEY\n{game_board[6:]} 789\n{game_board[3:6]} 456\n{game_board[:3]} 123')


def ending():
    if is_win(game_board, AI_MARK):
        print('AI Win')
    elif is_win(game_board, HUMAN_MARK):
        print('HUMAN Win')
    else:
        print('Tie')


if __name__ == '__main__':
    main()

initializing ...

BRD KEY
___ 789
___ 456
X__ 123

1~9?5

BRD KEY
___ 789
_O_ 456
X__ 123

BRD KEY
___ 789
_O_ 456
XX_ 123

1~9?3

BRD KEY
___ 789
_O_ 456
XXO 123

BRD KEY
X__ 789
_O_ 456
XXO 123

1~9?4

BRD KEY
X__ 789
OO_ 456
XXO 123

BRD KEY
X__ 789
OOX 456
XXO 123

1~9?9

BRD KEY
X_O 789
OOX 456
XXO 123

BRD KEY
XXO 789
OOX 456
XXO 123
Tie