Example: tic tac toe (also called noughts and crosses) is a game for two players, X and O , who take turns marking the spaces in a 3 × 3 grid. The player who succeeds in placing three of their marks in a diagonal, horizontal, or vertical row is the winner.
Game tree
Game is typically an Adversarial Search problem where your opponent has something to say about your strategy.
Types of games
Many different types of games.
- Is there some randomness element in the game
- Deterministic, e.g., Tic-Tac-Toe, Chess, Chinese Chess, Go
- Stochastic, e.g., Poker, Mah-jong
- How many players
- One, e.g., Solitaire, various puzzle games
- Two, e.g., Tic-Tac-Toe, Chess, Chinese Chess, Go
- More than two e.g., many Poker games, Mah-jong
- Are you playing against each other (strictly competitive)
- Zero sum, e.g. Tic Tac Toe, Chess, Go, Poker
- Non zero sum, e.g. Prisoner’s Dilemma
- Can you see the state
- Perfect information, e.g. Tic Tac Toe, Chess, Chinese Chess, Go
- Imperfect information, e.g. Poker, Mah-jong
Formalisation
- States :
- Actions : (may depend on player/state)
- Transition function :
- Terminal test : (true, false)
- Players : (usually take turns)
- Utilities : (values on outcomes)
- A utility function (also called an objective function or payoff function) defines the final numeric value for a game that ends in terminal state for a player . Goal of a search algorithm: for a player, we want the algorithm to find a strategy Policy ) which recommends a move for each state, in order that they can end up with the maximum achievable utility.