1. Intro
Monte Carlo Tree Search (MCTS) is a decision-making algorithm that consists in searching combinatorial spaces represented by trees. In such trees, nodes denote states, also referred to as confgurations of the problem, whereas edges denote transitions (actions) from one state to another.
Structure:
- Section 2—Classic MCTS
- Section 3—Games with Perfect Information
- Action Reduction: 消除明显错误的动作
- UCT Alternatives: Upper Confidence Bounds for tree
- Early Termination: 设置cut-off depth
- Opponent Modelling: 建模对手行为
- Section 4: Games with imperfect information
- Determinizations: 为每个未知feature设置专门值，以消除randomness
- Information Sets: 从玩家角度无法区分的状态被分组在信息集中
- Heavy Playouts: domain-specific knowledge
- Policy Update
- Master combination: 各种算法的组合
- Opponent Modelling
- Section 5: Machine Learning
- NN
- Temporal Difference Learning, TDL
- Summary
- Section 6: Evolutionary methods
- Heuristic Functions
- Policies
- Rolling Horizon Evolutionary Algorithm, RHEA
- Evolutionary MCTS
- Section 7: Applications
- Planning: logistics and robotics
- Security: optimal patrolling schedules
- Chemical synthesis
- Scheduling: e.g., risk management
- Vehicle Routing
- Section 8: Parallelization
- Section 9: Conclusion