Monte carlo tree search on perfect rectangle packing problem instances
Igor Pejic, Daan van den Berg · 2020
We explore the possibilities of Monte Carlo tree search (MCTS), immensely successful in games such as Go and Chess, to solve the perfect rectangle packing problem. Experiments are done on two differently generated problem sets of 1,000 instances each, and we explore six different rollout numbers and two different action-selection strategies for MCTS. We compare the algorithm's performance to an exact depth-first algorithm equipped with efficient pruning techniques. By rating the number of solutions found against the total number of tiles placed, we define a 'computationally economic tradeoff'. Different rollout numbers and strategies lead to different results, both within and between the two problem sets. We discuss these results in context of other heuristic algorithms on this problem and closely related areas.