Cutting Corners to Win and Handling Chance

In our previous articles, we explored how the Minimax algorithm helps computers make decisions in games like Tic-Tac-Toe. But there's a big problem: checking every possible move can take a very long time in complex games!

Why Games Are Hard for Computers

Even simple games create huge game tree:

• Tic-Tac-Toe: ~255,168 possible states
• Chess: ~10^120 possible games (more than atoms in the universe!)
• Go: ~10^360 possible positions

No computer could possibly check every move in complex games like chess or Go. That's why we need smarter approaches.

Let's see how computers overcome this challenge.

Evaluation Functions: Making Educated Guesses

In games too complex to search to the end, computers use evaluation functions to estimate how good a position is.

For example, a simple tic-tac-toe evaluation might count:

• +0.1 for each row, column, or diagonal with one X and no Os
• +0.2 for each row, column, or diagonal with two Xs and no Os
• -0.1 for each row, column, or diagonal with one O and no Xs
• -0.2 for each row, column, or diagonal with two Os and no Xs

In chess, evaluation functions consider many factors:

• Material (how many pieces each player has)
• Position (control of the center, king safety)
• Mobility (how many moves are available)
• Pawn structure (how well pawns protect each other)

Deep Blue, the computer that defeated world chess champion Garry Kasparov in 1997, used an evaluation function with approximately 6,000 different factors!

Alpha-Beta Pruning: Working Smarter, Not Harder

Imagine you're deciding which movie to watch by reading reviews. If the first three reviews for Movie A are terrible, would you need to read all 100 reviews before deciding not to watch it? Probably not!

This is the idea behind Alpha-Beta Pruning. It's a technique that helps computers skip checking branches of the game tree that won't affect the final decision.

How Alpha-Beta Pruning Works

Let's understand this with a simple example:

1. Max is considering Move A and Move B
2. After exploring Move A thoroughly, Max discovers it guarantees a score of at least 5
3. Max starts exploring Move B and discovers that Min can force the score to be 3
4. Should Max continue exploring other possibilities for Move B? No! Since Move A already guarantees a better score (5), Max can "prune" (ignore) the rest of Move B's possibilities

Why This Matters

Alpha-Beta Pruning can dramatically reduce the number of positions a computer needs to check:

• Without pruning: might need to check millions of positions
• With pruning: might only need to check thousands of positions

This means computers can look much deeper into the game tree and make better decisions in the same amount of time!

Real-Time Decisions in Complex Games

Even with Alpha-Beta Pruning, games like chess are too complex to explore all the way to the end. To handle this, computers use:

1. Depth limits: Only look a certain number of moves ahead
2. Evaluation functions: Estimate how good a position is without playing to the end
3. Opening books: Use pre-calculated best moves for the beginning of games
4. Endgame databases: Store perfect play for positions with few pieces left

Handling Games of Chance

What about games with random elements, like backgammon with dice rolls?

For these games, computers use an algorithm called expectiminimax which:

1. Works just like minimax for player turns
2. Adds "chance" nodes that calculate expected values based on probabilities

This allows computers to make optimal decisions even in games where luck plays a role.

From Tic-Tac-Toe to AI Champions

The techniques we've discussed have helped computers master many games. However, the journey of game-playing AI shows how far adversarial search has come:

• Tic-Tac-Toe: Early computers in the 1950s could play perfect tic-tac-toe
• Checkers: Completely solved in 2007 (perfect play leads to a draw)
• Chess: Computers have been stronger than human champions since 1997. Deep Blue defeated the world chess champion using advanced minimax with alpha-beta pruning
• Go: Long considered the hardest classic board game for AI, but mastered by AlphaGo in 2016. AlphaGo mastered Go by combining adversarial search with neural networks.
• Video games: AI now competes in complex video games like Dota 2 and StarCraft

Next time you play a game against a computer—whether it's tic-tac-toe, chess, or a video game—you'll know a bit more about the adversarial search algorithms working behind the scenes, calculating the moves most likely to defeat you!

---

Challenge: Can you beat an unbeatable AI? Try playing against one online and see if you can force a draw! Remember, with perfect play from both sides, Tic-Tac-Toe always ends in a draw.