Monte Carlo Tree Search
Monte Carlo tree search (MCTS) is a sampling and simulation based technique for searching in large search spaces containing both decision nodes and probabilistic event. We have used this technique in games like poker (Van den Broeck et al, 2009). Such games have known rules and the alternation between self-moves and non-deterministic events or opponent moves can be used to prune unintersting branches. While Monte Carlo Tree Search (MCTS) represented a revolution in game related AI research, it is currently unfit for tasks that deal with continuous actions and (often as a consequence) game-states. Recent applications of MCTS to quasi continuous games such as no-limit Poker variants have circumvented this problem by discretizing the action or the state-space. We have presented Tree Learning Search (TLS) as an alternative to a priori discretization. TLS employs ideas from data stream mining to combine incremental tree induction with MCTS to construct game-state-dependent discretizations that allow MCTS to focus its sampling spread more efficiently on regions of the search space with promising returns.
Educational tools and InnovationLab
Games are an ideal container to explain and motivate techniques from artificial intelligence and machine learning. We have built, for example, a rock-scissors-paper playing machine, a pokerbot and a sensor-controlled games to motivate elementary school and high school students to study mathematics. Most of these efforts are joined in the Faculty of Engineering's InnovationLab.
- Prof. Luc De Raedt
- Prof. Danny De Schreye
- Rock-Scissors-Paper robot at Technopolis Together with Technopolis, we developed an installation to play rock-scissors-paper against a computer. The system consists out of two modules to play this game. The first module analyses a video of the hand to detect the shape presented. The second module builds a model of your previous decisions and tactiques. These two elements are combined to play a counter-move that maximizes the machine's chances of winning.
- Poker player and Pokerbot We have built a tool to intuitively compose rules for a pokerbot. All pokerbots are continuously playing against each other and the goal is to improve your bot to maximize your average profits. To gain the most profit it is not only important to build a smart set of rules to play poker but also to adapt to the strategies of your opponents.
- Travian MMPG Predictions Travian is a massively mulitplayer real-time strategy game played by around 3.000.000 players around the world. We have investigated how we can model this world and its dynamic aspects and how to predict events (e.g. forming an alliance).
- Van den Broeck, Guy, and Kurt Driessens. "Automatic discretization of actions and states in Monte-Carlo tree search." In Proceedings of the ECML/PKDD 2011 Workshop on Machine Learning and Data Mining in and around Games, pp. 1-12. 2011.
- Van den Broeck, Guy, Kurt Driessens, and Jan Ramon. "Monte-Carlo tree search in poker using expected reward distributions." In Advances in Machine Learning, pp. 367-381. Springer Berlin Heidelberg, 2009.