Algorithms and Insights for RaceTrack

Bekos, Michael A.; Bruckdorfer, Till; Förster, Henry; Kaufmann, Michael; Poschenrieder, Simon; Stüber, Thomas

doi:10.4230/LIPIcs.FUN.2016.6

File

LIPIcs.FUN.2016.6.pdf

Filesize: 0.84 MB
14 pages

Document Identifiers

DOI: 10.4230/LIPIcs.FUN.2016.6
URN: urn:nbn:de:0030-drops-58818

Author Details

Michael A. Bekos

Till Bruckdorfer

Henry Förster

Michael Kaufmann

Simon Poschenrieder

Thomas Stüber

Cite AsGet 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.

Keywords

Racetrack
State-graph
complexity

Metrics

Access Statistics
Total Accesses (updated on a weekly basis)

0

PDF Downloads

0

Metadata Views

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.