The hide-and-seek game is considered an excellent domain for studying the interactions between mobile robots and humans. Prior to the implementation and test in our mobile robots TIBI and DABO, we have been devising different models and strategies to play this game and comparing them extensively in simulations. We propose the use of MOMDP (Mixed Observability Markov Decision Processes) models to learn a good policy to be applied by the seeker. For two players the amount of states is quadratic in the number of discrete map cells. The number of cells were reduced by using a two-level MOMDP, where the policy is computed on-line at the top level with a reduced number of states independent of the grid size. In this paper, we also introduce a new fast heuristic method for the seeker and compare its performance to both off-line and on-line MOMDP approaches. We show simulation results in maps of different sizes against two types of automated hiders.