28 Search Results for "M�ller, Mike"

Volume

Dagstuhl Follow-Ups, Volume 6

Artificial and Computational Intelligence in Games

Editors: Simon M. Lucas, Michael Mateas, Mike Preuss, Pieter Spronck, and Julian Togelius

Document
DOI: 10.4230/LIPIcs.STACS.2022.55
Superlinear Lower Bounds Based on ETH

Authors: András Z. Salamon and Michael Wehar

Published in: LIPIcs, Volume 219, 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)

Abstract
We introduce techniques for proving superlinear conditional lower bounds for polynomial time problems. In particular, we show that CircuitSAT for circuits with m gates and log(m) inputs (denoted by log-CircuitSAT) is not decidable in essentially-linear time unless the exponential time hypothesis (ETH) is false and k-Clique is decidable in essentially-linear time in terms of the graph’s size for all fixed k. Such conditional lower bounds have previously only been demonstrated relative to the strong exponential time hypothesis (SETH). Our results therefore offer significant progress towards proving unconditional superlinear time complexity lower bounds for natural problems in polynomial time.
Cite as

András Z. Salamon and Michael Wehar. Superlinear Lower Bounds Based on ETH. In 39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 219, pp. 55:1-55:16, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)

Copy BibTex To Clipboard

@InProceedings{salamon_et_al:LIPIcs.STACS.2022.55,
  author =	{Salamon, Andr\'{a}s Z. and Wehar, Michael},
  title =	{{Superlinear Lower Bounds Based on ETH}},
  booktitle =	{39th International Symposium on Theoretical Aspects of Computer Science (STACS 2022)},
  pages =	{55:1--55:16},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-222-8},
  ISSN =	{1868-8969},
  year =	{2022},
  volume =	{219},
  editor =	{Berenbrink, Petra and Monmege, Benjamin},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2022.55},
  URN =		{urn:nbn:de:0030-drops-158652},
  doi =		{10.4230/LIPIcs.STACS.2022.55},
  annote =	{Keywords: Circuit Satisfiability, Conditional Lower Bounds, Exponential Time Hypothesis, Limited Nondeterminism}
}
Document
DOI: 10.4230/LIPIcs.ESA.2021.39
Data Structures Lower Bounds and Popular Conjectures

Authors: Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová

Published in: LIPIcs, Volume 204, 29th Annual European Symposium on Algorithms (ESA 2021)

Abstract
In this paper, we investigate the relative power of several conjectures that attracted recently lot of interest. We establish a connection between the Network Coding Conjecture (NCC) of Li and Li [Li and Li, 2004] and several data structure problems such as non-adaptive function inversion of Hellman [M. Hellman, 1980] and the well-studied problem of polynomial evaluation and interpolation. In turn these data structure problems imply super-linear circuit lower bounds for explicit functions such as integer sorting and multi-point polynomial evaluation.
Cite as

Pavel Dvořák, Michal Koucký, Karel Král, and Veronika Slívová. Data Structures Lower Bounds and Popular Conjectures. In 29th Annual European Symposium on Algorithms (ESA 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 204, pp. 39:1-39:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{dvorak_et_al:LIPIcs.ESA.2021.39,
  author =	{Dvo\v{r}\'{a}k, Pavel and Kouck\'{y}, Michal and Kr\'{a}l, Karel and Sl{\'\i}vov\'{a}, Veronika},
  title =	{{Data Structures Lower Bounds and Popular Conjectures}},
  booktitle =	{29th Annual European Symposium on Algorithms (ESA 2021)},
  pages =	{39:1--39:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-204-4},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{204},
  editor =	{Mutzel, Petra and Pagh, Rasmus and Herman, Grzegorz},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ESA.2021.39},
  URN =		{urn:nbn:de:0030-drops-146207},
  doi =		{10.4230/LIPIcs.ESA.2021.39},
  annote =	{Keywords: Data structures, Circuits, Lower bounds, Network Coding Conjecture}
}
Document
Track A: Algorithms, Complexity and Games
DOI: 10.4230/LIPIcs.ICALP.2021.88
Sorting Short Integers

Authors: Michal Koucký and Karel Král

Published in: LIPIcs, Volume 198, 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)

