Deutsch Intern
  • none
Institute of Mathematics

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

Alpha-Beta Pruning Explored, Extended and Verified
Date: 05/27/2024, 4:15 PM - 5:15 PM
Category: Veranstaltung
Location: Hubland Nord, Geb. 40, 01.003
Speaker: Prof. Dr. Tobias Nipkow - TU München

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