Monte Carlo Tree Search on Perfect Rectangle Packing Problem Instances

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 di erently generated problem sets of 1,000 instances each, and we explore six di erent rollout numbers and two di erent action-selection strategies for MCTS. We compare the algorithm’s performance to an exact depth- rst algorithm equipped with e - cient pruning techniques. By rating the number of solutions found against the total number of tiles placed, we de ne a ’computation- ally economic tradeo ’. Di erent rollout numbers and strategies lead to di erent results, both within and between the two problem sets. We discuss these results in context of other heuristic algo- rithms on this problem and closely related areas.