mctser

一个极其易于使用的蒙特卡洛树搜索库。

你只需在这个库中为你的游戏类型实现四个必要的特质。

使用方法

在Cargo.toml中添加依赖项

cargo add mctser

要使用这个库，需要为你的游戏类型实现两个特质 mctser::GameState 和 mctser::Action，以及两个标记特质 mctser::EndStatus 和 mctser::Action。这四个特质的定义如下。

/// The trait for the end status of the game, like player1 wins, player2 wins, or tie
pub trait EndStatus {}

/// The trait for the action. For example, in tictactoe, the action is the coordinate of the next move
pub trait Action: Eq + Clone {}

/// The trait for the player
pub trait Player<E: EndStatus> {
    fn reward_when_outcome_is(&self, outcome: &E) -> f32;
}

/// The trait for the game state
pub trait GameState<P, E, A>
where
    P: Player<E>,
    E: EndStatus,
    A: Action,
{
    /// To get the next player
    fn player(&self) -> P;
    /// Judge if the game is over; if not, return None; if true, return the status of the game result
    fn end_status(&self) -> Option<E>;
    /// Get all possible actions for the player at the current state
    fn possible_actions(&self) -> Vec<A>;
    /// Get the next state after the player takes the action
    fn act(&self, action: &A) -> Self;
}

以下是一个井字棋的示例。示例的一些细节被隐藏了，点击这里查看完整示例。克隆此仓库，并运行 cargo run --example tictactoe 来查看两个 mctser 机器人之间的游戏。

使用此crate需要四个类型

1. 表示游戏状态的类型。对于井字棋，它将是棋盘上的情况，下一个移动的玩家，如果游戏结束以及谁赢得了游戏。
2. 表示玩家的类型。对于井字棋，我们可以使用一个 enum 来表示两个玩家。
3. 表示可能动作的类型。对于井字棋，它将是移动的坐标。
4. 表示游戏结束状态的类型。对于井字棋，它将是玩家1赢、玩家2赢或平局。

对于这些类型，我们在crate中有四个相应的特质，即 GameState、Player、Action 和 EndStatus，你需要为你的类型实现这些特质。

作为开始，我们可以定义所需的四个类型如下

#[derive(Clone, Copy)]
pub enum EndStatus {
    Win(Player),
    Tie,
}

#[derive(PartialEq, Eq, Clone, Copy)]
pub enum Player {
    Player0,
    Player1,
}

#[derive(PartialEq, Eq, Clone, Copy)]
pub struct Action(pub usize, pub usize);

pub struct TictactoeGame {
    pub board: [[Option<Player>; 3]; 3],
    pub player: Player,
    pub end_status: Option<EndStatus>,
}

为了使游戏可玩，我们需要实现一些必要的方法。这里可以看到详细的实现。然后我们可以为这些类型实现相应的特质。

impl mctser::EndStatus for EndStatus {}
impl mctser::Action for Action {}

impl mctser::Player<EndStatus> for Player {
    fn reward_when_outcome_is(&self, outcome: &EndStatus) -> f32 {
        match outcome {
            EndStatus::Win(winner) => {
                if self == winner {
                    1.
                } else {
                    0.
                }
            }
            EndStatus::Tie => 0.5,
        }
    }
}

impl mctser::GameState<Player, EndStatus, Action> for TictactoeGame {
    fn end_status(&self) -> Option<EndStatus> {
        self.end_status
    }

    fn player(&self) -> Player {
        return self.player;
    }

    fn possible_actions(&self) -> Vec<Action> {
        let mut possible_actions = Vec::new();
        for row in 0..3 {
            for col in 0..3 {
                if !self.occupied(Action(row, col)) {
                    possible_actions.push(Action(row, col));
                }
            }
        }
        possible_actions
    }

    fn act(&self, selection: &Action) -> Self {
        self.place(&selection).unwrap()
    }
}

然后您可以构建一个 mcts::SearchTree 并开始搜索。为了使前一次搜索的搜索记录在下一次移动中使用，使用 mcts::SearchTree::renew 来前进。

fn main() {
    // We use `RC` to store the game status. Create a new game and pass it to the search tree through `RC::clone()`.
    let mut game = Rc::new(TictactoeGame::new());
    let mut search_tree = mctser::SearchTree::new(game.clone());

    while game.end_status.is_none() {
        // Make 1000 simulations to find the best move
        let selected = search_tree.search(1000).unwrap();
        // Step forward to the next state using the action provided by the search tree
        search_tree.renew(&selected).unwrap();
        // Get current game state after the move
        game = search_tree.get_game_state();
        game.draw_board();
    }
}

这个库的使用非常简单，不是吗？

待办事项

• 添加测试用例
• 支持自定义树策略
• 添加并行搜索

贡献

欢迎所有类型的贡献。请随意提出问题或发送拉取请求。