English Intern
  • none
Institut für Mathematik

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

Alpha-Beta Pruning Explored, Extended and Verified
Datum: 27.05.2024, 16:15 - 17:15 Uhr
Kategorie: Veranstaltung
Ort: Hubland Nord, Geb. 40, 01.003
Vortragende: 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