Artificial intelligence (AI) techniques have been applied to video games to make the overall experience more enjoyable. In games with interactive storytelling (IS), player actions can substantially affect plot events and plot characters. Therefore, AI planning techniques have been used to shape the plot inresponse to player actions that conflict with authorial goals. While such methods are poised to increase player fun andagency, two recent implementations (ASD and PAST) have not been formally evaluated to date. In this paper we do so via a series of user studies for the first time. We show that ASD significantly enhances fun and agency, whereas PAST gets mixed results with an interaction between effects of the experience manager and player prior gaming experience in one user study, and marginally significant results for increased agency in a study with a constrained story domain.