Game theory and imperfect information

Hi. I finally finished my save games. Well, sort of. =D Anyways, I’m trying to add the second player to an actual conflict (the AI).

I made something that ‘brute forces’ the map by studying folds and the branches of potential decisions (at branchDepth = 7 it reaches almost a second to calculate, so I definitely need to do some optimization).

So I understand the very basics of that sort of weighted decision making for abstract strategy games (like they do in a lot of Chess engines) … But what I was wondering is, as game developers, how do you ‘hide’ information from the AI’s decision making to simulate things like a Fog of War?

Right now, from the player’s perspective, each location has a fogOfWar value for each belligerent. It goes 0 never revealed, 1 revealed but no longer adjacent, 2 revealed but adjacent and 3 currently occupying. Each level reveals more information about the Location and it’s occupants strengths and/or weaknesses.

My problem is that unless the field is cloned before each decision, the AI ends up with a near perfect view of the battlefield at the end of every turn. Is there a way to hide information revealed from one branch of a decision tree from all other branches, and then all of the information revealed from all the decision tree searches from the decision maker itself without cloning the field, performing the move and assigning a ‘weight value’ to the outcome (’cause I imagine that would make it even slower)?

And thanks again to everyone for being so helpful and understanding of my nubbiness at game programming. :D

I’m not sure I understand what you’re doing. If there is some fog of war, it should apply equally to the player and AI, each from their own perspective, so each location should have a playerFogOfWar value and an aIFogOfWar value. While the AI is thinking, it shouldn’t be acquiring new information. Any action that changes the fog of war value on any location shouldn’t be undoable, so there should never be a need to duplicate the field.

If the AI is allowed to try out each series of decisions to see the result and then pick the best course of action back from the starting point, it’s cheating! In a strategy game, it would make it impossible for the player to ambush the AI. In poker, it would be impossible to either bluff the AI, or bait it.

The AI should be fun to play against. When making an AI, cheating is encouraged.

As long as it seems fair, the player will have no idea how the AI makes its decisions. Have the AI send scouts all over the map and the player will assume that its information has been collected legitimately.

I disagree (maybe?) with CG. If you have a strategy game with Fog of War, do not let the AI know where the units are hidden! There’s nothing more annoying than an omniscient AI that knows stuff it shouldn’t.

Oh I see, yes that makes sense… I think. I wanted to make it kind of an abstract strategy and war game simulation hybrid – so perfect decision making is possible inside a given location, but information became more generic the further from that location you got.

So, the decision making process should only input the ‘battle field’ that the player would see, if he were to suddenly switch places with the computer? And then to simulate ‘long term strategy’ I would weight desirability of moving towards unrevealed locations by, say, the number of connecting locations (which a player would be able to see without having revealed the location)?

Or would you build it in layers? One AI that deals with the perfectly revealed variables inside an occupied location, one that deals with imperfect variable ranges inside revealed but unoccupied locations and then one that deals with minimal information in unrevealed locations – and then weight the results of the individual searches to determine a ‘best decision’?

Originally posted by Enigmatrix05:

So, the decision making process should only input the ‘battle field’ that the player would see, if he were to suddenly switch places with the computer?

Exactly. Although what CuriousGaming was getting to is that it’s very hard to make a good AI that works in this way. It is very tempting to make an AI that cheats so it actually presents a challenge to the player. It’s easier to dumb down an overperforming AI, after all. And he’s right, the goal of a game is to make the player have fun, not to showcase your amazing AI. On the other hand, if it becomes obvious that the AI is cheating to make up for its crude thinking, strategy-minded players will likely look elsewhere for their entertainment, because nobody likes to play against an obvious cheater.

I guess the truth is somewhere in the middle: Make the AI as good as you can make it, and give it a few illegal nudges here and there if it still needs them.

The ‘map’ (i.e. what is used for input for AIs and for rendering for the player) should have two layers: what is actually happening, which is a single instance, and a visibility overlay (i.e. ‘fog of war’), which you need to store for each player.

I definitely disagree with CG, it’s hard to cheat without consequences of that cheating becoming obvious to the player, and that breaks the illusion of fairness. It’s much better, if you can, to write an AI that is competitive without cheating.

Okay, sweet.

Thanks for the help everyone. I’m going to try and make one without cheating – for now anyways. But I am going to make an ‘AIInterface’ that my new AI (PaintEatingAI) will implement, and that interface (getAction()) is all that the ‘GameEngine’ will require… That way, if I ever get more advanced, I can have multiple AI options (ranging from the easy paint eater, to the ultra tough lived-under-powerlines-next-to-a-nuclear-dump-site).

So long as the ‘decision making’ is on the other side of getAction(), that should work right? Or would I want to make 2 interfaces if I wanted to be able to update the AI later (a getAction() and a decideAction() one)?

Anyways, thanks again for all the help and tips. :)