α/β Pruning

This post is meant to prepare me for my next project, a chess AI.

Weights

Humans are very different from computers. What we lack in raw processing power, we make up for intuition. Computers are the very opposite. With no intuition or subconscious, everything is either explicit or calculated. Modern AI uses weights from explicit rules to train a neural net. This is some imitation of intuition. I will attempt to use this method to quickly determine if a move is good or bad.
See Weight In Uncertainty

Challenge

The challenge of a modern chess AI is complex in many different aspects. The framework you begin with defines how effective the program may perform, not just from a time-space-complexity standpoint, but also from a competitive perspective.

The premise:

Teach an AI:

How the pieces move,
How to take other pieces,
Where the pieces are the most valuable,
How to open, more on this later
How to checkmate,
How to determine if a move is good or bad.

Q:

1. What data structures are required?
2. How do we reduce big(O)?
3. How do we quickly evaluate a move?
4. How do we find the best move set?
5. What makes a good move?

This final objective is clearly the most difficult to accomplish and the reason for this blog. First, what makes a move "good"?

The entire premise of chess is to move your pieces in a way that gives you a checkmate against your opponent. The best way to think of this is through position. The "position" is the way the pieces are arranged. If you have the better position you will win.

3,5: So if a move improves our position, it is good.

To evaluate a position we must create rules and weights based on the first five objectives: How the pieces move, how to capture pieces, where they are the most valuable, how to open like a pro, and how checkmate is possible.

A position is evaluated on these five weights.

The Problem

Now we just have to evaluate every possible position with these weights, ~10^100... That's a one with 100 zeros.
How about the first six moves? After some math, it's about 9,132,484 distinct positions. What gives we can even see a few moves ahead without some insane number of positions. Most games of chess last at least 20 moves, some even in the hundreds. How can we reduce the number of positions to evaluate without a major loss of competitive potential?

1,2,4 The Solution

α/β Pruning

This gives us the answer to questions 1 and 2. What is alpha-beta pruning? α/β Pruning is a search algorithm that reduces the number of nodes on a tree based on some explicit or evaluated rules. Say you generate a layer of nodes on a tree with values 1-10. The pruning then removes any node with a value of less than 3. This removes 1/3 of nodes and your next layer is 1/3 * children smaller. If half of all chess moves are objectively bad the problem becomes more linear instead of some runaway value of 10^100 moves.

Thanks for reading and have a wonderful day.