Source
r/chess•
_mess_

AlphaZero understanding ?

I read basically every thread I found and things are really confused and I think nobody really clearly understood it.

I just don't get mainly on what the evaluation is based upon... just past game result ?

And what if an actual game encounter a position never met before?

Also it is very unclear what the engine "saves" when learning, he plays a game against himself ok, so what? He save the whole game? From what some ppl say it just seems a huge database contradicting the whole idea of "AI"

Posted Dec 8, 2017, 9:00 AM UTC

347
gnullify1900 Lichess•

Brush up on reinforcement learning.

6
_mess_OP•

I already did, I just dont grasp this specific application and how to apply the generic idea on chess

1
beete17•

Say it's playing the 2 knights as white. It'll play a game where it plays 4.Nc3 and another game where it'll try 4.d3. If it wins with Nc3 it'll reinforce it, say by using a point system, making it more likely to play 4.Nc3 in the future for that specific position. If it loses with Nc3, it'll take take note and be less likely to play that move in the future, thus making it more likely to play 4.d3. Rinse and repeat 40 million times in many positions and it develops an "artificial intuition" where it finds moves based on previous successes and losses. This is a very simplified description but yeah, that's the basic idea. Matt Parker on YouTube has a video using this principle to teach boxes filled with jellybeans how to play tic tac toe.

1
_mess_OP•

for that specific position.

that's the problem, so you are saying it search some "database" of identical position with the assigned value?

Most other ppl seems to think otherwise

1
beete17•

You have to understand that this isn't the only algorithm at play. If it was, anyone could build a chess crushing AI. DeepMind is not going to reveal all the inner workings of their AI. The idea I presented is like a first stepping stone, arguably the most important one. At the end of the day the AI is a program which makes use of its memory to collect data and make decisions based on the information presented. There are many ways to do it and this AI is just a collection of these methods.

2
zc_eric•

I think it is a little more like this:

Why did it play Nc3 in one game and d3 in the other?

Perhaps because in the first game, the NN parameters favoured piece development in a certain kind of position a little bit more than the second; while the second one chose d3 because it gives more weight to forming pawn chains in that sort of position.

