Skip to Main Content
 

Global Search Box

 
 
 
 

Files

File List


cwru-cse-thesis.pdf (641.41 KB)

ETD Abstract Container

Abstract Header

A THEORETIC APPROACH FOR BINARY GAME TREE EVALUATION

Zhao, Boning
http://rave.ohiolink.edu/etdc/view?acc_num=case1586520140611046

Abstract Details

2020, Master of Sciences, Case Western Reserve University, EECS - Computer and Information Sciences.
The Binary game tree model is perhaps the simplest model that computes Boolean functions: it charges only for reading an input variable. We proposed a theoretical binary game tree evaluation analysis process with Yao's principle and randomized complexity. Based on the concept of reluctant input, we studied the power of randomness in this model with both directional and non-directional algorithm. We made a comparison of their lower bounds. These results are obtained via general and efficient methods for computing lower bounds on the probabilistic complexity and based on a particular type of uniform binary decision tree, which we call it nor-tree, and it is an equivalent transformation of AND/OR tree. As a result of the study, we finally build up a methodology for evaluating binary game trees and proving its lower bound. To test its versatility, we also apply this analysis process to two different types of binary game tree: Fibonacci tree and skew-F tree. Both two have a more complicated structure for game tree evaluation. The results show that this process could also be used for getting other types of game trees lower bound.
Vincenzo Liberatore (Advisor)
Computer Science
Game Theory, Binary Game Tree, Minimax Principle, Game Tree Evaluation

Recommended Citations

Citations

  • Zhao, B. (2020). A THEORETIC APPROACH FOR BINARY GAME TREE EVALUATION [Master's thesis, Case Western Reserve University]. OhioLINK Electronic Theses and Dissertations Center. http://rave.ohiolink.edu/etdc/view?acc_num=case1586520140611046

    APA Style (7th edition)

  • Zhao, Boning. A THEORETIC APPROACH FOR BINARY GAME TREE EVALUATION. 2020. Case Western Reserve University, Master's thesis. OhioLINK Electronic Theses and Dissertations Center, http://rave.ohiolink.edu/etdc/view?acc_num=case1586520140611046.

    MLA Style (8th edition)

  • Zhao, Boning. "A THEORETIC APPROACH FOR BINARY GAME TREE EVALUATION." Master's thesis, Case Western Reserve University, 2020. http://rave.ohiolink.edu/etdc/view?acc_num=case1586520140611046

    Chicago Manual of Style (17th edition)

case1586520140611046
629
© 2020, all rights reserved.
This open access ETD is published by Case Western Reserve University School of Graduate Studies and OhioLINK.