TwiddleLab / Artificial Intelligence / Search, Games and Plans
Scoring Positions: Evaluation Functions
What you will learn
- Big games can't be searched to the end, so the search stops at a depth limit.
- At the cut, an evaluation function scores the position instead: a weighted sum of features, like 4 x open threes + 2 x open twos + 1 x centre.
- Minimax then works as before, on scores instead of wins and losses.
- Better features and weights make a stronger bot with the same search.
How the lesson goes
Chess has more possible games than there are atoms in the observable universe. So how does a chess bot pick a move in a second?
First, a bet: a computer checks a billion positions a second. How long would it take to read the whole chess tree, about 10^120 games?
Four in a row has 7 columns. How deep can a bot search in under a second?
Turn the dial. Each extra move multiplies the positions by 7.
7^7 = 823,543 positions at a million a second is 0.82 s. One more move is 7^8 = 5,764,801: almost 6 seconds. The game itself can last 42 moves, so the bot never sees the end.
The search stopped here. No one has won. Which board is best for red?
Red to move in all three. Trust your eyes.
Board B has an open three for red: red plays the empty square and wins. Board C has two open threes for yellow, and red can only block one. You judged the boards by counting threats: that is what an evaluation function does.
Scoring a position without finishing the game.
The search stops at a depth limit. There an evaluation function gives the position a score from features you can count: score = 4 x open threes + 2 x open twos + 1 x centre discs (red's minus yellow's). A win is worth 1000.
Count red's open threes on this board.
Tap every empty square where a red disc would finish a line of four.
The red row of three has an empty square at each end: two open threes. The diagonal from the bottom row up to the right has three red discs and an empty fourth: a third one. 3 open threes give 4 x 3 = 12 points.
Build the score function yourself.
Put a feature next to each weight. Watch which board your formula prefers.
An open three is one move from a win, an open two is two moves away, and centre discs take part in more lines. Each feature times its weight, added up, is a weighted sum: exactly what a neuron computes. Discs on the board or moves played are the same for both players, so they tell you nothing.
Minimax, two moves deep, with your score at the cut.
Step through it. Red has three candidate columns.
Tune your bot until it wins at least 8 of 10 games.
It starts with every weight at 0: it can't tell good positions from bad. Set the weights, then play a match.
Which board does the formula score highest?
4 x threes + 2 x twos + 1 x centre, red's minus yellow's.
Board A scores 2, board B scores 7 and board C scores -2. B has an open three going up the middle column, and red owns that column, which counts for the centre feature too.
Now play against the bot you tuned.
You are red and go first. It looks two moves ahead with your weights.
Previous lesson: Minimax · Next lesson: Alpha-Beta: Skip What Doesn't Matter · Part of the course: Search, Games and Plans
Lessons are interactive and need JavaScript. Turn it on to play them.