These differences in the NN parameters would have been there through the whole of both games, so there is no reason for the NN to think that the win or loss was due to move 4 in some way (and indeed it probably wasn't due to that!).

But what happens is that when it adjusts its parameters for the next trial, it will choose a set which is closer to the set in the game it won, rather than the game it lost.

So if in positions "like that" (whatever that means to the NN), bringing a piece out is better than moving a pawn, parameters which cause the NN to choose "that sort of move" (whatever that means to the NN) will tend to be chosen.

1
KapteeniJ•

How it works is best though of in two parts. The learning part, which creates the AI, and the actual AI performance part.

So how does the final AI work? Assuming you know tree searches, basically AlphaZero does that. It's a slightly fancier version than typically seen in chess, but the basic idea is that you check moves suggested by a network, and then see if they're any good by again consulting with the network to tell you if you're winning or not.

So the crux is the network. It takes board position as input, does some algebra on it using very particular formula with certain coefficients on each input "feature"(which in this case probably are numbers indicating what each square holds, so 0 for empty, 1 for white pawn, 2 for white knight, etc). Which is simple to do, but the question then becomes, how did we get these coefficients for our formula?

So we enter learning phase. Our network outputs move suggestions with some weight of "how good is this move". What one can do is take bunch of games, and for each coefficient check if nudging it up or down a bit would've made moves in won games weighted as more promising ones, on average. If either action helps, do that. Do so for each of the millions of coefficients. Now you've nudged the network a bit, and the hope is that it's playing slightly better than before. So Google would have it play itself again thousands of times, then repeat the process with those new games, nudging coefficients a little again, then play, then nudge, etc. That would be repeated hundreds of thousands of times.

So the engine just updates coefficients as it learns. Initially they're set to random numbers.

Also the idea isn't that the network remembers past games. Rather, it's been tweaked so that it would make successful moves in the situations its encountered before, and the hope is that simplest way to do this is by developing an "idea" of what good chess looks like. I really don't know how to prove it happens though

4
_mess_OP•

So the crux is the network. It takes board position as input, does some algebra on it using very particular formula with certain coefficients on each input "feature"(which in this case probably are numbers indicating what each square holds, so 0 for empty, 1 for white pawn, 2 for white knight, etc). Which is simple to do, but the question then becomes, how did we get these coefficients for our formula?

my question would be more about the formula tbh, how could it come up with a formula

which is the biggest problem I have asked around, for easy games like TTT or similar the node can be anything cause the combinations are really very limited but in chess you cant, also there isnt much correlation between a single tile and a single piece per se, having a N on A1 is generally worse than having it on C3 ofc but that can't really lead to anything, positions must be evaluated from the whole scenario

So Google would have it play itself again thousands of times,

ok but how many times did it play in only 4 h?

it would make successful moves in the situations its encountered

the problem is what is this "situation" you are talking about? IF it is the position then IT MUST memorize every single position, which is actually impossible

Another big question is how it can even be able to play a super bad or super good situation. I mean chess endings are very long and complex and can't really have played them all cause the move combinations would be absurd, one of trhe game I watched there was a clearly won but super difficult ending with a good exchange (R for N I think and 1 less pawn or similar) and it took 100 moves or so, Stockfish could evaluate on the spot in fact his resistance was fierce and long, but not being able to evaluate something new seems to make some situation impossible

But this was a digression the question was, if I am a human in a lost scenario and do a even worse move like exchanging my N for a Pawn or something, this is something AlphaZero cannot have encountered often being a losing situation, it shouldn't be able to even play such situation

Thank for your help but still raised more doubt about the whole thing

1
piotor87•

Brief explanations:

AlphaMind uses MonteCarlo Tree searches. In order to "understand" if a move is good or not it plays games and checks if the outcome of the games (win/loss/draw) is compatible with the prediction it had made of whether that move was winning or not (good or bad in general). The algorithm then changes the weights that calculate the evaluation of the position in order to match the outcome.

In 9h the program played 44 million games.

In general though I think you have interesting questions but that stem from a very poor knowledge of how neural networks work. Trying to understand directly how learning to play chess works is not absolutely easy and I suggest you check on simpler NN that solve "easier" problems. On the internet you can find some similar examples of NN that learn to play simple videogames such as mario or driving video games.

The whole point is that NN have the ability to "generalize" concepts in a way that resembles the way we think.

Imagine a driving game where you need to implement a turn. If you were to write a script to drive like stockfish you'd have to have it always check how much the road is bending and adjusting the turning of the steering wheel so that the curvature of the road and of the turn of the car match. If you then want to improve speed you need to implement a function that understands the compromise between speed and angle of the curve in order to minimize the running time.

A NN instead learns from previous runs that being in the part of the road with a higher curvature is more beneficial than being in the middle or the opposite side. Similarly, it knows that the fastest it goes the better in general, but also that if it goes too fast and crashes it will be less beneficial. Of course there's thousands and thousands of different curves possible, but even though the NN hasn't seen all of them it learns to generalize the concept of a turn. Similarly, even though AlphaZero hasn't seen all chess positions it has learned to understand their basic properties and it has learned "rules" that will be valid in most of them.

3
_mess_OP•

I know I lack something but still there are points that logically makes no sense

take your super mario example, the mario game is always the same, the NN only have to understand "ehy I am in level 3 segment 3, now I know I have to jump 3 times etc etc"

Its easy to recognize the situation, unlike chess, which can be difficult

My problem is how to "recognize" the position to ask the network about, when each position is totally different

Same with the driving example "ehy there is a turn, you ask how to drive a turn, but in chess "ehy there is a queen", but there always is a queen, what matters is how the queen is positionated compared to all other pieces right?

Anyway if you have resources to consult I would gladly give them a look

1
piotor87•

Just like in a track there are thousands of possible turns that can be somewhat "aggregated" in types (left or right? small angle- large angle? sharp or not?) similarly a chess NN can recognize the "position". This reminds me of when I hear GM commentary saying "this is a typical motif in these kind of positions" and I have absolutely no clue what they mean with it. Similarly, the chess NN understands the similar structures and is able to use the knowledge learned in one of these situations to apply it in another one.

Also, bear in mind that the NN does calculate stuff. It just doesn't brute force it but it does (in the training phase) play games until the end to check if its intution is working correctly or not. At the end of each batch of games, the NN adapts its weights (i.e. its intuition) to match the game outcome.

If you want a simple example check out this video: https://www.youtube.com/watch?v=Aut32pR5PQA

here a simple neural network (only 5 inputs, ~20 nodes and 4 layers) is able to learn to drive in ~50 generations. A0 instead has 119 inputs and an unspecified number of nodes. For comparison Alpha go had 13 layers!

2
wokcity•

No it doesn't work that way. It doesn't recognize the situation in absolute terms, it understands it based on statistical abstractions that arise from the training the network. It doesn't care if it's in level 3 segment 3 or not, it cares about what is actually being presented. That's why classical chess engines are primitive and this thing is not. It's able to create a 'mental model' like we do and then applies it to new situations it hasn't seen before.

1
Sulleyy•

Heres a general explanation. A neural network consists of many individual "neurons". When training a neural network you're just fine tuning the thresholds that make these neurons fire. The combination of all of these neurons are intended to act like a brain but the information that each individual neuron is focused on doesn't make sense to humans. That's how it's able to analyze a full chess position without memorizing every position it's ever seen, the neuron values just improve over time.

1
KapteeniJ•

the problem is what is this "situation" you are talking about? IF it is the position then IT MUST memorize every single position

Network doesn't. Training program does.

It's a question of, if you tweaked one coefficient up, then you go through every single game and every single move in those games, and run the network again for each of those, and check if the winning moves(moves made by player who won the game) would've on average risen or fallen on how much network recommends them.

AlphaZero cannot have encountered often being a losing situation, it shouldn't be able to even play such situation

AlphaZero has no memory. The idea is that instead of memorizing games, it simply gets better at recognizing what a good move in chess looks like, so if you put yourself in bad situation, it's still gonna play good moves.

ok but how many times did it play in only 4 h?

Not sure exactly, but on the ballpark of millions of games.

my question would be more about the formula tbh, how could it come up with a formula

random coefficients which were step by step tweaked to make winning moves pop up more often.

also worth noting that the algebra connecting inputs and outputs is complex. There are some billions of coefficients to it.

2
balackLT•

Well, for one thing, a huge database does not in any way contradict the concept of "AI". Our brains don't work that much differently. They just efficiently traverse a large array of positions that you remember - that is have stored somewhere in memory.

As Dijkstra said: "The question of whether machines can think is about as relevant as the question of whether submarines can swim."

3
_mess_OP•

Well, for one thing, a huge database does not in any way contradict the concept of "AI".

true, I just would like to know the real way it works, surely a super huge database would make it a bit less breakthrough

Our brains don't work that much differently.

well, it kind of does, we dont store every car but we know what is a car cause we can extrapolate from other elements, having 4 wheels, moving, place to drive, etc

some ppl seems to believe this engine is like a nearly human while I found absolutely no evidence whatsoever, maybe I am wrong, that's why I am asking but didn't get much explanation till now

2
EvilNalu•

well, it kind of does, we dont store every car but we know what is a car cause we can extrapolate from other elements, having 4 wheels, moving, place to drive, etc

That's also what a neural network does. I think this is the gap in your understanding. The neural network does not just build a database of everything that can be a car and then look for a perfect match. It "learns" the features of cars and if you train it on a bunch of pictures of cars, then it will learn what a car looks like in general and be able to identify new pictures it has not seen before as cars, just like a human can. Same idea with chess. It "learns" what positional features are good and what types of moves are good. It's not just a tablebase with a bunch of positions memorized.

The problem is it's very hard to describe what's going on because at the end of the day the network is essentially a black box that you feed inputs and get outputs from but you can't really describe how it is arriving at these outputs in a meaningful conceptual way like you can with some other algorithms. Of course, you know the math behind it and how the network is structured but you can't really distill it any further than that.

1
_mess_OP•

yeah but a pixel is a finite serie of pixels, and a car is a fixed object, unlike chess, my problem is not understanding the learning part, the problem is starting the procedure of evaluating a position, if, like you all say, this process is drastically different from the usual engines

1
ZibbitVideosFIDE Master/Trainer 2377•

I dont really understand but isnt this just learning? It starts with playing itself. At some poont it figures out losing the Queen isnt good. It doesnt know how to mate with it but eventually learns. So gradually it learns about material. Right there playing itself the gamed becone more quality. At some point the learning progresses and it starts to understand structure...dynamics etc. This is what makes sense to me but I dont know enough to know if thats the way it is.

2
_mess_OP•

yeah it makes sense for a human, but I am quite confidently sure an engine cannot ever understand "structure", but I do have doubts though

1
ZibbitVideosFIDE Master/Trainer 2377•

I think it understands certain structures but each engine is differently programmed to deal with those aspects.

1
kazedcat•

Equation can describe structure. It can describe lines, circles and any kind of shape. In higher mathematics it can even describe the sequence of moves to solve a Rubik's cube. Yes there is an equation on how to solve a Rubik's cube. The problem is finding the equation. Neural network is a formalised way to find an approximate equation. The training process is a guided way to find the equation. It is a giant multi-dimensional calculus.

1
_mess_OP•

Yes but in all these case the "equation" must be set up prior to "solving" it

In A0 case nobody seems to know even slightly how it was set up

It's too easy to say there is an equation and there are coefficient, like you say that is true for nearly everything in life, given the proper setup which was the point of it all

1
kazedcat•

We know how the equation was set up. It was in the previous two papers. In fact there is an open source recreation of Alphago Zero. The hard part is reproducing all the coefficient you need millions of self play game for that. It is like having points and you need a curve that fit those points. The curve is describe by an equation. You can use math to find the equation of the curve. Once you have the equation you can quickly tell if a point lie's on the curve or not even if the point is not one of the sample points you use to find the equation. Now extend it to multi dimensional space with thousands of dimension. The points are now the set of all moves. The curve is the set of moves with winning probability of 1 and the shortest distance between the point and the curve is the winning probability of that point. You don't need to examine all points you just need a sample of points big enough that the curve you will create is a good approximation of the winning curve. Once you have the curve you can just search the points representing the current legal moves and choose one with the highest win probability.

1
keinespur•

The system works by having a set of inputs, in this case probably one for every square on the board and a few others for the game state so that it knows how to avoid draws and castling rights.

These inputs get sent individually to specific nodes, where some information is extracted about their relationships and their "importance" to the AI. What it finds important is not something we actually know. The outputs are likely a set of probabilities (my understanding is that a Bayesian probability is used), some of that information gets saved (this is the short term memory), and it the probabilities are passed to the next layer as inputs.

That process gets repeated through all 40 layers, where it's continually building a set of "this is probably important to me" outputs, and telling the next layer what was probably important from the last, until it picks a move that is probably good in that position.

During training multiple games get played against itself, starting with no knowledge, so at the beginning it's generating those probabilities effectively randomly. As it's "learning" in each generation it adjusts the "weights" on each node (or relationship) for how important they are to itself using some calculus. After a set of games the versions that are performing "best" are combined in some possibly random method, and the values of some of the nodes in the network are forcibly shifted to different values so that children have some of the traits of the last generation but are forcibly different to help them find values that are maybe better at those points. The selected parents from the last generation are kept also, and then the process repeats.

The evaluation is based on whatever the NN thinks is statistically important from its previous history and what has performed the best.

In an actual game if it encounters a position its never met before it will select a move that it thinks is probably best. This is done by generating a move tree like any other engine, probably from a set of candidate moves (actually a very human method) and then evaluating a random selection of nodes in that move tree for how probably good they are -- the "randomly pick nodes from tree to test for goodness" is the Monte Carlo part.

A good way to think of it is if I were to show you paint chips of red and green colors and have you pick whether I THINK red or green, it's easy for you to say green, forest green, emerald green, etc are green, and red, pink, burgundy, wine, etc are red. But as the colors get more orange or more yellow -- combinations of red and green -- you might need to go "well, that's like 45% red and 55% green, so it's probably green". But you're guessing my answers, so let's say I'm insensitive to green or extra sensitive to red, over time you'll adjust your guesses and go "well, that's like 30% red, and 70% green, but this guy can't see green as well so he probably thinks its red still."

That's done a lot of times so that AZ can pick what it thinks is probably a good choice for the position it's looking at.

2
_mess_OP•

All of this is very clear, what is unclear is the process of "unwrapping" the position and searching each node for that something

Also what is left after the NN work?

1
keinespur•

I'm not sure what you're asking about "what's left."

There is no unwrapping or searching of the nodes. Again, each node is configured to an input or a relationship of the inputs, and how important that node is given the inputs is adjusted internally during training. It's a simple value goes in, probability comes out.

Using the color analogy above, if I give you web color of #FF0000, you could say with 100% certainty that's red. If I give you one that's maybe #CC5500 you could maybe assign a probability of 70% I'll think it's red and 30% I'll think it's green to it. The inputs here (RGB values) map directly to some probability of how much I'll think it's red or green.

At the end of that you go "Well, the highest probability this is the right choice is X" so you answer X.

1
_mess_OP•

ok but again this is easy to do and understand

What doest each node of AlphaZero hundreds do? How do they different from each other ?

1
programmerChilli•

Do you understand how a neural network for image classification works? It seems to me that most of your questions would apply equally well to image classification.

For image classification at least, there's this great visualization of "what each node out of hundreds do", as well as how they're different from each other: https://distill.pub/2017/feature-visualization/appendix/

1
repaeR_mirG•

there is a good youtube channel "3Blue1Brown" which goes through what a NN is:

https://www.youtube.com/watch?v=aircAruvnKk

2
Harawaldr•

Have you read the paper?

If not, start there and see what remains confusing.

1
TommyTheTiger•

How do you remember a game? Did you save it in a database in your head? The way a convolutional neural net learns is as close as we know how to emulate the way that animals learn. The "memories" are stored as weights on connections between "neurons" in this modeled network.

1
_mess_OP•

no, but I memorize some concept, like rook on free lane, opposite bishops etc, which is teh same way(in surface) as a normal engine does the evaluation

1