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.

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

Gerard Philippe Michon

1983

The dissertation of Gerard Philippe Michon is approved

University of California, Los Angeles

iii

Appendix
Page
Table of contents		iii
Index to definitions, theorems and figures		iv
Abstract		vii
0.	Preface and Summary	1
1.	Introduction	11
2.	Impartlal recursive random games	15
3.	Matched statistics and inert structures	29
4.	Analyzing the complexity of game solving	41
5.	Partisan games	57
6.	Error propagation and pathology analysis	67
7.	Quiescence analysis	77
8.	Estimating the winning probability after a truncated search	94

A.	Strange non-inert internal structures	101
B.	Necessary and sufficient conditions for inertness	105
C.	Standard pruning transforms N and M	107
References		113

(c) Copyright by
Gerard Philippe Michon
1983

iii

Index to Definitions, Theorems and Figures

Branching Factor r			Def.	2.4
- of SOLVE			Th.	4.1
- of SOLVE_i			Th.	4.3
Bushy Inert Structures	Th	4.2	Fig.	3.2
External Structure			Def.	3.2
Games of Finite Height			Def.	2.3
Game Structure (G)			Def.	2.6
HSOLVE			Fig.	7.2
Inert Games			Def.	3.4
Internal Structure			Def.	3.1
Length of a Game			Def.	2.5
Matched statistics	Th	3.1	Def.	3.3
Minimal Search Tree			Def.	7.1
Misère Play Rule			Fig.	1.1
Normal Play Rule			Fig.	1.1
Partisan Games			Def.	5.1
Partisan Statistics			Def.	5.2
Performance of SOLVE			Fig.	4.1
Performance of SOLVE_i			Fig.	4.2
Probability of finiteness	Th	2.1	Fig.	2.2
Probability of a game			Fig.	2.1
Probability of losses			Def.	2.3
Probability of ties			Fig.	2.3
Probability of wins			Def.	2.3

QSOLVE	Fig.	7.2
Quiescence	Def.	7.2
Quiescence Consistency	Th.	7.1
Quiescence Threshold	Fig.	7.1
Recursive Random Games G	Def.	2.1
Stability	Fig.	5.2
Static Evaluation	Fig.	6.1
Statistical Structure F	Def.	2.2
Status of Games	Fig.	1.1
Status Diagram	Fig.	3.1
Survival Rate (b)	Def.	2.2
Transition Statistics	Fig.	2.4
Visible Nodes	Fig.	7.2
Winning probability p	Def.	2.2

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

vii

ABSTRACT OF THE DISSERTATION

Recursive Random Games:
A Probabilistic Model for Perfect Information Games

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 exhibits features likely to be found in realistic games. The model allows any node to have n offsprings (including n=0) with probability f_n 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.

vii

home | title | contents | overview | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | appendix | references | help

UNIVERSITY OF CALIFORNIA Los Angeles

Recursive Random Games: A Probabilistic Model for Perfect Information Games

Doctor of Philosophy in Computer Science

Gerard Philippe Michon

Table of contents

Page

Abstract

Appendix

References

Index to Definitions, Theorems and Figures

Recursive Random Games: A Probabilistic Model for Perfect Information Games

UNIVERSITY OF CALIFORNIA
Los Angeles

Recursive Random Games:
A Probabilistic Model for Perfect Information Games

Recursive Random Games:
A Probabilistic Model for Perfect Information Games