Description

This paper explores the inner workings of algorithms that computers may use to play Chess. First, we discuss the classical Alpha-Beta algorithm and several improvements, including Quiescence Search, Transposition Tables, and more. Next, we examine the state-of-the-art Monte Carlo Tree

This paper explores the inner workings of algorithms that computers may use to play Chess. First, we discuss the classical Alpha-Beta algorithm and several improvements, including Quiescence Search, Transposition Tables, and more. Next, we examine the state-of-the-art Monte Carlo Tree Search algorithm and relevant optimizations. After that, we consider a recent algorithm that transforms Alpha-Beta into a “Rollout” search, blending it with Monte Carlo Tree Search under the rollout paradigm. We then discuss our C++ Chess Engine, Homura, and explain its implementation of a hybrid algorithm combining Alpha-Beta with MCTS. Finally, we show that Homura can play master-level Chess at a strength currently exceeding that of our backtracking Alpha-Beta.

Reuse Permissions
  • 4.96 MB application/pdf

    Download restricted. Please sign in.
    Restrictions Statement

    Barrett Honors College theses and creative projects are restricted to ASU community members.

    Details

    Title
    • The Application of Rollout-Style Search to Decision-Making in the Game of Chess
    Contributors
    Date Created
    2023-05
    Resource Type
  • Text
  • Machine-readable links