Using Ant Colony Optimisation for map generation and improving game balance in the Terra Mystica and Settlers of Catan board games
Authors: 
Rommel Dias Saraiva, Alexandr Grichshenko, Luiz Jonatã Pires de Araújo, Bonfim Amaro Junior, Guilherme Nepomuceno de CarvalhoAuthors Info & Claims
Article No.: 112, Pages 1 - 7
Abstract
Game 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 subtle adjustments in the components and adopted strategies that resemble brute force - and algorithmic solutions that use qualitative and measurable design goals when developing game components. The literature contains examples of methods that employ artificial intelligence to generate maps in computer games that offer balanced and fairness of starting conditions for the players. The use of such methods for tabletop games, however, has been scarce in the academic literature, for the best of the authors’ knowledge. This paper investigates the application of the ant colony optimisation metaheuristic to generate content and improving game balance for two well-known tabletop games, namely, Terra Mystica and Settlers of Catan. The resultant configurations satisfy complex game-dependent requirements while optimising a model for game balancing. Moreover, the results showed to be promising when compared with existing game maps and setup.
References
[1]
Christian Blum, Mateu Yábar Vallès, and Maria J Blesa. 2008. An ant colony optimization algorithm for DNA sequencing by hybridization. Computers & Operations Research 35, 11 (2008), 3620–3635.
[2]
Igor Borovikov, Yunqi Zhao, Ahmad Beirami, Jesse Harder, John Kolen, James Pestrak, Jervis Pinto, Reza Pourabolghasem, Harold Chaput, Mohsen Sardari, 2019. Winning isn’t everything: Training agents to playtest modern games. In AAAI Workshop on Reinforcement Learning in Games.
[3]
Joseph Alexander Brown and Marco Scirea. 2018. Procedural Generation for Tabletop Games: User Driven Approaches with Restrictions on Computational Resources. In International Conference in Software Engineering for Defence Applications. Springer, 44–54.
[4]
Cameron B Browne, Edward Powley, Daniel Whitehouse, Simon M Lucas, Peter I Cowling, Philipp Rohlfshagen, Stephen Tavener, Diego Perez, Spyridon Samothrakis, and Simon Colton. 2012. A survey of monte carlo tree search methods. IEEE Transactions on Computational Intelligence and AI in games 4, 1(2012), 1–43.
[5]
Bernd Bullnheimer, Richard F Hartl, and Christine Strauss. 1999. An improved ant System algorithm for thevehicle Routing Problem. Annals of operations research 89 (1999), 319–328.
[6]
Guillaume Chaslot, Sander Bakkes, Istvan Szita, and Pieter Spronck. 2008. Monte-Carlo Tree Search: A New Framework for Game AI. In AIIDE.
[7]
Alberto Colorni, Marco Dorigo, Vittorio Maniezzo, 1992. An Investigation of some Properties of an” Ant Algorithm”. In Ppsn, Vol. 92.
[8]
Luiz Jonatã Pires de Araújo, Alexandr Grichshenko, Rodrigo Lankaites Pinheiro, Rommel D Saraiva, and Susanna Gimaeva. 2020. Map Generation and Balance in the Terra Mystica Board Game Using Particle Swarm and Local Search. In International Conference on Swarm Intelligence. Springer, 163–175.
[9]
Fernando de Mesentier Silva, Scott Lee, Julian Togelius, and Andy Nealen. 2017. AI-based playtesting of contemporary board games. In Proceedings of the 12th International Conference on the Foundations of Digital Games. ACM, 13.
[10]
Marco Dorigo, Mauro Birattari, and Thomas Stutzle. 2006. Ant colony optimization. IEEE computational intelligence magazine 1, 4 (2006), 28–39.
[11]
Marco Dorigo and Luca Maria Gambardella. 1997. Ant colony system: a cooperative learning approach to the traveling salesman problem. IEEE Transactions on evolutionary computation 1, 1(1997), 53–66.
[12]
Miguel Frade, Francisco Fernandéz de Vega, and Carlos Cotta. 2009. Breeding terrains with genetic terrain programming: the evolution of terrain generators. International Journal of Computer Games Technology 2009 (2009).
[13]
Marc Gravel, Wilson L Price, and Caroline Gagné. 2002. Scheduling continuous casting of aluminum using a multiple objective ant colony optimization metaheuristic. European Journal of Operational Research 143, 1 (2002), 218–229.
[14]
Alexandr Grichshenko, Luiz Jonatã Pires de Araújo, Susanna Gimaeva, and Joseph Alexander Brown. 2020. Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game. International Journal of Machine Learning and Computing (IJMLC, ISSN: 2010-3700).
[15]
Ken Hartsook, Alexander Zook, Sauvik Das, and Mark O Riedl. 2011. Toward supporting stories with procedurally generated game worlds. In 2011 IEEE Conference on Computational Intelligence and Games (CIG’11). IEEE, 297–304.
[16]
Cathleen Heyden. 2009. Implementing a computer player for Carcassonne. Master’s thesis, Department of Knowledge Engineering, Maastricht University (2009).
[17]
Ahmed Khalifa and Magda Fayek. 2015. Literature review of procedural content generation in puzzle games.
[18]
Hwanhee Kim, Seongtaek Lee, Hyundong Lee, Teasung Hahn, and Shinjin Kang. 2019. Automatic Generation of Game Content using a Graph-based Wave Function Collapse Algorithm. In 2019 IEEE Conference on Games (CoG). IEEE, 1–4.
[19]
Aliona Kozlova, Joseph Alexander Brown, and Elizabeth Reading. 2015. Examination of representational expression in maze generation algorithms. In 2015 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 532–533.
[20]
Antonios Liapis, Georgios N Yannakakis, Mark J Nelson, Mike Preuss, and Rafael Bidarra. 2018. Orchestrating game generation. IEEE Transactions on Games 11, 1 (2018), 48–68.
[21]
Tobias Mahlmann, Julian Togelius, and Georgios N Yannakakis. 2012. Spicing up map generation. In European Conference on the Applications of Evolutionary Computation. Springer, 224–233.
[22]
Jonas Juhl Nielsen and Marco Scirea. 2018. Balanced Map Generation Using Genetic Algorithms in the Siphon Board-Game. In International Conference in Software Engineering for Defence Applications. Springer, 221–231.
[23]
Gonçalo Pereira, Pedro A Santos, and Rui Prada. 2009. Self-adapting dynamically generated maps for turn-based strategic multiplayer browser games. In Proceedings of the International Conference on Advances in Computer Enterntainment Technology. ACM, 353–356.
[24]
Michael Pfeiffer. 2004. Reinforcement learning of strategies for Settlers of Catan. In Proceedings of the International Conference on Computer Games: Artificial Intelligence, Design and Education.
[25]
William L Raffe, Fabio Zambetta, Xiaodong Li, and Kenneth O Stanley. 2014. Integrated approach to personalized procedural map generation using evolutionary algorithms. IEEE Transactions on Computational Intelligence and AI in Games 7, 2(2014), 139–155.
[26]
Noor Shaker. 2016. Intrinsically motivated reinforcement learning: A promising framework for procedural content generation. In 2016 IEEE Conference on Computational Intelligence and Games (CIG). IEEE, 1–8.
[27]
Alena Shmygelska and Holger H Hoos. 2005. An ant colony optimisation algorithm for the 2D and 3D hydrophobic polar protein folding problem. BMC bioinformatics 6, 1 (2005), 30.
[28]
Adam M Smith and Michael Mateas. 2011. Answer set programming for procedural content generation: A design space approach. IEEE Transactions on Computational Intelligence and AI in Games 3, 3(2011), 187–200.
[29]
Adam Summerville, Sam Snodgrass, Matthew Guzdial, Christoffer Holmgård, Amy K Hoover, Aaron Isaksen, Andy Nealen, and Julian Togelius. 2018. Procedural content generation via machine learning (PCGML). IEEE Transactions on Games 10, 3 (2018), 257–270.
[30]
István Szita, Guillaume Chaslot, and Pieter Spronck. 2009. Monte-carlo tree search in settlers of catan. In Advances in Computer Games. Springer, 21–32.
[31]
Julian Togelius, Mike Preuss, and Georgios N Yannakakis. 2010. Towards multiobjective procedural map generation. In Proceedings of the 2010 workshop on procedural content generation in games. 1–8.
[32]
Julian Togelius, Georgios N Yannakakis, Kenneth O Stanley, and Cameron Browne. 2010. Search-based procedural content generation. In European Conference on the Applications of Evolutionary Computation. Springer, 141–150.
[33]
Julian Togelius, Georgios N Yannakakis, Kenneth O Stanley, and Cameron Browne. 2011. Search-based procedural content generation: A taxonomy and survey. IEEE Transactions on Computational Intelligence and AI in Games 3, 3(2011), 172–186.
[34]
Josep Valls-Vargas, Santiago Ontanón, and Jichen Zhu. 2013. Towards story-based content generation: From plot-points to maps. In 2013 IEEE Conference on Computational Inteligence in Games (CIG). IEEE, 1–8.
[35]
Roland Van Der Linden, Ricardo Lopes, and Rafael Bidarra. 2013. Procedural generation of dungeons. IEEE Transactions on Computational Intelligence and AI in Games 6, 1(2013), 78–89.
[36]
Georgios N Yannakakis and Julian Togelius. 2011. Experience-driven procedural content generation. IEEE Transactions on Affective Computing 2, 3 (2011), 147–161.
- Using Ant Colony Optimisation for map generation and improving game balance in the Terra Mystica and Settlers of Catan board games
Recommendations
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. ...
Avoiding Revenge Using Optimal Opponent Ranking Strategy in the Board Game Catan
The study analyses the attitude of players in a board game called Catan. In Catan, we are basically handling the players as opponents, but this does not rule out the possibility of cooperation. In a game with three players, in order to increase the ...
Map Generation and Balance in the Terra Mystica Board Game Using Particle Swarm and Local Search
Advances in Swarm IntelligenceAbstractModern 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 ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
September 2020
804 pages
ISBN:9781450388078
DOI:10.1145/3402942
Copyright © 2020 ACM.
Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 17 September 2020
Check for updates
Author Tags
Qualifiers
- Research-article
- Research
- Refereed limited
Conference
FDG '20
FDG '20: International Conference on the Foundations of Digital Games
September 15 - 18, 2020
Bugibba, Malta
Acceptance Rates
Overall Acceptance Rate 152 of 415 submissions, 37%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 196Total Downloads
- Downloads (Last 12 months)37
- Downloads (Last 6 weeks)9
Reflects downloads up to 21 Dec 2024
Other Metrics
Citations
Cited By
View allView Options
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign inFull Access
View options
View or Download as a PDF file.
PDFeReader
View online with eReader.
eReaderHTML Format
View this article in HTML Format.
HTML Format