Map Generation and Balance in the Terra Mystica Board Game Using Particle Swarm and Local Search
Authors: 
Luiz Jonatã Pires de Araújo, Alexandr Grichshenko, Rodrigo Lankaites Pinheiro, Rommel D. Saraiva, Susanna GimaevaAuthors Info & Claims
Pages 163 - 175
Abstract
Modern board games offer an interesting opportunity for automatically generating content and models for ensuring balance among players. This paper tackles the problem of generating balanced maps for a popular and sophisticated board game called Terra Mystica. The complexity of the involved requirements coupled with a large search space makes of this a complex combinatorial optimisation problem which has not been investigated in the literature, to the best of the authors’ knowledge. This paper investigates the use of particle swarm optimisation and steepest ascent hill climbing with a random restart for generating maps in accordance with a designed subset of requirements. The results of applying these methods are very encouraging, fully showcasing the potential of search-based metaheuristics in procedural content generation.
References
[1]
Alam, M.N.: Particle swarm optimization: algorithm and its codes in MATLAB, pp. 1–10. ResearchGate (2016)
[2]
Grichshenko, A., Jonatã, L., de Araújo, P., Gimaeva, S., Brown, J.A.: Using Tabu search algorithm for map generation in the Terra Mystica tabletop game (2020)
[3]
Araújo, L.J., Özcan, E., Atkin, J.A., Baumers, M.: A part complexity measurement method supporting 3D printing. In: NIP and Digital Fabrication Conference, vol. 2016, pp. 329–334. Society for Imaging Science and Technology (2016)
[4]
Ashlock D, Lee C, and McGuinness C Search-based procedural generation of maze-like levels IEEE Trans. Comput. Intell. AI Games 2011 3 3 260-273
[5]
Barros, G.A., Togelius, J.: Balanced civilization map generation based on open data. In: 2015 IEEE Congress on Evolutionary Computation (CEC), pp. 1482–1489. IEEE (2015)
[6]
Chira C, Horvath D, and Dumitrescu D Pizzuti C, Ritchie MD, and Giacobini M An evolutionary model based on hill-climbing search operators for protein structure prediction Evolutionary Computation, Machine Learning and Data Mining in Bioinformatics 2010 Heidelberg Springer 38-49
[7]
Eberhart, R., Kennedy, J.: Particle swarm optimization. In: Proceedings of the IEEE International Conference on Neural Networks, vol. 4, pp. 1942–1948. Citeseer (1995)
[8]
Gravina, D., Khalifa, A., Liapis, A., Togelius, J., Yannakakis, G.N.: Procedural content generation through quality diversity. In: 2019 IEEE Conference on Games (CoG), pp. 1–8. IEEE (2019)
[9]
Khalifa, A., Bontrager, P., Earle, S., Togelius, J.: PCGRL: procedural content generation via reinforcement learning. arXiv preprint arXiv:2001.09212 (2020)
[10]
Khalifa, A., Fayek, M.: Literature review of procedural content generation in puzzle games (2015)
[11]
Krause J, Ruxton GD, Ruxton GD, Ruxton IG, et al. Living in Groups 2002 Oxford Oxford University Press
[12]
Lara-Cabrera R, Cotta C, and Fernández-Leiva AJ Esparcia-Alcázar AI A procedural balanced map generator with self-adaptive complexity for the real-time strategy game planet wars Applications of Evolutionary Computation 2013 Heidelberg Springer 274-283
[13]
Lin SW, Ying KC, Lu CC, and Gupta JN Applying multi-start simulated annealing to schedule a flowline manufacturing cell with sequence dependent family setup times Int. J. Prod. Econ. 2011 130 2 246-254
[14]
Mahlmann T, Togelius J, Yannakakis GN, et al. Di Chio C et al. Spicing up map generation Applications of Evolutionary Computation 2012 Heidelberg Springer 224-233
[15]
de Mesentier Silva, F., Lee, S., Togelius, J., Nealen, A.: Ai-based playtesting of contemporary board games. In: Proceedings of the 12th International Conference on the Foundations of Digital Games, p. 13. ACM (2017)
[16]
Morosan M and Poli R Squillero G and Sim K Automated game balancing in MS PacMan and StarCraft using evolutionary algorithms Applications of Evolutionary Computation 2017 Cham Springer 377-392
[17]
Nielsen JJ and Scirea M Ciancarini P, Mazzara M, Messina A, Sillitti A, and Succi G Balanced map generation using genetic algorithms in the siphon board-game Proceedings of 6th International Conference in Software Engineering for Defence Applications 2020 Cham Springer 221-231
[18]
Pereira, G., Santos, P.A., Prada, R.: Self-adapting dynamically generated maps for turn-based strategic multiplayer browser games. In: Proceedings of the International Conference on Advances in Computer Entertainment Technology, pp. 353–356. ACM (2009)
[19]
Togelius, J., Preuss, M., Beume, N., Wessing, S., Hagelbäck, J., Yannakakis, G.N.: Multiobjective exploration of the StarCraft map space. In: Proceedings of the 2010 IEEE Conference on Computational Intelligence and Games, pp. 265–272. IEEE (2010)
[20]
Togelius J, Yannakakis GN, Stanley KO, Browne C, et al. Di Chio C et al. Search-based procedural content generation Applications of Evolutionary Computation 2010 Heidelberg Springer 141-150
[21]
Togelius J, Yannakakis GN, Stanley KO, and Browne C Search-based procedural content generation: a taxonomy and survey IEEE Trans. Comput. Intell. AI Games 2011 3 3 172-186
[22]
Uriarte, A., Ontanón, S.: PSMAGE: balanced map generation for StarCraft. In: 2013 IEEE Conference on Computational Intelligence in Games (CIG), pp. 1–8. IEEE (2013)
Index terms have been assigned to the content through auto-classification.
Recommendations
Using Ant Colony Optimisation for map generation and improving game balance in the Terra Mystica and Settlers of Catan board games
FDG '20: Proceedings of the 15th International Conference on the Foundations of Digital GamesGame balancing is one of the most challenging features to be implemented in a typical game design process. Approaches for evaluating and achieving game balancing include extensive playtesting - which typically requires several iterations of games with ...
Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game
ISMSI '20: Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm IntelligenceTabu Search (TS) metaheuristic improves simple local search algorithms (e.g. steepest ascend hill-climbing) by enabling the algorithm to escape local optima points. It has shown to be useful for addressing several combinatorial optimization problems. ...
A Modified Quantum-Behaved Particle Swarm Optimization
ICCS '07: Proceedings of the 7th international conference on Computational Science, Part I: ICCS 2007Based on the previously introduced Quantum-behaved Particle Swarm Optimization (QPSO), a revised QPSO with Gaussian disturbance on the mean best position of the swarm is proposed. The reason for the introduction of this novel method is that the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
Jul 2020
688 pages
© Springer Nature Switzerland AG 2020.
Publisher
Springer-Verlag
Berlin, Heidelberg
Publication History
Published: 14 July 2020
Author Tags
Qualifiers
- Article
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 0Total Downloads
- Downloads (Last 12 months)0
- Downloads (Last 6 weeks)0
Reflects downloads up to 21 Dec 2024