University of Cambridge > Talks.cam > Formalisation of mathematics with interactive theorem provers  > Alpha-Beta Pruning Explored, Extended and Verified

Alpha-Beta Pruning Explored, Extended and Verified

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

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.

Tell a friend about this talk:

This talk is included in these lists:

Note that ex-directory lists are not shown.

 

© 2006-2024 Talks.cam, University of Cambridge. Contact Us | Help and Documentation | Privacy and Publicity