Here's one way to formulate the problem as a Markov Game -- something I know how to solve:

Suppose there are N rooms. From the point of view of the pursuer, each either might be occupied (a one), or is not occupied (a zero).

The way in which this possible-occupancy-map evolves is clear: At each step, either the pursuer does not see the evader, or he does. If he does not, then each room that the pursuer cannot see changes its value to the maximum of its neighbors' (including itself). If he does, then the room in which the evader is spotted gets marked with a one and all the other rooms are reset to zero. This is deterministic.

The "if he is seen" part of the above is deterministic as well. In addition to the occupancy map, the state contains the positions of the two players. "If he is seen" depends only on the positions of the two players.

In any state in which the two player's positions are the same, the pursuer gets a reward of +1, and the evader gets a reward of -1.

Now we have a totally deterministic, two-player zero-sum Markov game. Discount future rewards and allow mixed (stochastic) policies, and you've got something that is solvable by minimax Value Iteration. This is computationally heavy, but the optimal policy that is computed in this way can be precomputed offline and stored alongside the map.

To summarize, the state space is

{0,1}[sup]N[/sup] x {1,...,N} x {1,...,N}

and contains N[sup]2[/sup] 2[sup]N[/sup] states, where N is the number of rooms.

This paper describes minimax Q-learning, which is closely related to Value Iteration. The whole "multi-agent" angle of the paper is mostly irrelevant; it's really a two player game (they just each happen to control many pieces).

One addition to what I described above... influence can't spread by jumping over an area that is seen. So if you search one branch of a system of rooms completely, then start searching the other branch -- but keep the nexus of the two in view -- then the influence can't move back to the initial branch. It's tricky, but works well.

Here's one way to formulate the problem as a Markov Game -- something I know how to solve:

[font=arial, verdana, tahoma, sans-serif][size=2]Emergent: Thank you. I guess I'll have to look those Markov games up, as it's a concept I haven't read about before. Hopefully the occupancy map will be enough though. When I tried it out on a 2D application, it seemed to result in the guards slowly expanding the area where they looked, evey now and then going back to areas already searched just to make sure the player hasn't gone back there.[/font]

One addition to what I described above... influence can't spread by jumping over an area that is seen. So if you search one branch of a system of rooms completely, then start searching the other branch -- but keep the nexus of the two in view -- then the influence can't move back to the initial branch. It's tricky, but works well.

I'll keep it in mind, though I think my implementation already has that effect, though purely by accident, due to a occupancyValue > 0 check.
Right now I think the biggest issue will be how to check if a tile on the map is seen, as line of sight checks are a huge bottleneck for us. I've settled for just having the tile where an enemy is standing being seen, and just checking every frame if the tile they want to search at the moment is in their sight cone with LOS. But that's hardly optimal.
Thank you anyway though, you've been a huge help!