Oberseminar "Mathematische Logik" - Prof. Dr. Tobias Nipkow

Alpha-beta pruning is an efficient search strategy for two-player game trees. It was invented in the late 1950s and is at the heart of most implementations of combinatorial game playing programs. In this talk I will survey my recent formalizations and verifications of a number of standard variations of alpha-beta pruning. Findings include:

- Basic variants already having a property ascribed to an improved version

- Authors being confused about which algebraic structure they actually work in
- Generalizations to new algebraic structures

- The implementation in a well-known paper is flawed