# Browser Go: The Weak Move Guesser To estimate how strong a Go move is using Monte-Carlo Tree Search, your program repetitively walks through the search tree along the most promising moves. When reaching a leaf (which happens immediately, if the search tree is empty), it uses its weak move guesser to play the rest of the game until one side wins. For each move it can make, it counts the number of wins and losses. The move with the best ratio is more likely to be the one it makes. Counter-intuitively, the weak move guesser does not need to be particularly strong. Even if it is purely random, the results are reasonable given a large enough number of playouts. So, a critical factor is how fast it can play. However, obviously, having it be better helps a bit, too. As a result, we focus on three parameters to estimate our weak move guesser: 1. The accuracy of guesses (as a proportion of moves from the KGS master games that are correctly guessed), 2. The average time a guess takes, 3. The ratio of the two, in s^-1. The percentage of correct KGS guesses correlates surprisingly well with how strong a move guesser is. However, a number does not give a good idea of how it plays. Here is a more qualitative equivalence: - At 0.01%, it plays randomly. - At 5%, if it was human, it would either be a baby that saw you play, or someone having a stroke. - At 15%, it is black-out drunk. - At 25%, it is a beginner to the game. (AlphaGo's weak move guesser is there.) - At 50%, it wins amateur competitions. (AlphaGo's strong move guesser is at 55%.) Beyond about 57% (where we'd win half the KGS games), the percentage becomes less meaningful, as you already are at the level at which KGS games are played. If you are guessing the play of a weaker player, and you guess differently, you might be guessing a better move. On the off-chance that you think the weak move guesser is rubbish because it plays like a beginner, AlphaGo's MCTS with its fast and finely tuned weak move guesser beat every open-source program available in 2015. # Mask Match Find the dumbest way to find meaning in Go. Therefore, let's count the number of moves played on a spot for every board configuration in the KGS dataset. Except that every board configuration gets pretty unique. Well, locality is important, right? When you place a stone, you look at surrounding intersections. So, instead of counting moves for each permutation of the board, let's count them for every permutation within a mask around the given move. We can try a mask with just the four nearest neighbors of a move, or the 3x3 square, or the 12-point diamond, or even just the edge of the 12-point diamond…

From testing, edge masks are not very useful. I tried making a tree of masks further and further away from the move, and it too failed. The best ratio I got was with the 12-diamond mask: ``` $ node src/ai/probaduk/count-matches.js > patterns.json start training training: 1.22e+5ms validation: 3.21e+3ms Accuracy: 3047/20971 (14.5%), time: 0.000153s, ratio: 948 Total: 100198 matches ``` But, as I mentioned above, 14.5% corresponds to playing with a black-out drunk human specimen. I will spare you the picture of me playing with Mr I-Make-Lines-In-The-Middle-Of-Nowhere. # Decision Tree Getting more bang for the buck costs more time with dumb pattern matching, because you need to compare more intersections to build your pattern. But for every intersection we notice around us, some pieces of information would just be noise that we can ignore. What if we built a tree checking one piece of information at a time? We could avoid spending time on meaningless data. So I built a tree, where each node asks a single question, like "Is the stone at the right of this potential move an enemy?" or "Does the group two intersections up have three or more liberties?" I add a leaf to the tree by looking at all leaves and computing the leaf and the question that most increases the probability that we find a move. ``` $ node src/ai/probaduk/build-decision-tree.js sgf/kgs4d/ 100 20 300 > dtree.json sgf/kgs4d/ 100 20 300 parsing: 97.0ms training: 8.99e+6ms validation: 2.57e+3ms Guessed 5923/23817 (24.9%), time: 0.000108s, ratio: 2306 ``` But it still struggled against GNU Go at level 1.

Decision tree vs. GNU Go — *Spoiler: it doesn't end well for white.*

