Beating Go thanks to the power of randomness
CC Attribution 3.0 Unported:
You are free to use, adapt and copy, distribute and transmit the work or content in adapted or unchanged form for any legal purpose as long as the work is attributed to the author in the manner specified by the author or licensor.
Pfeiffer, Tobias
Go is a board game that is more than 2,500 years old (yes, this is not about the programming language!) and it is fascinating from multiple viewpoints. For instance, go bots still can’t beat professional players, unlike in chess. This talk will show you what is so special about Go that computers still can’t beat humans. We will take a look at the most popular underlying algorithm and show you how the Monte Carlo method, basically random simulation, plays a vital role in conquering Go's complexity and creating the strong Go bots of today.
 Music Yeah, thanks everyone for showing up. So, oh god no. Here is 1997, the computer of IBM Deep Blue beats Gary Kasparov on the tournament conditions in I think a six or seven game series. This is the first time ever that a computer has won against the premier human player and Gary Kasparov is considered to be one of the best players of all time in chess. At around the same time, computer girl we had the tournament from 1985 to 2000 which was called the World Cup with a total price of a million dollars. If someone would be able to beat 10 to 14 year old Chinese children that were Go Prodigies in an even game, so it was not for the lack of trying. But in the same year, 1997, there was this tournament and the winner of the tournament placed against these Chinese so called Insays. And the program won, but by a huge handicap for those of you that know Go, I think 11 handicapped stones which is pretty much the difference of a very immature player and maybe an intermediate player, so to say. So let's dig a bit more into the current history, in the more recent history of computer Go and also in why is Go so hard to master as compared to chess. Why are we so much behind? Okay, years 2001, an anime by the name of Ikaruna Go is launched in Japan, revitalizing Go and making it more popular among the youth. It has been going downhill in Japan for some time before that, but overall it's very popular in Eastern Asia, so there are professional players that get paid to play. You can watch it on TV and everything. And in 2009, Google invented a language called Go saying, oh, there's a game that's like what, 4,300 years old, we're just going to name Steamroad right over that old board game. And of course, there's also another programming language by the name of Go and they're also just Steamroad right over that because what the hell with Google we can do whatever we want. Year 2014 on the right is Rimi Kulon, he's the programmer of a program called Crazy Stone and it's one of the two strongest programs that we have in Go. And he plays against a professional that's called Yoda, he's a ninth down professional player and Crazy Stone won with a handicap of four stones, which is a lot less than the other handicapper that's still a real big difference in playing strength. 31st of October 2015 in the Code Century Go challenge between the program Zen, which is one of the two most strongest programs played in an even game against one of the strongest amateur of the world, Franz Josef Dikut, a German 5-dan player. The German, the human prevails in a five game in a best of five series, three to one, this is the last move played in that series. 3rd November 2015 Facebook publishes a blog post that's like oh we're doing all this cool machine learning stuff and by the way we wrote a Go engine, it's awesome and we don't really tell you what we're doing exactly but pattern recognition and their CTO did not answer my Facebook message about what they're really doing, quite to my surprise. But we're going to get a bit into that and how strong that engine really is for all that we know. 13th November 2015, this site hits second use, it says play Go against a deep neural network, we will also have a look at what's up with that, what's the science behind this. We're going to look at a lot of stuff that is in scientific papers but don't be afraid, it's all cool. If you don't know Go, all cool, we're going to go over the basics of Go shortly. So this talk is beating Go things to power of randomness. Hi, I'm Toby, you can find me on Twitter, GitHub and everywhere else as Praktop. I'm out of Berlin all the way here, I organized a group in Berlin, the React user group in Berlin. I'm a Red Scouts coach, I do open source, I do shoes, who knows shoes, like that's amazing stuff. I work at a great company called Bicro, which is an agency, so we help startups build things, lots of fun to work there. Right now we're actually hiring, so if you want to relocate to Berlin, one of the best cities, just saying, and they paid for me to go here, so pretty great. Some of you might be concerned about my t-shirt because it's like, oh God, would Yoda allow him to wear the t-shirt of Yoda? Is that physically okay for him? I can tell you, you know, this is saying that Superman wears like a Czech Novelist t-shirt, so Yoda obviously wears a Toby t-shirt. So we're buddies, you know, we made that out, so everything cool there. So continuing with the basics of Go, Go is played on a board with lines in the sections and the normal size is a 19 by 19 board. Then we also have 13 by 13 and 9 by 9. Normal professional games are played on the 19 by 19 board, but the 9 by 9 board is also still relevant and interesting. So how does Go, Go? We start playing Move, Black starts and we play on an intersection, so there is now a Black move, then White moves, Black, White, and whoa, too far, sorry. That's the basic thing. So taking further from that, a stone has so-called liberties. Those are the adjacent cutting points that are empty, so this stone has four liberties. If I play another stone, they form a group together and they have six liberties. When White plays next to the Black stone, both of these stones have three liberties because they take one liberty away from each other. So if White continues to play, now I have two liberties and in the end, three liberties. Now we're in a state which is called Atari. Atari's company name was really chosen by that name of that Go term. Go term and that term means before capture, sort of. So if White plays another move, that removes the last liberty from the Black stone, and that means the Black stone is captured and taken off the board and counts as a point for White. Of course, Black isn't stupid, Black knows how to play and can stretch out, so now Black has three liberties again and it's all good. So I told you right now that there is a point which White gains from the capture. So how do you win in the game of Go? The game of Go is basically about getting more territory than your opponent. You try to encircle territory and claim it for yourself and then territory is then one point of these intersections, and then in the end it is counted who made more territory. So it's basically a game of dividing. I try to get more of the cake than my enemy does. So in this example, we would have encircled one point so that would be one point for Black. If we go further, White could now encircle Black, and now Black is at one liberty, so we know what's probably going to happen. White can capture thereby making eight captures, so eight points. And of course, this now also counts as White territory, so it's going to be eight points of territory, so 16 points made here and total, which is pretty much a lot on a nine-by-nine board. But is it an endless game of capture and recapture? No, because there's also something in the state that a group is alive. So we say, and this is a typical group that is alive, it has two eyes, which means we have two points of territory here, and White can simultaneously occupy both of those liberties, because if White would play in there, it would be immediately recaptured, the so-called suicide move, which is forbidden under Japanese rules, but not under Chinese rules. So this group cannot be captured, and in the end, all of them are alive. So what does a game look like in the end? This is the end position of a game played between a professional player and one of the strongest go-in. I think it was then, but I'm not quite sure. And so how do we count that? Well, we remove the so-called dead stones that have no chance to live and then count the territory. And this game was drawn, and if you see now, it doesn't look like a draw. Black has way more points. Why was the game a draw? Well, there's a concept called komi, which is a set of bonus points that White gets because Black makes the first move. And so this game was a draw. So what does a real game look like on the 19 by 19 board? This is the first game between Francois de Sticut and Zen this year. And you usually start to occupy the corners first, and we can't go through the full game, so I'll fast forward. And so we can sort of see how the game starts forming here. Like Black claims sort of the lower right corner and the upper right corner. And there's also something very, like for me, interesting going on that you cannot see the immediate value of in the lower left corner. Black starts a bit like sort of a wall that faces upwards, and that is called influence. It is a very difficult, even for really good players to see like who is ahead here and who is not. And if you see the game commentary, there's lots of discussion about like who is in a better position at this place. So you can imagine how difficult it must be for a computer to assess the current situation. The game moves on, we see more moves played and even more moves played. And at this point I want to focus your attention to the lower right corner. And this looks at the first look, if you don't know, it looks like OK, Black and White are battling it out out there. Unfortunately that is not at all the case. That Black group is practically that, it is still on the board, but it only has two liberties left, right down there. And so it can be captured at any moment. A go engine that would have to play and understand this would have to understand that this is not actually a not played out position, but those stones are actually lost. If you fast forward to the end of the game, we can see that eventually White did capture that Black group. And there are lots more, many, much more complicated positions on the board that I would not be able to assess because those programs and the player played a much higher level than I do. OK, so now we count this game and this game was the only game that Zen won and that was by a margin of one and a half points. So when we talk about Go versus chess, what's the difference? In Go you start building something, you start with an empty board and you build. The stones don't move, they might get captured, but you can't move them, you don't flip them. You build something, you have to plan strategically ahead like where do I want to be, where do I want to stand in my game. In chess you go out and destroy, basically. Your goal is to destroy the other king and so you get less and less of what you really have. When I first looked into this, which was in 2010, also an interesting concept came up, the concept of the difference between what is complex and what is complicated. Go is very simple and it's hard. There is a set of formalized rules that are just ten rules that basically define the game of Go and I've taught you almost all of them by now. Go is very complex because there are many possibilities where it can play which results into many things that could happen which makes Go very complex. On the other hand, chess is more complicated and complex. Chess has many rules. Which piece can move where, like there's the rojada and the first move, like the pawns can move too. So it's much more complicated of a game and some of its complexity stands from it being so complicated. So this is a code by Edward Lesker who was a chess grandmaster and he discovered Go a bit later in his life and he said, while the baroque rules of chess could only have been created by humans, the rules of Go are so elegant, organic and rigorously logical that if intelligent life forms exist elsewhere in the universe, they almost certainly play Go. So when we want to talk about how strong programs are, I'm going to quickly introduce you to the ranking system used in Go. You can see at the beginning when you're at 30Q which is basically you learn the rules and you play the first game. So that's 30 to 20Q. A casual player you can become after maybe a couple of months of play of a really hardcore, then maybe in the first week or so, then you're between 19Q and 10Q. The intermediate amateur is from 9Q to 1Q and it's really different what people say. Like if you look at a Go wiki, they say, oh, you can reach it in a month. I don't think so. If you look at computer Go papers, they mostly say, oh, well, it takes an amateur player years to reach that level, but I think they just say that to make their programs look stronger when they reach the Q level. And then there's also the advanced amateur and the professional. Now for quick show of hands, who has already played Go? Who at least reached the beginner state? Okay. At least reached casual player, intermediate amateur. Okay. Advanced amateur. Oh, God, there are people here that are much better than me. I didn't play actively that much anymore, but I was around in 8Q, so a weak intermediate amateur and took me about one and a half years to go there despite playing tournaments and online and everything. So you might talk to me while I said wrong about some of the positions later on. That would be nice. Thank you. Why am I showing you this? It also gives you a hint of what the worth of those handicapped stones is, because in the amateur level it is considered the difference of one handicap stone between the ranks. So when a 9Q plays against a 5Q, the 9Q gets a handicap of four stones, which then looks like this. The stones are already placed, so black essentially gets four free moves. So this is the handicap at which Crazy Stone won in 2014. This is the handicap of 9 stones, that is like the highest handicap that you give in official games at tournaments, as far as I know. And this is the handicap at which one of the strongest go-programs lost in 1998 to the strongest, to the Chinese, and say the 10 to 15 year old children. This is a handicap of 3D and stones, I played once at that handicap at the Blitz team tournament. We were around 10Q and we played against the team of Dan players, and this handicap is just unfair. So we bet the Dan level players, although making very, very bad mistakes. And we were the only team to beat the team of Dan players. They went on to win the tournament. So that shows you how unfair that handicap is. This is a handicap of 29 stones, which is just, I don't know, if you just pick up Go and played on the 19 times, 19 board against me, you would most certainly win, most certainly. In 1998, a German 5 Dan player bet the strongest go-program at that handicap, and that was one year after Kasparov was defeated. So that's just meant to show you how far the programs were behind. So why is Go so hard? What makes it that much more complicated and difficult than chess? So at first, we have a much, much larger board. Our board is 19 by 19 as opposed to just 8 by 8 for chess. Then almost every move is legal. Like I said, I told you almost all the moves are left out of the co-rule, but basically you have to move inside the field, you can't move at a place where somebody else already is, and then you can't play co-moves and not the so-called suicide moves, and that's it. So that leads to a very high average branching factor. What is an average branching factor? It's basically the average number of moves that are legal at any point in the game. So for Go, we have 250 and chess just 45. We also have a very high state-space complexity. State-space complexity is the number of valid board positions that exist, and I think some mathematicians calculated those. So for Go, it's 2 to the power of 171, and chess 10 to the power of 171, and for chess it's 10 to the power of 47. So those are huge numbers. What does that even mean? The number of atoms in the observable universe is estimated to be around 10 to the power of 80, which sort of means that we could take each of these atoms and make a combination with also all of the other atoms and have that as a combination list, which would turn out to be 10 to the power of 160 possible combinations, if my math doesn't fail me, and that would still be less than the number of valid Go positions. So at this point you might get a sense of the scale, how big that problem is. And also moves have a very global impact. You can't just go like, okay, I'm just going to play locally here where my enemy played last. That doesn't work due to multiple reasons. One is oftentimes it is the best move not to answer the move of your opponent just placed somewhere else because the move somewhere else is much, much bigger. And the other thing is that a move that I played down here in the bottom right can have severe influences on a position to the top left. It might break things there and actually defeat, decide the state of a group. So let's finally, after we've gotten our intro to Go and why it is so hard, let's talk about artificial intelligence for a second here. This is an image from Wikipedia of the alphabet of pruning or alphabet of search, which is one of the, which is the algorithm basically to play chess, like deep blue use it, and I think modern chess programs still use it. It's a depth first search in that graph where you go to leave and then you have to evaluate the state of the board at that point in time because you can't play all the way to the end because even for chess there would be way too much to do. And then you always assume perfect play, which means that's the min-max part. And the first move, that's our move, we try to maximize the value of the evaluation function to say like, okay, we want to have the best position for us. But that's the first step. And afterwards it's the minimize because it's our opponent's move. And of course our opponent is clever and we try to minimize the overall value of the evaluation function because your opponent wants to make a good move and then we maximize and so on. So what's the problem here? As I tried to show you before, it is very hard to write an evaluation function for the game of Go. If you remember this position, for instance, it's not very clear where territory will be of room in the end and how much it will be and there are other concepts involved like mojo and influence. It's like, okay, black has very much influence there, but white has more territory. That is something that you commonly hear in game commentary and it's not easy to decide what is worth more and especially not for computers. So far we have been unable to find a good evaluation function. There's one Go program called GNU Go that uses alpha-batter search, alpha-batter pruning, but it plays around the level of 5Q, 5.4Q, and current strong Go programs play about a strange of a 5-dan or 6-dan amateur player. So we came up with this great thing which is called the Monte Carlo method. So to tell you what the Monte Carlo method is, I want to ask you a question first. What is pi? What is the value of pi? 3.14 something, cool. So how do you know that? How do you determine the value of pi? Come on, people. No one? No. So it's some sort of circumference, blah, blah, blah, math things. There is another way to do this. You can draw a, I think it's called Union Square on a piece of paper and do a circle in it and then you throw random pins at it and then you count how many pins land inside the circle, how many land outside of the circle, multiply that relation by 4, and then you get an estimation of pi, which is an example of the Monte Carlo method applied and you can see it here. And right at the top, I think it's cut off, but you can see with the number of simulations, with the number of more random dots that we throw in there, our estimation of pi gets better and better. So this is the Monte Carlo method. Pi is not its best use case, but it's usually used in spaces where it's very hard to do a full simulation of something, so we just do a random simulation and in the end, we just assess what is the outcome and by running multiple random simulations and then assessing the outcome, we can get an estimate or a guess of what the final value is and in go that is basically our evaluation function. So this, like the Monte Carlo method was proposed before in 1993 in a paper, but it was not made to work. It was not until the year of 2006 until the Monte Carlo tree search was developed and successfully applied to go or was actually developed before go and at that year, the program that implemented Monte Carlo tree search also won the go tournament. So ever since, all go programs that are successful use Monte Carlo tree searches. So that was sort of a revolution and it's been rather recent. So Monte Carlo tree search has been around since 1957 or something. So this is the basics of the Monte Carlo tree search. We go through a selection phase first to select the number we want to play at, then we do an expansion, then we do a random simulation and afterwards we do a back propagation of our results. So what does it look like in detail? In this graph, we say each node has at first like the wins that have been at that node and then last the visits, how many times have I visited that node and the nodes represent a board state and then afterwards it's like we play a move and then the next node is like the board state that results when we play that move. So at first we go to the selection phase, we select the node we want to play it, we want to say, okay, we want to see here what happens here, we've got one again, more information here. So we do an expansion that says like, okay, this is the move we're going to try here at that specific node, then we're going to do a random play out and you might be right now, you might be like, okay, what random play out, what are we doing? It seems like not very smart to do a random play out. But the hypothesis is this, if I'm standing better at the board in general, if I have a better position, if I do a random play out and I win in the end, I'm more likely to win in the end if my position was better. And if we do that lots and lots of times, we get a pretty clear view of is our position ultimately better or worse. So in the end we do a back propagation that says, okay, we have one here, so we propagate that result back to the top. And here you've got to be careful a bit if you remember the min max. So it's also a matter of perspective. Remember the sort of darkish thing is like the black move and down here it's the white move and of course we can do a back propagation that when white has won, then of course black has not won, black has lost. And so you either have to take that into account during selection or how my go-board does it and how I know other go-boards do it is you always alternate how you report the results. You say, okay, white won, then black lost, white won, black lost, white won, black lost. And so you always alternate the result that you report so that the selection is sort of uniform. So let's talk about a bit about the selection because it's a crucial part. So we could just take like every move all the time and play each move equally all of the time, but that's not very smart. And since we're already doing like the random play out stuff, we at least want to be smart about the selection, you know. And this is a so-called multi-arm bandit problem, which is one of the most interesting problems I've come across there. And it's that scenario you're sitting at a casino and you're playing at those bandits and you're playing at your machine and it's going good and you're like, okay, I make a lot of money, that's cool. But then you start wondering, like, maybe one of these other machines yields better results, maybe they give me more money. And that's sort of the thing that you want to balance also in the tree. Like you can always play at the point where you're winning or you think your winning percentage is best, but there might be another note that might yield better results, but you were just unlucky, unlucky, sorry, so far there. So that is called exploitation versus exploration. Exploitation is like, okay, I'm playing at the note with the best winning percentage, and exploration is like, okay, is there something else out there to try and balance what we're doing? And for this, the standard solution that we use, it's the upper confidence bound or in Go, it's UCT, the upper confidence bound applied to tree search, and this is the general formula. And this value is calculated for every note to then select which note we're going to see. So we take the winning percentage, and then we add to that some sort of exploration factor that you can set to your liking, and there are multiple papers about, like which is the best exploration factor, of course, and then you take the square root of the logarithm, the natural logarithm of the total visits divided by visits. So that is sort of balanced, like, if I haven't visited a note a lot, let's try and visit it again. So how does that work? This is like now a real example that I took from my Go engine. Right now at the top here, the number is just a number of visits because not enough space. So anyway, first selection, we select this note because it has the best winning percentage of all the notes that we have right now. So I cut out lots of other notes to make it fit on the slide. But then what was interesting for me when I looked again into this is on the second selection, at least for the exploration factor that I use, we do not play on the free of free note that we would say that would be the exploitation. It's a note that's going good. We're going to play there again. But it's like, okay, this note has, like, a pretty good winning percentage, 50%. We haven't visited it a lot. So let's try playing there again. Let's try what's happening when I play there. So at this point, you might ask, like, what are we doing here? This is not at all like human-like. Where, like, humans don't play like that. Humans don't go out and be like, okay, I start the game, so I'm just going to play random moves in my head, and at the end I'm going to counter perfectly, and then I'm going to decide on that how I play. Humans look for patterns. They look for, like, how does the board look, and what would I normally play? And there's a lot of intuition involved, a lot of times, in human play. And I chose the picture because I want to remind you of how humans try to fly in, I don't know, the 16th century. We try to imitate birds. We try to have feathers and fet or wings and fly, and that didn't work out quite well. And what we do right now is we have this huge, like, much bigger than birds, these huge metal cages with some wings that sort of resemble them, but not quite, and helicopters are even more different, and that works out better for us. Why does it work out better for us? Because we choose the strength of humans to build these mechanical things and we have our engines and everything. We use that and not what birds are good at. Similarly, in Go, we don't do what we are good at, but we're doing what machines are good at. They're good at playing random moves, and then in the end counting the result perfectly and doing that lots and lots of times per second. So Go engines play, do, like, 50,000 of those playouts per second. Not mine because it's in Ruby, but, yeah, that's, you know. So what are the characteristics of this algorithm or the Monte Carlo tree search? At first, it is a heuristic, which means, I've talked to you about it, and we're just playing random moves. We don't put, we don't have to put any expert knowledge into it. So all that we need to know is how do I generate a valid random move, which is basically what I teach any beginner if I teach them Go. I tell them, okay, this is valid, this is, you can do this, but not that. And we have to teach it who has won. We don't even really need to teach, well, yeah, we have to teach them to score to figure out who has won, but we're only interested in who has won in Go. And for me, that sort of blew my mind because it means that I can be, like, a bad Go player, and I don't have to know a lot of Go. I don't have to encode it into the machine. The machine really plays by itself. It figures out what is the best move by itself by just teaching it, okay, this is valid, and then in the end you can see, have a won, have a lost. And that is really amazing, because that's why we're also not limited by human knowledge, because the machine might at some time surpass us and think of moves that we could never think of, and otherwise we might limit it by our human knowledge or human assumptions that are encoded into the game. Which means also that the Monte Carlo Tree Search is the go-to algorithm for general game playing, which is a discipline that I did not know much about before, but it's basically tournaments where before you get, like, a rule set encoded in a file and then the engines have to play games that they never knew before. And due to that characteristic of the Monte Carlo Tree Search that it does not need to know game-specific knowledge, it's the go-to algorithm for general game playing as well. Also, the algorithm is anytime. With the Alphabet search, it's a depth-first search, so I always have to search through the whole tree until I can make my decision on the best move. With the Monte Carlo Tree Search, I can stop it at any time and say, like, okay, this is a good enough move. Like, I can play this move. It might be really bad, but I can do that, which is good if you're doing time management. And Monte Carlo Tree Search is lazy. This is my favorite paper about Monte Carlo, so I have to tell you this. So imagine a game. This game is called Double Step. It's stupidly simple. In Double Step, you can make one move or two moves. Oops. Too far. Oops. One move or two moves. And you win when you reach the end of that thing. So it's pretty easy. As a human, you say, okay, two moves is always the best move. You know? So, yeah, we win when we're at the end. So what does a Monte Carlo Tree Search do here now? And so, on the top here, we have the handicap. A handicap of minus two means, like, I'm two steps behind. A handicap of two means, okay, I get a handicap of two. I'm two steps ahead. On the left side, we have the number of simulations of Monte Carlo simulations that I ran. So eight random playouts, 16 random playouts, 32, 64, 100, et cetera. And what we have in the middle here is the percentage of that black for its first move selected two steps. And so I ran this 10,000 times each for each of those. And we see the winning percentage here. So we can see at the bottom that we're doing pretty good. If we do 100 playouts, we're at 99.8% or even at 100% if it's an even game. And we can see many characteristics here. So for instance, especially with the lower playouts, so let's look at the first line, the eight playouts, we can see that when we're behind by two, we only have a percentage of 86% to pick the optimal move because that is Monte Carlo and just gets sort of desperate. When they're behind by a lot, they often play nonsense moves, especially also in Go. They play moves that's like, okay, here I play that and then my opponent would have to not answer that move for two or three turns in a row in order for that to yield because they get really desperate. But what's even more interesting is the number in the bottom right. As we get more handicapped, as we had more, our moves get worse at least for the 100 playouts. So we just take the best move 98% of the time. And that's because most Monte Carlo engines just care about if they're winning or losing. They're not caring about how many points they win because that yields worse results as research shows. And you can often observe that in play when a Monte Carlo bot that you're playing against is ahead by a lot. It will just play very, very safe moves according to the model, better safe than sorry. And by the end, the Go bot will win by maybe two points or something. You'll be like, oh, I almost sped that Go bot. Yes. Not at all. The Go bot says, I have won either way. So I'm just going to play these really safe moves because I don't care because I'm going to win either way. So a move that sort of showcases this is the last move of the game that Zen won against Francis of Dicute. In the commentary and also for every other world of our plays, that last move, it's marked with the X in the middle and also Green Highly highlighted now. Most human players consider that move unnecessary because it's pretty clear that middle is fully Black territory. There are some cutting stones, but there's not much danger coming from them. Nevertheless, Zen still played there because why? Zen knew it was two and a half points ahead, so wasting a move in the territory, it was still one and a half points ahead and it would still win. So it played better safe than sorry. So what are some of the enhancements that we can do to play better in the Monte Carlo True Search algorithm? Well, my favorite enhancement is all moves as first and also has a variant which is called RAVE, Rapid Action Value Estimation. The basic idea is this. If we play random moves all the way out all the time, then does it really matter in which order we play them? No, it really doesn't if the moves are pure random. So here in the back propagation phase when we propagate the result of the game back, we also look at all of our sibling nodes and look at if any of those nodes is a move that we made at any point during the game. And then we also update the win stats for that move. What the RAVE algorithm then does is it says, okay, that's cool that we do that, but it's not the most accurate thing in the end. So it gives those extra moves that we update. So the call of ARMAWINS and ARMAWISITS for all moves as first. It gives them a diminishing value. So at first they're taken into account a lot during the selection phase, but when we reach like 2,000 ARMAWISITS or something, then it ignores those values because we've fed a border and just takes a look at the real winning percentage of moves that were really played at that specific node. Of course, we can also encode expert knowledge into the multicultural research. And there are two phases where we can do that. First is the selection phase, so where we select at which node do we want to play, which node do we want to try out. And therefore we can use patterns, we can use Atari solvers, and we can also use Yuziki's or opening libraries. And the second is the play out policy, so our random simulation. We can also use patterns there to try and make the playouts not purely random, but more realistic to get a better value out of them. And this is very dangerous, especially if you use it with all moves as first, which almost every engine does. I think every engine does, every good engine at least. Mine doesn't yet, but we're getting to that. It is dangerous because then it's not purely random anymore, and you could get like false positives and false negatives when you update the tree. So you've got to be very cautious with that, and it is to improve in a science that if you do a heavy play out that biases or a selection or a play out that biases the tree too much, your problem actually gets worse, although you add knowledge. But nevertheless, all strong programs these days do these so-called heavy play outs, and so they're only doing 5,000 play outs because heavy play outs of course take more time to calculate. Oh, by the way, I forgot to say before, in the match between Francis Likert and Zen, Zen played, I think, on a cluster that had 80 cores in total and like 60 gigabytes of RAM, so it's also a pretty high computing thing. So this gets us to that thing that I was mentioning that probably some of you saw at Hacker News. It's playing go against a deep neural network, and this site was done by the author of this paper, which they took a deep convoluted neural network. I don't really know much about what that really is, to be honest. But they trained it with professional games, and they managed a prediction rate of the professional moves on their training set that had a value of, I think, 44%. It told us that it's very good at predicting professional moves. And this paper, it was also referencing this paper. This paper is from 2014, and they did about the same thing with a 12-layer convolutional neural network, and they managed a prediction rate of 51% in there as well. Which is great, like this approach has been tried before, and it's only like this paper is, to my knowledge, the first one that made it useful, because before I think it was tried in 2007, 2009, it was always deemed not useful at the time. And it's a great success. It's one of the newest things in computer go, but these engines have a big problem. They only know what professional moves are and how professionals react. So if you play moves like trick moves or very bad moves, sometimes they react really badly because they're not used to what you're doing there. And they also get them into complicated fights that are not like professional fights, and they're pretty very, very badly. And if you've seen the keynote on the first day by Carina, that's also what all their machine learning hours and their fuckups were in those algorithms, because then they fuck up badly, and that is also reflected here. So the strange varies badly between those. But what's really great about this is we can include this into Monte Carlo. So these are pretty strong, but they still lose against strong Monte Carlo bots. So for Igo, which is about a one-dance train, but from the other convolution network bot, lost 86% of the time, so they're not better than Monte Carlo bots. But we can incorporate the neural networks into our Monte Carlo bots, and we do that at the selection phase. We don't have much computing power left, because we're always using all our cores and everything to do the simulations and the tree updates and everything, but we have a little nice thing in our computer that's a graphics card. So what we can do to incorporate that is to, as synchronously, push the computation of the recommendations of the neural network to our graphics cards, let it compute those computations, and then bring them back and incorporate them into our selection so that we try to play the moves that the network proposes to us first. And for me, that's kind of crazy. Now, you use all of our cores, you use the graphics card, you use tons of memory, and I hope you have a good cooler in there. So this basically bumps the strength. I think I implemented it, and just by adding convolutional neural networks, it bumped its rating on KGS by one down from like three down to four down. So it's pretty cool, and it's a cool area of research. So that Facebook thing that I made sort of a buzz around, we think we found, they bought on KGS playing, and it plays around the level of 4Q or something, and in the video that they showed where they totally bet another engine, they just bet Canugo at a very low level, so it's not much to be excited about yet. But interesting to see what they come up with, and if they, at some point, gonna share their findings with computer go and the computer go mailing list, that would be nice of them. Oh yeah, if you're interested in this thing, there's a very cool computer go mailing list where all the authors of the popular programs are there, and they share, and you can ask, and you sometimes see me asking silly questions or good questions depending on my mood. So of course I wrote a Go engine in Ruby, which is called RubyCon, you can find it at github.com, praktop, RubyCon, and you can also do gem install RubyCon, and then you can invoke RubyCon to play a little game in the CLI. It just implements multicolor research yet, there's still lots of performance optimization potential for me to do the move generation and the scoring faster, but I'm onto it. I also have another project, which is Vekko, which of course looks beautiful, which we implemented the whole thing in CoffeeScript and using web workers to outsource the work, but I still have to do some work on that. Another thing that you might want to look at, a much better engine is Michi. It's a Python engine, there are like 500 lines of Python, and it is very readable, it's all just one file, but it's like a mini-malistic Go engine, I take lots of inspiration from there. And for those of you that are into Rust, because Rust is a cool thing to be in, there's also a nice Rust engine, who's also a German. So now in the end, let's see how much time do I have left. Ooh, damn it. Okay, what have I learned? Quickly, so there's a huge difference between making X faster and doing less of X, and all the time we just try to make something really fast and not go the road of doing less of it. Programming Ruby, doing less of things, costs nothing, and so it's rude, I rent lots of times. Modifying small components, Monte Carlo Tree Search is completely independent of the game of Go, and so mine is as well, you can plug in any game into my Monte Carlo Tree Search library, and it will play it, if you have a facade class to get into there. And benchmark everything, and there's a huge difference between solving things, we always try to solve problems the human way, and not the computer way, but we should actually be doing most of the time as I try to show you with the Monte Carlo Tree Search, and then of course I recommend everyone the jar of creation, like seeing an engine that you build yourself, and then you say, oh, it made that move, that's cute, or it made that move, that's actually pretty good, I'm pretty fighting spirit. So thank you for talking to you, thank you very much for listening to me Rambo Foss alone. This was Bidding Go, thanks to the Power of Randomness, I'm Praktor, thanks. Thank you.
 Music  Yeah, thanks everyone for showing up.  So, oh god no.  Here is 1997, the computer of IBM Deep Blue beats Gary Kasparov on the tournament conditions in I think a six or seven game series.  This is the first time ever that a computer has won against the premier human player and Gary Kasparov is considered to be one of the best players of all time in chess.  At around the same time, computer girl we had the tournament from 1985 to 2000 which was called the World Cup with a total price of a million dollars.  If someone would be able to beat 10 to 14 year old Chinese children that were Go Prodigies in an even game, so it was not for the lack of trying.  But in the same year, 1997, there was this tournament and the winner of the tournament placed against these Chinese so called Insays.  And the program won, but by a huge handicap for those of you that know Go, I think 11 handicapped stones which is pretty much the difference of a very immature player and maybe an intermediate player, so to say.  So let's dig a bit more into the current history, in the more recent history of computer Go and also in why is Go so hard to master as compared to chess.  Why are we so much behind?  Okay, years 2001, an anime by the name of Ikaruna Go is launched in Japan, revitalizing Go and making it more popular among the youth.  It has been going downhill in Japan for some time before that, but overall it's very popular in Eastern Asia, so there are professional players that get paid to play.  You can watch it on TV and everything.  And in 2009, Google invented a language called Go saying, oh, there's a game that's like what, 4,300 years old, we're just going to name Steamroad right over that old board game.  And of course, there's also another programming language by the name of Go and they're also just Steamroad right over that because what the hell with Google we can do whatever we want.  Year 2014 on the right is Rimi Kulon, he's the programmer of a program called Crazy Stone and it's one of the two strongest programs that we have in Go.  And he plays against a professional that's called Yoda, he's a ninth down professional player and Crazy Stone won with a handicap of four stones, which is a lot less than the other handicapper that's still a real big difference in playing strength.  31st of October 2015 in the Code Century Go challenge between the program Zen, which is one of the two most strongest programs played in an even game against one of the strongest amateur of the world, Franz Josef Dikut, a German 5-dan player.  The German, the human prevails in a five game in a best of five series, three to one, this is the last move played in that series.  3rd November 2015 Facebook publishes a blog post that's like oh we're doing all this cool machine learning stuff and by the way we wrote a Go engine, it's awesome and we don't really tell you what we're doing exactly but pattern recognition and their CTO did not answer my Facebook message about what they're really doing, quite to my surprise.  But we're going to get a bit into that and how strong that engine really is for all that we know.  13th November 2015, this site hits second use, it says play Go against a deep neural network, we will also have a look at what's up with that, what's the science behind this.  We're going to look at a lot of stuff that is in scientific papers but don't be afraid, it's all cool. If you don't know Go, all cool, we're going to go over the basics of Go shortly.  So this talk is beating Go things to power of randomness. Hi, I'm Toby, you can find me on Twitter, GitHub and everywhere else as Praktop.  I'm out of Berlin all the way here, I organized a group in Berlin, the React user group in Berlin. I'm a Red Scouts coach, I do open source, I do shoes, who knows shoes, like that's amazing stuff.  I work at a great company called Bicro, which is an agency, so we help startups build things, lots of fun to work there.  Right now we're actually hiring, so if you want to relocate to Berlin, one of the best cities, just saying, and they paid for me to go here, so pretty great.  Some of you might be concerned about my t-shirt because it's like, oh God, would Yoda allow him to wear the t-shirt of Yoda?  Is that physically okay for him? I can tell you, you know, this is saying that Superman wears like a Czech Novelist t-shirt, so Yoda obviously wears a Toby t-shirt.  So we're buddies, you know, we made that out, so everything cool there.  So continuing with the basics of Go, Go is played on a board with lines in the sections and the normal size is a 19 by 19 board.  Then we also have 13 by 13 and 9 by 9.  Normal professional games are played on the 19 by 19 board, but the 9 by 9 board is also still relevant and interesting.  So how does Go, Go? We start playing Move, Black starts and we play on an intersection, so there is now a Black move, then White moves, Black, White, and whoa, too far, sorry.  That's the basic thing. So taking further from that, a stone has so-called liberties.  Those are the adjacent cutting points that are empty, so this stone has four liberties.  If I play another stone, they form a group together and they have six liberties.  When White plays next to the Black stone, both of these stones have three liberties because they take one liberty away from each other.  So if White continues to play, now I have two liberties and in the end, three liberties.  Now we're in a state which is called Atari.  Atari's company name was really chosen by that name of that Go term.  Go term and that term means before capture, sort of.  So if White plays another move, that removes the last liberty from the Black stone,  and that means the Black stone is captured and taken off the board and counts as a point for White.  Of course, Black isn't stupid, Black knows how to play and can stretch out, so now Black has three liberties again and it's all good.  So I told you right now that there is a point which White gains from the capture.  So how do you win in the game of Go?  The game of Go is basically about getting more territory than your opponent.  You try to encircle territory and claim it for yourself and then territory is then one point of these intersections,  and then in the end it is counted who made more territory.  So it's basically a game of dividing.  I try to get more of the cake than my enemy does.  So in this example, we would have encircled one point so that would be one point for Black.  If we go further, White could now encircle Black, and now Black is at one liberty,  so we know what's probably going to happen.  White can capture thereby making eight captures, so eight points.  And of course, this now also counts as White territory, so it's going to be eight points of territory,  so 16 points made here and total, which is pretty much a lot on a nine-by-nine board.  But is it an endless game of capture and recapture?  No, because there's also something in the state that a group is alive.  So we say, and this is a typical group that is alive, it has two eyes,  which means we have two points of territory here,  and White can simultaneously occupy both of those liberties,  because if White would play in there, it would be immediately recaptured,  the so-called suicide move, which is forbidden under Japanese rules, but not under Chinese rules.  So this group cannot be captured, and in the end, all of them are alive.  So what does a game look like in the end?  This is the end position of a game played between a professional player  and one of the strongest go-in.  I think it was then, but I'm not quite sure.  And so how do we count that?  Well, we remove the so-called dead stones that have no chance to live  and then count the territory.  And this game was drawn, and if you see now, it doesn't look like a draw.  Black has way more points. Why was the game a draw?  Well, there's a concept called komi, which is a set of bonus points  that White gets because Black makes the first move.  And so this game was a draw.  So what does a real game look like on the 19 by 19 board?  This is the first game between Francois de Sticut and Zen this year.  And you usually start to occupy the corners first, and we can't go through the full game, so I'll fast forward.  And so we can sort of see how the game starts forming here.  Like Black claims sort of the lower right corner and the upper right corner.  And there's also something very, like for me, interesting going on  that you cannot see the immediate value of in the lower left corner.  Black starts a bit like sort of a wall that faces upwards, and that is called influence.  It is a very difficult, even for really good players to see like who is ahead here and who is not.  And if you see the game commentary, there's lots of discussion about like who is in a better position at this place.  So you can imagine how difficult it must be for a computer to assess the current situation.  The game moves on, we see more moves played and even more moves played.  And at this point I want to focus your attention to the lower right corner.  And this looks at the first look, if you don't know, it looks like OK,  Black and White are battling it out out there.  Unfortunately that is not at all the case.  That Black group is practically that, it is still on the board, but it only has two liberties left, right down there.  And so it can be captured at any moment.  A go engine that would have to play and understand this would have to understand that this is not actually a not played out position,  but those stones are actually lost.  If you fast forward to the end of the game, we can see that eventually White did capture that Black group.  And there are lots more, many, much more complicated positions on the board that I would not be able to assess  because those programs and the player played a much higher level than I do.  OK, so now we count this game and this game was the only game that Zen won  and that was by a margin of one and a half points.  So when we talk about Go versus chess, what's the difference?  In Go you start building something, you start with an empty board and you build.  The stones don't move, they might get captured, but you can't move them, you don't flip them.  You build something, you have to plan strategically ahead like where do I want to be, where do I want to stand in my game.  In chess you go out and destroy, basically.  Your goal is to destroy the other king and so you get less and less of what you really have.  When I first looked into this, which was in 2010,  also an interesting concept came up, the concept of the difference between what is complex and what is complicated.  Go is very simple and it's hard.  There is a set of formalized rules that are just ten rules that basically define the game of Go  and I've taught you almost all of them by now.  Go is very complex because there are many possibilities where it can play which results into many things that could happen  which makes Go very complex.  On the other hand, chess is more complicated and complex.  Chess has many rules.  Which piece can move where, like there's the rojada and the first move, like the pawns can move too.  So it's much more complicated of a game and some of its complexity stands from it being so complicated.  So this is a code by Edward Lesker who was a chess grandmaster and he discovered Go a bit later in his life  and he said, while the baroque rules of chess could only have been created by humans,  the rules of Go are so elegant, organic and rigorously logical that if intelligent life forms exist elsewhere in the universe,  they almost certainly play Go.  So when we want to talk about how strong programs are,  I'm going to quickly introduce you to the ranking system used in Go.  You can see at the beginning when you're at 30Q which is basically you learn the rules and you play the first game.  So that's 30 to 20Q.  A casual player you can become after maybe a couple of months of play of a really hardcore,  then maybe in the first week or so, then you're between 19Q and 10Q.  The intermediate amateur is from 9Q to 1Q and it's really different what people say.  Like if you look at a Go wiki, they say, oh, you can reach it in a month.  I don't think so.  If you look at computer Go papers, they mostly say, oh, well, it takes an amateur player years to reach that level,  but I think they just say that to make their programs look stronger when they reach the Q level.  And then there's also the advanced amateur and the professional.  Now for quick show of hands, who has already played Go?  Who at least reached the beginner state?  Okay.  At least reached casual player, intermediate amateur.  Okay.  Advanced amateur.  Oh, God, there are people here that are much better than me.  I didn't play actively that much anymore, but I was around in 8Q, so a weak intermediate amateur  and took me about one and a half years to go there despite playing tournaments and online and everything.  So you might talk to me while I said wrong about some of the positions later on.  That would be nice.  Thank you.  Why am I showing you this?  It also gives you a hint of what the worth of those handicapped stones is,  because in the amateur level it is considered the difference of one handicap stone between the ranks.  So when a 9Q plays against a 5Q, the 9Q gets a handicap of four stones, which then looks like this.  The stones are already placed, so black essentially gets four free moves.  So this is the handicap at which Crazy Stone won in 2014.  This is the handicap of 9 stones, that is like the highest handicap that you give in official games at tournaments,  as far as I know.  And this is the handicap at which one of the strongest go-programs lost in 1998 to the strongest,  to the Chinese, and say the 10 to 15 year old children.  This is a handicap of 3D and stones, I played once at that handicap at the Blitz team tournament.  We were around 10Q and we played against the team of Dan players, and this handicap is just unfair.  So we bet the Dan level players, although making very, very bad mistakes.  And we were the only team to beat the team of Dan players.  They went on to win the tournament.  So that shows you how unfair that handicap is.  This is a handicap of 29 stones, which is just, I don't know, if you just pick up Go and played on the 19 times,  19 board against me, you would most certainly win, most certainly.  In 1998, a German 5 Dan player bet the strongest go-program at that handicap,  and that was one year after Kasparov was defeated.  So that's just meant to show you how far the programs were behind.  So why is Go so hard?  What makes it that much more complicated and difficult than chess?  So at first, we have a much, much larger board.  Our board is 19 by 19 as opposed to just 8 by 8 for chess.  Then almost every move is legal.  Like I said, I told you almost all the moves are left out of the co-rule,  but basically you have to move inside the field, you can't move at a place where somebody else already is,  and then you can't play co-moves and not the so-called suicide moves, and that's it.  So that leads to a very high average branching factor.  What is an average branching factor?  It's basically the average number of moves that are legal at any point in the game.  So for Go, we have 250 and chess just 45.  We also have a very high state-space complexity.  State-space complexity is the number of valid board positions that exist,  and I think some mathematicians calculated those.  So for Go, it's 2 to the power of 171, and chess 10 to the power of 171,  and for chess it's 10 to the power of 47.  So those are huge numbers. What does that even mean?  The number of atoms in the observable universe is estimated to be around 10 to the power of 80,  which sort of means that we could take each of these atoms and make a combination with also all of the other atoms  and have that as a combination list, which would turn out to be 10 to the power of 160 possible combinations,  if my math doesn't fail me, and that would still be less than the number of valid Go positions.  So at this point you might get a sense of the scale, how big that problem is.  And also moves have a very global impact.  You can't just go like, okay, I'm just going to play locally here where my enemy played last.  That doesn't work due to multiple reasons.  One is oftentimes it is the best move not to answer the move of your opponent just placed somewhere else  because the move somewhere else is much, much bigger.  And the other thing is that a move that I played down here in the bottom right can have severe influences  on a position to the top left.  It might break things there and actually defeat, decide the state of a group.  So let's finally, after we've gotten our intro to Go and why it is so hard,  let's talk about artificial intelligence for a second here.  This is an image from Wikipedia of the alphabet of pruning or alphabet of search,  which is one of the, which is the algorithm basically to play chess, like deep blue use it,  and I think modern chess programs still use it.  It's a depth first search in that graph where you go to leave and then you have to evaluate the state of the board  at that point in time because you can't play all the way to the end  because even for chess there would be way too much to do.  And then you always assume perfect play, which means that's the min-max part.  And the first move, that's our move, we try to maximize the value of the evaluation function  to say like, okay, we want to have the best position for us.  But that's the first step.  And afterwards it's the minimize because it's our opponent's move.  And of course our opponent is clever and we try to minimize the overall value of the evaluation function  because your opponent wants to make a good move and then we maximize and so on.  So what's the problem here?  As I tried to show you before, it is very hard to write an evaluation function for the game of Go.  If you remember this position, for instance, it's not very clear where territory will be  of room in the end and how much it will be and there are other concepts involved like mojo and influence.  It's like, okay, black has very much influence there, but white has more territory.  That is something that you commonly hear in game commentary and it's not easy to decide what is worth more  and especially not for computers.  So far we have been unable to find a good evaluation function.  There's one Go program called GNU Go that uses alpha-batter search, alpha-batter pruning,  but it plays around the level of 5Q, 5.4Q,  and current strong Go programs play about a strange of a 5-dan or 6-dan amateur player.  So we came up with this great thing which is called the Monte Carlo method.  So to tell you what the Monte Carlo method is, I want to ask you a question first.  What is pi? What is the value of pi?  3.14 something, cool.  So how do you know that? How do you determine the value of pi?  Come on, people. No one?  No.  So it's some sort of circumference, blah, blah, blah, math things.  There is another way to do this.  You can draw a, I think it's called Union Square on a piece of paper and do a circle in it  and then you throw random pins at it and then you count how many pins land inside the circle,  how many land outside of the circle, multiply that relation by 4,  and then you get an estimation of pi, which is an example of the Monte Carlo method applied  and you can see it here.  And right at the top, I think it's cut off, but you can see with the number of simulations,  with the number of more random dots that we throw in there,  our estimation of pi gets better and better.  So this is the Monte Carlo method.  Pi is not its best use case, but it's usually used in spaces where it's very hard to do a full simulation  of something, so we just do a random simulation and in the end,  we just assess what is the outcome and by running multiple random simulations  and then assessing the outcome, we can get an estimate or a guess of what the final value is  and in go that is basically our evaluation function.  So this, like the Monte Carlo method was proposed before in 1993 in a paper,  but it was not made to work.  It was not until the year of 2006 until the Monte Carlo tree search was developed  and successfully applied to go or was actually developed before go  and at that year, the program that implemented Monte Carlo tree search also won the go tournament.  So ever since, all go programs that are successful use Monte Carlo tree searches.  So that was sort of a revolution and it's been rather recent.  So Monte Carlo tree search has been around since 1957 or something.  So this is the basics of the Monte Carlo tree search.  We go through a selection phase first to select the number we want to play at,  then we do an expansion, then we do a random simulation  and afterwards we do a back propagation of our results.  So what does it look like in detail?  In this graph, we say each node has at first like the wins that have been at that node  and then last the visits, how many times have I visited that node  and the nodes represent a board state and then afterwards it's like we play a move  and then the next node is like the board state that results when we play that move.  So at first we go to the selection phase, we select the node we want to play it,  we want to say, okay, we want to see here what happens here,  we've got one again, more information here.  So we do an expansion that says like, okay, this is the move we're going to try here  at that specific node, then we're going to do a random play out  and you might be right now, you might be like, okay, what random play out,  what are we doing?  It seems like not very smart to do a random play out.  But the hypothesis is this, if I'm standing better at the board in general,  if I have a better position, if I do a random play out and I win in the end,  I'm more likely to win in the end if my position was better.  And if we do that lots and lots of times, we get a pretty clear view of  is our position ultimately better or worse.  So in the end we do a back propagation that says, okay, we have one here,  so we propagate that result back to the top.  And here you've got to be careful a bit if you remember the min max.  So it's also a matter of perspective.  Remember the sort of darkish thing is like the black move and down here it's the white move  and of course we can do a back propagation that when white has won,  then of course black has not won, black has lost.  And so you either have to take that into account during selection  or how my go-board does it and how I know other go-boards do it  is you always alternate how you report the results.  You say, okay, white won, then black lost, white won, black lost, white won, black lost.  And so you always alternate the result that you report so that the selection is sort of uniform.  So let's talk about a bit about the selection because it's a crucial part.  So we could just take like every move all the time and play each move equally all of the time,  but that's not very smart.  And since we're already doing like the random play out stuff,  we at least want to be smart about the selection, you know.  And this is a so-called multi-arm bandit problem,  which is one of the most interesting problems I've come across there.  And it's that scenario you're sitting at a casino and you're playing at those bandits  and you're playing at your machine and it's going good and you're like, okay, I make a lot of money, that's cool.  But then you start wondering, like, maybe one of these other machines yields better results,  maybe they give me more money.  And that's sort of the thing that you want to balance also in the tree.  Like you can always play at the point where you're winning  or you think your winning percentage is best,  but there might be another note that might yield better results,  but you were just unlucky, unlucky, sorry, so far there.  So that is called exploitation versus exploration.  Exploitation is like, okay, I'm playing at the note with the best winning percentage,  and exploration is like, okay, is there something else out there to try and balance what we're doing?  And for this, the standard solution that we use,  it's the upper confidence bound or in Go, it's UCT,  the upper confidence bound applied to tree search,  and this is the general formula.  And this value is calculated for every note to then select which note we're going to see.  So we take the winning percentage, and then we add to that some sort of exploration factor  that you can set to your liking, and there are multiple papers about,  like which is the best exploration factor, of course,  and then you take the square root of the logarithm,  the natural logarithm of the total visits divided by visits.  So that is sort of balanced, like, if I haven't visited a note a lot,  let's try and visit it again.  So how does that work?  This is like now a real example that I took from my Go engine.  Right now at the top here, the number is just a number of visits because not enough space.  So anyway, first selection, we select this note because it has the best winning percentage  of all the notes that we have right now.  So I cut out lots of other notes to make it fit on the slide.  But then what was interesting for me when I looked again into this  is on the second selection, at least for the exploration factor that I use,  we do not play on the free of free note that we would say that would be the exploitation.  It's a note that's going good. We're going to play there again.  But it's like, okay, this note has, like, a pretty good winning percentage, 50%.  We haven't visited it a lot.  So let's try playing there again.  Let's try what's happening when I play there.  So at this point, you might ask, like, what are we doing here?  This is not at all like human-like.  Where, like, humans don't play like that.  Humans don't go out and be like, okay, I start the game,  so I'm just going to play random moves in my head,  and at the end I'm going to counter perfectly,  and then I'm going to decide on that how I play.  Humans look for patterns.  They look for, like, how does the board look, and what would I normally play?  And there's a lot of intuition involved, a lot of times, in human play.  And I chose the picture because I want to remind you of how humans  try to fly in, I don't know, the 16th century.  We try to imitate birds.  We try to have feathers and fet or wings and fly,  and that didn't work out quite well.  And what we do right now is we have this huge, like, much bigger than birds,  these huge metal cages with some wings that sort of resemble them,  but not quite, and helicopters are even more different,  and that works out better for us.  Why does it work out better for us?  Because we choose the strength of humans to build these mechanical things  and we have our engines and everything.  We use that and not what birds are good at.  Similarly, in Go, we don't do what we are good at,  but we're doing what machines are good at.  They're good at playing random moves,  and then in the end counting the result perfectly  and doing that lots and lots of times per second.  So Go engines play, do, like, 50,000 of those playouts per second.  Not mine because it's in Ruby, but, yeah, that's, you know.  So what are the characteristics of this algorithm or the Monte Carlo tree search?  At first, it is a heuristic, which means, I've talked to you about it,  and we're just playing random moves.  We don't put, we don't have to put any expert knowledge into it.  So all that we need to know is how do I generate a valid random move,  which is basically what I teach any beginner if I teach them Go.  I tell them, okay, this is valid, this is, you can do this, but not that.  And we have to teach it who has won.  We don't even really need to teach, well, yeah,  we have to teach them to score to figure out who has won,  but we're only interested in who has won in Go.  And for me, that sort of blew my mind  because it means that I can be, like, a bad Go player,  and I don't have to know a lot of Go.  I don't have to encode it into the machine.  The machine really plays by itself.  It figures out what is the best move by itself by just teaching it,  okay, this is valid, and then in the end you can see,  have a won, have a lost.  And that is really amazing, because that's why we're also not limited  by human knowledge, because the machine might at some time surpass us  and think of moves that we could never think of,  and otherwise we might limit it by our human knowledge  or human assumptions that are encoded into the game.  Which means also that the Monte Carlo Tree Search is the go-to algorithm  for general game playing, which is a discipline that I did not know much about before,  but it's basically tournaments where before you get, like, a rule set encoded in a file  and then the engines have to play games that they never knew before.  And due to that characteristic of the Monte Carlo Tree Search  that it does not need to know game-specific knowledge,  it's the go-to algorithm for general game playing as well.  Also, the algorithm is anytime.  With the Alphabet search, it's a depth-first search,  so I always have to search through the whole tree  until I can make my decision on the best move.  With the Monte Carlo Tree Search, I can stop it at any time  and say, like, okay, this is a good enough move.  Like, I can play this move.  It might be really bad, but I can do that,  which is good if you're doing time management.  And Monte Carlo Tree Search is lazy.  This is my favorite paper about Monte Carlo,  so I have to tell you this.  So imagine a game. This game is called Double Step.  It's stupidly simple.  In Double Step, you can make one move or two moves.  Oops. Too far.  Oops. One move or two moves.  And you win when you reach the end of that thing.  So it's pretty easy.  As a human, you say, okay, two moves is always the best move.  You know?  So, yeah, we win when we're at the end.  So what does a Monte Carlo Tree Search do here now?  And so, on the top here, we have the handicap.  A handicap of minus two means, like, I'm two steps behind.  A handicap of two means, okay, I get a handicap of two.  I'm two steps ahead.  On the left side, we have the number of simulations  of Monte Carlo simulations that I ran.  So eight random playouts, 16 random playouts,  32, 64, 100, et cetera.  And what we have in the middle here is the percentage  of that black for its first move selected two steps.  And so I ran this 10,000 times each for each of those.  And we see the winning percentage here.  So we can see at the bottom that we're doing pretty good.  If we do 100 playouts, we're at 99.8%  or even at 100% if it's an even game.  And we can see many characteristics here.  So for instance, especially with the lower playouts,  so let's look at the first line, the eight playouts,  we can see that when we're behind by two,  we only have a percentage of 86% to pick the optimal move  because that is Monte Carlo and just gets sort of desperate.  When they're behind by a lot, they often play nonsense moves,  especially also in Go.  They play moves that's like, okay, here I play that  and then my opponent would have to not answer that move  for two or three turns in a row in order for that to yield  because they get really desperate.  But what's even more interesting is the number in the bottom right.  As we get more handicapped, as we had more,  our moves get worse at least for the 100 playouts.  So we just take the best move 98% of the time.  And that's because most Monte Carlo engines just care about  if they're winning or losing.  They're not caring about how many points they win  because that yields worse results as research shows.  And you can often observe that in play when a Monte Carlo bot  that you're playing against is ahead by a lot.  It will just play very, very safe moves  according to the model, better safe than sorry.  And by the end, the Go bot will win by maybe two points or something.  You'll be like, oh, I almost sped that Go bot. Yes.  Not at all. The Go bot says, I have won either way.  So I'm just going to play these really safe moves  because I don't care because I'm going to win either way.  So a move that sort of showcases this  is the last move of the game that Zen won against Francis of Dicute.  In the commentary and also for every other world of our plays,  that last move, it's marked with the X in the middle  and also Green Highly highlighted now.  Most human players consider that move unnecessary  because it's pretty clear that middle is fully Black territory.  There are some cutting stones, but there's not much danger coming from them.  Nevertheless, Zen still played there because why?  Zen knew it was two and a half points ahead,  so wasting a move in the territory,  it was still one and a half points ahead and it would still win.  So it played better safe than sorry.  So what are some of the enhancements that we can do  to play better in the Monte Carlo True Search algorithm?  Well, my favorite enhancement is all moves as first  and also has a variant which is called RAVE,  Rapid Action Value Estimation.  The basic idea is this.  If we play random moves all the way out all the time,  then does it really matter in which order we play them?  No, it really doesn't if the moves are pure random.  So here in the back propagation phase  when we propagate the result of the game back,  we also look at all of our sibling nodes  and look at if any of those nodes is a move  that we made at any point during the game.  And then we also update the win stats for that move.  What the RAVE algorithm then does is it says,  okay, that's cool that we do that,  but it's not the most accurate thing in the end.  So it gives those extra moves that we update.  So the call of ARMAWINS and ARMAWISITS for all moves as first.  It gives them a diminishing value.  So at first they're taken into account a lot during the selection phase,  but when we reach like 2,000 ARMAWISITS or something,  then it ignores those values because we've fed a border  and just takes a look at the real winning percentage of moves  that were really played at that specific node.  Of course, we can also encode expert knowledge  into the multicultural research.  And there are two phases where we can do that.  First is the selection phase,  so where we select at which node do we want to play,  which node do we want to try out.  And therefore we can use patterns,  we can use Atari solvers,  and we can also use Yuziki's or opening libraries.  And the second is the play out policy,  so our random simulation.  We can also use patterns there to try and make the playouts  not purely random, but more realistic  to get a better value out of them.  And this is very dangerous, especially if you use it with all moves  as first, which almost every engine does.  I think every engine does, every good engine at least.  Mine doesn't yet, but we're getting to that.  It is dangerous because then it's not purely random anymore,  and you could get like false positives and false negatives  when you update the tree.  So you've got to be very cautious with that,  and it is to improve in a science that if you do a heavy play out  that biases or a selection or a play out that biases the tree too much,  your problem actually gets worse, although you add knowledge.  But nevertheless, all strong programs these days  do these so-called heavy play outs,  and so they're only doing 5,000 play outs  because heavy play outs of course take more time to calculate.  Oh, by the way, I forgot to say before,  in the match between Francis Likert and Zen,  Zen played, I think, on a cluster that had 80 cores in total  and like 60 gigabytes of RAM,  so it's also a pretty high computing thing.  So this gets us to that thing that I was mentioning  that probably some of you saw at Hacker News.  It's playing go against a deep neural network,  and this site was done by the author of this paper,  which they took a deep convoluted neural network.  I don't really know much about what that really is, to be honest.  But they trained it with professional games,  and they managed a prediction rate of the professional moves  on their training set that had a value of, I think, 44%.  It told us that it's very good at predicting professional moves.  And this paper, it was also referencing this paper.  This paper is from 2014,  and they did about the same thing with a 12-layer  convolutional neural network,  and they managed a prediction rate of 51% in there as well.  Which is great, like this approach has been tried before,  and it's only like this paper is, to my knowledge,  the first one that made it useful,  because before I think it was tried in 2007, 2009,  it was always deemed not useful at the time.  And it's a great success.  It's one of the newest things in computer go,  but these engines have a big problem.  They only know what professional moves are  and how professionals react.  So if you play moves like trick moves or very bad moves,  sometimes they react really badly  because they're not used to what you're doing there.  And they also get them into complicated fights  that are not like professional fights,  and they're pretty very, very badly.  And if you've seen the keynote on the first day by Carina,  that's also what all their machine learning hours  and their fuckups were in those algorithms,  because then they fuck up badly,  and that is also reflected here.  So the strange varies badly between those.  But what's really great about this is we can  include this into Monte Carlo.  So these are pretty strong, but they still lose  against strong Monte Carlo bots.  So for Igo, which is about a one-dance train,  but from the other convolution network bot,  lost 86% of the time,  so they're not better than Monte Carlo bots.  But we can incorporate the neural networks  into our Monte Carlo bots,  and we do that at the selection phase.  We don't have much computing power left,  because we're always using all our cores and everything  to do the simulations and the tree updates and everything,  but we have a little nice thing in our computer  that's a graphics card.  So what we can do to incorporate that is to,  as synchronously, push the computation  of the recommendations of the neural network  to our graphics cards, let it compute those computations,  and then bring them back and incorporate them  into our selection so that we try to play the moves  that the network proposes to us first.  And for me, that's kind of crazy.  Now, you use all of our cores, you use the graphics card,  you use tons of memory,  and I hope you have a good cooler in there.  So this basically bumps the strength.  I think I implemented it,  and just by adding convolutional neural networks,  it bumped its rating on KGS by one down  from like three down to four down.  So it's pretty cool, and it's a cool area of research.  So that Facebook thing that I made sort of a buzz around,  we think we found, they bought on KGS playing,  and it plays around the level of 4Q or something,  and in the video that they showed where they totally bet  another engine, they just bet Canugo at a very low level,  so it's not much to be excited about yet.  But interesting to see what they come up with,  and if they, at some point,  gonna share their findings with computer go  and the computer go mailing list, that would be nice of them.  Oh yeah, if you're interested in this thing,  there's a very cool computer go mailing list  where all the authors of the popular programs are there,  and they share, and you can ask,  and you sometimes see me asking silly questions  or good questions depending on my mood.  So of course I wrote a Go engine in Ruby,  which is called RubyCon, you can find it at github.com,  praktop, RubyCon, and you can also do  gem install RubyCon,  and then you can invoke RubyCon to play a little game in the CLI.  It just implements multicolor research yet,  there's still lots of performance optimization potential  for me to do the move generation and the scoring faster,  but I'm onto it.  I also have another project, which is Vekko,  which of course looks beautiful,  which we implemented the whole thing in CoffeeScript  and using web workers to outsource the work,  but I still have to do some work on that.  Another thing that you might want to look at,  a much better engine is Michi.  It's a Python engine,  there are like 500 lines of Python,  and it is very readable, it's all just one file,  but it's like a mini-malistic Go engine,  I take lots of inspiration from there.  And for those of you that are into Rust,  because Rust is a cool thing to be in,  there's also a nice Rust engine,  who's also a German.  So now in the end, let's see how much time do I have left.  Ooh, damn it.  Okay, what have I learned?  Quickly, so there's a huge difference between making X faster  and doing less of X,  and all the time we just try to make something really fast  and not go the road of doing less of it.  Programming Ruby, doing less of things, costs nothing,  and so it's rude, I rent lots of times.  Modifying small components, Monte Carlo Tree Search  is completely independent of the game of Go,  and so mine is as well,  you can plug in any game into my Monte Carlo Tree Search library,  and it will play it,  if you have a facade class to get into there.  And benchmark everything,  and there's a huge difference between solving things,  we always try to solve problems the human way,  and not the computer way,  but we should actually be doing most of the time  as I try to show you with the Monte Carlo Tree Search,  and then of course I recommend everyone the jar of creation,  like seeing an engine that you build yourself,  and then you say, oh, it made that move, that's cute,  or it made that move, that's actually pretty good,  I'm pretty fighting spirit.  So thank you for talking to you,  thank you very much for listening to me Rambo Foss alone.  This was Bidding Go, thanks to the Power of Randomness,  I'm Praktor, thanks.  Thank you.
