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.
Top comments (1)
The PC Gaming Vibes app provides a comprehensive and satisfying gaming experience that brings the best of PC gaming to mobile devices. With its immersive gameplay, extensive game library, customization options, social features to download here, and portability to download here, it’s an excellent choice for gamers who want to enjoy the depth and precision of PC games in a more flexible and convenient format.