Justin Yokota

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2022-219

August 19, 2022

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-219.pdf

Strongly solving abstract strategy games is generally a computationally intensive task; for large games, computation must be parallelized to complete within a reasonable time. Prior solvers have used tools such as MapReduce to distribute work; however, this approach is hampered by high disk use. This report details the development of a new shard solver, which allows for the efficient solving of certain games on large-scale distributed computing nodes, while significantly reducing memory use. A particular target of this project was a fast and memory-efficient strong solve of the game Connect 4. Optimizations made in this project, as well as the improved solving paradigm provided by the shard solver, allowed for a solve in less than 6 hours on a 960-node system, while using less than one-eighth of the disk space required for a MapReduce Solve. In addition, a new compression scheme was developed for storing the resulting database, reducing the database size from a naive 32 TiB size to 557 GiB.

Advisors: Dan Garcia

---

BibTeX citation:

@mastersthesis{Yokota:EECS-2022-219,
    Author= {Yokota, Justin},
    Editor= {Garcia, Dan and Demmel, James},
    Title= {High Efficiency Computation of Game Tree Exploration in Connect 4},
    School= {EECS Department, University of California, Berkeley},
    Year= {2022},
    Month= {Aug},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-219.html},
    Number= {UCB/EECS-2022-219},
    Abstract= {Strongly solving abstract strategy games is generally a computationally intensive task; for large games, computation must be parallelized to complete within a reasonable time. Prior solvers have used tools such as MapReduce to distribute work; however, this approach is hampered by high disk use. This report details the development of a new shard solver, which allows for the efficient solving of certain games on large-scale distributed computing nodes, while significantly reducing memory use. A particular target of this project was a fast and memory-efficient strong solve of the game Connect 4. Optimizations made in this project, as well as the improved solving paradigm provided by the shard solver, allowed for a solve in less than 6 hours on a 960-node system, while using less than one-eighth of the disk space required for a MapReduce Solve. In addition, a new compression scheme was developed for storing the resulting database, reducing the database size from a naive 32 TiB size to 557 GiB.},
}

EndNote citation:

%0 Thesis
%A Yokota, Justin 
%E Garcia, Dan 
%E Demmel, James 
%T High Efficiency Computation of Game Tree Exploration in Connect 4
%I EECS Department, University of California, Berkeley
%D 2022
%8 August 19
%@ UCB/EECS-2022-219
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2022/EECS-2022-219.html
%F Yokota:EECS-2022-219