One of the main aims of game AI research is the building of challenging and believable artificial opponents that act as if capable of strategic thinking. In this paper we describe a novel mechanism that successfully endows NPCs in real-time games with strategic planning capabilities. Our approach creates adaptive behaviours that take into account long-term and short term consequences. Our approach is unique in that: (i) it is sufficiently fast to be used for hundreds of agents in real time; (ii) it is flexible in that it requires no previous knowledge of the playing field; and (iii) it allows customization of the agents in order to generate differentiated behaviours that derive from virtual personalities.