python用uct算法实现井字棋

可以使用以下代码实现：

import random

class Node:
    def __init__(self, state, parent=None):
        self.state = state
        self.parent = parent
        self.children = []
        self.wins = 0
        self.visits = 0

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

    def update(self, result):
        self.visits += 1
        self.wins += result

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

    def best_child(self, c_param=1.4):
        choices_weights = [
            (c.wins / c.visits) + c_param * math.sqrt((2 * math.log(self.visits) / c.visits))
            for c in self.children
        ]
        return self.children[choices_weights.index(max(choices_weights))]

    def rollout(self):
        current_rollout_state = self.state
        while not current_rollout_state.is_terminal():
            possible_moves = current_rollout_state.get_legal_moves()
            if not possible_moves:
                break
            move = random.choice(possible_moves)
            current_rollout_state = current_rollout_state.move(move)
        return current_rollout_state.game_result()

    def backpropagate(self, result):
        node = self
        while node is not None:
            node.update(result)
            node = node.parent

class UCT:
    def __init__(self, time_limit=None, iteration_limit=None):
        if time_limit:
            self.time_limit = time_limit
            self.limit_type = 'time'
        elif iteration_limit:
            self.iteration_limit = iteration_limit
            self.limit_type = 'iterations'
        else:
            raise ValueError("Must supply either time_limit or iteration_limit")
        self.states = []

    def uct_search(self, state):
        self.states = []
        root_node = Node(state)
        self.states.append(root_node.state)
        if self.limit_type == 'time':
            time_limit = time.time() + self.time_limit
            while time.time() < time_limit:
                self.uct_iteration(root_node)
        else:
            for i in range(self.iteration_limit):
                self.uct_iteration(root_node)
        best_child = root_node.best_child(c_param=0)
        return best_child.state.last_move

    def uct_iteration(self, root_node):
        node = root_node
        state = root_node.state.clone()

        # Select
        while node.fully_expanded() and not state.is_terminal():
            node = node.best_child()
            state = state.move(node.state.last_move)
            self.states.append(state)

        # Expand
        if not state.is_terminal():
            unexplored_move = random.choice(state.get_legal_moves())
            state = state.move(unexplored_move)
            self.states.append(state)
            node = node.add_child(state)

        # Simulate
        result = node.rollout()

        # Backpropagate
        node.backpropagate(result)

这是一个基于 UCT 算法的井字棋 AI，可以在 Python 中使用。