Beating_Go_thanks_to_the_power_of_randomness_0_47.png Beating_Go_thanks_to_the_power_of_randomness_48_263.png Beating_Go_thanks_to_the_power_of_randomness_264_371.png Beating_Go_thanks_to_the_power_of_randomness_372_599.png Beating_Go_thanks_to_the_power_of_randomness_600_2867.png Beating_Go_thanks_to_the_power_of_randomness_2868_3527.png Beating_Go_thanks_to_the_power_of_randomness_3528_4103.png Beating_Go_thanks_to_the_power_of_randomness_4104_4883.png Beating_Go_thanks_to_the_power_of_randomness_4884_5675.png Beating_Go_thanks_to_the_power_of_randomness_5676_6851.png Beating_Go_thanks_to_the_power_of_randomness_6852_8315.png Beating_Go_thanks_to_the_power_of_randomness_8316_8543.png Beating_Go_thanks_to_the_power_of_randomness_8544_11771.png Beating_Go_thanks_to_the_power_of_randomness_11772_13583.png Beating_Go_thanks_to_the_power_of_randomness_13584_14651.png Beating_Go_thanks_to_the_power_of_randomness_14652_17759.png Beating_Go_thanks_to_the_power_of_randomness_17760_19823.png Beating_Go_thanks_to_the_power_of_randomness_19824_23315.png Beating_Go_thanks_to_the_power_of_randomness_23316_25607.png Beating_Go_thanks_to_the_power_of_randomness_25608_29207.png Beating_Go_thanks_to_the_power_of_randomness_29208_29435.png Beating_Go_thanks_to_the_power_of_randomness_29436_30959.png Beating_Go_thanks_to_the_power_of_randomness_30960_31151.png Beating_Go_thanks_to_the_power_of_randomness_31152_32243.png Beating_Go_thanks_to_the_power_of_randomness_32244_32519.png Beating_Go_thanks_to_the_power_of_randomness_32520_32723.png Beating_Go_thanks_to_the_power_of_randomness_32724_34835.png Beating_Go_thanks_to_the_power_of_randomness_34836_37259.png Beating_Go_thanks_to_the_power_of_randomness_37260_37847.png Beating_Go_thanks_to_the_power_of_randomness_37848_37967.png Beating_Go_thanks_to_the_power_of_randomness_37968_38231.png Beating_Go_thanks_to_the_power_of_randomness_38232_39191.png Beating_Go_thanks_to_the_power_of_randomness_39192_39659.png Beating_Go_thanks_to_the_power_of_randomness_39660_40535.png Beating_Go_thanks_to_the_power_of_randomness_40536_43139.png Beating_Go_thanks_to_the_power_of_randomness_43140_43223.png Beating_Go_thanks_to_the_power_of_randomness_43224_45455.png Beating_Go_thanks_to_the_power_of_randomness_45456_52943.png Beating_Go_thanks_to_the_power_of_randomness_52944_54047.png Beating_Go_thanks_to_the_power_of_randomness_54048_54335.png Beating_Go_thanks_to_the_power_of_randomness_54336_54503.png Beating_Go_thanks_to_the_power_of_randomness_54504_56267.png Beating_Go_thanks_to_the_power_of_randomness_56268_58919.png Beating_Go_thanks_to_the_power_of_randomness_58920_62051.png Beating_Go_thanks_to_the_power_of_randomness_62052_65591.png Beating_Go_thanks_to_the_power_of_randomness_65592_66479.png Beating_Go_thanks_to_the_power_of_randomness_66480_66911.png Beating_Go_thanks_to_the_power_of_randomness_66912_67379.png Beating_Go_thanks_to_the_power_of_randomness_67380_68279.png Beating_Go_thanks_to_the_power_of_randomness_68280_68339.png Beating_Go_thanks_to_the_power_of_randomness_68340_68679.png