even-cooperative-chess-is-hard | episodes

listen on castbox.fmlisten on google podcastslisten on player.fmlisten on pocketcastslisten on podcast addictlisten on tuninlisten on Amazon Musiclisten on Stitcher


Even Cooperative Chess is Hard

Asside from victory questions like “can black force a checkmate on white in 5 moves?” many novel questions can be asked about a game of chess. Some questions are trivial (e.g. “How many pieces does white have?") while more computationally challenging questions can contribute interesting results in computational complexity theory.

In this episode, Josh Brunner joins us to discuss his recent paper Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard.

Josh Brunner

Josh Brunner is a Master's student at MIT in Theoretical Computer Science and has received his Bachelor's in Math and Computer Science from MIT. Josh's main hobbies are playing various board games, especially chess variants, and a game that he and a group of friends invented and playtest at least twice a week. His research is primarily about the algorithmic complexity of various puzzles and games. He has also done research in online algorithms and other algorithmic hardness results.