Extending computational game theory : simultaneity, multiple agents, chance and metareasoning /
Abstract: "This thesis extends the class of games that can be solved efficiently by computer play. Previous research has focused on two- player zero-sum games of perfect information without chance occurrences. However, computer analysis and control of strategic interactions (e.g., in planning,...
| Main Author: | |
|---|---|
| Format: | Thesis Book |
| Language: | English |
| Published: |
Cambridge, Mass. :
Massachusetts Institute of Technology. Laboratory for Computer Science,
[1994]
|
| Series: | Technical report (Massachusetts Institute of Technology. Laboratory for Computer Science) ;
MIT/LCS/TR-634 |
| Subjects: |
| Summary: | Abstract: "This thesis extends the class of games that can be solved efficiently by computer play. Previous research has focused on two- player zero-sum games of perfect information without chance occurrences. However, computer analysis and control of strategic interactions (e.g., in planning, communication and social science problems) requires more general and more useful forms of games. We present efficient solutions to two- player zero-sum games where players act simultaneously, including games that have chance occurrences. We also provide efficient solutions to games of perfect information for arbitrary numbers of players, using bounds on payoff sums. We analyze best-case performance, and describe experimental investigations of the efficacy of our algorithms. The theoretical and experimental results indicate that our algorithms obtain significant improvements over the performance of the most obvious algorithms to solve these games. We also detail corresponding extensions to the methods of heuristic play and improved search invented for two-player zero-sum games of perfect information." |
|---|---|
| Item Description: | Cover title "September 1994." |
| Physical Description: | 140 p. : ill. ; 28 cm Also available on the internet |
| Bibliography: | Includes bibliographical references |