Exploring Explainable Multi-agent MCTS-minimax Hybrids in Board Game Using Process Mining
Abstract
Monte-Carlo Tree Search (MCTS) is a family of sampling-based search algorithms widely used for online planning in sequential decision-making domains and at the heart of many recent advances in artificial intelligence. Understanding the behavior of MCTS agents is difficult for developers and users due to the frequently large and complex search trees that result from the simulation of many possible futures, their evaluations, and their relationships. This paper presents our ongoing investigation into potential explanations for the decision-making and behavior of MCTS. A weakness of MCTS is that it constructs a highly selective tree and, as a result, can miss crucial moves and fall into tactical traps. Full-width minimax search constitutes the solution. We integrate shallow minimax search into the rollout phase of multi-agent MCTS and use process mining technique to explain agents' strategies in 3v3 checkers.
Figures & tables
| last_turn_id | last_turn_movement | piece_id | move | captured | reward |
|---|---|---|---|---|---|
| -1 | () | 2 | (‘left’, ‘down’) | [] | 0 |
| 1 | (‘right’, ‘down’) | 3 | (‘left’, ‘up’) | [] | 0 |
| 2 | (‘right’, ‘down’) | 3 | (‘left’, ‘down’) | [] | 0 |
| 1 | (‘right’, ‘up’) | 3 | (‘left’, ‘down’) | [] | 0 |
| 3 | (‘right’, ‘up’) | 3 | (‘left’, ‘down’) | [2] | 14 |
| 1 | (‘right’, ‘down’) | 3 | (‘right’, ‘up’) | [] | 0 |
| task_id | transition |
|---|---|
| 1 | ((-1, ‘()’), (2, “(‘left’, ‘up’)”), 0) |
| 1 | ((3, “(‘right’, ‘up’)”), (3, “(‘left’, ‘up’)”), 0) |
| 1 | ((3, “(‘right’, ‘down’)”), (2, “(‘left’, ‘down’)”), 0) |
| 1 | ((3, “(‘right’, ‘down’)”), (2, “(‘left’, ‘down’)”), 0) |
| 1 | ((3, “(‘right’, ‘up’)”), (2, “(‘left’, ‘up’)”), 0) |
| 1 | ((1, “(‘right’, ‘up’)”), (3, “(‘left’, ‘up’)”), 7) |
| Metric | R.A-A.D 1000 | R.A-I.M 1000 | W.A-A.D 1000 | W.A-I.M 1000 |
|---|---|---|---|---|
| Calc. Time (ms) | 15.74 | 3243.23 | 4.33 | 3738.53 |
| Num. States | 981.20 | 200008.10 | 1.00 | 200019.90 |
| Trace Fitness | 0.10 | 1.00 | 1.00 | 1.00 |
| Raw Fitness Cost | 60.00 | 0.00 | 0.00 | 0.00 |
| Move-Model Fitness | 0.77 | 1.00 | 1.00 | 1.00 |
| Pre-process time (ms) | 0.40 | 0.34 | 0.33 | 0.59 |
| Reward | Actions |
|---|---|
| 10 | A, B, C |
| 6 | D, E |
| 4 | F, G, H |
| 0 | I, J, K, L |
Appendix figures & tables54 assets
Supplementary material from the paper’s appendix.
Appendix
| last_turn_id | last_turn_movement | piece_id | move | captured | reward |
|---|---|---|---|---|---|
| 2 | (‘left’, ‘down’) | 1 | (‘right’, ‘down’) | [] | 0 |
| 3 | (‘left’, ‘up’) | 2 | (‘right’, ‘down’) | [] | 0 |
| 3 | (‘left’, ‘down’) | 1 | (‘right’, ‘up’) | [] | 0 |
| 3 | (‘left’, ‘down’) | 3 | (‘right’, ‘up’) | [] | 0 |
| 3 | (‘left’, ‘down’) | 1 | (‘right’, ‘down’) | [] | 0 |
| 3 | (‘right’, ‘up’) | 1 | (‘right’, ‘up’) | [2] | 7 |
| task_id | transition |
|---|---|
| 1 | ((2, “(‘left’, ‘up’)”), (3, “(‘right’, ‘up’)”), 0) |
| 1 | ((3, “(‘left’, ‘up’)”), (3, “(‘right’, ‘down’)”), 0) |
| 1 | ((2, “(‘left’, ‘down’)”), (3, “(‘right’, ‘up’)”), 0) |
| 1 | ((2, “(‘left’, ‘up’)”), (1, “(‘right’, ‘up’)”), 0) |
| 1 | ((3, “(‘left’, ‘up’)”), (1, “(‘right’, ‘down’)”), 0) |
| 1 | ((1, “(‘left’, ‘up’)”), (2, “(‘right’, ‘up’)”), 0) |
| Model | Calculation Time (ms) | Trace Fitness | Move-Model Fitness | Move-Log Fitness | Num. States | Approx. memory used (kb) | Trace Length |
| Model 5 | 15.74 | 0.10 | 0.77 | 0.10 | 981.20 | 105.30 | 65.90 |
| Model 6 | 3243.23 | 1.00 | 1.00 | 1.00 | 200008.10 | 12007.10 | 65.90 |
| Model 7 | 4.33 | 1.00 | 1.00 | 1.00 | 1.00 | 62.60 | 65.20 |
| Model 8 | 3738.53 | 1.00 | 1.00 | 1.00 | 200010.90 | 11603.90 | 65.20 |
| Model 9 | 4.34 | 1.00 | 1.00 | 1.00 | 1.00 | 68.50 | 108.33 |
| Model 10 | 2365.69 | 1.00 | 1.00 | 1.00 | 200004.50 | 11026.00 | 108.33 |
| Model | Calculation Time (ms) | Trace Fitness | Move-Model Fitness | Move-Log Fitness | Num. States | Approx. memory used (kb) | Trace Length |
| Model 17 | 4.07 | 1.00 | 1.00 | 1.00 | 1.00 | 77.40 | 88.90 |
| Model 18 | 3315.54 | 1.00 | 1.00 | 1.00 | 200006.10 | 12607.70 | 88.90 |
| Model 19 | 15.38 | 0.14 | 1.00 | 0.12 | 742.70 | 105.30 | 88.60 |
| Model 20 | 4072.42 | 1.00 | 1.00 | 1.00 | 200010.60 | 11789.60 | 88.60 |
| Model 21 | 4.07 | 1.00 | 1.00 | 1.00 | 1.00 | 77.40 | 88.90 |
| Model 22 | 3315.54 | 1.00 | 1.00 | 1.00 | 200006.10 | 12607.70 | 88.90 |
| Metric | R.A-A.D 10 | R.A-I.M 10 | W.A-A.D 10 | W.A-I.M 10 |
|---|---|---|---|---|
| Calc. Time (ms) | 4.07 | 3315.54 | 15.38 | 4072.42 |
| Num. States | 1.00 | 200006.10 | 742.70 | 200010.60 |
| Trace Fitness | 1.00 | 1.00 | 0.14 | 1.00 |
| Raw Fitness Cost | 0.00 | 0.00 | 77.10 | 0.00 |
| Move-Model Fitness | 1.00 | 1.00 | 1.00 | 1.00 |
| Pre-process time (ms) | 0.69 | 0.38 | 0.30 | 0.52 |
| Model | Calculation Time (ms) | Trace Fitness | Move-Model Fitness | Move-Log Fitness | Num. States | Approx. memory used (kb) | Trace Length |
| Model 29 | 3.44 | 1.00 | 1.00 | 1.00 | 1.00 | 54.80 | 64.80 |
| Model 30 | 3330.23 | 1.00 | 1.00 | 1.00 | 200011.00 | 11414.50 | 64.80 |
| Model 31 | 7.48 | 0.09 | 0.91 | 0.09 | 432.30 | 71.80 | 64.20 |
| Model 32 | 3974.60 | 1.00 | 1.00 | 1.00 | 200007.40 | 11856.50 | 64.20 |
| Model 33 | 2.82 | 1.00 | 1.00 | 1.00 | 1.00 | 51.90 | 72.10 |
| Model 34 | 3566.72 | 1.00 | 1.00 | 1.00 | 200008.40 | 12427.20 | 72.10 |
| Metric | R.A-A.D 1 | R.A-I.M 1 | W.A-A.D 1 | W.A-I.M 1 |
|---|---|---|---|---|
| Calc. Time (ms) | 3.44 | 3330.23 | 7.48 | 3974.60 |
| Num. States | 1.00 | 200011.00 | 432.30 | 200007.40 |
| Trace Fitness | 1.00 | 1.00 | 0.09 | 1.00 |
| Raw Fitness Cost | 0.00 | 0.00 | 59.40 | 0.00 |
| Move-Model Fitness | 1.00 | 1.00 | 0.91 | 1.00 |
| Pre-process time (ms) | 0.67 | 0.53 | 0.25 | 0.31 |
Game-Playing Agents
Game-playing agents use search, learning, and reasoning to choose actions in games with strategic, uncertain, or changing environments.
See all 218 papers