Intelligent System FP – 08/01/2020 update

In last week, we already made a function that generates every possible moves including each move’s heuristic values for the AI, by the time this eight post published, we have finished the mini-max algorithm and improved the possibilities generator speed by using alpha-beta pruning.

Mini-Max algorithm

We made a function which implements the Mini-Max algorithm. Using the score that has been generated, the algorithm runs for every depth returns a heuristic value for leaf nodes (terminal nodes and nodes at the maximum search depth). Non leaf nodes inherit their value from a descendant leaf node. The heuristic value is a score measuring the score of the node for the maximizing player. Hence nodes resulting in a favorable outcome, such as a win, for the maximizing player have higher scores than nodes more favorable for the minimizing player.

The algorithm treats the players differently, in this case the AI will be the maximizer and its opponent will be the minimizer .

The heuristic value for terminal (game ending) leaf nodes are scores corresponding to win, loss, or draw, for the maximizing player. For non terminal leaf nodes at the maximum search depth, an evaluation function estimates a heuristic value for the node. The quality of this estimate and the search depth determine the quality and accuracy of the final mini-max result.

Alpha-Beta pruning algorithm

To improve the speed of the mini-max algorithm past depth of five, we implemented alpha-beta pruning. The algorithm maintains two values, alpha and beta, which represent the minimum score that the maximizing player is assured of and the maximum score that the minimizing player is assured of respectively. Initially, alpha is negative infinity and beta is positive infinity, i.e. both players start with their worst possible score. Whenever the maximum score that the minimizing player (i.e. the “beta” player) is assured of becomes less than the minimum score that the maximizing player (i.e., the “alpha” player) is assured of (i.e. beta < alpha), the maximizing player need not consider further descendants of this node, as they will never be reached in the actual play.