grandmaster level chess AI using python - Part 3 - Some additional thoughts
Architecture of a Chess AI
(note: the writing below is mostly stream of consciousness and hasn't been revised yet)
A pretty typical architecture for a game playing AI consists of two components, a heuristic algorithm and tree search. The heuristic algorithm is basically the equivalent of human intuition. Intuition is something that is learned from experience. As we experience more of the world around us, we become wiser and learn to make quick and accurate judgment calls just from a few quick glances. For example, a seasoned car mechanic can quickly diagnose whats wrong with a car after having inspected it for a few minutes. A seasoned VC investor can quickly identify good startups to invest in just by having a brief conversation with the founders. If they have decades of experience, then they can quickly make these judgment calls although they may seem biased from an outsiders perspective.
The tree search aspect of a game playing AI is the logical component. "If I move here, then my opponent could move here, which would be bad, therefore I should move here instead, etc etc." Computers are extremely good at logical thinking because they have immense processing power. CPU's these days are extremely fast and typical off the shelf processors can easily calculate millions of possible chess moves per second. Humans, on the other hand, can only calculate only average one move every few seconds. Even top chess Grandmasters such as Garry Kasparov are not much faster than the average human at doing this.
These days, humans are no match for the top chess engines. Even chess engines running on personal laptops with a small fraction of the power of Deep Blue can beat the top Grandmasters. Why is this the case? The reason is because the software has gotten much better. More specifically, the heuristic algorithm that is used to evaluate position has gotten exponentially better. With the power of machine learning, you can train a model to evaluate the quality of a chess position. Doing this is essentially creating the human equivalent of "intuition." Gary Kasparov has said that for most moves, he only looks one move into the future. Yet he is able to defeat a super computer which can calculate 200 million chess positions per second. Chess Grandmasters have said that they are able to "feel" the best moves. This ability to do this is developed over a lifetime. Most Grandmasters have been training at chess since a very young age. From the time they first started playing, they have probably played ten of thousands of games and spend hundreds of thousands of hours studying the game.
a picture of World Champion Garry Kasparov losing to Deep Blue
An artificial neural network can also be trained to play chess (and many other board games for that matter). You can imagine that the training data for this neural network to be chess positions from historically played games (and for the best results from games played by skilled players such as Grandmasters). The thing that we are try to predict is binary, the outcome of the game, whether it is a win (1) or a loss (0). Now, if you were to train an extremely complex multi-layered neural network consisting of billions and billions of neurons on millions of chess positions, it could potentially learn to evaluate positions at the level of a Grandmaster (or possibly even better).
A chess AI that has a uses a neural network would be extremely powerful. However, this is only one of the pieces that you will need if you want to create a strong game playing AI. Intuition isn't always right. You have heard of the phrase "don't judge a book by its cover." People tend to do this a lot, and although it sounds bad its not necessarily a bad thing. We have rely on our "intuition" or in other term our unconscious mind quite a bit or else we wouldn't be able to function. Imagine being unable to learn from experience and having to calculate and recalculate everything over again over again every time you experience it in order to determine the best course of action.
If this were the case, people would be unable to get good at games like chess. We would be unable to learn from playing games and have to logically calculate out every single move every time we play. We wouldn't be able to learn heuristics such as "pawn islands are bad", "developed knights are good", or "a castled king is a safe king and therefore good." We would only see the board in the literal sense and all the possible moves would need to be calculated via brute force. In real life, we wouldn't be able to recognize dangerous situations, such as a dark alleyway or a ghetto neighborhood, because we don't have the experiences to guide our judgment.
These days well trained CNN's are extremely effective at recognizing images, and sometimes even better than humans. CNN's essentially reduce something of high dimensionality (such as all the pixels of an image) to low dimensionality (such as a binary output: 1 cat or 0 not a cat) while extracting signal from noise.
This is essentially the general idea behind how a chess algorithm will be trained. A chess position (i.e a chess board with pieces on it) can be treated as an 8x8 pixel image with different colors representing the different chess pieces. We have something of high dimensionality, such as a chess position, and reduce it down to something of low dimensionality (i.e the probability of winning given this chess position).
Once we have this chess algorithm, we will combine it with tree search to create an extremely powerful AI. A well trained chess algorithm will be able to significantly reduce the search space of the tree. Instead of having to sift through all 20-30 possible moves at each step, we can narrow it down to just two or three because we have the power of intuition at our side. This allows for the chess AI to compute much more efficiently and become exponentially stronger as result.
A visualization of convolutional network architecture. Convolutional neural networks (CNN's) are a specialized class of neural networks that are specifically architected for doing image recognition. A CNN is a multilayered algorithm that extracts useful signal from noise by combining, destroying, and transforming data through a specific pattern of parameter reuse involving convolutional layers, pooling layers, activation layers, and fully collected layers.
Although we are still in the relative early stages of AI's development, we have already seen amazing developments.
Just recently (2016), Google DeepMind's Alpha Go was able to defeat one of the best Go players of all time, Lee Se-Dol. Go was once thought to be a game inconquerable by computers. Top Go players took great pride in their craft in part because they believed that only human could master something as complex as Go. Go is thought to be "an analogy of life", a game that "mirrored ones own personality", a game that required "strategy", "feeling", and "abstract thinking" For these reasons, most Go players believed Go was a game that computers could never master, but they were proven wrong. With today's computing power combined with biologically inspired neural networks, computers have mastered something previously thought impossible.
At this rate, I can only imagine the exciting advancements in the AI space: self driving cars, augmented intelligence, human-computer interfaces, the list goes on! The most terrifying yet exciting possibility is that of a superintelligence. Today's AI is only capable of very narrow tasks, such as playing board games, doing image recognition, text recognition, although. An artificial general intelligence (AGI) would be capable of a broad range of tasks and would be extremely good at it. As soon as we hit a point where an intelligence is relatively close in ability to that of a humans, it will quickly surpass it.
It is easy to see why this is so. We have seen that in simple games such as Chess and Go, a computer's ability quickly surpasses that of the top grandmaster as soon as it starts to develop a relatively weak intuition about the game. This is because computers also have extremely large computational power compared to biological creatures. (Although this may change with the development of augmented intelligence).
No conclusion...the post is done
(note: the writing below is mostly stream of consciousness and hasn't been revised yet)
A pretty typical architecture for a game playing AI consists of two components, a heuristic algorithm and tree search. The heuristic algorithm is basically the equivalent of human intuition. Intuition is something that is learned from experience. As we experience more of the world around us, we become wiser and learn to make quick and accurate judgment calls just from a few quick glances. For example, a seasoned car mechanic can quickly diagnose whats wrong with a car after having inspected it for a few minutes. A seasoned VC investor can quickly identify good startups to invest in just by having a brief conversation with the founders. If they have decades of experience, then they can quickly make these judgment calls although they may seem biased from an outsiders perspective.
The tree search aspect of a game playing AI is the logical component. "If I move here, then my opponent could move here, which would be bad, therefore I should move here instead, etc etc." Computers are extremely good at logical thinking because they have immense processing power. CPU's these days are extremely fast and typical off the shelf processors can easily calculate millions of possible chess moves per second. Humans, on the other hand, can only calculate only average one move every few seconds. Even top chess Grandmasters such as Garry Kasparov are not much faster than the average human at doing this.
These days, humans are no match for the top chess engines. Even chess engines running on personal laptops with a small fraction of the power of Deep Blue can beat the top Grandmasters. Why is this the case? The reason is because the software has gotten much better. More specifically, the heuristic algorithm that is used to evaluate position has gotten exponentially better. With the power of machine learning, you can train a model to evaluate the quality of a chess position. Doing this is essentially creating the human equivalent of "intuition." Gary Kasparov has said that for most moves, he only looks one move into the future. Yet he is able to defeat a super computer which can calculate 200 million chess positions per second. Chess Grandmasters have said that they are able to "feel" the best moves. This ability to do this is developed over a lifetime. Most Grandmasters have been training at chess since a very young age. From the time they first started playing, they have probably played ten of thousands of games and spend hundreds of thousands of hours studying the game.
a picture of World Champion Garry Kasparov losing to Deep Blue
An artificial neural network can also be trained to play chess (and many other board games for that matter). You can imagine that the training data for this neural network to be chess positions from historically played games (and for the best results from games played by skilled players such as Grandmasters). The thing that we are try to predict is binary, the outcome of the game, whether it is a win (1) or a loss (0). Now, if you were to train an extremely complex multi-layered neural network consisting of billions and billions of neurons on millions of chess positions, it could potentially learn to evaluate positions at the level of a Grandmaster (or possibly even better).
A chess AI that has a uses a neural network would be extremely powerful. However, this is only one of the pieces that you will need if you want to create a strong game playing AI. Intuition isn't always right. You have heard of the phrase "don't judge a book by its cover." People tend to do this a lot, and although it sounds bad its not necessarily a bad thing. We have rely on our "intuition" or in other term our unconscious mind quite a bit or else we wouldn't be able to function. Imagine being unable to learn from experience and having to calculate and recalculate everything over again over again every time you experience it in order to determine the best course of action.
If this were the case, people would be unable to get good at games like chess. We would be unable to learn from playing games and have to logically calculate out every single move every time we play. We wouldn't be able to learn heuristics such as "pawn islands are bad", "developed knights are good", or "a castled king is a safe king and therefore good." We would only see the board in the literal sense and all the possible moves would need to be calculated via brute force. In real life, we wouldn't be able to recognize dangerous situations, such as a dark alleyway or a ghetto neighborhood, because we don't have the experiences to guide our judgment.
Training a convolutional neural net to create the equivalent of human intuition:
For my chess AI, I plan to train a convolutional neural network on database of millions of chess games against the outcome of the game. Convolutional neural networks (CNN's) are a specialized class of neural networks that are specifically architected for doing image recognition. CNN architecture was discovered by Yann LeCunn, one of the pioneers of artificial intelligence. It is a multilayered algorithm that extracts useful signal from noise by combining, destroying, and transforming data through a specific pattern of parameter reuse involving convolutional layers, pooling layers, activation layers, and fully collected layers. (It is a fairly complex topic that I won't go into detail here but there are plenty of resources online.)These days well trained CNN's are extremely effective at recognizing images, and sometimes even better than humans. CNN's essentially reduce something of high dimensionality (such as all the pixels of an image) to low dimensionality (such as a binary output: 1 cat or 0 not a cat) while extracting signal from noise.
This is essentially the general idea behind how a chess algorithm will be trained. A chess position (i.e a chess board with pieces on it) can be treated as an 8x8 pixel image with different colors representing the different chess pieces. We have something of high dimensionality, such as a chess position, and reduce it down to something of low dimensionality (i.e the probability of winning given this chess position).
Once we have this chess algorithm, we will combine it with tree search to create an extremely powerful AI. A well trained chess algorithm will be able to significantly reduce the search space of the tree. Instead of having to sift through all 20-30 possible moves at each step, we can narrow it down to just two or three because we have the power of intuition at our side. This allows for the chess AI to compute much more efficiently and become exponentially stronger as result.
A visualization of convolutional network architecture. Convolutional neural networks (CNN's) are a specialized class of neural networks that are specifically architected for doing image recognition. A CNN is a multilayered algorithm that extracts useful signal from noise by combining, destroying, and transforming data through a specific pattern of parameter reuse involving convolutional layers, pooling layers, activation layers, and fully collected layers.
Although we are still in the relative early stages of AI's development, we have already seen amazing developments.
Just recently (2016), Google DeepMind's Alpha Go was able to defeat one of the best Go players of all time, Lee Se-Dol. Go was once thought to be a game inconquerable by computers. Top Go players took great pride in their craft in part because they believed that only human could master something as complex as Go. Go is thought to be "an analogy of life", a game that "mirrored ones own personality", a game that required "strategy", "feeling", and "abstract thinking" For these reasons, most Go players believed Go was a game that computers could never master, but they were proven wrong. With today's computing power combined with biologically inspired neural networks, computers have mastered something previously thought impossible.
At this rate, I can only imagine the exciting advancements in the AI space: self driving cars, augmented intelligence, human-computer interfaces, the list goes on! The most terrifying yet exciting possibility is that of a superintelligence. Today's AI is only capable of very narrow tasks, such as playing board games, doing image recognition, text recognition, although. An artificial general intelligence (AGI) would be capable of a broad range of tasks and would be extremely good at it. As soon as we hit a point where an intelligence is relatively close in ability to that of a humans, it will quickly surpass it.
It is easy to see why this is so. We have seen that in simple games such as Chess and Go, a computer's ability quickly surpasses that of the top grandmaster as soon as it starts to develop a relatively weak intuition about the game. This is because computers also have extremely large computational power compared to biological creatures. (Although this may change with the development of augmented intelligence).
No conclusion...the post is done
Comments
Post a Comment