Can't read my
Can't read my
Noooo he can't reaaaad my
pooooker face
She is gonna let nobody
P p p poker face, p p p poker face
na na na na
Big love if you’ve read this with Cartman’s voice <3
Heeey Nikola, where have you been so long? I’ve read this with Cartman’s voice!
Then, big love for you bro<3
What’s uuup? Do you remember when we talked last time about AI and stealing the bike? Oh... I have... I have good news for you!
Oh, what kind of the news?
I gotta show you this... look at this, look... taaa daaaa.
Bro, is this your bicycle?
Yes, it’s not stolen!!!
I think that you don’t underst...
And look, I’ve tied it with four cables hahah, say how powerful developer I am!
You rock!
What are we going to learn today and why are you singing this Lady Gaga’s song?
Well... what do you think, could AI really read your poker face and beat you in the poker? Or maybe in chess, or checkers?
Hmmm let’s find out.
Maxpixel.net, Public domain CC0
Last time, we were talking about some uninformed search algorithms and I gave you small insight into how they work. Can we apply similar strategies to AI in order to learn it to play some games? And why would people spend time in a laboratory, trying to make some program which will play some board game? Aren’t we supposed to make AI which will do everyday stuff, talk with us, do some simple tasks, eventually conquer the world?
Games were always attractive to people from AI field, because they represent certain polygon where we can see how smart is our AI. Maybe some of you are familiar with the Game Theory which says that a game is actually one process of making decisions and basically, we can look on everything in our life like on a game, because we are supposed to always find out the best possible decision in every situation. So when our AI starts managing itself in some board game successfully, we could apply that maybe on some problems in the real world. Also, it’s easier to evaluate performance of the AI in a game environment, because it can either win or lose – it was successful or it wasn’t.
First game that computer was able to play, was the game of checkers. The man who developed that program was Arthur Samuel from IBM and that program was learning how to play checkers simply by playing against itself thousands of times. For just a few days, program succeeded to beat Samuel in this game and later in 1962 it won against the man who was “a blind checkers master”. If we consider that making this program was in 1950s and that technology at that moment was on a very low level comparing with today’s ( this program used magnetic tape as a memory!) we can say that this was one really big step in a computer science.
Checkers are nice, but there is one game that challenges and occupies people since its beginning – that’s right, chess. This game is interesting because it has so many tactics and possible moves that it represented the real challenge in the area of AI. You’ve probably heard about IBM’s famous computer called Deep Blue which won against Kasparov? Do you know how it did it?
Maxpixel.net, Public domain CC0
The truth is that it wasn’t quite fair battle, because Deep Blue wasn’t able to actually think like a man, it just had brutal force that was calculating every possible move in the game. That’s not quite intelligent behavior, but it did the job. In 1996, Deep Blue was able to calculate 50-100 million moves per second! With such power, It stepped on the battle field against Garry Kasparov and – lost.
Yes, such a powerful machine couldn’t beat such great chess player as Garry Kasparov. IBM then stepped up, improved the computer, simply by doubling the number of chips and improving a little bit software, so then it could calculate over 300 million of chess moves per second! The rematch was appointed and in 1997 it finally succeeded to won against Kasparov. Interesting thing is that, even then, it was tight – computer won in the deciding game when Kasparov made a mistake during the opening. Kasparov said that he felt something like “human intelligence” in some moves and demanded to see printouts of the machine’s log files but IBM refused. Later they published those files on the Internet. Kasparov also demanded a rematch, but IBM also refused. The results – Deep Blue will be remembered in the history and IBM’s stocks nicely jumped on the market at that moment.
Last year, one interesting thing happened – Google’s AI called AlphaGo won against world’s best Go player. What is Go and why is this significant?
Go is an ancient Chinese board game and it’s interesting because unlike the chess which is playing on the 8x8 table, Go has 19x19 table! Do you remember my story from the last time about trees, nodes and branches? Go, with such big table and its rules, has enormous branching factor – it has more possible states than there is atoms in the universe! That’s what I call a real challenge. Can we make such powerful computer that can calculate every possible move in this game? Ummmm... no. So how Google succeeded? Are they aliens? Illuminati?
Maybe they are, I don’t know (probably yes), but I know on which principle their AI works. They used one thing about which I was writing two weeks ago – neural networks.
AlphaGo has 48 layers of neurons that search patterns on the table during the game and try to conclude what could be the best move.
Now when Go is conquered, we can say that AI can certainly beat man in every board game.
Oh this is so exciting, I’ll make my own AI that can play games! Yeah... I will... I will go in Vegas and become like Robert De Niro in Casino! Or... or like Joe Pesci hahah he’s so funny man...
Or I can be like Godfather! Yeahhh, that’s the real talk... how can I do that, Nikola please tell me, pleaaaase?
I’m gonna make you an algorithm you can’t refuse.
What exactly AI does while it’s playing a game?
First, we have to define a game as a searching process which is actually competitive. We have two agents who want to lower chances of each other for win. If one agent wins, then other agent must lose.
Now, on your way to become Robert De Niro, you have to get familiar with one term which is called - heuristic.
Heuristic is one very important thing and it is actually a function which works as an additional information that you use in your search strategy to have better results. For example, cost function from the last time when you had to travel from Belgrade to Kruševac could work as a heuristic or if you are trying to solve Rubik’s cube, heuristic can be the number of squares that aren’t on the right place for each color and so on.
It helps you as a parameter which you follow during the search to know how successful you are and what decision you should do next. It’s really, really crucial to choose the best and the most representative heuristic for your problem. How can you know what is the best? Well, that’s the catch – no one will tell you that, it’s something that you have to conclude on your own.
There are few ways to generate good heuristic – first, you can simplify your problem or to break it on more sub-problems and try your assumption experimentally. If it works – good, you can try your heuristic now on the real problem. Second way is learning from experience – you can solve many, many problems that are similar to yours and then you will intuitively know what to choose for your heuristic. At the end, it’s possible to combine more heuristics into one in order to get better results.
Using that logic about heuristics, we can use something called value function. For example, in chess, we can say that pawn has value 1, knight and bishop 3, rook 5 and so on. Also we can make value of the positions of the figures and then we can simply make sum of all of those values and then we have the information how valuable is one state in the chess. Based on that, an algorithm could choose between possible states in order to know what to play next!
But Nikola, how does that algorithm work?
Minimax algorithm
Imagine that we have two agents which are playing against each other and one of them is called MIN and other one is MAX.
Lol, hello my name is MIN hahah it’s so stupid name...
No it’s not. Take a look at this tree on the picture below:
Self-made picture
MAX is called MAX because it tries to find the state with the highest value and analog to that MIN tries to find the state with the lowest value. Take a look at these nodes – let’s say that the nodes which are represented with triangle turned up are the states where MAX chooses its next move and the nodes which are turned down are states where MIN chooses its next move.
According to that, MAX will choose to go from A to B (because 3>2) and then MIN will choose to go to E, because it’s the best possible answer at that moment.
And that’s how this algorithm works.
How did it calculate the values of the nodes?
If you look more carefully, you can see that algorithm first developed whole tree and went to the deepest nodes and there calculated the value of those states. Then, depending on which agent should go there (MIN or MAX) it picked appropriate values and copied it in the parent node. You can see that it’s supposed for MIN to go to E, F or G, so it chose minimal value which is 3 and assigned that to node B. Same logic is used for C, D and for A.
Interesting thing is that this algorithm needs to develop whole tree in order to go to the deepest nodes and calculate values, so the time needs for this algorithm are exponential O(b^m) and you are maybe remembering what I said in my previous part about exponential needs – it’s s c a r y.
So, can we improve somehow this algorithm?
The answer is yes – we can use its improved version called Alpha-beta pruning.
Alpha – Beta pruning
The trick is that we can conclude in which nodes MIN or MAX can’t go and simply to prune that part of the tree. We are pruning the parts which just can’t affect our future decision. Look at the example below:
Self-made picture
Let’s say that MAX is in the A and it choses where to go, to B or C. First it developed B and as we can see, by the logic which I described above, it will assign value 3 to the node B. Now, when it starts exploring C, it first sees that H has value 2, so pay your attention right now – two is the biggest value that can be assigned to C (remember, we are taking minimal value from deepest nodes here) so we don’t need to explore further successors of the C node because we saw already that B has already value 3, so MAX will never go to C and we can prune now its successors and save our memory and time.
I hope that I was clear.
And that’s how the Alpha-Beta pruning works.
I gave you a small insight in how those algorithms work in the world of board games and, of course, there are much more strategies and modifications. Right now, AI succeeded to accomplish pretty much everything in this area, so it’s interesting to see what could happen next, in the future. What a time to be alive, literally.
Gambling is the next industry that could be heavily affected by the AI development and right now there are bots that could probably beat you in poker and take your money, house, car...wife.
Just joking, she will probably go by herself.
For the end I will just quote Omar Little, from the best tv show ever made:
It’s all in the game, yo! All in the game...
I hope that you enjoyed,
Many thanks to my tireless mentor @scienceangel who's always here to help me with my ideas.
Sources:
Artificial Intelligence: A Modern Approach, Peter Norvig and Stuart Russell
Artificial Intelligence: The Very Idea, John Haugeland
Sci-Show
Kasparov vs. Deep Blue