This is part two of the Dev-Log Series about the Connect 6 Coding Competition. I highly recommend reading the first part (here), even if you are only interested in the MiniMax Algorithm.
The reason I discuss this algorithm in greater detail is because I’ll use it as a base for my KI. This approach differs from my first thoughts in the way the algorithm goes through the tree. The MiniMax algorithm is based on a depth first search. This means the algorithm first traverses the tree down towards a leaf. Once it has visited a leaf it goes up to the parent and goes down again to the next leaf. If every leaf of a parent node is visited it moves up further. Which Node gets treated as a leaf is dependent on the depth the algorithm is set on. This process for depth 2 is shown in the image below. Which depth gets used depends heavily one the available system resources, because the calculation time grows exponentially.
Once the algorithm visits a leaf, the state of the game gets valued dependent on the chances of winning. The values of the leaf gets propagated towards the root node. If a node is a minimizing node (opponents turn) it changes it’s value to the lowest value of it’s childs. A maximizing node (own turn) works exactly the opposite way. The following animation tries to demonstrate the algorithm.
It’s important to note that each node gets evaluated for the color of the KI thus the need for minimizing and maximizing nodes. A different approach would be maximizing every layer inside the tree but evaluate each layer with alternating colors. Choose whatever is easier for you to implement.
If you want to adapt this algorithm for a game with more than two players, we call it Paranoid-Algorithm. We assume that all opponents form an alliance against us, therefor try to minimize our score. This case is worse than each player trying to maximize his own score. This is a very pessimistic calculation and results in a very careful KI. That’s why it’s called Paranoid-Algorithm. Choosing the approach from above where every node gets evaluated for the corresponding player and it maximizes very time circumvents this worst-case approximation. So it’s recommended to use the second approach when you want to implement it for a game with more than two players.
When you implement this algorithm I recommend using recursion.
This concludes this post about Minimax. The described algorithm is a good base to implement further optimizations like Alpha-Beta-Pruning, Turnsorting etc. to optimize the exponential execution time. But those will be covered in a later Dev-Log.
For now: Signing off.