Abstract
We build boolean circuits of size 𝒪(nm²) and depth 𝒪(log(n) + m log(m)) for sorting n integers each of m-bits. We build also circuits that sort n integers each of m-bits according to their first k bits that are of size 𝒪(nmk (1 + log^*(n) - log^*(m))) and depth 𝒪(log³(n)). This improves on the results of Asharov et al. [Asharov et al., 2021] and resolves some of their open questions.
Cite as

Michal Koucký and Karel Král. Sorting Short Integers. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 198, pp. 88:1-88:17, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{koucky_et_al:LIPIcs.ICALP.2021.88,
  author =	{Kouck\'{y}, Michal and Kr\'{a}l, Karel},
  title =	{{Sorting Short Integers}},
  booktitle =	{48th International Colloquium on Automata, Languages, and Programming (ICALP 2021)},
  pages =	{88:1--88:17},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-195-5},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{198},
  editor =	{Bansal, Nikhil and Merelli, Emanuela and Worrell, James},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ICALP.2021.88},
  URN =		{urn:nbn:de:0030-drops-141577},
  doi =		{10.4230/LIPIcs.ICALP.2021.88},
  annote =	{Keywords: sorting, small integers, boolean circuits}
}
Document
DOI: 10.4230/LIPIcs.ITCS.2021.64
A New Connection Between Node and Edge Depth Robust Graphs

Authors: Jeremiah Blocki and Mike Cinkoske

Published in: LIPIcs, Volume 185, 12th Innovations in Theoretical Computer Science Conference (ITCS 2021)

Abstract
Given a directed acyclic graph (DAG) G = (V,E), we say that G is (e,d)-depth-robust (resp. (e,d)-edge-depth-robust) if for any set S ⊂ V (resp. S ⊆ E) of at most |S| ≤ e nodes (resp. edges) the graph G-S contains a directed path of length d. While edge-depth-robust graphs are potentially easier to construct many applications in cryptography require node depth-robust graphs with small indegree. We create a graph reduction that transforms an (e, d)-edge-depth-robust graph with m edges into a (e/2,d)-depth-robust graph with O(m) nodes and constant indegree. One immediate consequence of this result is the first construction of a provably ((n log log n)/log n, n/{(log n)^{1 + log log n}})-depth-robust graph with constant indegree, where previous constructions for e = (n log log n)/log n had d = O(n^{1-ε}). Our reduction crucially relies on ST-Robust graphs, a new graph property we introduce which may be of independent interest. We say that a directed, acyclic graph with n inputs and n outputs is (k₁, k₂)-ST-Robust if we can remove any k₁ nodes and there exists a subgraph containing at least k₂ inputs and k₂ outputs such that each of the k₂ inputs is connected to all of the k₂ outputs. If the graph if (k₁,n-k₁)-ST-Robust for all k₁ ≤ n we say that the graph is maximally ST-robust. We show how to construct maximally ST-robust graphs with constant indegree and O(n) nodes. Given a family 𝕄 of ST-robust graphs and an arbitrary (e, d)-edge-depth-robust graph G we construct a new constant-indegree graph Reduce(G, 𝕄) by replacing each node in G with an ST-robust graph from 𝕄. We also show that ST-robust graphs can be used to construct (tight) proofs-of-space and (asymptotically) improved wide-block labeling functions.
Cite as

Jeremiah Blocki and Mike Cinkoske. A New Connection Between Node and Edge Depth Robust Graphs. In 12th Innovations in Theoretical Computer Science Conference (ITCS 2021). Leibniz International Proceedings in Informatics (LIPIcs), Volume 185, pp. 64:1-64:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2021)

Copy BibTex To Clipboard

