Min-Max Gaming Theory (with Alpha-Beta Pruning)

Let’s pretend that we are playing a game, and it is our turn. On our turn we have two choices, “A” and “B.” By selecting choice “A” we will lose the game, and by selecting choice “B” we will win the game. The obvious choice would be “B” for the win. If we have ten choices that we can choose from and the first choice gives us a win, the remaining nine choices can be ignored since any other choice will not produce a result better than the first choice, which results in a win. This is the theory called “Min-Max with Alpha-Beta pruning.” You seek to find the best result, and your opponent seeks to find your worst result (or his best result). If choice “A” for your opponent leads to you winning and choice “B” for your opponent leads to you losing, your opponent will choose “B,” leading to your loss (or their win). As you evaluate each level or turn to be made, you seek a positive, winning result while your opponent seeks a negative (losing for you) result.

Once the maximum or a preset cutoff (threshold) result has been found, all remaining decisions (or paths) are unnecessary to examine. Many “n-player” games like chess, Othello, and checkers utilize these gaming theories to quickly evaluate and determine the non-human player’s strategy (also called AI, or artificial intelligence, since we are simulating intelligent thinking).

In Chapter 13, we discuss artificial intelligence in more depth.

Before we look at instructing a machine to process our commands (or programming), let’s look at a simple gaming process on paper and replicate it through a flowchart (a diagram explaining our process) and then various methods of writing our instructions (also known as “coding” or “programming”).