I am not sure, but I think this question is more of a mathematical nature than programming/gaming/computer science one, so I'm asking it here.
Suppose I have a game, not too dissimilar to Pacman, where I play a character, in a bordered 2D map/grid, and my purpose is to stay alive as long as possible. In this map, the only entities present are me, and a number of enemy monster characters, whose purpose is to kill me. The only way I can be killed, is if me and any of these monster occupy the same position simultaneously. Other than this kill condition, there's little difference between me and the monsters: the characters occupy one position at any given frame, and can also make a single move in each frame. The characters have 5 options regarding their moves: they can either move 1 unit up, down, left or right, or they can stay where they are.
Knowing this, where's my problem: I'm trying to make an AI agent to play the game for me. And while I can indeed stay alive indefinitely when there's only 1 enemy I have to contend with (in a map of dimensions 2x2 or bigger), I cannot accomplish that versus a bigger number of enemies. Is there any known formula that can give me the number of possibles moves I can make at any given frame, that result in me being alive in the very next frame, no matter what the enemy does? And that also guarantees that I can preserve my ability to make a move that keeps me alive in the frame after that?
Currently, I can stay alive indefinitely versus a single enemy using this formula at each frame to calculate my next move:
- I calculate the 5 (or less, if I'm at a border/corner) positions I can occupy in the next frame, according to my movement options;
- I calculate the 5 (or less, if the enemy is at a border/corner) positions the enemy can occupy in the next frame, according to its movement options;
- I choose a random move that results in a position not included in the positions the enemy can occupy in the next frame.
Applying the above stategy at each frame does keep me alive indefinitely, because there is always at least one move I can make that leads to a position the enemy can't reach in the next frame. Even in the worst case scenario (excluding me having the same position as the enemy, where I would lose immediately, or being in a 1*n map, where I could reach a point where I would lose all movement options, except staying still or move backwards, to where the enemy could be), like being in a corner, I would lose 2 movement options, but the enemy can also only remove 2 movement options from me at most, leaving me always with 1 movement options where I can move to a position the enemy can't.
With 2 enemies, I could try to apply the above formula for each enemy (maybe recursion/recurrence could be apply here), which would leave me with no movement options in certains cases (again, like being cornered, but also like trapped at a border). I could try to add other considerations, like movement that, even if they guaranteed my survival in the next frame, could also put me in a position where I couldn't guarantee it in the frame after that (like, as mentioned before, being cornered or trapped at a border). And in this case, I need to look not only at the next frame, but 2 frames ahead from where I'm at (1 frame ahead for 1 enemy, (at least) 2 frames ahead for 2 enemies... is there a pattern here?). But I honestly don't know if that is enough, and much less how to generalise this to a bigger number of enemies.
I guess what I'm asking is, can anyone help me come up with a formula I could apply at each frame that, taking into account my position, the enemies positions, the movement options we're allowed to realise, the dimensions of the map, and the frames I can look ahead, that could give me the number of possible moves I could make that would not only guarantee my survival in the next frame, but would also preserve my ability to do the same in the next frame(s)?
The Good News
If the enemies are (a) identical, (b) deterministic, and (c) can co-exist in a square, it may be possible to continue moving indefinitely, but you would need to know their behavior in advance, and have sufficiently large distance to prepare.
For example, consider a basic enemy that always aligns with you horizontally, then moves up or down vertically to try to "capture" you. For any number of enemies, if the greatest horizontal distance to an enemy is n, and you have room/time to wait and/or move up n times, then do so. At this point, all of the enemies are in a column beneath you, with at least one blank square between you (if not, change one of those earlier waits to a move up). Their next move will be to move up, and your next move will be to the right. On their next move, their algorithm will require them to go right, but you will go left, leaving you still unaligned. If you keep alternating this left and right movement, so will they, giving you a trivial way to stay alive indefinitely.
The more complex their deterministic strategy is, the more distance you need to have to prepare, and the more your strategy needs to "clump" the enemies into as similar a position as possible.
The Bad News
If the enemies are allowed different strategies, or the same strategy with a random choice included, or pile up into adjacent squares, you're sunk. Consider two enemies, one which prioritizes aligning horizontally and one that prioritizes aligning vertically. Given a room with size $n \times n$ grid, it will take the enemies at most $n$ moves to align with you in their preferred direction, and at most $2n$ additional moves to corner and capture you. Given that such enemies will decidedly capture you in at most $3n$ moves, random players could eventually stumble into the same position, although the number of moves required would be unknown.
Similarly, any randomness or adjacency issues present a problem with the exploitative nature of the above solution; anyone who wasn't in the column (because of a random move or because the column spot was full) could move toward you, ruining the symmetry of the movements and allowing you to be captured.
In Short
Unless your enemies are painfully obvious, there is no good solution for n=2 or more enemies.