@InProceedings{blocki_et_al:LIPIcs.ITCS.2021.64,
  author =	{Blocki, Jeremiah and Cinkoske, Mike},
  title =	{{A New Connection Between Node and Edge Depth Robust Graphs}},
  booktitle =	{12th Innovations in Theoretical Computer Science Conference (ITCS 2021)},
  pages =	{64:1--64:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-177-1},
  ISSN =	{1868-8969},
  year =	{2021},
  volume =	{185},
  editor =	{Lee, James R.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.ITCS.2021.64},
  URN =		{urn:nbn:de:0030-drops-136038},
  doi =		{10.4230/LIPIcs.ITCS.2021.64},
  annote =	{Keywords: Depth robust graphs, memory hard functions}
}
Document
DOI: 10.4230/DagRep.5.1.207
Artificial and Computational Intelligence in Games: Integration (Dagstuhl Seminar 15051)

Authors: Simon M. Lucas, Michael Mateas, Mike Preuss, Pieter Spronck, and Julian Togelius

Published in: Dagstuhl Reports, Volume 5, Issue 1 (2015)

Abstract
This report documents Dagstuhl Seminar 15051 "Artificial and Computational Intelligence in Games: Integration". The focus of the seminar was on the computational techniques used to create, enhance, and improve the experiences of humans interacting with and within virtual environments. Different researchers in this field have different goals, including developing and testing new AI methods, creating interesting and believable non-player characters, improving the game production pipeline, studying game design through computational means, and understanding players and patterns of interaction. In recent years it has become increasingly clear that many of the research goals in the field require a multidisciplinary approach, or at least a combination of techniques that, in the past, were considered separate research topics. The goal of the seminar was to explicitly take the first steps along this path of integration, and investigate which topics and techniques would benefit most from collaboration, how collaboration could be shaped, and which new research questions may potentially be answered.
Cite as

Simon M. Lucas, Michael Mateas, Mike Preuss, Pieter Spronck, and Julian Togelius. Artificial and Computational Intelligence in Games: Integration (Dagstuhl Seminar 15051). In Dagstuhl Reports, Volume 5, Issue 1, pp. 207-242, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)

Copy BibTex To Clipboard

@Article{lucas_et_al:DagRep.5.1.207,
  author =	{Lucas, Simon M. and Mateas, Michael and Preuss, Mike and Spronck, Pieter and Togelius, Julian},
  title =	{{Artificial and Computational Intelligence in Games: Integration (Dagstuhl Seminar 15051)}},
  pages =	{207--242},
  journal =	{Dagstuhl Reports},
  ISSN =	{2192-5283},
  year =	{2015},
  volume =	{5},
  number =	{1},
  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/DagRep.5.1.207},
  URN =		{urn:nbn:de:0030-drops-50404},
  doi =		{10.4230/DagRep.5.1.207},
  annote =	{Keywords: Multi-agent systems, Dynamical systems, Entertainment modeling, Player satisfaction, Game design, Serious games, Game theory}
}
Document
DOI: 10.4230/LIPIcs.FSTTCS.2013.475
On the Pseudoperiodic Extension of u^l = v^m w^n

Authors: Florin Manea, Mike Müller, and Dirk Nowotka

Published in: LIPIcs, Volume 24, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)

Abstract
We investigate the solution set of the pseudoperiodic extension of the classical Lyndon and Sch\"utzenberger word equations. Consider u_1 ... u_l = v_1 ... v_m w_1 ... w_n, where u_i is in {u, theta(u)} for all 1 <= i <= l, v_j is in {v, theta(v)} for all 1 <= j <= m, w_k is in {w, theta(w)} for all 1 <= k <= n and u, v and w are variables, and theta is an antimorphic involution. A solution is called pseudoperiodic, if u,v,w are in {t, theta(t)}^+ for a word t. [Czeizler et al./I&C/2011] established that for small values of l, m, and n non-periodic solutions exist, and that for large enough values all solutions are pseudoperiodic. However, they leave a gap between those bounds which we close for a number of cases. Namely, we show that for l = 3 and either m,n >= 12 or m,n >= 5 and either m and n are not both even or not all u_i's are equal, all solutions are pseudoperiodic.
Cite as

