Robert Shi

EECS Department, University of California, Berkeley

Technical Report No. UCB/EECS-2024-87

May 10, 2024

http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-87.pdf

Many abstract strategy games have a large number of positions, with a significant fraction of games loopy in nature. Previous efforts to develop solvers in GamesmanClassic for these loopy tier games have utilized single-threaded approaches, which does not take advantage of the parallelism necessary to solve large games. This report provides a comprehensive overview of the design and development of a parallelized loopy solver for generic tierable games. It elaborates on the loopy solving algorithm, explores sources of parallelism, addresses synchronization issues, and details optimizations that enhance the solving process. Furthermore, it showcases the application of this algorithm in solving Quixo and endgames of Chinese Chess, demonstrating the effectiveness of our approach.

Advisors: Dan Garcia

---

BibTeX citation:

@mastersthesis{Shi:EECS-2024-87,
    Author= {Shi, Robert},
    Editor= {Garcia, Dan and Yokota, Justin},
    Title= {Parallel Solving of Two-Player Tierable Abstract Strategy Games},
    School= {EECS Department, University of California, Berkeley},
    Year= {2024},
    Month= {May},
    Url= {http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-87.html},
    Number= {UCB/EECS-2024-87},
    Abstract= {Many abstract strategy games have a large number of positions, with a significant fraction of games loopy in nature. Previous efforts to develop solvers in GamesmanClassic for these loopy tier games have utilized single-threaded approaches, which does not take advantage of the parallelism necessary to solve large games. This report provides a comprehensive overview of the design and development of a parallelized loopy solver for generic tierable games. It elaborates on the loopy solving algorithm, explores sources of parallelism, addresses synchronization issues, and details optimizations that enhance the solving process. Furthermore, it showcases the application of this algorithm in solving Quixo and endgames of Chinese Chess, demonstrating the effectiveness of our approach.},
}

EndNote citation:

%0 Thesis
%A Shi, Robert 
%E Garcia, Dan 
%E Yokota, Justin 
%T Parallel Solving of Two-Player Tierable Abstract Strategy Games
%I EECS Department, University of California, Berkeley
%D 2024
%8 May 10
%@ UCB/EECS-2024-87
%U http://www2.eecs.berkeley.edu/Pubs/TechRpts/2024/EECS-2024-87.html
%F Shi:EECS-2024-87