Types of Games

deterministic: fully observable environments in which two agents act alternately and in which the utility values art the end of the game are always equal and opposite

imperfect / imperfect information: whether information are visible to each player

Games vs Search Problems

If we want to apply search strategies to win games

• what would be the solution when applying search strategies to games?
• The solution will be a strategy that specifies a move for every possible opponent reply

Challenges

• Very, very, very large search space
• Time limits

Game as a Search Problem

• $S_0$: the initial state, which specifies how the game is set up at the start
• $\text{PLAYER}(s)$: Defines which player has the move in a state
• $\text{ACTIONS}(s)$: returns the set of legal moves in a state
• $\text{RESULT}(s,a)$: The transition model, which defines the result of a move
• $\text{TERMINAL-TEST}(s)$: (the goal test), a terminal test, which is true when the game is over and false otherwise. States where the game has ended are called terminal states
• $\text{UTILITY}(s,p)$: A utility function that defines the final numeric value for a game that ends in terminal state s for a player p
  • Also called an objective function or payoff function

The initial state, ACTIONS function and RESULT function define the game tree for the game — a tree where the nodes are game states and the edges are moves.

Finding Optimal Decisions In Games