Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

Alpha Go Zero: How and Why It Works

tim.hibal.org

Post reply on HN
Print view View original

91–100 of 116 posts

Re: Alpha Go Zero: How and Why It Works

#91

Post by nojvek »

gizmo686 wrote: post #51
bluetwo wrote: post #46

Saw the AlphaGo movie at a festival recently. Been following the AlphaGo Zero developments, which leap-frog what was going on in the movie (although still very much worth seeing). One thing I was curious about is if Go would be considered solved, either hard or weakly solved, since AlphaGo Zero at this point doesn't seem to be able to be beat by any living human. Wikipedia does not list it as solved in either sense,…

Go still has not been Ultra-weakly solved (eg. we do not know who is supposed to win). If AlphaGo has weakly solved go, then it should either have a 100% win rate when playing against itself as white, or a 100% win rate when playing against itself as black.

Or 100% rate of a draw. Like tic tac toe.

Re: Alpha Go Zero: How and Why It Works

#92

Post by nilkn »

shghs wrote: post #26

The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a g…

Are you sure AlphaGo Zero even uses temporal difference learning? The Nature paper suggests it does not and merely references some older programs that did. I think it just uses a somewhat custom form of self-play reinforcement learning combined with MCTS.

Re: Alpha Go Zero: How and Why It Works

#93

Post by thom »

nojvek wrote: post #89
naveen99 wrote: post #79

Earlier quoted context omitted.

There was a project for chess, called giraffe https://bitbucket.org/waterreaction/giraffe whose author shut it down after joining google deep mind: http://www.talkchess.com/forum/viewtopic.php?t=59003 He thinks it's only a matter of time till machine learning beats hand crafted systems like stockfish even in chess. http://arxiv.org/abs/1509.01549

Does alphazero beat stock fish purely by self play. That would be huge. Stock fish is the result of so many hand crafted optimizations over a large game play dataset.

Intuitively you'd expect deep learning to improve on Stockfish's evaluation of positions, but perhaps not at the same level of throughput. I'm also intrigued as to whether a purely self-taught AI system can compare in the endgame to an engine with access to a 7-piece endgame tablebase, whose evaluation of those positions is obviously _perfect_.

Re: Alpha Go Zero: How and Why It Works

#94

Post by nilkn »

erikb wrote: post #83

I don't get what is new in the set of attributes that this article describes. Monte Carlo was already used in 2005 in AIs playing on KGS. Gradient Descent is a basic algorithm is a basic algorithm that I saw in an AI class in ~2008 as well. I bet both are even a lot older and well known by all experts. This is not what makes AlphaGo special or Zero successful. The curious thing about Zero is that usually with Gradien…

> The curious thing about Zero is that usually with Gradient Descent you run a huge risk of running into a local maximum and then stop evolving because every evolution makes you not better than the current step.

Deep networks have many parameters and represent extremely high-dimensional cost functions. Some basic heuristics suggest that sufficiently random high-dimensional functions have relatively few local extrema, but lots of saddle points. (Look at the signs of the eigenvalues of the Hessian matrix and apply a coin flipping argument. This suggests that local extrema become exponentially rarer as the dimension increases.)

Moreover, stochastic gradient descent is actually pretty good at escaping saddle points.

Re: Alpha Go Zero: How and Why It Works

#95

Post by falcor84 »

alkonaut wrote: post #86
falcor84 wrote: post #82

As someone who has played many a game of Tic-Tac-Toe, I found the numerical examples really hard to follow. s(0,5) is obviously the winning move for the X player, but for some reason all examples seem to favor s(0,1).

Winning move how? With which board? with O__ _X_ O_X Then X can't win in the next move and must choose (0,1) between the two O's the left column in order to not lose.

D'oh, thanks. I suppose I just misread the oh's.

Re: Alpha Go Zero: How and Why It Works

#96

Post by fspeech »

Given that AlphaGo Zero was trained on several million games of self plays, each game involving hundreds of steps, each step with 1600 MCTS simulations, the total number of board positions it has considered is on the order of trillions. While impressive it pales in comparison to the number of possible board positions of 10^170 (https://en.m.wikipedia.org/wiki/Go_and_mathematics). So its amazing performance tells us that:

1. Possibly the elegant rule of the game cuts down the search space so much that there is a learnable function that gives us optimal MCTS supervision;

2. Or CNN approximates human visual intuition so well, so while Zero has not evaluated so many board positions it has evaluated all the positions that human has ever considered - so it remains possible that a different network could produce different strategies and be better than Zero.

Re: Alpha Go Zero: How and Why It Works

#97

Post by gamegoblin »

nojvek wrote: post #91
gizmo686 wrote: post #51

Earlier quoted context omitted.

Go still has not been Ultra-weakly solved (eg. we do not know who is supposed to win). If AlphaGo has weakly solved go, then it should either have a 100% win rate when playing against itself as white, or a 100% win rate when playing against itself as black.

Or 100% rate of a draw. Like tic tac toe.

Due to komi, a go game cannot be drawn. That is, the 2nd player is awarded some number of points for the disadvantage of moving 2nd, and that number of points typically has a fractional 0.5 in it to break ties.

The most common komi values these days are 6.5 or 7.5, depending on ruleset.

Re: Alpha Go Zero: How and Why It Works

#98

Post by dfan »

_0ffh wrote: post #64
shghs wrote: post #26

The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a g…

For anyone interested: Learn more on TD and RL in general from Sutton (inventor of TD-lambda) and Barto's book: http://www.incompleteideas.net/sutton/book/the-book.html Sidenote: It used to be that simply googling "sutton barto book" would bring you to the right place with the first suggested link. Now this stuff is so popular all of a sudden, I needed to consult the link I had set on my own page in order to find it.…

Here is the latest publicly available draft of the 2nd edition (June 2017, 538 pages): http://incompleteideas.net/sutton/book/bookdraft2017june19.p...

Re: Alpha Go Zero: How and Why It Works

#99

Post by psb217 »

nilkn wrote: post #92
shghs wrote: post #26

The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a g…

Are you sure AlphaGo Zero even uses temporal difference learning? The Nature paper suggests it does not and merely references some older programs that did. I think it just uses a somewhat custom form of self-play reinforcement learning combined with MCTS.

You are correct. There is no TD learning in AGZ. The value network is trained to directly predict the game outcome given the current state, and is not trained through "bootstrapping" based on the next state's value estimate.

Re: Alpha Go Zero: How and Why It Works

#100

Post by psb217 »

gabrielgoh wrote: post #37
shghs wrote: post #26

The main reason AlphaGo Zero learns so much faster than its predecessors is because it uses temporal-difference learning.[1] This effectively removes a huge amount of the value network's state space for the learning algorithm to search through, since it bakes in the assumption that a move's value ought to equal that of the best available move in the following board position, which is exactly what you'd expect for a g…

could you elaborate on this point? what you're saying sounds like dynamic programming, which does not reduce the state space at all, just saves on redundant computations (and is a favourite of programming interviews everywhere)

Training via bootstrapping (i.e. dynamic programming) does reduce the state space for search when working with function approximation. It represents a bias in what sorts of values the value function approximator should predict for each state. It encodes a sort of "local continuity/coherence" constraint that wouldn't necessarily be induced by simply training to predict the raw values -- collected stochastically via interaction with the environment. This local coherence constraint acts as a regularizer (i.e. bias) while training the value function approximator.
Post reply on HN