ML Newsnew | past | best | rss | submit about
Multiplayer AlphaZero (arxiv.org)
53 points by hardmaru on Oct 30, 2019 | hide | past | pdf | 17 comments on HN

In plain words: AlphaZero normally learns two-player games by playing against itself; here it is adjusted to handle three or more players at once. In two simple three-player games, it learned winning strategies and consistently beat the usual tree-search player that guesses ahead by sampling random games.

Abstract

The AlphaZero algorithm has achieved superhuman performance in two-player, deterministic, zero-sum games where perfect information of the game state is available. This success has been demonstrated in Chess, Shogi, and Go where learning occurs solely through self-play. Many real-world applications (e.g., equity trading) require the consideration of a multiplayer environment. In this work, we suggest novel modifications of the AlphaZero algorithm to support multiplayer environments, and evaluate the approach in two simple 3-player games. Our experiments show that multiplayer AlphaZero learns successfully and consistently outperforms a competing approach: Monte Carlo tree search. These results suggest that our modified AlphaZero can learn effective strategies in multiplayer game scenarios. Our work supports the use of AlphaZero in multiplayer games and suggests future research for more complex environments.

Nick Petosa, Tucker Balch
arXiv:1910.13012 · cs.AI · submitted Oct 29, 2019 · updated Dec 9, 2019
abstract · pdf · html

add comment on HN

Mageek on Oct 30, 2019 [–]
Nice and concise paper. All that changed was outputting a vector of predicted game values, as we go from having a zero-sum game with two players (which can be summarized with a single value) to a game with n players. Makes sense.

The comparison against MCTS shows strong performance from AlphaZero. Would be curious to see the performance of AlphaZero vs. number of its own rollouts - ie is the probability head output alone already encoding enough information to play well, and how deep does it have to look ahead to determine good play. Finally, for tic-tac-mo and connect 3x3, it should be possible to determine the optimal move. How much training / lookahead is required to achieve that? Does AlphaZero achieve perfect play for these games?

The paper's first listed contribution is "an independent reimplementation of DeepMind's AlphaZero algorithm". Maybe I missed it, but I don't see a link to a repo with the implementation.

reply
gok on Oct 30, 2019 [–]
Interesting results but they really only use toy examples (Tic-Tac-Toe and Connect Four). It would be kind of surprising if it didn't work.
reply
jstrong on Oct 30, 2019 [–]
> e.g. equity trading
reply
narrator on Oct 30, 2019 | parent [–]
As much as I liked to get excited bout these kinds of papers:

"Recomputing the AlphaGo Zero weights will take about 1700 years on commodity hardware."

[1] https://github.com/leela-zero/leela-zero

reply
fnbr on Oct 30, 2019 | parent [–]
Yeah, but that's an embarassingly parallel task, so you can recreate it with sufficient resources. If there's a sufficiently lucrative application, businesses will happily pay that.
reply
dmurray on Oct 30, 2019 | parent [–]
And it's already been done for the chess version, in a community effort[0]. Well, "recomputing the weights" isn't plausible for a neural network of this size, but computing weights that give the network a similar level of performance.

[0] https://lczero.org/

reply
narrator on Oct 30, 2019 | parent [–]
One thing I think that will be critical to the future of software is community efforts to build deep neural nets that match the AI power of the big companies.
reply
pixelpoet on Oct 30, 2019 | parent [–]
There are newer approaches where specialising for the problem domain (Go) gets you a 5-100x speedup: https://github.com/lightvector/KataGo/
reply
make3 on Oct 30, 2019 | parent [–]
Indeed that's a weird thing to say, especially since AFAIK AlphaGo is for (very large) discrete search spaces (where Monte Carlo Tree Search would be used), & equity trading doesn't strike me as a discrete search space.. is it ?
reply
dmurray on Oct 30, 2019 | parent [–]
Yes? At any point in time you can buy or sell a discrete number of shares in a finite universe of stocks.

The bigger difference in equity trading is that it's a "game" of hidden information with asymmetric and maybe unknown payoffs. Of course, computers are pretty good at trading stocks, too, but I can say confidently AlphaZero won't be the most useful approach.

reply
make3 on Oct 30, 2019 | parent [–]
A part missing in your analysis is that time is involved in the decisions, and that time is continuous, and that time is very important
reply
falcor84 on Nov 2, 2019 | parent [–]
Is time really continuous in this case? I have absolutely no idea how it's implemented in practice, but would assume that stock exchange computers use some sort of game loop at a consistent rate.
reply
degski on Oct 30, 2019 | parent [–]
Sound is not discrete either, it does not seem to be a problem on computers, though.
reply
make3 on Oct 30, 2019 | parent [–]
That's the feature space, not the decision space
reply
amitport on Oct 30, 2019 | parent [–]
Well at least the second author, Tucker Balch, is a computational investing consultant / lecturer. I'm sure they'll continue to work this angle, even if it's not yet there.
reply
mrleiter on Oct 30, 2019 [–]
Anyone who's interested to see how brilliant AlphaZero played against the best chess computer (then), with solid explanations: https://www.youtube.com/watch?v=lFXJWPhDsSY
reply
dmurray on Oct 30, 2019 | parent [–]
I'd recommend instead the videos made by Matthew Sadler for chess24[0]. Unlike the guy in your videos, Sadler is a strong chess player and literally wrote the book [1] on Alphazero. The videos are approachable for all levels of chess ability.

[0] https://www.youtube.com/playlist?list=PLAwlxGCJB4NchyTBYik8F... [1] https://www.newinchess.com/game-changer

https://www.youtube.com/playlist?list=PLAwlxGCJB4NchyTBYik8F...

reply
About | RSS | RSS (all) | HN arXiv