Information Set Monte Carlo Tree Search (ISMCTS)の概要とアルゴリズム及び実装例について

import random

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_factor=0.7):
        return max(self.children.values(), key=lambda child: child.get_score(exploration_factor))

    def get_score(self, exploration_factor):
        if self.visits == 0:
            return float('inf')
        exploitation = self.score / self.visits
        exploration = exploration_factor * (self.parent.visits / (1 + self.visits))
        return exploitation + exploration

    def add_child(self, action, child_state):
        child = Node(child_state, self)
        self.children[action] = child
        return child

class BlackjackState:
    def __init__(self, player_hand, dealer_hand, usable_ace):
        self.player_hand = player_hand
        self.dealer_hand = dealer_hand
        self.usable_ace = usable_ace

    def get_legal_moves(self):
        return ['hit', 'stand']

    def clone(self):
        return BlackjackState(self.player_hand[:], self.dealer_hand[:], self.usable_ace)

    def is_terminal(self):
        return self.get_score(self.player_hand) > 21 or (len(self.player_hand) == 2 and self.get_score(self.player_hand) == 21) or self.get_score(self.dealer_hand) > 21 or (len(self.dealer_hand) == 2 and self.get_score(self.dealer_hand) == 21)

    def get_score(self, hand):
        score = sum(hand)
        if score <= 11 and 1 in hand and self.usable_ace: score += 10 return score def move(self, action): new_state = self.clone() if action == 'hit': new_state.player_hand.append(random.randint(1, 13)) if new_state.get_score(new_state.player_hand) > 21:
                return new_state, -1
            else:
                return new_state, 0
        elif action == 'stand':
            while new_state.get_score(new_state.dealer_hand) < 17: new_state.dealer_hand.append(random.randint(1, 13)) if new_state.get_score(new_state.dealer_hand) > 21 or new_state.get_score(new_state.player_hand) > new_state.get_score(new_state.dealer_hand):
                return new_state, 1
            elif new_state.get_score(new_state.player_hand) == new_state.get_score(new_state.dealer_hand):
                return new_state, 0
            else:
                return new_state, -1

def ismcts_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()
            if node.state.is_terminal():
                break
            state, reward = state.move(random.choice(state.get_legal_moves()))

        # 展開
        if not state.is_terminal():
            unexplored_move = random.choice(state.get_legal_moves())
            new_state, reward = state.move(unexplored_move)
            node = node.add_child(unexplored_move, new_state)

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

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

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

def main():
    initial_player_hand = [random.randint(1, 13) for _ in range(2)]
    initial_dealer_hand = [random.randint(1, 13) for _ in range(2)]
    root_state = BlackjackState(initial_player_hand, initial_dealer_hand, True)

    print("Player's initial hand:", root_state.player_hand)
    print("Dealer's initial hand:", root_state.dealer_hand)

    while not root_state.is_terminal():
        action = ismcts_search(root_state, 10000)
        root_state, reward = root_state.move(action)
        print("Player's hand after action:", root_state.player_hand)

    player_score = root_state.get_score(root_state.player_hand)
    dealer_score = root_state.get_score(root_state.dealer_hand)
    if player_score > 21:
        print("Player busts! Dealer wins.")
    elif dealer_score > 21:
        print("Dealer busts! Player wins.")
    elif player_score > dealer_score:
        print("Player wins with a score of", player_score, "vs Dealer's score of", dealer_score)
    elif player_score < dealer_score:
        print("Dealer wins with a score of", dealer_score, "vs Player's score of", player_score)
    else:
        print("It's a tie!")

if __name__ == "__main__":
    main()