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

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

URL: http://arxiv.org/abs/2006.02716v1
Date: Thu, 4 Jun 2020 09:15:46 GMT
Title: Using Tabu Search Algorithm for Map Generation in the Terra Mystica Tabletop Game
Authors: Alexandr Grichshenko, Luiz Jonata Pires de Araujo, Susanna Gimaeva, Joseph Alexander Brown
Abstract summary: Tabu Search (TS) metaheuristic improves simple local search algorithms by enabling the algorithm to escape local optima points. 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.
Score: 60.71662712899962
License: http://creativecommons.org/licenses/by/4.0/
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.

Related papers

NavTopo: Leveraging Topological Maps For Autonomous Navigation Of a Mobile Robot [1.0550841723235613]
We propose a full navigation pipeline based on topological map and two-level path planning. The pipeline localizes in the graph by matching neural network descriptors and 2D projections of the input point clouds. We test our approach in a large indoor photo-relaistic simulated environment and compare it to a metric map-based approach based on popular metric mapping method RTAB-MAP.
arXiv Detail & Related papers (2024-10-15T10:54:49Z)
LiteSearch: Efficacious Tree Search for LLM [70.29796112457662]
This study introduces a novel guided tree search algorithm with dynamic node selection and node-level exploration budget. Experiments conducted on the GSM8K and TabMWP datasets demonstrate that our approach enjoys significantly lower computational costs compared to baseline methods.
arXiv Detail & Related papers (2024-06-29T05:14:04Z)
Playing Board Games with the Predict Results of Beam Search Algorithm [0.0]
This paper introduces a novel algorithm for two-player deterministic games with perfect information, which we call PROBS (Predict Results of Beam Search) We evaluate the performance of our algorithm across a selection of board games, where it consistently demonstrates an increased winning ratio against baseline opponents. A key result of this study is that the PROBS algorithm operates effectively, even when the beam search size is considerably smaller than the average number of turns in the game.
arXiv Detail & Related papers (2024-04-23T20:10:27Z)
GAN-Based Content Generation of Maps for Strategy Games [0.0]
We propose a model for the generation of maps based on Generative Adversarial Networks (GAN) In our implementation we tested out different variants of GAN-based networks on a dataset of heightmaps.
arXiv Detail & Related papers (2023-01-07T15:24:25Z)
Learning Obstacle-Avoiding Lattice Paths using Swarm Heuristics: Exploring the Bijection to Ordered Trees [0.0]
paths are functional entities that efficient navigation in discrete/grid maps. This paper presents a new scheme to generate collision-free lattice paths with paths.
arXiv Detail & Related papers (2022-09-12T12:27:12Z)
A Metaheuristic Algorithm for Large Maximum Weight Independent Set Problems [58.348679046591265]
Given a node-weighted graph, find a set of independent (mutually nonadjacent) nodes whose node-weight sum is maximum. Some of the graphs airsing in this application are large, having hundreds of thousands of nodes and hundreds of millions of edges. We develop a new local search algorithm, which is a metaheuristic in the greedy randomized adaptive search framework.
arXiv Detail & Related papers (2022-03-28T21:34:16Z)
Improved Image Matting via Real-time User Clicks and Uncertainty Estimation [87.84632514927098]
This paper proposes an improved deep image matting framework which is trimap-free and only needs several user click interactions to eliminate the ambiguity. We introduce a new uncertainty estimation module that can predict which parts need polishing and a following local refinement module. Results show that our method performs better than existing trimap-free methods and comparably to state-of-the-art trimap-based methods with minimal user effort.
arXiv Detail & Related papers (2020-12-15T14:32:36Z)
Rethinking Localization Map: Towards Accurate Object Perception with Self-Enhancement Maps [78.2581910688094]
This work introduces a novel self-enhancement method to harvest accurate object localization maps and object boundaries with only category labels as supervision. In particular, the proposed Self-Enhancement Maps achieve the state-of-the-art localization accuracy of 54.88% on ILSVRC.
arXiv Detail & Related papers (2020-06-09T12:35:55Z)
Model Selection in Contextual Stochastic Bandit Problems [51.94632035240787]
We develop a meta-algorithm that selects between base algorithms. We show through a lower bound that even when one of the base algorithms has $O(sqrtT)$ regret, in general it is impossible to get better than $Omega(sqrtT)$ regret.
arXiv Detail & Related papers (2020-03-03T18:46:34Z)
Offline Grid-Based Coverage path planning for guards in games [0.0]
We introduce a novel algorithm for covering a 2D polygonal (with holes) area. Experimental analysis over several scenarios ranging from simple layouts to more complex maps used in actual games show good performance.
arXiv Detail & Related papers (2020-01-15T18:28:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.