4 Search Results for "Thompson, Simon"

Document
DOI: 10.4230/OASIcs.EVCS.2023.26
Refactoring = Substitution + Rewriting: Towards Generic, Language-Independent Refactorings

Authors: Simon Thompson and Dániel Horpácsi

Published in: OASIcs, Volume 109, Eelco Visser Commemorative Symposium (EVCS 2023)

Abstract
Eelco Visser’s work has always encouraged stepping back from the particular to look at the underlying, conceptual problems. In that spirit we present an approach to describing refactorings that abstracts away from particular refactorings to classes of similar transformations, and presents an implementation of these that works by substitution and subsequent rewriting. Substitution is language-independent under this approach, while the rewrites embody language-specific aspects. Intriguingly, it also goes back to work on API migration by Huiqing Li and the first author, and sets refactoring in that general context.
Cite as

Simon Thompson and Dániel Horpácsi. Refactoring = Substitution + Rewriting: Towards Generic, Language-Independent Refactorings. In Eelco Visser Commemorative Symposium (EVCS 2023). Open Access Series in Informatics (OASIcs), Volume 109, pp. 26:1-26:9, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2023)

Copy BibTex To Clipboard

@InProceedings{thompson_et_al:OASIcs.EVCS.2023.26,
  author =	{Thompson, Simon and Horp\'{a}csi, D\'{a}niel},
  title =	{{Refactoring = Substitution + Rewriting: Towards Generic, Language-Independent Refactorings}},
  booktitle =	{Eelco Visser Commemorative Symposium (EVCS 2023)},
  pages =	{26:1--26:9},
  series =	{Open Access Series in Informatics (OASIcs)},
  ISBN =	{978-3-95977-267-9},
  ISSN =	{2190-6807},
  year =	{2023},
  volume =	{109},
  editor =	{L\"{a}mmel, Ralf and Mosses, Peter D. and Steimann, Friedrich},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/OASIcs.EVCS.2023.26},
  URN =		{urn:nbn:de:0030-drops-177961},
  doi =		{10.4230/OASIcs.EVCS.2023.26},
  annote =	{Keywords: refactoring, generic, language independent, rewriting, substitution, API upgrade}
}
Document
DOI: 10.4230/LIPIcs.MFCS.2020.20
List Homomorphism Problems for Signed Graphs

Authors: Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková

Published in: LIPIcs, Volume 170, 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)

Abstract
We consider homomorphisms of signed graphs from a computational perspective. In particular, we study the list homomorphism problem seeking a homomorphism of an input signed graph (G,σ), equipped with lists L(v) ⊆ V(H), v ∈ V(G), of allowed images, to a fixed target signed graph (H,π). The complexity of the similar homomorphism problem without lists (corresponding to all lists being L(v) = V(H)) has been previously classified by Brewster and Siggers, but the list version remains open and appears difficult. Both versions (with lists or without lists) can be formulated as constraint satisfaction problems, and hence enjoy the algebraic dichotomy classification recently verified by Bulatov and Zhuk. By contrast, we seek a combinatorial classification for the list version, akin to the combinatorial classification for the version without lists completed by Brewster and Siggers. We illustrate the possible complications by classifying the complexity of the list homomorphism problem when H is a (reflexive or irreflexive) signed tree. It turns out that the problems are polynomial-time solvable for certain caterpillar-like trees, and are NP-complete otherwise. The tools we develop will be useful for classifications of other classes of signed graphs, and we mention some follow-up research of this kind; those classifications are surprisingly complex.
Cite as

Jan Bok, Richard Brewster, Tomás Feder, Pavol Hell, and Nikola Jedličková. List Homomorphism Problems for Signed Graphs. In 45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 170, pp. 20:1-20:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)

Copy BibTex To Clipboard

@InProceedings{bok_et_al:LIPIcs.MFCS.2020.20,
  author =	{Bok, Jan and Brewster, Richard and Feder, Tom\'{a}s and Hell, Pavol and Jedli\v{c}kov\'{a}, Nikola},
  title =	{{List Homomorphism Problems for Signed Graphs}},
  booktitle =	{45th International Symposium on Mathematical Foundations of Computer Science (MFCS 2020)},
  pages =	{20:1--20:14},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-159-7},
  ISSN =	{1868-8969},
  year =	{2020},
  volume =	{170},
  editor =	{Esparza, Javier and Kr\'{a}l', Daniel},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2020.20},
  URN =		{urn:nbn:de:0030-drops-126886},
  doi =		{10.4230/LIPIcs.MFCS.2020.20},
  annote =	{Keywords: complexity, dichotomy, graph homomorphism, signed graph}
}
Document
DOI: 10.4230/DFU.Vol6.12191.77
General Video Game Playing

Authors: John Levine, Clare Bates Congdon, Marc Ebner, Graham Kendall, Simon M. Lucas, Risto Miikkulainen, Tom Schaul, and Tommy Thompson

Published in: Dagstuhl Follow-Ups, Volume 6, Artificial and Computational Intelligence in Games (2013)

