COMP2121›Game-playing in AI

Artificial IntelligenceTopic 9 of 19Regular Notes

Game-playing in AI

2 minread

363words

Beginnerlevel

📘 Problem Solving by Searching: Game Playing

1. What is Game Playing in AI?

Game playing in AI refers to designing systems that can play games intelligently against humans or other machines. AI uses search algorithms and decision-making strategies to determine the best move in a game.

AI treats the game as a search problem, where each move leads to a new state in the game tree.

2. Types of Games in AI

Game Type	Example	Features
Deterministic	Chess, Checkers	No chance elements, fully predictable
Stochastic	Backgammon	Involves randomness (dice, chance)
Turn-based	Tic-Tac-Toe	Players alternate turns
Simultaneous	Rock-Paper-Scissors	Players act at the same time
Zero-sum	Most board games	One player’s gain = another’s loss
Non-zero-sum	Trading games	Players can benefit together

3. Game as a Search Problem

Each game is modeled as a search tree:

Initial State: The current board or game setup.
Actions: Possible legal moves from the current state.
Successor Function: Resulting state after an action.
Terminal Test: Checks if the game is over.
Utility Function: Assigns a numeric value (score) to terminal states (e.g., +1 win, –1 loss, 0 draw).

4. Key Algorithms for Game Playing

Algorithm	Description	Used In
Minimax	Assumes opponent plays optimally; maximizes AI’s score while minimizing opponent's	Chess, Tic-Tac-Toe
Alpha-Beta Pruning	Optimized Minimax; prunes unnecessary branches to speed up search	All deterministic games
Expectiminimax	Extension of Minimax for stochastic games; accounts for chance nodes (like dice)	Backgammon
Monte Carlo Tree Search (MCTS)	Random simulations used to explore the most promising moves	Go, Poker, complex games

5. Minimax Overview (Recap)

Maximizer: AI player
Minimizer: Opponent
Evaluates all possible outcomes and chooses the best move assuming the opponent also plays perfectly.

6. Real-World Examples

Game	AI System
Chess	Deep Blue (beat human world champion)
Go	AlphaGo (used neural networks + MCTS)
Poker	Libratus (used game theory + simulation)
Tic-Tac-Toe	Simple Minimax implementation

✅ Summary

Concept	Explanation
Game Playing	AI agents playing games using search and decision-making
Search Tree	Represents all possible game states
Minimax	Used in deterministic, turn-based, zero-sum games
Alpha-Beta Pruning	Makes Minimax more efficient
Utility Function	Scores outcomes of games
Use Cases	Games, simulations, decision-making, strategy AI

Previous topic 8

Alpha-beta pruning

Next topic 10

Case Study: General Problem Solver

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.

COMP2121›Game-playing in AI

Artificial IntelligenceTopic 9 of 19Regular Notes

Game-playing in AI

2 minread

363words

Beginnerlevel

📘 Problem Solving by Searching: Game Playing

1. What is Game Playing in AI?

AI treats the game as a search problem, where each move leads to a new state in the game tree.

2. Types of Games in AI

Game Type	Example	Features
Deterministic	Chess, Checkers	No chance elements, fully predictable
Stochastic	Backgammon	Involves randomness (dice, chance)
Turn-based	Tic-Tac-Toe	Players alternate turns
Simultaneous	Rock-Paper-Scissors	Players act at the same time
Zero-sum	Most board games	One player’s gain = another’s loss
Non-zero-sum	Trading games	Players can benefit together

3. Game as a Search Problem

Each game is modeled as a search tree:

Initial State: The current board or game setup.
Actions: Possible legal moves from the current state.
Successor Function: Resulting state after an action.
Terminal Test: Checks if the game is over.
Utility Function: Assigns a numeric value (score) to terminal states (e.g., +1 win, –1 loss, 0 draw).

4. Key Algorithms for Game Playing

Algorithm	Description	Used In
Minimax	Assumes opponent plays optimally; maximizes AI’s score while minimizing opponent's	Chess, Tic-Tac-Toe
Alpha-Beta Pruning	Optimized Minimax; prunes unnecessary branches to speed up search	All deterministic games
Expectiminimax	Extension of Minimax for stochastic games; accounts for chance nodes (like dice)	Backgammon
Monte Carlo Tree Search (MCTS)	Random simulations used to explore the most promising moves	Go, Poker, complex games

5. Minimax Overview (Recap)

Maximizer: AI player
Minimizer: Opponent
Evaluates all possible outcomes and chooses the best move assuming the opponent also plays perfectly.

6. Real-World Examples

Game	AI System
Chess	Deep Blue (beat human world champion)
Go	AlphaGo (used neural networks + MCTS)
Poker	Libratus (used game theory + simulation)
Tic-Tac-Toe	Simple Minimax implementation

✅ Summary

Concept	Explanation
Game Playing	AI agents playing games using search and decision-making
Search Tree	Represents all possible game states
Minimax	Used in deterministic, turn-based, zero-sum games
Alpha-Beta Pruning	Makes Minimax more efficient
Utility Function	Scores outcomes of games
Use Cases	Games, simulations, decision-making, strategy AI

Previous topic 8

Alpha-beta pruning

Next topic 10

Case Study: General Problem Solver

Past Papers

Open this section to load past papers

Click on Show Past Papers to see past papers.