Date: Fri, 15 Jan 2021 18:02:01 +0000
<p>Aside 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.</p> <p>In this episode, Josh Brunner, Master's student in Theoretical Computer Science at MIT, joins us to discuss his recent paper Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard.</p> <p><strong>Works Mentioned</strong><br /> <a href="https://arxiv.org/abs/2010.09271">Complexity of Retrograde and Helpmate Chess Problems: Even Cooperative Chess is Hard</a><br /> by Josh Brunner, Erik D. Demaine, Dylan Hendrickson, and Juilian Wellman</p> <p><a href="https://deepai.org/publication/1-x-1-rush-hour-with-fixed-blocks-is-pspace-complete"> 1x1 Rush Hour With Fixed Blocks is PSPACE Complete</a><br /> by Josh Brunner, Lily Chung, Erik D. Demaine, Dylan Hendrickson, Adam Hesterberg, Adam Suhl, Avi Zeff</p>
