The computational complexity of Stratego perfect strategy

Abstract

In this thesis we look at some of the proofs of proven EXPTIME-complete games and give our own EXPTIME-completeness proof. We specifically look at chess and American checkers, for which we will describe their EXPTIME-hardness proofs. Furthermore for American checkers we will explain why the current proof is insufficient to prove any other checker variant and show an attempt at adapting it for international checkers. Next we give our own proof for perfect information Stratego being EXPTIME-complete. We do this by first proving a new game, that we call G2.5, to be EXPTIME-complete and making a reduction from that to stratego. The EXPTIME-hardness result within the EXPTIME-completeness proof can also be seen to apply to Stratego without perfect information. Lastly we will give some insights on how to improve both the checkers proof and our stratego proof.