# Tag Info

14

Good question. First and foremost is that in Go deepmind had no superhuman opponents to challenge. Go engines were not anywhere near the highest level of the top human players. In chess, however, the engines are 500 ELO points stronger than the top human players. This is a massive difference. The amount of work that has gone into contemporary chess engines ...

7

The output of the policy network is as described in the original paper: A move in chess may be described in two parts: selecting the piece to move, and then selecting among the legal moves for that piece. We represent the policy π(a|s) by a 8 × 8 × 73 stack of planes encoding a probability distribution over 4,672 possible moves. Each of the 8×8 ...

6

DQN and AlphaZero do not share much in terms of implementation. However, they are based on the same Reinforcement Learning (RL) theoretical framework. If you understand terms like MDP, reward, return, value, policy, then these are interchangeable between DQN and AlphaZero. When it comes to implementation, and what each part of the system is doing, then ...

6

Monte Carlo Tree Search is not usually thought of as a machine learning technique, but as a search technique. There are parallels (MCTS does try to learn general patterns from data, in a sense, but the patterns are not very general), but really MCTS is not a suitable algorithm for most learning problems. AlphaZero was a combination of several algorithms. ...

5

Note: you mentioned in the comments that you are reading the old, pre-print version of the paper describing AlphaZero on arXiv. My answer will be for the "official", peer-reviewed, more recent publication in Science (which nbro linked to in his comment). I'm not only focusing on the official version of the paper just because it is official, but also because ...

4

John's answer is correct in that MCTS is traditionally not viewed as a Machine Learning approach, but as a tree search algorithm, and that AlphaZero combines this with Machine Learning techniques (Deep Neural Networks and Reinforcement Learning). However, there are some interesting similarities between MCTS itself and Machine Learning. In some sense, MCTS ...

4

MCTS for chess had been tried in the literature with little success. It was assumed AlphaGo's approach would never work on chess, maybe in Go but not in chess. Suddenly, Google announced the approach was working and it was beating the World's strongest chess program by a very signficiant margin. Before Google, all chess programmers were taught crafting ...

4

Assuming you mean a mathematically perfect player, similar to what we can achieve trivially in Tic Tac Toe, then the answer is "maybe". The underlying reinforcement learning algorithms that it uses do have some convergence guarantees, but there are some caveats: Theories of convergence that apply to value and policy functions learned by RL assume ...

3

The more you read, the more deeply you can understand any paper, but given your stated background, reading the Monte-Carlo Tree Search chapter of Barto & Sutton, plus Gerald Tesauro's TD-Gammon paper (which is pretty accessible, and which is the basis for the other technique used in AlphaZero) should be enough to get a pretty good idea of what they did.

3

To my understanding, this is basically a supervised learning problem, where from the self play we have games associated with their winners, and the network is being trained to map game states to likelihood of winning. Yes, although the data for this supervised learning problem was provided by self-play. As AlphaZero learned, the board evaluations of the ...

3

We cannot tell with certainty whether AlphaGo Zero would become perfect with enough training time. This is because none of the parts (Neural Network) that would benefit from infinite training time (= a nice approximation of "enough" training time) are guaranteed to ever converge to a perfect solution. The main limiting factor is that we do not know whether ...

3

Neural network will eventually reach limit of it's approximation power. You can't expect to learn more and more things infinitely long with the same amount of learnable parameters. Also, if you eventually reach optimal performance, you can't play more optimal than what optimal is (not saying that it reached optimal performance but possibly something close to ...

3

It means that there is no explicit coding of action choices to promote to queen, it is the default assumption if the underpromotion actions are not taken. The Alpha Zero chess implementation can represent promotion to queen by not selecting an underpromotion action, whilst moving a pawn so that it qualifies for promotion.

3

Let's define your problem from another point of view. Let's say that in this RL problem you have two agents (agent1 and agent2) that compete with each other in order to accomplish their own goal, i.e., wining connect4 game. Therefore, we could say that from agent1's point of view, he is player1 and the player2 is agent2. The same way, from agent2's point of ...

3

On page 13, right under Table S1 in the linked paper, this is explained (emphasis in bold at the end mine): Each set of planes represents the board position at a time-step $t - T + 1, \dots, t$, and is set to zero for time-steps less than $1$. I suspect the solution they write there would indeed work better than just repeating the starting position up to ...

2

During the self-play training process, AlphaZero does not greedily play only the moves it thinks are "best" (which would normally be the move with the highest visit count leading out of the root node of the MCTS search tree). Instead, for the purpose of generating a more diverse set of experience, it samples moves proportionally to the visit counts. This ...

2

I see, based on the articles you provide, many levels of surprise in the victory: Chess is hard game to master and the counter part had the world's best practices, AlphaZero had tabula rasa. Learning took four hours and AlphaZero lost no match of 100. Playing style was an alien mix of human and computer like moves, aggressive and some times seeming ...

2

I am also a bit confused by your wording but I will try to clear some things up. During MCTS the policy head is used to guide the search while the value head is used as a replacement for roll outs to estimate how good the game position looks. One iteration of the search procedure in MCTS finds a new leaf node which has not been evaluated by the network yet. ...

2

The loss of the policy head here is really quite different from losses in, for instance, more "conventional" Supervised Learning approaches (where we typically expect/hope to see a relatively steady decrease in loss function). In this AlphaZero setup, the target that we're updating the policy head towards is itself changing during the training process. When ...

2

You're right that AlphaGo Zero doesn't perform rollouts in its MCTS. It does complete many, many games, though. Realize that AlphaGo Zero only iterates MCTS 1,600 times before taking an action. The next state resulting from that action becomes the root of future search trees. Since a typical game of Go only lasts a few hundred moves, the board will very ...

1

Yes it's possible to to combine AlphaZero with Minimax methods (including alpha-beta pruning). AlphaZero itself is combination of Monte Carlo Tree Search (MCTS) and Deep Network, where MCTS is used to get data to train network and network used for tree leafs evaluation (instead of rollout as in classical MCTS). It's possible to combine selection-expansion ...

1

The algorithm in the 2012 survey article (your second link) is the most common / standard implementation. Whenever someone mentions using MCTS or UCT, without explicitly stating any other info, it's safe to assume that that pseudocode is what they're using. The paper by Kocsis and Szepesvári from 2006 (your first link) is (one of) the original publication(s)...

1

You can actually combine AlphaZero-like approach with DQN: A* + DQN

1

Yes AlphaGo Zero could become undeniably perfect. It has won 100:0 against AlphaGo Lee (which won 4:1 against 18-time world champion (human) Lee Sedol) and 89:11 against AlphaGo Master (which won 60 straight online games against human professional Go players from 29 December 2016 to 4 January 2017). From the official AlphaGo website: "AlphaGo's 4-1 ...

1

No, ALL computer chess experts were surprised about the outcomes of the match. If you require references, please start a new question. Your question is simple... https://arxiv.org/pdf/1712.01815.pdf ... We evaluated the fully trained instances of AlphaZero against Stockfish, Elmo and the previous version of AlphaGo Zero (trained for 3 days) in ...

Only top voted, non community-wiki answers of a minimum length are eligible