Analysing And Improving The Knowledge-based Fast Evolutionary MCTS Algorithm

Abstract

In the ongoing strive to reach human-level intelligence with intelligent agents, it has become clear that the agents should be able to deal with a host of different problem domains. Being very good on one particular domain, like chess for instance, does not suffice. That is why the area of General Video Game Playing (GVGP) was introduced. Here, agents will play a wide range of different video games, while they do not know which game they will be playing beforehand. The agents are forced to learn the game by playing. This master thesis will research one particular version of the Monte Carlo Tree Search algorithm that was created for GVGP, called the Knowledge-based Fast Evolutionary (KB Fast-Evo) MCTS algorithm. This algorithm uses a knowledge base to store information about the game and also an evolutionary approach to bias game simulations. First a general study of the MCTS algorithm is given, together with a detailed explanation of General Video Game Playing. Then the KB Fast-Evo algorithm is analyzed, where a lot of room for improvement becomes apparent. In the final chapters an attempt is made to improve the KB Fast-Evo algorithm, by changing the evolutionary approach, by adding path finding and some other fine-tuning. The final algorithm does perform a lot better, but there is still room for improvement. However, it is not likely the algorithm will ever be optimal on its own