✦ LIBER ✦

The Variance of Two Game Tree Algorithms

✍ Scribed by Yanjun Zhang

Publisher: Elsevier Science
Year: 1998
Tongue: English
Weight: 210 KB
Volume: 28
Category: Article
ISSN: 0196-6774
DOI: 10.1006/jagm.1998.0928

No coin nor oath required. For personal study only.

✦ Synopsis

This article studies the variance of two game tree algorithms, ␣-␤ search and SCOUT, in the stochastic i.i.d. model. The problem of determining the variance of the classic ␣-␤ search algorithm in the i.i.d. model was long open. This article resolves this problem partially. It is shown, by the martingale method, that the standard deviation of the weaker ␣-␤ search without deep cutoffs is of the same order as the expected number of leaves evaluated. A nearly optimal upper bound on the variance of the general ␣-␤ search is obtained. A thorough treatment of the two-pass SCOUT algorithm is presented. The variance of the SCOUT algorithm is determined.

📜 SIMILAR VOLUMES

Two exact algorithms for the vehicle rou

Two exact algorithms for the vehicle routing problem on trees

✍ Pontien Mbaraga; André Langevin; Gilbert Laporte 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 80 KB 👁 2 views

This article describes a heuristic and two exact algorithms for several classes of vehicle routing problems defined on tree networks. These include capacitated and time-constrained vehicle routing problems. One of the exact algorithms is based on the computation of bin packing lower bounds. The othe

An Algorithm for Two-Dimensional Rigidit

An Algorithm for Two-Dimensional Rigidity Percolation: The Pebble Game

✍ Donald J. Jacobs; Bruce Hendrickson 📂 Article 📅 1997 🏛 Elsevier Science 🌐 English ⚖ 604 KB

Many important macroscopic properties of materials depend upon the number of microscopic degrees of freedom. The task of counting the number of such degrees of freedom can be computationally very expensive. We describe a new approach for this calculation which is appropriate for twodimensional, glas

The game of “N questions” on a tree

✍ Ronald L. Rivest 📂 Article 📅 1977 🏛 Elsevier Science 🌐 English ⚖ 330 KB

A game tree with distinct leaf values wh

A game tree with distinct leaf values which is easy for the alpha-beta algorithm

✍ Ingo Althöfer; Bernhard Balkenhol 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 318 KB

The Island of Two Trees

✍ Kennelly, Brian 📂 Fiction 📅 2019 🏛 TAN Books 🌐 en-US ⚖ 530 KB 👁 2 views

**What would happen if you found yourself inside your father’s imagination?** This is the question Connor, Maggie, and Lucy are forced to answer in this adventure story within a story. After creating a model island in their garage filled with castles, caves, mountains, forests, and village

A combinatorial description of the close

A combinatorial description of the closest tree algorithm for finding evolutionary trees

✍ Michael D. Hendy 📂 Article 📅 1991 🏛 Elsevier Science 🌐 English ⚖ 382 KB

The closest tree algorith¢a for estimating the evolutionary history of n species, from a set of homologous DNA or RNA sequences is designed to avoid the problem of inconsistency inherent in current methods. The algorithm, as previously described, required O(n~2 n) steps, making it impractical for va