|
The Structure of Games (short list)
The original goal of my Master's Thesis was
to create a program to play any game. Both Barney Pell and John W. Romein
have written their Ph.D. thesis and a few papers about programs that deal with many different games.
Victor Allis' Ph.D. thesis is about different search methods used in different
games.
|
Barney Pell. A Strategic Metagame Player for General Chess-like Games.
Computational Intelligence, 11(4), 1995. |
|
[URL] |
|
John W. Romein and Henri E. Bal
and Dick Grune. An Application Domain Specific Language for Describing Board
Games. In International Conference on Parallel and Distributed Processing
Techniques and Applications, pages 305-314, 1997. |
|
[PS] |
|
Louis Victor Allis. Searching
for Solutions in Games and Artificial Intelligence., Ph.D. Thesis,
University of Limburg, The Netherlands, 1994. |
[PDF] |
[URL] |
A program that can play several games will
probably need to learn how to play different games.
|
Johannes Fürnkranz.
Machine Learning in Games: A Survey. Technical
report, Austrian Research Institute for Artificial Intelligence, Schottengasse
3, A-1010Wien, Austria, 2001. |
[PDF] |
Combinatorial Game Theory is a mathematical theory of games that deals
abstractly with a large number of two player (only) games.
|
Erik D. Demaine. Playing Games
with Algorithms: Algorithmic Combinatorial
Game Theory. In Jivri Sgall and Alevs Pultr and Petr Kolman, editors,
Proceedings of the 26th Symposium on Mathematical Foundations in Computer
Science (MFCS 2001), pages 18–32, 2001. |
|
[PS] |
Games are really hard. Several authors have written about the
complexity of different games. Micheal Sipser has a short section on games in our
textbook "Introduction to the Theory of Computation" (p287-294).
|
David Eppstein. Computational
Complexity of Games and Puzzles.
Unpublished, 2000. |
|
[URL] |
|
David Wolfe. Go Endgames are
PSPACE-hard. In Richard Nowakowksi, editor,
More Games of No Chance, Mathematical Sciences Research Institution
Publication, pages 125–136, Cambridge University Press, 2002. |
|
[PS] |
My Master's Thesis program was able to play any number of games in one
specific class of games. But I should be able to describe any board game,
just as Turing Machines are able to describe any algorithm. Now when I do come
up with this method (call it Game Machines), then I will need to prove that it
does indeed describe all games. How do I do that? Well if Game
Machines are equivalent computational models to Turing Machines, and games are
really just a few TMs hooked together with some player interactivity, then Game
Machines could represent any board game. So my theory goes.
This aspect of interaction got me to reading stuff about Game Logic (a.k.a.
Computability Logic) and what has recently become known as Interactive
Computation.
|
Johan van Benthem. Extensive
games as process models. Journal of Logic,
Language,and Information, 11(3):289-313, 2002. |
[PDF]
|
|
Peter Wegner and Dina Goldin.
Computation beyond Turing machines. Commun.
ACM, 46(4):100–102, 2003. |
[PDF] |
|
Dina Q. Goldin and Scott A.
Smolka and Peter Wegner. Turing Machines, Transition Systems, and
Interaction. In Luca Aceto and Prakash Panangaden, editors, Electronic
Notes in Theoretical Computer Science, Elsevier, 2002. |
[PDF] |
There are a few markup languages for representing games. But they are
mostly concerned with representing popular games and game histories.
|
Steven J. Edwards. Portable Game
Notation Specification and Implementation Guide. ,. |
|
[URL] |
|
