This is the exact text of a 1983 UCLA dissertation. The page layout has not been preserved, but the original page breaks and page numbers appear in the right margin (see HTML code). Some pictures were scanned from the original submission. © 1983 Gérard P. Michon, Ph.D.
back
next

UNIVERSITY OF CALIFORNIA
Los Angeles

Recursive Random Games:
A Probabilistic Model for Perfect Information Games

A dissertation submitted in partial satisfaction
of the requirements for the degree

Doctor of Philosophy in Computer Science

by

Gerard Philippe Michon

1983
 UCLA Logo
i
ii



The dissertation of Gerard Philippe Michon is approved
 Let There Be Light  Jack W. Carlyle,
Thomas S. Ferguson,
Sheila A. Greibach,
E. Burton Swanson,
Judea Pearl, Committee Chair.
University of California, Los Angeles
1983
ii
iii



Table of contents

Page
Table of contents iii
Index to definitions, theorems and figures iv

Abstract

vii
0.Preface and Summary1
1.Introduction11
2.Impartlal recursive random games15
3.Matched statistics and inert structures29
4.Analyzing the complexity of game solving41
5.Partisan games57
6.Error propagation and pathology analysis67
7.Quiescence analysis77
8.Estimating the winning probability after a truncated search94
 

Appendix

A.Strange non-inert internal structures101
B.Necessary and sufficient conditions for inertness 105
C.Standard pruning transforms N and M107

References

113

(c) Copyright by
Gerard Philippe Michon
1983
iii
iv

Index to Definitions, Theorems and Figures

Branching Factor rDef.2.4
      - of SOLVETh.4.1
      - of SOLVEiTh. 4.3
Bushy Inert Structures Th  4.2    Fig.  3.2
External StructureDef.3.2
Games of Finite HeightDef.2.3
Game Structure (G)Def.2.6
HSOLVEFig.7.2
Inert GamesDef.3.4
Internal StructureDef.3.1
Length of a GameDef.2.5
Matched statisticsTh3.1Def. 3.3
Minimal Search TreeDef.7.1
Misère Play RuleFig. 1.1
Normal Play RuleFig.1.1
Partisan GamesDef.5.1
Partisan StatisticsDef.5.2
Performance of SOLVEFig.4.1
Performance of SOLVEiFig.4.2
Probability of finitenessTh2.1Fig. 2.2
Probability of a gameFig. 2.1
Probability of lossesDef.2.3
Probability of tiesFig.2.3
Probability of winsDef.2.3
iv
QSOLVEFig.7.2
QuiescenceDef.7.2
Quiescence ConsistencyTh.7.1
Quiescence ThresholdFig.7.1
Recursive Random Games GDef. 2.1
StabilityFig.5.2
Static EvaluationFig.6.1
Statistical Structure FDef.2.2
Status of GamesFig.1.1
Status DiagramFig.3.1
Survival Rate (b)Def.2.2
Transition StatisticsFig.2.4
Visible NodesFig.7.2
Winning probability pDef.2.2
v

v
vi

VITA
March 29, 1956--Born, Talence (Gironde), France
1976-1979-- Ecole Polytechnique, Paris, France
1979-1980-- Ecole Nationale Supérieure des Télécommunications
1980-1981-- M.S., University of California, Los Angeles
1981-1983-- Research Assistant, Department of Computer Science
            University of California, Los Angeles
vi
vii

ABSTRACT OF THE DISSERTATION

Recursive Random Games:
A Probabilistic Model for Perfect Information Games

by

Gerard Philippe Michon
Doctor of Philosophy in Computer Science
University of California, Los Angeles, 1983
Professor Judea Pearl, Chair

A simple probabilistic model for game trees is described which ex­hibits features likely to be found in realistic games. The model allows any node to have n offsprings (including n=0) with probability fn and assigns each terminal node a WIN status with probability p and a LOSS status with probability q = 1-p. Our model may include infinite game trees and/or games that never end when played perfectly. The statistical properties of games and the computational complexities of various game solving approaches are quantified and compared. A simple analysis of game pathology and quiescence is also given. The model provides a theoretical justification for the observed good behavior of game-playing programs whose search horizon is not rigid. Pathological features that were recently found to be inherent in some former game models are put in a new perspective.



Valid HTML
vii
visits since 2001-03-29 Doctoral dissertation © Copyright 1983 by Gérard P. Michon, Ph.D.
back
next
home | title | contents | overview | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | appendix | references | help