Florin Manea, Mike Müller, and Dirk Nowotka. On the Pseudoperiodic Extension of u^l = v^m w^n. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013). Leibniz International Proceedings in Informatics (LIPIcs), Volume 24, pp. 475-486, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InProceedings{manea_et_al:LIPIcs.FSTTCS.2013.475,
  author =	{Manea, Florin and M\"{u}ller, Mike and Nowotka, Dirk},
  title =	{{On the Pseudoperiodic Extension of u^l = v^m w^n}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2013)},
  pages =	{475--486},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-64-4},
  ISSN =	{1868-8969},
  year =	{2013},
  volume =	{24},
  editor =	{Seth, Anil and Vishnoi, Nisheeth K.},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2013.475},
  URN =		{urn:nbn:de:0030-drops-43948},
  doi =		{10.4230/LIPIcs.FSTTCS.2013.475},
  annote =	{Keywords: Word equations, Pseudoperiodicity, Lyndon-Sch\"{u}tzenberger equation}
}
Document
Complete Volume
DOI: 10.4230/DFU.Vol6.12191
DFU, Volume 6, Artificial and Computational Intelligence in Games, Complete Volume

Authors: Simon M. Lucas, Michael Mateas, Mike Preuss, Pieter Spronck, and Julian Togelius

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

Abstract
DFU, Volume 6, Artificial and Computational Intelligence in Games, Complete Volume
Cite as

Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@Collection{DFU.Vol6.12191,
  title =	{{DFU, Volume 6, Artificial and Computational Intelligence in Games, Complete Volume}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  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},
  URN =		{urn:nbn:de:0030-drops-43518},
  doi =		{10.4230/DFU.Vol6.12191},
  annote =	{Keywords: Applications and Expert Systems: Games}
}
Document
DOI: 10.4230/DFU.Vol6.12191.i
Frontmatter

Authors: Simon M. Lucas, Michael Mateas, Mike Preuss, Pieter Spronck, and Julian Togelius

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

Abstract
Frontmatter, table of contents, preface, author list
Cite as

Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 0:i-0:xiv, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{lucas_et_al:DFU.Vol6.12191.i,
  author =	{Lucas, Simon M. and Mateas, Michael and Preuss, Mike and Spronck, Pieter and Togelius, Julian},
  title =	{{Frontmatter}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{0:i--0:xiv},
  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.i},
  URN =		{urn:nbn:de:0030-drops-43315},
  doi =		{10.4230/DFU.Vol6.12191.i},
  annote =	{Keywords: Frontmatter, table of contents, preface, author list}
}
Document
DOI: 10.4230/DFU.Vol6.12191.1
Search in Real-Time Video Games

Authors: Peter I. Cowling, Michael Buro, Michal Bida, Adi Botea, Bruno Bouzy, Martin V. Butz, Philip Hingston, Hector Muñoz-Avila, Dana Nau, and Moshe Sipper

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

Abstract
This chapter arises from the discussions of an experienced international group of researchers interested in the potential for creative application of algorithms for searching finite discrete graphs, which have been highly successful in a wide range of application areas, to address a broad range of problems arising in video games. The chapter first summarises the state of the art in search algorithms for games. It then considers the challenges in implementing these algorithms in video games (particularly real time strategy and first-person games) and ways of creating searchable discrete representations of video game decisions (for example as state-action graphs). Finally the chapter looks forward to promising techniques which might bring some of the success achieved in games such as Go and Chess, to real-time video games. For simplicity, we will consider primarily the objective of maximising playing strength, and consider games where this is a challenging task, which results in interesting gameplay.
Cite as

