AI-Powered Connect-4
Artificial intelligence has always piqued my interest. The idea that you can create a being (although hardly conscious) that makes logical decisions based on how it views a situation has always been appealing to me. Stateful AIs have been in play since the dawn of modern computer science theory. Only recently, however, has our computing ability been able practically realize algorithms that were once theorized.
TLDR — I implemented an AI that utilizes a minimax algorithm enhanced with alpha-beta pruning that competes with you on a game of Connect-4. Every move you make recalculates the decision that the AI will make based on the utility of each possible move.
Since you’re past the TLDR — If you somehow forgot how connect-4 works, here’s a quick dry-run: The game is played on an NxN Grid in which players take turns placing their markers. If a player is able to make a connected sequence of four of their markers, they win. The sequence can be connected horizontally, vertically, and even diagonally.
How Does The AI work?
The AI is architected using the Minimax Algorithm to determine utility with Alpha-Beta Pruning to reduce the size of the decision tree.
Ok. Now English, I suppose. An AI views the condition of its environment in the form of a state. A state could be composed of anything. In the case of a Roomba (those wonderful, tidy little creatures that clean up your mess), a state could consist of the number of room it's cleaned, the amount of dust particles it's detecting, barriers it can see, etc. Each state is composed of a utility. In plain terms, utility is the equivalent of an AI's happiness. The higher the utility, the more happy the AI is (yay!). Hence the word "utilitarian" (but we'll discuss that at a different time and different place).
Still with me? Great. In the case of this AI, the utility measurement is simple -- the number of ways it can win in the lowest possible number of moves. If move A increases the likelihood that the AI can win (from any different number of moves), then the AI will perform move A. Second, if move A reduces the likelihood that the player will win (the opposite of the previous statement), the more utility the move has.
Now that the concept of utility is established, we can talk about Minimax. Let's suppose you're playing a game of chess. Every move you make is in anticipation of your opponent's move. Your ultimate game is to make the opponent make a series of moves that ensure that they will lose and correspondingly that you win . Did you castle your king & rook if it was useless? Probably not. You expect some outcome from that move. The minimax algorithm works in this way. A decision tree is created at each state from all the possible moves that the AI can make. If the AI places a mark in Cell C, what is the best possible move the human can make, then what is the best move it can make in response, so on, so forth. Once this decision tree is made, the AI can determine which move will ensure the greatest probability that it can win and execute that move. Alpha-Beta pruning just ensures that decision subtrees which automatically guarantee less utility than the maximum will never be evaluated. This reduces the resource drain from the algorithm.
There. Done. You survived. Pat yourself on the back, you just learned something new (hopefully). If you'd like to learn more about this project, you can view it on my GitHub here.