AI Algorithms for Gaming

Introduction

• Playing against a computer is only fun when it's challenging
• What you should know

1. Turn-Based Games

• Some history as motivation
• Different types of games
• Tree-based decision-making
• Time complexity of brute force approaches
• Time complexity of chess
• The cat trap game
• The Python setting for the cat trap
• Code example: A random cat

2. The Minimax Algorithm

• Minimax overview
• Minimax example
• The minimax algorithm
• A word on complexity
• Code example: A perfect cat in a small world
• Alpha-beta pruning
• The alpha-beta search algorithm
• Code example: A pruning cat

3. Depth-Limited Search

• Depth-limited search
• Writing good evaluation functions
• Is alpha-beta pruning still relevant?
• Challenge: Write your own evaluation function
• Challenge solution
• Code example: A depth-limited cat

4. Iterative Deepening

• The iterative deepening technique
• Is iterative deepening a waste of time?
• Code example: An iteratively deepening cat
• Is iterative deepening really that good?
• Is alpha-beta pruning really that good?

5. Fun with Optimizations

• The negamax algorithm
• Transposition tables
• Monte Carlo evaluation functions

Conclusion

• Next steps