Building an AlphaZero AI using Python and Keras

Regarding supervised learning, what data do you use? Would it make sense to use endgame tablebases[1]?

1. https://en.wikipedia.org/wiki/Endgame_tablebase

I've been having fun following along with Leela Zero, it's a great way to understand how a project like this goes at significant scale. Good luck with Leela Chess, I'm excited for it!

From the leela-zero page :

> If your CPU is not very recent (Haswell or newer, Ryzen or newer), performance will be outright bad,

Obviously TPU >> GPU >> CPU

But are there special vector instructions added in Haswell? Or is this just general preference for a multi core newish cpu ?

What does SPRT stand for in that context?

This is really cool! The chart on that page makes it look like Leela Zero is already much much better than AlphaZero (~7400 Elo vs ~5200 Elo). I suspect I'm misinterpreting something though, could you clarify?

The irony here being you're using Stockfish move representation in a codebase written by the author of Sjeng :-)

To benchmark A0 further, you can take whatever NN you're training and instead train it against the 'ground truth' of Velena's moves when going first (the NN predicts for each possible move if Velena would take it or not, 0/1 labels). Then one can know how close does the A0 NN trained via expert iteration approaches the Velena-supervised NN and how much compute is spent on the need to train from scratch?

The Fhourstones benchmark at http://tromp.github.io/c4/fhour.html solves the 7x6 game in under 2 minutes. The "make C476" version at https://github.com/tromp/fhourstones88 also maintains a book, allowing for much faster replies.

MCTS has always been popular and probably the best online/out-of-the-box MDP technique. But fundamentally its different than RL methods. In MCTS you assume you have a perfect simulation of the MDP which is rarely true outside of games. MCTS also doesnt really have a learning phase.

> My intuition is that MCTS is better for planning, but takes longer to train/evaluate.

There is no training phase in MCTS, rollouts can take a while, its important to have a fast simulator and rollout policy (like random/UCT).

> Is there some games one will work better than the other?

Games with simulators and perfect information!

It has been a while since I read the paper, but I believe they have some results where they ran AlphaZero without MCTS, using only the policy network. My recollection is that is still performed pretty well, but it was clearly outperformed by MCTS.

In vanilla policy gradient, one plays the game to the end and then bumps the probability of all actions taken by the agent up (if AlphaGo won) or down (if it lost). This is very slow because there ~150 moves in an expert game, and we do not know which moves caused decisive victory or loss - i.e. the problem of "long term credit assignment". Also, it is actually preferable to compute the policy gradient with respect to the advantage of every action, so we encourage actions that were better than average and punish actions that were worse than average - otherwise the policy gradient estimator has high variance.

I think about MCTS in the following way: suppose you have a perfect "simulator" for some reinforcement learning task you are trying to accomplish (i.e. real-world robot grasping for a cup). Then instead of trying to grasp the cup over and over again, you can just try/"plan" in simulation until you arrive at a motion plan that picks up the cup.

MCTS is exactly a "planning" module, and it works so well in Go because the simulator fidelity is perfect. AlphaGo can't model adversary behavior perfectly, but MCTS and the policy network complement each other because the policy reduces the search space of MCTS. As long as the best adversary is not far away from the space that MCTS + policy is able to consider, AlphaGo can match or beat the adversary. Then, we train the value network to amortize the computation of the MTCS operator (via Bellman equality). Finally, self-play is an elegant solution for keeping adversary + policy close to each other.

For more rigorous mathematical intuition, Ferenc Huszar has a nice blog post on MCTS as a "policy improvement operator": http://www.inference.vc/alphago-zero-policy-improvement-and-...

The MCTS variant used by AZ offers a big advantage in the exploration/exploitation tradeoff, with a better exploration profile during training and better exploitation during competitive play.

The training phase emphasizes exploration using a modified upper confidence bound for tree search criteria to limit the expansion of the search tree. With a uniform prior over the action space (like standard MCTS), you will explore a large number of unlikely actions. The prior provided by the NN allows them to bootstrap the value of leaf nodes _and_ efficiently sample the actions at each state. AZ has eliminated the simulation phase of MCTS entirely.

AZ uses different criteria for move selection during training and during competitive play. The competitive selection criteria basically replaces the UCBT criteria with standard argmax over the actions (like a normal RL policy selection). We know that tree pruning can be very effective during search _if_ you can order the nodes in a beneficial way. AZ MCTS uses the output of the NN as the prior instead of a uniform prior, which is like a "virtual" pruning (because moves with low probability in the prior are unlikely to be explored). This tends to more quickly focus the search on strong lines of play, so the algorithm produces strong choices with less search (AZ uses about an order of magnitude fewer expansions than other state-of-the-art MCTS engines).

Direct link: https://www.netflix.com/title/80190844

And here is a much lower budget (but still enjoyable) documentary about Fine Art, an AlphaGo clone by the Chinese company Tencent:

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

Favorite line from it: "AI blew the gates of the Go palace open. And we realized there was no one inside."

Another interesting thought was when one of the developers gets asked why bother to clone AlphaGo when AlphaGo already exists, he says something like "Was it pointless for China to develop the atomic bomb even though the USA already had?"

Watching this now. 10 minutes in and loving it, thanks for the recommendation.

One thing I found strange about that documentary was how little mention "Google" got. Unless I missed it, the acquisition wasn't even mentioned.

I've only skimmed it a little bit so far, I'm just wondering, if both players use the optimal strategy, shouldn't the game always result in a draw?

Which is why I was a bit confused by the target '80% Win/Tie rate going second', but I could well be missing something.

Edit: I'm an idiot, I see that the opponent takes random moves now. Seems a fun project :), a while ago I built a very simple rule-based tic-tac-toe thing in lisp, but the rules were all hardcoded alas.

you'll have to summarize your work better than this if you want any meaningful feedback

I don't think it's Office Code Pro but it looks very similar to me. Maybe that helps you with the search!

Looks like SF Mono.

Try this - https://medium.com/applied-data-science/how-to-build-your-ow...

The link looks https to me, but this is where it redirects if that's of any use: https://medium.com/applied-data-science/how-to-build-your-ow...

Too vague. Do you predict that AlphaZero will not be able to beat humans in a game like Go but where there's 1 in 100 chance for a stone to land in unintended place?