Abstract
One of the grand challenges of AI is to create general intelligence: an agent that can excel at many tasks, not just one. In the area of games, this has given rise to the challenge of General Game Playing (GGP). In GGP, the game (typically a turn-taking board game) is defined declaratively in terms of the logic of the game (what happens when a move is made, how the scoring system works, how the winner is declared, and so on). The AI player then has to work out how to play the game and how to win. In this work, we seek to extend the idea of General Game Playing into the realm of video games, thus forming the area of General Video Game Playing (GVGP). In GVGP, computational agents will be asked to play video games that they have not seen before. At the minimum, the agent will be given the current state of the world and told what actions are applicable. Every game tick the agent will have to decide on its action, and the state will be updated, taking into account the actions of the other agents in the game and the game physics. We envisage running a competition based on GVGP playing, using arcadestyle (e.g. similar to Atari 2600) games as our starting point. These games are rich enough to be a formidable challenge to a GVGP agent, without introducing unnecessary complexity. The competition that we envisage could have a number of tracks, based on the form of the state (frame buffer or object model) and whether or not a forward model of action execution is available. We propose that the existing Physical Travelling Salesman (PTSP) software could be extended for our purposes and that a variety of GVGP games could be created in this framework by AI and Games students and other developers. Beyond this, we envisage the development of a Video Game Description Language (VGDL) as a way of concisely specifying video games. For the competition, we see this as being an interesting challenge in terms of deliberative search, machine learning and transfer of existing knowledge into new domains.
Cite as

John Levine, Clare Bates Congdon, Marc Ebner, Graham Kendall, Simon M. Lucas, Risto Miikkulainen, Tom Schaul, and Tommy Thompson. General Video Game Playing. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 77-83, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{levine_et_al:DFU.Vol6.12191.77,
  author =	{Levine, John and Congdon, Clare Bates and Ebner, Marc and Kendall, Graham and Lucas, Simon M. and Miikkulainen, Risto and Schaul, Tom and Thompson, Tommy},
  title =	{{General Video Game Playing}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{77--83},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-62-0},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{6},
  editor =	{Lucas, Simon M. and Mateas, Michael and Preuss, Mike and Spronck, Pieter and Togelius, Julian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol6.12191.77},
  URN =		{urn:nbn:de:0030-drops-43374},
  doi =		{10.4230/DFU.Vol6.12191.77},
  annote =	{Keywords: Video games, artificial intelligence, artificial general intelligence}
}
Document
DOI: 10.4230/DFU.Vol6.12191.85
Towards a Video Game Description Language

Authors: Marc Ebner, John Levine, Simon M. Lucas, Tom Schaul, Tommy Thompson, and Julian Togelius

Published in: Dagstuhl Follow-Ups, Volume 6, Artificial and Computational Intelligence in Games (2013)

Abstract
This chapter is a direct follow-up to the chapter on General Video Game Playing (GVGP). As that group recognised the need to create a Video Game Description Language (VGDL), we formed a group to address that challenge and the results of that group is the current chapter. Unlike the VGDL envisioned in the previous chapter, the language envisioned here is not meant to be supplied to the game-playing agent for automatic reasoning; instead we argue that the agent should learn this from interaction with the system. The main purpose of the language proposed here is to be able to specify complete video games, so that they could be compiled with a special VGDL compiler. Implementing such a compiler could provide numerous opportunities; users could modify existing games very quickly, or have a library of existing implementations defined within the language (e.g. an Asteroids ship or a Mario avatar) that have pre-existing, parameterised behaviours that can be customised for the users specific purposes. Provided the language is fit for purpose, automatic game creation could be explored further through experimentation with machine learning algorithms, furthering research in game creation and design. In order for both of these perceived functions to be realised and to ensure it is suitable for a large user base we recognise that the language carries several key requirements. Not only must it be human-readable, but retain the capability to be both expressive and extensible whilst equally simple as it is general. In our preliminary discussions, we sought to define the key requirements and challenges in constructing a new VGDL that will become part of the GVGP process. From this we have proposed an initial design to the semantics of the language and the components required to define a given game. Furthermore, we applied this approach to represent classic games such as Space Invaders, Lunar Lander and Frogger in an attempt to identify potential problems that may come to light. Work is ongoing to realise the potential of the VGDL for the purposes of Procedural Content Generation, Automatic Game Design and Transfer Learning.
Cite as

Marc Ebner, John Levine, Simon M. Lucas, Tom Schaul, Tommy Thompson, and Julian Togelius. Towards a Video Game Description Language. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 85-100, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{ebner_et_al:DFU.Vol6.12191.85,
  author =	{Ebner, Marc and Levine, John and Lucas, Simon M. and Schaul, Tom and Thompson, Tommy and Togelius, Julian},
  title =	{{Towards a Video Game Description Language}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{85--100},
  series =	{Dagstuhl Follow-Ups},
  ISBN =	{978-3-939897-62-0},
  ISSN =	{1868-8977},
  year =	{2013},
  volume =	{6},
  editor =	{Lucas, Simon M. and Mateas, Michael and Preuss, Mike and Spronck, Pieter and Togelius, Julian},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/DFU.Vol6.12191.85},
  URN =		{urn:nbn:de:0030-drops-43385},
  doi =		{10.4230/DFU.Vol6.12191.85},
  annote =	{Keywords: Video games, description language, language construction}
}
  • Refine by Author
  • 2 Ebner, Marc
  • 2 Levine, John
  • 2 Lucas, Simon M.
  • 2 Schaul, Tom
  • 2 Thompson, Tommy
  • Show More...

  • Refine by Classification
  • 1 Mathematics of computing → Graph theory
  • 1 Software and its engineering → Software evolution

  • Refine by Keyword
  • 2 Video games
  • 1 API upgrade
  • 1 artificial general intelligence
  • 1 artificial intelligence
  • 1 complexity
  • Show More...

  • Refine by Type
  • 4 document

  • Refine by Publication Year
  • 2 2013
  • 1 2020
  • 1 2023

Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact