Why AI is beating humans to our own games
For the longest time, humans have dominated games like Chess, Go (a very sophisticated game in East Asia) and the like because, they require some level of deep thinking and strategy. Well, it seems our reign has finally come to an end with the advent of Artificial Intelligence (AI). Just this year, Google’s AI called AlphaGo beat the world’s best player in Go 4-1. According to Google, “There are
1,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,000,
000,000,000,000,000,000,000,000,000,000,000,000,000
possible positions in this game — that’s more than the number of atoms in the universe, and more than a googol times larger than chess”. In the game of Chess, in 1997 IBM’s Deep Blue computer beat world’s leader Kasparov 3.5-2.5 and since then, we have seen more and more of such victories for AI. The question now is; how does an AI manage to beat the best of the best even though it is not human. The secret is quite simple: Graphs, Bread First Search and Game Theory.
Whenever an AI plays a game like chess, it considers the game as a graph where potential moves corresponds to the edges of the graph and each potential resulting game state is a node. Even as humans, we usually try to make our best move by anticipating the move of our opponent. Well, the AI does not do anything differently; only that it does this to a greater depth than where humans usually could get to.
Consider a game where a human plays against an AI. Let’s say the human makes the first move. Now, it is time for the AI to play. Assuming that there are 5 possible moves it could make: Move A,B,C,D or E. This is what the AI does:
First it considers all the five possible moves (edges of the graphs) and the potential game states (neighboring nodes) that would occur if any of those moves are made. This is a form of breadth first search. From each of those potential game states, it tries to anticipate what move you would make because it would then be your turn to play. The AI is able to guess your move because of game theory. You will definitely go for the move that would bring you the most returns hence it is able to predict your move. It would then repeat this process to a greater depth to which it has been programmed and then it makes the best move according what it has seen could happen in the future. With this, it is always many steps ahead of the human because it knows how the game would end if you make move A as compared to move B. This is the secret of AI beating humans to our own games.
Let’s look at a typical instance that most of us can relate to. Have you wondered why whenever you play a game against the computer and the level of difficulty is set to easy, you stand a better chance of winning than if it was set to hard. Well, the answer is quite simple. When you set the game to easy, the AI is only set to anticipate very few steps ahead (usually like just one step ahead). However, if it is set to hard, the AI program sets to a greater depth and so it becomes pretty hard to beat it because it can think so many steps ahead and make the best moves to guarantee a win. It is not 100% certain that AI would always win but for now, they are winning most games they play against humans provided their depth of search is high enough.
Sources:
https://en.wikipedia.org/wiki/Human–computer_chess_matches
Google: Defeating Go champion shows AI can ‘find solutions humans don’t see’
https://en.wikipedia.org/wiki/Minimax
http://www.cs.cornell.edu/home/kleinber/networks-book/networks-book-ch02.pdf