Tic-tac-toe is a fairly simple game. Each player takes a turn marking a square, and the first player to claim 3 in a line wins. A computer is very good at this game, and won’t ever get anything worse than a draw. Give it a try!

But how does it do it? We need a way to represent this problem before we can try to have a computer solve it. Trees can work well because we can enumerate every move and its resulting state. Make a move to see how we traverse the tree.
In addition to this we’re going to use an evaluation function, a heuristic, to help us solve this problem. Our evaluation function will assign states that X wins a value of 1, draw states a value of 0, and states that O wins a value of -1. Our goal is to choose the state with the highest value.
Using this evaluation function, can you decide what X should pick here?
First we'll look at the bottom left node.
We find that the node has a value of 0.
We return to the parent node, but we find that there's still options that we have not considered.
We find that the right child is a win!
Because all of the children are now evaluated, we can now pick a move with confidence.
Our goal as X is to maximize the value, so we pick the child with the highest value.
We can peek into all possible futures by looking at the current state's children, and using our evaluation function, we can assign a value to the states we see. This will allow us to choose the most valuable move.
Our choice was correct in the last example, but it isn’t hard to imagine a situation where this method of choosing moves could lead us astray. Look at the next example: all of the children are inconclusive, so the states have a value of 0. Does this mean all of them are equally viable moves? As we can see, we yield the choice for the next state to O. Of course we don’t know what O will pick, but if we want any kind of guarantee about the worst case scenario for a move, we should assume that our opponent will play perfectly. If we’re willing to look deeper into the tree, we’re able to reevaluate a state’s value based on where we think it will lead us.
When O tries to decide what move to make, O can also assume that X will pick the best option for themselves. But what is the best move for X? Now we're back to the same place we started, searching for the best move X can make, only deeper into the tree. We could stop any time, but our results will be more reliable the deeper we go. Here is the same tree, but we evaluate each node in order.
This is the essence of the Minimax algorithm, which is the foundation of many powerful techniques. It is a very exhaustive algorithm, so it will try to evaluate every node in a tree if you allow it to. This can be a problem, as trees can have explosive growth. Depending on a game’s branching factor(possible plays in a turn) and how many layers(turns) deep into the tree you want to look, the problem can quickly become unmanageable.

Luckily, there are many ways we can improve the performance of Minimax

I want to draw your attention to a specific moment in the middle of evaluation for our last diagram. At this point we should be able to tell that the best-case scenario for this move is worse than another option we already found. So why keep looking into the branch?
We can account for this by keeping track of the best and worst case scenario.
We store the best and worst options we find in α and β. We start by filling them with two extreme values so that we don't discard our first options.
The first option has a value of 1!
Now we return to our parent. It's the root player's choice so we compare it with α and find that the value we found is better, so we update it.
Now we start looking at the next child. We pass the current node's α and β to it.
This node isn't a leaf/terminal node, so we look at it's children as well. We find that the first one has a value of 0!
Because the opposing player picks the move on this node, we compare it with β, and find it to be better(worse for us), so we update it. However we notice that α is now greater than β. This means that in the best case for us, this branch is already worse(0) than another option(1) that we've already found. We now have no reason to keep looking into this branch.
This will give us identical results to Minimax, but can give us vastly better performance.
One thing to keep in mind is that alpha beta cannot guarantee that we’ll get better performance. The order in which things are evaluated makes a huge difference. We're lucky because the most valueable move is found first, but it's perfectly plausible that we'll evaluate moves in increasing value, meaning that we could see little to no performance increase.
Luckily there are a few things that we use to help us avoid this problems. One solution is to pick a random move each turn. Doing that can help us avoid falling into obvious patterns, which may have helped us in the above example. Heuristics can also help us. For example, in chess, moves that lead to captures will often be a good indicator of which branch to pick. Finally, we can also employ iterative deepening, choosing to expand the path leading to the most valuable state first, as previous states are a good indicator of future valuable states. This encours a slight overhead, but it’s often worth it in larger trees. Here is an example of it in action:
Here is a comparison of techniques used!
Like we mentioned before, iterative deepening has an overhead, but it prunes branches far more aggressively, allowing for us to go far deeper in large trees. There is almost no reason not to use alpha beta pruning over minimax, but your choice of branch ordering can have a massive effect on the outcome. Which one is best depends on your specific game.