Peter I. Cowling, Michael Buro, Michal Bida, Adi Botea, Bruno Bouzy, Martin V. Butz, Philip Hingston, Hector Muñoz-Avila, Dana Nau, and Moshe Sipper. Search in Real-Time Video Games. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 1-19, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{cowling_et_al:DFU.Vol6.12191.1,
  author =	{Cowling, Peter I. and Buro, Michael and Bida, Michal and Botea, Adi and Bouzy, Bruno and Butz, Martin V. and Hingston, Philip and Mu\~{n}oz-Avila, Hector and Nau, Dana and Sipper, Moshe},
  title =	{{Search in Real-Time Video Games}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{1--19},
  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.1},
  URN =		{urn:nbn:de:0030-drops-43328},
  doi =		{10.4230/DFU.Vol6.12191.1},
  annote =	{Keywords: search algorithms, real-time video games, Monte Carlo tree search, minimax search, game theory}
}
Document
DOI: 10.4230/DFU.Vol6.12191.21
Pathfinding in Games

Authors: Adi Botea, Bruno Bouzy, Michael Buro, Christian Bauckhage, and Dana Nau

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

Abstract
Commercial games can be an excellent testbed to artificial intelligence (AI) research, being a middle ground between synthetic, highly abstracted academic benchmarks, and more intricate problems from real life. Among the many AI techniques and problems relevant to games, such as learning, planning, and natural language processing, pathfinding stands out as one of the most common applications of AI research to games. In this document we survey recent work in pathfinding in games. Then we identify some challenges and potential directions for future work. This chapter summarizes the discussions held in the pathfinding workgroup.
Cite as

Adi Botea, Bruno Bouzy, Michael Buro, Christian Bauckhage, and Dana Nau. Pathfinding in Games. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 21-31, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{botea_et_al:DFU.Vol6.12191.21,
  author =	{Botea, Adi and Bouzy, Bruno and Buro, Michael and Bauckhage, Christian and Nau, Dana},
  title =	{{Pathfinding in Games}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{21--31},
  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.21},
  URN =		{urn:nbn:de:0030-drops-43334},
  doi =		{10.4230/DFU.Vol6.12191.21},
  annote =	{Keywords: path finding, search, games}
}
Document
DOI: 10.4230/DFU.Vol6.12191.33
Learning and Game AI

Authors: Hector Muñoz-Avila, Christian Bauckhage, Michal Bida, Clare Bates Congdon, and Graham Kendall

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

Abstract
The incorporation of learning into commercial games can enrich the player experience, but may concern developers in terms of issues such as losing control of their game world. We explore a number of applied research and some fielded applications that point to the tremendous possibilities of machine learning research including game genres such as real-time strategy games, flight simulation games, car and motorcycle racing games, board games such as Go, an even traditional game-theoretic problems such as the prisoners dilemma. A common trait of these works is the potential of machine learning to reduce the burden of game developers. However a number of challenges exists that hinder the use of machine learning more broadly. We discuss some of these challenges while at the same time exploring opportunities for a wide use of machine learning in games.
Cite as

Hector Muñoz-Avila, Christian Bauckhage, Michal Bida, Clare Bates Congdon, and Graham Kendall. Learning and Game AI. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 33-43, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{munozavila_et_al:DFU.Vol6.12191.33,
  author =	{Mu\~{n}oz-Avila, Hector and Bauckhage, Christian and Bida, Michal and Congdon, Clare Bates and Kendall, Graham},
  title =	{{Learning and Game AI}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{33--43},
  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.33},
  URN =		{urn:nbn:de:0030-drops-43348},
  doi =		{10.4230/DFU.Vol6.12191.33},
  annote =	{Keywords: Games, machine learning, artificial intelligence, computational intelligence}
}
Document
DOI: 10.4230/DFU.Vol6.12191.45
Player Modeling

Authors: Georgios N. Yannakakis, Pieter Spronck, Daniele Loiacono, and Elisabeth André

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

