UCT (Upper Confidence Bounds for Trees)の概要とアルゴリズム及び実装例について

import random
import math

class Node:
    def __init__(self, state, parent=None):
        self.state = state  # ゲームの状態
        self.parent = parent  # 親ノード
        self.children = []  # 子ノード
        self.visits = 0  # ノードへの訪問回数
        self.score = 0  # ノードの合計スコア

    def is_fully_expanded(self):
        return len(self.children) == len(self.state.get_legal_moves())

    def select_child(self):
        exploration_constant = 1.0 / math.sqrt(2.0)
        return max(self.children, key=lambda c: c.score / c.visits + exploration_constant * math.sqrt(2 * math.log(self.visits) / c.visits))

    def add_child(self, child_state):
        child = Node(child_state, self)
        self.children.append(child)
        return child

class TicTacToeState:
    def __init__(self):
        self.board = [[' ' for _ in range(3)] for _ in range(3)]
        self.current_player = 'X'
        self.last_move = None

    def clone(self):
        clone_state = TicTacToeState()
        clone_state.board = [row[:] for row in self.board]
        clone_state.current_player = self.current_player
        clone_state.last_move = self.last_move
        return clone_state

    def get_legal_moves(self):
        legal_moves = []
        for i in range(3):
            for j in range(3):
                if self.board[i][j] == ' ':
                    legal_moves.append((i, j))
        return legal_moves

    def move(self, move):
        i, j = move
        new_state = self.clone()
        new_state.board[i][j] = self.current_player
        new_state.current_player = 'O' if self.current_player == 'X' else 'X'
        new_state.last_move = move
        return new_state

    def is_terminal(self):
        for i in range(3):
            if self.board[i][0] == self.board[i][1] == self.board[i][2] != ' ':
                return True
            if self.board[0][i] == self.board[1][i] == self.board[2][i] != ' ':
                return True
        if self.board[0][0] == self.board[1][1] == self.board[2][2] != ' ':
            return True
        if self.board[0][2] == self.board[1][1] == self.board[2][0] != ' ':
            return True
        if all(self.board[i][j] != ' ' for i in range(3) for j in range(3)):
            return True
        return False

    def get_winner(self):
        for i in range(3):
            if self.board[i][0] == self.board[i][1] == self.board[i][2] != ' ':
                return 1 if self.board[i][0] == 'X' else -1
            if self.board[0][i] == self.board[1][i] == self.board[2][i] != ' ':
                return 1 if self.board[0][i] == 'X' else -1
        if self.board[0][0] == self.board[1][1] == self.board[2][2] != ' ':
            return 1 if self.board[0][0] == 'X' else -1
        if self.board[0][2] == self.board[1][1] == self.board[2][0] != ' ':
            return 1 if self.board[0][2] == 'X' else -1
        return 0

def uct_search(root_state, num_iterations):
    root_node = Node(root_state)

    for _ in range(num_iterations):
        node = root_node
        state = root_state.clone()

        # 選択
        while not state.is_terminal() and node.is_fully_expanded():
            node = node.select_child()
            state = state.move(node.state.last_move)

        # 展開
        if not state.is_terminal():
            unexplored_moves = [move for move in state.get_legal_moves() if move not in [child.state.last_move for child in node.children]]
            chosen_move = random.choice(unexplored_moves)
            state = state.move(chosen_move)
            node = node.add_child(state)

        # シミュレーション
        while not state.is_terminal():
            move = random.choice(state.get_legal_moves())
            state = state.move(move)

        # バックプロパゲーション
        while node is not None:
            node.visits += 1
            node.score += state.get_winner()
            node = node.parent

    return max(root_node.children, key=lambda c: c.visits).state.last_move

def main():
    state = TicTacToeState()

    while not state.is_terminal():
        if state.current_player == 'X':
            move = uct_search(state, 1000)
        else:
            print("O's turn. Enter move (row,col): ")
            move = tuple(map(int, input().split(',')))
        state = state.move(move)
        print(state.board[0])
        print(state.board[1])
        print(state.board[2])

    winner = state.get_winner()
    if winner == 1:
        print("X wins!")
    elif winner == -1:
        print("O wins!")
    else:
        print("Draw!")

if __name__ == "__main__":
    main()