On Enhancing Recent Multi-player Game Playing Strategies Using a Spectrum of Adaptive Data Structures

摘要

Multi-Player Game Playing (MPGP) strategies have predominantly been built on the basis of utilizing Two-Player Game Playing (TPGP) strategies that were designed for games such as Chess and Go. However, a few strategies, such as the Best-Reply Search (BRS), that have been specifically tuned for the multi-player setting, have been introduced in the literature. Recently, these strategies have been further optimized by incorporating into them techniques from the field of Adaptive Data Structures (ADS) [1]. In this paper, we extend this area of research by demonstrating the efficacy of a broader spectrum of techniques from the field of ADS. The results presented in [1] have been enhanced in two directions, namely by considering a set of list-based ADSs capable of "ranking" the relative strengths of the perspective player's opponents, and by also considering the ply-depth to which the ADSs can be invoked. The results that we present conclusively prove that the incorporation of ADSs positively enhances the BRS, that the semantics of the ADS scheme used question can influence its performance, and that the advantage gleaned remains at deeper search depths.