LIPIcs.FUN.2016.6.pdf
- Filesize: 0.84 MB
- 14 pages
Document
Algorithms and Insights for RaceTrack
Authors
-
Part of:
Volume:
8th International Conference on Fun with Algorithms (FUN 2016)
Series: Leibniz International Proceedings in Informatics (LIPIcs)
Conference: International Conference on Fun with Algorithms (FUN) - License:
Creative Commons Attribution 3.0 Unported license
- Publication Date: 2016-06-02
Cite As Get BibTex
Michael A. Bekos, Till Bruckdorfer, Henry Förster, Michael Kaufmann, Simon Poschenrieder, and Thomas Stüber. Algorithms and Insights for RaceTrack. In 8th International Conference on Fun with Algorithms (FUN 2016). Leibniz International Proceedings in Informatics (LIPIcs), Volume 49, pp. 6:1-6:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2016)
https://doi.org/10.4230/LIPIcs.FUN.2016.6
Abstract
We discuss algorithmic issues on the well-known paper-and-pencil game RaceTrack. On a very simple track called Indianapolis, we introduce the problem and simple approaches, that will be gradually refined. We present and experimentally evaluate efficient algorithms for single player scenarios. We also consider a variant where the parts of the track are known as soon as they become visible during the race.
Subject Classification
Keywords
- Racetrack
- State-graph
- complexity
Metrics
- Access Statistics
-
Total Accesses (updated on a weekly basis)
0PDF Downloads
References
-
Kristian Ahlmann-Ohlsen. Applying binary decision diagrams to solve the shortest path problem in vectorrace, 2005.
- Jeff Erickson. How hard is optimal racing?, 2009. URL: http://3dpancakes.typepad.com/ernie/2009/06/how-hard-is-optimal-racing.html.
-
Martin Gardner. Mathematical games - Sim, chomp and race track: new games for the intellect (and not for lady luck). Scientific American, 228(1):108-115, 1973.
-
Peter E. Hart, Nils J. Nilsson, and Bertram Raphael. A formal basis for the heuristic determination of minimum cost paths. IEEE Trans. Systems, Science and Cybernetics, SSC-4(2):100-107, 1968.
-
Markus Holzer and Pierre McKenzie. The computational complexity of racetrack. In Paolo Boldi and Luisa Gargano, editors, FUN 2010, volume 6099 of LNCS, pages 260-271. Springer, 2010.
-
Robert Olsson and Andreas Tarandi. A genetic algorithm in the game racetrack, 2011.
- Jakob Schmid. VectorRace - finding the fastest path through a two-dimensional track, 2005. URL: http://schmid.dk/articles/vectorRace.pdf.
- Wikipedia. Racetrack (game). URL: https://en.wikipedia.org/wiki/Racetrack_game.