Alpha Beta Pruning with the Selection Monad

Johannes Hartmann

doi:10.1007/978-3-031-99751-8_16

2026-01-01

PRE

Johannes Hartmann *

DOI：10.1007/978-3-031-99751-8_16

原文链接

原文求助

摘要

En 中文

本文探讨了如何在顺序博弈的背景下，将广泛研究的selection monad扩展以支持alpha-beta剪枝算法。selection monad为完美信息双人博弈中常用的minimax算法提供了优雅的实现。然而，由于计算复杂度，minimax算法在大博弈树中效率低下。Alpha-beta剪枝是一种广为人知的优化方法，可减少minimax算法中评估的节点数量。我们提出了一种基于selection monad的alpha-beta剪枝算法的通用实现，并在简单示例树上展示了其应用。此外，我们还展示了如何利用generalized selection monad实现alpha-beta剪枝算法，以提高博弈树评估的效率。

Keyword:

Selection monad

Functional programming

Algorithm design

Performance Optimisation

Monads

Alpha Beta Pruning