Model-based testing (MBT) allows a target software to be tested systematically and automatically by making use of a model of the software under test. It has been successfully applied in various domains. However its application for testing computer games has not been much studied. The highly dynamic nature of computer games makes it challenging for modeling. In this paper we propose a predicate-based modeling approach coupled with an on-line test generation approach. Both aspects ease the details that need to be incorporated in the model to facilitate effective test generation. Additionally we also leverage the use of intelligent agents, so that dealing with hazards and obstacles can optionally be delegated to such an agent, hence keeping the model clean from such aspects. A case study with a game called MiniDungeon is included to discuss the viability and benefit of the approach, e.g. in terms of code coverage and ability to cover deep states.