I use influence maps in my AI, and that works fairly well to generate a good strategic and tactical disposition of the forces opposing the player. Except, in the case where the enemy is surrounded. The AI should really try hard to break free, and I'm working to overcome the problem of desire to escape versus having to break out of an encirclement. Once that is solved, there will be a further problem: the (human) player will catch on to that, and will leave a one-hex corridor free, so the enemy isn't completely surrounded, obliterating any enemy that attempts to escape that way. I could try pathing every possible escape route, but that would be much, much too time consuming. There must be some way of taking my influence map data, and generating some sort of measure that would rate the closeness to being surrounded. Does anyone know of an article or technique I can use to detect the amount of "surroundedness"?

My initial reaction before I even read your posts was "influence maps and pathing." I was relieved when I saw I didn't have to explain the former. For the pathing, you only need to attempt to find ONE path from your current location to the edge of a map or some other point outside the circle. If you weights are such that you can make those occupied and semi-occupied areas "impassable", then your path should fail (after filling the entire area of the circle). If that is the case, you are surrounded.

Also, you can treat it like topology and use the techniques for detecting local minima, etc. That is, if you are in a "bowl", you are surrounded. I don't know these techniques off-hand.

One thing you need to watch out for is that the definition of surrounded can be dicey. You want to include a range component as well. Being surrounded in terms of feet and yards is often different than being surrounded with the enemy miles away.

In terms of handling things, remember to combine multiple influence maps... the negative of the enemy and the positive of your goals (like retreating to your base). If you lay down a preferred path from your current location to your goal and boost it, you can bias that area so that (all other things being equal) it becomes your preferred break-out direction.

It's that one hex path that is the problem. I'm looking for a way to get the AI to recognize the encirclement *before* it is total. When it is a "C" shape, for instance - recognizing the developing danger in that rather than letting the human player fold-up the AI's lines into itself.