Genetic Algorithm
Recently the artificial intelligence from Google’s DeepMind shocked the world with the announcement of AlphaGo — the AI that beats a Go world champion. Even though the AI for chess has been exciting since 50s, why did it take over 5 decades to develop the AI for Go? The problem with Go is that it is less about logic but more about intuition. Each placement of the stone is reasoned by the experience and intuition of players, which makes it harder for computer algorithm to simulate. After several breakthrough in AI algorithm and technologies, Google’s DeepMind managed to develop AlphaGo and beat the current world champion of Go. Not only the AlphaGo, but DeepMind has been developing several intriguing projects. For example, they have created AI that learns how to play arcade game, and eventually formulates the method to win the game. Those breakthrough were mainly achieved by two algorithms: Deep Learning and Genetic Algorithm. Even though deep learning is an amazing field of study, in this article, we will focus on the genetic algorithm and how they can be applied to solve game theory.
As the name suggests, genetic algorithm is inspired by genetics. Similar to the human genetics, genetic algorithm will pass down some traits to the next generations. After thousands of generation, AI will learn the best combination of some traits and finally be able to find the best strategy. For example, in the realm of game AI, the input is some kind of graphic screen, and output will be the sequence of commands. These commands, strategies, will often return some quantifiable benefits to the player, such as higher score, better domination, and faster playtime (in racing games). This logic is very similar to that of evolutionarily stable strategy.
The genetic algorithm starts with 0 generation where all strategies are chosen randomly. Just like finding better strategies in game theory, we need several players to model this situation. They represents the first parents of genetic algorithm. After calculating the numeric benefits suggested in the previous paragraph, the algorithm will choose players with better results, and create next generation by selecting strategies that the better players have chosen, and keep passing the better “gene” to the next generation. After thousands of iteration, the AI is able to find the best strategy.
In real life examples, genetic algorithm involves many variables. In the class examples, we often consider “games” with 2 or 3 strategies; however, they often include 100 to 1000 strategies. Therefore, it is very difficult to find the best strategy in different circumstances. In this situation, genetic algorithm becomes very useful. It is built upon the idea that, if you keep choosing the strategy that generates better payoff, you will eventually end up with evolutionarily state equilibrium. What makes genetic algorithm very intriguing is that they usually show better result by allowing “mutation”, This means that at some low rate, the new generation will choose new strategy that they parents did not suggest.
Even though genetic algorithm is fairly old technique, with the increasing processor speed and the size of data sources, the application has achieved many breakthroughs in recent years. The golden age of AI is yet to come.
https://www.youtube.com/watch?v=qv6UVOQ0F44
http://www.iaeng.org/publication/WCE2007/WCE2007_pp61-64.pdf