Do you know how IBM's Deep Blue chess computer controversially beat champion, Gary Kasparov in 1997? It's a search algorithm called min-max. This article describes how it works at a high-level.
Adversarial search is characterized by opposition or conflict. These problems require us to anticipate, understand, and counteract the actions of an opponent in pursuit of a goal. In chess, we must react to the moves made by an opponent while carrying out your own strategy.
Examples of adversarial problems include two-player turn-based games such as Tic-Tac-Toe and Connect Four. Players take turns for the opportunity to change the state of the environment of the game to their favour.
A set of rules dictates how the environment may be changed and what the winning and end states are. The min-max algorithm uses a heuristic score to make decisions. This score is defined by a crafted heuristic and is not learned by the algorithm.
Assume that we have a heuristic that provides a score in which positive numbers are better than negative numbers. More about heuristics here: https://rhurbans.com/using-heuristics-for-intelligence/
By simulating every possible valid move, the min-max search algorithm tries to minimize making moves where the opponent will have an advantage or a winning state and maximize making moves that give the computer agent an advantage or a winning state.
Deep Blue also consisted of a database with known effective opening moves and end-game scenarios. This required human intervention to be created and tweaked. Since, there have been huge developments that allow algorithms to learn how to master a game with no human intervention.
If you'd like more details about this algorithm, see Grokking Artificial Intelligence Algorithms with Manning Books: http://bit.ly/gaia-book, consider following me - @RishalHurbans, or join my mailing list for infrequent knowledge drops in your inbox: https://rhurbans.com/subscribe.
Latest comments (0)