In this paper, we explore how the selection monad, widely studied in the context of sequential games, can be extended to support the alpha-beta pruning algorithm. The selection monad provides an elegant implementation of the minimax algorithm, commonly used to determine the best move in two-player games with perfect information. However, the minimax algorithm becomes inefficient for large game trees due to computational complexity. Alpha-beta pruning is a well-known optimization that reduces the number of nodes evaluated in the minimax algorithm. We present a general implementation of the alpha-beta pruning algorithm utilizing the selection monad and demonstrate its application on a simple example tree. Additionally, we show how the alpha-beta pruning algorithm can be implemented using the generalized selection monad, enhancing the efficiency of game tree evaluations.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Alpha Beta Pruning with the Selection Monad

  • Johannes Hartmann

摘要

In this paper, we explore how the selection monad, widely studied in the context of sequential games, can be extended to support the alpha-beta pruning algorithm. The selection monad provides an elegant implementation of the minimax algorithm, commonly used to determine the best move in two-player games with perfect information. However, the minimax algorithm becomes inefficient for large game trees due to computational complexity. Alpha-beta pruning is a well-known optimization that reduces the number of nodes evaluated in the minimax algorithm. We present a general implementation of the alpha-beta pruning algorithm utilizing the selection monad and demonstrate its application on a simple example tree. Additionally, we show how the alpha-beta pruning algorithm can be implemented using the generalized selection monad, enhancing the efficiency of game tree evaluations.