Optimization of Player-Combinations in Multiplayer Games

There are many games in which a large number of players form groups, and each group plays against the other on the Internet. When separating players from a set of players into groups of the same number with players, a combinatorial explosion may occur. When trying to find the best grouping, the search consumes a considerable amount of time. Especially, in an environment where players are gathered randomly and groups are formed and disbanded one after another, as is often the case in online games over the Internet, it is necessary to find the optimal combination of players in a short period. Such grouping optimization is performed as an application on the network and focuses on the interaction of players. To cope with this combinatorial optimization problem, this study uses quantum annealing, a computational technique that has attracted much attention in recent years. In this paper, we describe the setting of the multiplayer game, define the optimal grouping requirements, and show the conversion of those requirements into Hamiltonians. The novelty is to use quantum annealing for optimization in an environment where the elements to be grouped are randomly collected, e.g., elements on a large network, where fast and accurate grouping is required. This study also presents the implementation results using Fixstars Amplify and discusses future directions.