More Web Proxy on the site http://driver.im/

research-article

Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game

Authors:

Alexandr Grichshenko,

Luiz Jonatã Pires de Araújo,

Susanna Gimaeva,

Joseph Alexander BrownAuthors Info & Claims

ISMSI '20: Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence

Pages 119 - 122

https://doi.org/10.1145/3396474.3396492

Published: 30 May 2020 Publication History

Abstract

Tabu 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. This paper investigates the performance of TS and considers the effects of the size of the Tabu list and the size of the neighbourhood for a procedural content generation, specifically the generation of maps for a popular tabletop game called Terra Mystica. The results validate the feasibility of the proposed method and how it can be used to generate maps that improve existing maps for the game.

References

[1]

F. Glover, "Future paths for integer programming and links to artificial intelligence," Computers & operations research, vol. 13, no. 5, pp. 533--549, 1986

[2]

F. Glover and E. Taillard, "A user's guide to tabu search," Annals of operations research, vol. 41, no. 1, pp. 1--28, 1993.

[3]

J. Togelius, G. N. Yannakakis, K. O. Stanley, and C. Browne, "Search-based procedural content generation: A taxonomy and survey," IEEE Transactions on Computational Intelligence and AI in Games, vol. 3, no. 3, pp. 172--186, 2011.

[4]

A. Khalifa and M. Fayek, "Literature review of procedural content generation in puzzle games," 2015.

[5]

S. Edelkamp and S. Schroedl, Heuristic search: theory and applications. Elsevier, 2011.

[6]

E. Taillard, "Robust taboo search for the quadratic assignment problem," Parallel computing, vol. 17, no. 4-5, pp. 443--155, 1991.

Digital Library

[7]

G. Pereira, P. A. Santos, and R. Prada, "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, 2009, pp. 353--356.

[8]

T. Mahlmann, J. Togelius, and G. N. Yannakakis, "Spicing up map generation," in European Conference on the Applications of Evolutionary Computation. Springer, 2012, pp. 224--233.

[9]

J. J. Nielsen and M. Scirea, "Balanced map generation using genetic algorithms in the siphon board-game," in International Conference in Software Engineering for Defence Applications. Springer, 2018, pp. 221--231.

[10]

R. Lara-Cabrera, C. Cotta, and A. J. Ferńandez-Leiva, "A procedural balanced map generator with self-adaptive complexity for the real-time strategy game planet wars," in European Conference on the Applications of Evolutionary Computation. Springer, 2013, pp. 274--283.

[11]

D. Ashlock and C. McGuinness, "Automatic generation of fantasy role-playing modules," in 2014 IEEE Conference on Computational Intelligence and Games. IEEE, 2014, pp. 1--8.

[12]

F. Glover, "Tabu search---part i," ORSA Journal on computing, vol. 1, no. 3, pp. 190--206, 1989.

[13]

L. St, S. Wold et al., "Analysis of variance (anova)," Chemometrics and intelligent laboratory systems, vol. 6, no. 4, pp. 259--272, 1989.

[14]

S. Salhi, "Defining tabu list size and aspiration criterion within tabu search methods," Computers & Operations Research, vol. 29, no. 1, pp. 67--86, 2002.

[15]

S. Tsubakitani and J. R. Evans, "Optimizing tabu list size for the traveling salesman problem," Computers & Operations Research, vol. 25, no. 2, pp. 91--97, 1998.

Digital Library

[16]

Y. Zhong, C. Wu, L. Li, and Z. Ning, "The study of neighborhood structure of tabu search algorithm for traveling salesman problem," in 2008 Fourth International Conference on Natural Computation, vol. 1. IEEE, 2008, pp. 491--495

Cited By

Önal EBulbul A(2025)A constructive approach to strategy game map generationEntertainment Computing10.1016/j.entcom.2024.10088652(100886)Online publication date: Jan-2025
https://doi.org/10.1016/j.entcom.2024.100886
Alyaseri SConner A(2024)Comparative Analysis of Metaheuristic Algorithms for Procedural Race Track Generation in GamesInternational Journal of Applied Metaheuristic Computing10.4018/IJAMC.35033015:1(1-30)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.4018/IJAMC.350330
Saraiva RGrichshenko AAraújo LAmaro Junior Bde Carvalho G(2020)Using Ant Colony Optimisation for map generation and improving game balance in the Terra Mystica and Settlers of Catan board gamesInternational Conference on the Foundations of Digital Games10.1145/3402942.3409778(1-7)Online publication date: 17-Sep-2020
https://doi.org/10.1145/3402942.3409778
Show More Cited By

Index Terms

Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game
1. Computing methodologies
  1. Artificial intelligence
    1. Search methodologies

Recommendations

A tabu search algorithm for the quadratic assignment problem

Tabu search approach based algorithms are among the widest applied to various combinatorial optimization problems. In this paper, we propose a new version of the tabu search algorithm for the well-known problem, the quadratic assignment problem (QAP). ...
An efficient tabu search for solving the uncapacitated single allocation hub location problem

Given an efficient tabu search the uncapacitated single allocation hub location problem.Given some new tabu rules.Given some new theoretical results for computing the changes in the objective function's value for three types of moves.Improved the best ...
Probabilistic GRASP-Tabu Search algorithms for the UBQP problem

This paper presents two algorithms combining GRASP and Tabu Search for solving the Unconstrained Binary Quadratic Programming (UBQP) problem. We first propose a simple GRASP-Tabu Search algorithm working with a single solution and then reinforce it by ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Other conferences

ISMSI '20: Proceedings of the 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence

March 2020

142 pages

ISBN:9781450377614

DOI:10.1145/3396474

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]

In-Cooperation

University of Delhi

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 30 May 2020

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed limited

Conference

ISMSI '20

ISMSI '20: 2020 4th International Conference on Intelligent Systems, Metaheuristics & Swarm Intelligence

March 21 - 22, 2020

Thimphu, Bhutan

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

4
Total Citations
View Citations
87
Total Downloads

Downloads (Last 12 months)8
Downloads (Last 6 weeks)0

Reflects downloads up to 21 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

Önal EBulbul A(2025)A constructive approach to strategy game map generationEntertainment Computing10.1016/j.entcom.2024.10088652(100886)Online publication date: Jan-2025
https://doi.org/10.1016/j.entcom.2024.100886
Alyaseri SConner A(2024)Comparative Analysis of Metaheuristic Algorithms for Procedural Race Track Generation in GamesInternational Journal of Applied Metaheuristic Computing10.4018/IJAMC.35033015:1(1-30)Online publication date: 17-Sep-2024
https://dl.acm.org/doi/10.4018/IJAMC.350330
Saraiva RGrichshenko AAraújo LAmaro Junior Bde Carvalho G(2020)Using Ant Colony Optimisation for map generation and improving game balance in the Terra Mystica and Settlers of Catan board gamesInternational Conference on the Foundations of Digital Games10.1145/3402942.3409778(1-7)Online publication date: 17-Sep-2020
https://doi.org/10.1145/3402942.3409778
de Araújo LGrichshenko APinheiro RSaraiva RGimaeva S(2020)Map Generation and Balance in the Terra Mystica Board Game Using Particle Swarm and Local SearchAdvances in Swarm Intelligence10.1007/978-3-030-53956-6_15(163-175)Online publication date: 13-Jul-2020
https://doi.org/10.1007/978-3-030-53956-6_15

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents