Partially Observable Games

Partial observability: lack of access to the choices and/or state of the opponent:

• very common in many games, including video games
• and real life situations (competition between companies, countries, etc.)

examples: battleship, kriegspiel

Belief states are important. We will need to do state estimation, to keep track of the state of the player.

• We could consider the opponent as non-deterministic (as they also don’t have information about our positions)

Strategies in partially observable games are no longer based on the moves of the opponents, but on the possible percept sequence that we might get to.

e.g. in Kriegspiel, a strategy can be:

• Guaranteed checkmate, if for each possible percept sequence, it leads to a checkmate (AND-OR tree)
• Probabilistic Checkmate, if by randomizing the winning player moves, it is more likely to win than not (usually happens when there is a clear advantage but not a single strategy)
• Accidental checkmate, if the strategy leads to a checkmate depending on black’s move or position that is not know

Important: for each move, the player needs to move the pieces to the right squares, but:

• maximize the information they get about the board
• minimize the information the other player gets about them. Optimal strategies might reveal information to the opponent, sometimez randomizing is a good strategy
• This is a common pattern in game theory situations

#Card Games

Stochastic partially observable games

• stochastic because the missing information is generated by random chance. Initial approach: averaging over clairvoyance.
• EXPECTIMINIMAX with the first node being all the possible card options.

it would find a solution but:

• it will not consider belief states after acting (i.e. not learning or gathering information)
• it is likely to reveal too much information to the opponent (or at least makes no effort in hiding it)
  • Bluffing is an important part of this king of games.

Averaging over clairvoyance can be improved:

• Instead of considering every possible hand (which might not be possible), we consider abstraction (types of hands)
• We apply forward pruning
• We can apply heuristics, and cut-off search
• Adjust probability based on information (e.g. betting done by other players) Computers can in general beat top players in poker, and other similar games