# Ranking Imagine that there is an objective ranking for all possible moves of all possible board configurations. Let's say that you own a machine that can give you the ranking for each move on your game. You will systematically play the move with the best score on the board (or randomly pick one among ties). You start with an empty board, where you see the rankings of each choice. We can guess that the corners will have a terrible score, and the 4-4 points will have an identically good score. When a stone is placed, you see its neighbors' score change. Presumably, the nearest ones get changed more than the furthest ones. Indeed, locality seems relevant when playing Go. With the resulting board, you pick the move with the best ranking, which may be different from the best ranking move you saw before the last move. Let's assume that the players in our KGS dataset own that machine, and use it to always play the move with the highest rank. Can we use their games to deduce how a move affects each empty intersection's rank? ## Unit Whether we use a ranking (this move in this board configuration is the best move ever, this move in that configuration is second best, etc.), an arbitrary score, or a probability, each measure is mostly interchangeable. We can convert the rankings to as many subdivisions of the 0-1 interval; we can do the same with scores. At the end of the day, we will only take the move with the best number. We only care about comparing the numbers that our imaginary machine outputs for each possible move. ## Probability Delta Let's consider a mask over the 12 nearest points around an intersection. Every possible pattern it can match will on average change the score of moves around it. We can compute that change, and here is how. First, estimate from the KGS games the probability of moves around an intersection if that intersection is *not played* (ie, it is empty), and if it *is played*. Imagine a function that takes those two probabilities and uses them to update the probabilities of surrounding moves. We don't know how to make that function yet, but let's give it a shot, and the name `probupdate(a, b)`. `a` is the probability before the intersection is played, and `b` is the probability after it is played. We know three facts about that function: - `probupdate(a, b)(a) = b`: if on average, playing the intersection changes a move's probability from 0.5 to 0.2, then if that move's probability was 0.5 before playing the intersection, the move's probability is 0.2 after laying the stone. - `probupdate(a, b)(0) = 0`: something impossible stays so. - `probupdate(a, b)(1) = 1`: something inevitable stays so. You can already get a feeling that this function is not linear, and it feels parabolic. Fortunately, there is a single parabola going through three points. (Said otherwise, an order-2 polynomial equation has three unknown parameters, and we have three equations, allowing us to solve it.) Going through the math gives us `probupdate(a, b) = x → x(αx - α + 1)`, given `α = (b-a) ÷ a(a - 1)`. We can update probabilities of nearby empty intersections every time a move is made, for both players. For each player, 1. we build a pattern out of the 12 neighbors, 2. we make 24 updates (the 5x5 square around the move), 3. we keep a list of all possible moves sorted by best probability, and replace the 24 updated intersections. With binary search, each replacement takes ceil(log2(19^2)) = 9 checks, 4. we yield that list as our approximation of the imaginary perfect-play machine. A quick back-of-the-envelope estimate gives a 1 μs guess. ## Rank Regeneration It turns out that if you account for stone color and group liberties (1, 2, or 3+), there are "only" 14 billion configurations within the 12-point diamond surrounding a spot. Every time a move is played, we know that all other moves had a worse or equal score. We also know that they all kept their score, except for the ones near the move. # Linear Softmax So, what did DeepMind do? It is surprisingly hard to answer that question. The information provided in the paper is lacking. There is an image of a single-layer neural network that mirrors the architecture of the strong move guesser. Elsewhere, it is described as a linear softmax. That implies that it is barely more than a regression, a linear separator in a high-dimensional space. The time it takes to guess a single move is also an indication. 2 μs. There are only so many multiplications you can do in that time. Assuming you achieve one multiplication every 2 ns, you are doing 1000 multiplications. A board is made of 361 intersections, so that you can only do 2 multiplications per intersection. And we're not even accessing data from surrounding intersections. Finally, we have a table indicating the parameters of the weak move guesser. They are nothing like the parameters for the strong move guesser. First of all, there are 109747 parameters, presumably each with its own neural network weight. That is way too many multiplications. Second, most of those parameters are simply patterns of 8 or 12 intersections, defined by their color (empty, black, white) and liberties (1, 2, ≥ 3). But of course, we don't need to process every intersection if we make the same assumptions as we did before. We only recompute the probabilities of intersections around groups around the previous move, and keep the other ones intact. (The most serious case where it is not true that a move probability is affected only by nearby moves is when a group is in atari. It is then a turn away from being captured by another move potentially far away. That is likely why they added a specific parameter for atari, which would have a fairly high weight.) We don't have to involve every weight in the neural network in the computation. Every probability computation is softmax(nakadePatternWeight(move) + absolutePatternWeight(move) + relativePatternWeight(move, prevMove) + relativeWeight(relativePatternWeight > 0) + directNeighborWeight(move, prevMove) + atariWeight(move)), with all pattern weights defaulting to zero if the pattern is unknown. In this design, gradient descent simply makes weights learn each pattern's comparative rank. # Post-Scriptum First of all, the AI designer needs to apprehend smooth problem spaces that span trillions of parallel permutations. We iterate through guesses in how our evolving understanding can help the learning process, but it's a thankless walk through muddy waters. The AlphaGo paper betrays that hard work: they mention complex efforts like building neural architectures that leverage board symmetries that turned out to be failures. I tried talking about my own failures as well. I feel like the publishing of academic papers has a tendency to exhibit survival bias and cargo culting: failed efforts are rarely published, creating a blind spot for newbies, and encouraging authors to steer to where the flock is. The AlphaGo paper also betrays having many authors. Some parts of the design are explained with amazing precision and with trivializing graphics. Others, like the rollout policy, are barely described. Reading between the lines, it was probably a work-intensive effort to have a probabilistic model compete with deep learning. They probably could have got away without MCTS, but someone persisted, and through their iterating design, they got a subtle, fine-tuned system that could barely compete. That's the strength of deep learning. Bulky memory, power-hungry, but strong results. Second, we often think about the evolution of AI in terms of the difference between Einstein and a baby. However, AI doesn't start as smart as a baby. AI's real journey is to go from as smart as a dead human to as smart as the best human. The effort to make it on par with the least intelligent human is gigantic in comparison to the work needed to go from there to the best human. And that, my peers, is the next episode.