Abstract
Player modeling is the study of computational models of players in games. This includes the detection, modeling, prediction and expression of human player characteristics which are manifested through cognitive, affective and behavioral patterns. This chapter introduces a holistic view of player modeling and provides a high level taxonomy and discussion of the key components of a player's model. The discussion focuses on a taxonomy of approaches for constructing a player model, the available types of data for the model's input and a proposed classification for the model's output. The chapter provides also a brief overview of some promising applications and a discussion of the key challenges player modeling is currently facing which are linked to the input, the output and the computational model.
Cite as

Georgios N. Yannakakis, Pieter Spronck, Daniele Loiacono, and Elisabeth André. Player Modeling. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 45-59, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{yannakakis_et_al:DFU.Vol6.12191.45,
  author =	{Yannakakis, Georgios N. and Spronck, Pieter and Loiacono, Daniele and Andr\'{e}, Elisabeth},
  title =	{{Player Modeling}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{45--59},
  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.45},
  URN =		{urn:nbn:de:0030-drops-43351},
  doi =		{10.4230/DFU.Vol6.12191.45},
  annote =	{Keywords: User modeling, Computer Games, Computational and Artificial Intelligence, Affective Computing}
}
Document
DOI: 10.4230/DFU.Vol6.12191.61
Procedural Content Generation: Goals, Challenges and Actionable Steps

Authors: Julian Togelius, Alex J. Champandard, Pier Luca Lanzi, Michael Mateas, Ana Paiva, Mike Preuss, and Kenneth O. Stanley

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

Abstract
This chapter discusses the challenges and opportunities of procedural content generation (PCG) in games. It starts with defining three grand goals of PCG, namely multi-level multicontent PCG, PCG-based game design and generating complete games. The way these goals are defined, they are not feasible with current technology. Therefore we identify nine challenges for PCG research. Work towards meeting these challenges is likely to take us closer to realising the three grand goals. In order to help researchers get started, we also identify five actionable steps, which PCG researchers could get started working on immediately.
Cite as

Julian Togelius, Alex J. Champandard, Pier Luca Lanzi, Michael Mateas, Ana Paiva, Mike Preuss, and Kenneth O. Stanley. Procedural Content Generation: Goals, Challenges and Actionable Steps. In Artificial and Computational Intelligence in Games. Dagstuhl Follow-Ups, Volume 6, pp. 61-75, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2013)

Copy BibTex To Clipboard

@InCollection{togelius_et_al:DFU.Vol6.12191.61,
  author =	{Togelius, Julian and Champandard, Alex J. and Lanzi, Pier Luca and Mateas, Michael and Paiva, Ana and Preuss, Mike and Stanley, Kenneth O.},
  title =	{{Procedural Content Generation: Goals, Challenges and Actionable Steps}},
  booktitle =	{Artificial and Computational Intelligence in Games},
  pages =	{61--75},
  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.61},
  URN =		{urn:nbn:de:0030-drops-43367},
  doi =		{10.4230/DFU.Vol6.12191.61},
  annote =	{Keywords: procedural content generation, video games}
}
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}
}
  • Refine by Author
  • 6 Lucas, Simon M.
  • 6 Togelius, Julian
  • 5 Mateas, Michael
  • 5 Preuss, Mike
  • 5 Spronck, Pieter
  • Show More...

  • Refine by Classification
  • 1 Security and privacy → Mathematical foundations of cryptography
  • 1 Theory of computation → Complexity classes
  • 1 Theory of computation → Computational complexity and cryptography
  • 1 Theory of computation → Cryptographic primitives
  • 1 Theory of computation → Models of computation
  • Show More...

  • Refine by Keyword
  • 3 artificial intelligence
  • 2 Computer Games
  • 2 Games
  • 2 Symbolic computation
  • 2 Video games
  • Show More...

  • Refine by Type
  • 27 document
  • 1 volume

  • Refine by Publication Year
  • 12 2013
  • 7 2006
  • 3 2021
  • 2 2008
  • 1 2009
  • Show More...

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