Alpha-Beta Pruning Explored, Extended and Verified

Add to your list(s) Download to your calendar using vCal

• Professor Tobias Nipkow (Technische Universität München)
• Thursday 13 June 2024, 17:00-18:00
• Live-streamed at MR14 Centre for Mathematical Sciences.

If you have a question about this talk, please contact Anand Rao Tadipatri.

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 famous paper is flawed

—-

Watch online here: https://cam-ac-uk.zoom.us/j/89453157536?pwd=lUNbK9xamhh2B6O7Df6bNfUEEkGrVo.1

This talk is part of the Formalisation of mathematics with interactive theorem provers series.

This talk is included in these lists:

• All CMS events
• All Talks (aka the CURE list)
• CMS Events
• Cambridge talks
• DPMMS Lists
• DPMMS Pure Maths study groups
• DPMMS info aggregator
• DPMMS lists
• Department of Computer Science and Technology talks and seminars
• Formalisation of mathematics with interactive theorem provers
• Hanchen DaDaDash
• Interested Talks
• Live-streamed at MR14 Centre for Mathematical Sciences
• School of Physical Sciences
• School of Technology
• Trust & Technology Initiative - interesting events
• bld31

Note that ex-directory lists are not shown.