Computational Models of Games
Modeling games provides a deeper understanding of computational models in general. Researchers in artificial intelligence have looked to chess as a model of thinking that can be automated while those in distributed computing and cryptography need models that reflect the competitive nature of distributed and cryptographic protocols.Computational Models of Games describes a model of two person games - called a probabilistic game automaton - that unifies other important models that have been developed to reflect the game-like properties of computational problems. It also covers interesting models of games not previously studied (introducing games against unknown nature, for example) and proves new results on time bounded game automata, space bounded game automata with complete information, and space bounded game automata with partial information.By incorporating the three important features of randomness, secrecy, and limited power for the players, the probabilistic game automaton models in a natural way many problems that computer scientists confront and provides insight into their complexity. It generalizes computational models such as the alternating Turing machines of Chandra, Kozen, and Stockmeyer, Papadimitriou's games against nature, the Arthur-Merlin games of Babai, and the interactive proof systems of Goldwasser, Micali, and Rackoff.Anne Condon received her doctorate from The University of Washington and is Assistant Professor at The University of Wisconsin Computational Models of Games is a 1988 ACM Distinguished Dissertation
What people are saying - Write a review
We haven't found any reviews in the usual places.
Time Bounded Game Automata
Space Bounded Game Automata with Complete Information
2 other sections not shown
3-invalid accept[a accepting leaf algorithm alternating Turing machines automata with complete automata with partial bounded game automata bounded random game bounded winning strategy checkcount checks a symbol class of languages coin-tossing node coin-tossing steps computation tree define denote deterministic Turing machine displays complete information follows games against nature halts with probability Hence history bound history H interactive proof systems languages accepted Lemma listed by player Markov decision process Markov strategy Merlin game moves node 77 node of G nondeterministic Turing machine partial information player 1 displays polynomial time bounded prob[VH probabilistic game automaton probability of reaching problems prove random game automaton reaching an accepting rejecting sequence simulating strategy space bounded game space constructible steps of player strategy of player string Theorem 5.1 turn indicator universal node valid strategy valuea(n valueopt(n verifier visible configuration visible history visible tape visible to player vp(i worktape