Role-playing games, and other types of contemporary video games, usually contain a main storyline consisting of several causally related quests. As players have different motivations, tastes and preferences, it can be beneficial to customize game plotlines. In this paper, we present an offline algorithm for adapting human-authored game plotlines for computer role-playing games to suit the unique needs of individual players, thereby customizing gaming experiences and enhancing re-playability. Our approach uses an plan refinement technique based on partial-order planning to (a) optimize the global structure of the plotline according to input from a player model, (b) maintain plotline coherence, and (c) facilitate authorial intent by preserving as much of the original plotline as possible. A theoretical analysis of the authorial leverage and a user study suggest the benefits of this approach.