4 ms·
I wonder how a machine learning approach like AlphaGo zero would do.
by tim333 9y ago
I wonder how a machine learning approach like AlphaGo zero would do.
- tromp 9y agoI think that on typical desktop hardware, there's little doubt that its cycles are much better spent on alpha beta search (with all its modern enhancements like late move reduction) and hand built evaluation function than on evaluating neural nets. If, however, your hardware were to include a few tensor processing units, then the answer is less clear (but I'd still bet on alpha beta).
- Recursing 9y agoI think it's really hard to parallelize alpha beta search, there might be a point where other approaches become more useful
- ZirconiumX 9y agoParallelising A-B has been done, but even the state of the art approaches like Lazy SMP (where there is no synchronisation between threads, and only at the root is effort made to disperse threads), YBWC (where only the first node is synchronised, and if it doesn't produce a cut is then parallelised) and DTS (where the threads choose their own work points) produce sub-linear scaling. I think research needs to be done on algorithms that are designed from the start to be parallel, but I'm not smart enough to do that.
- bluetwo 9y agoAlphaGo Zero is really about the MCTS not neural nets.
- Jach 9y agoMore specifically it's about driving MCTS with neural nets rather than pure random sampling as prior strong (but quite far from pro level) go bots were. Of course before AlphaGo was released there were papers on a pure deep net version of a go bot that beat Pachi and Fuego (both MCTS), not sure if it beat CrazyStone of the time.
- dragontamer 9y agoThe machine learning approach was applied to Go because there aren't any good heuristics known for the game of Go. In chess, a DAMN GOOD heuristic is that Queens are worth 9 points, Rooks are worth 5, Bishops / Knights are worth 3, and Pawns are worth 1. A few additional heuristics regarding "two bishops bonus", "passed pawn bonus", "Castled King bonus" and the like work really well in Chess. ---------- There's no equivalent to that in Go, so the best researchers could do was throw machine learning at it and hope for the best. EDIT: I'm well aware of Joseki (aka Openings) and Tesuji (Go "Tactics"). But Tesuji are not very easy to program. The alternative is maybe to apply the Monte-Carlo Search Tree to Chess instead of Go. All games end in Chess (due to the 50-move draw rule). But Chess is incredibly tactical, and its far more important to exhaustively see all possibilities 3 or 4 steps ahead rather than try to figure out how the endgame's position might look like. So Alpha-Beta pruning is likely a way better algorithm for Chess. A Machine Learning algorithm would have to figure out how to beat the current state of hand-programmed heuristics, which is not only incredibly efficient (due to bitboards and other optimizations), but also incredibly powerful.
- lozenge 9y agoAlphago Zero has beat all previous Go engines without examining any external games. I don't see any reason to believe Chess is a special game where humans understand it better (to write AIs) than computers can do "on their own". They are both turn-based deterministic games where the only asymmetry is which player gets the first turn.
- Recursing 9y agoLots of the parameters of the evaluation function are (at least in part) automatically tuned. Here https://chessprogramming.wikispaces.com/Automated+Tuning https://chessprogramming.wikispaces.com/Automated+Tuning you can fnd some of the most successful methods
- dragontamer 9y ago> without examining any external games That's only a big deal in Go circles, where Go computers have only been super-human for less than 2 years. Chess AIs are well known to have been super-human for decades now. Chess AIs are able to build the Chess game database backwards (ie: Tablebases) AND forwards (Opening Databases). There's very little human knowledge involved in a 6-move Chess Tablebase: https://en.wikipedia.org/wiki/Endgame_tablebase https://en.wikipedia.org/wiki/Endgame_tablebase . Indeed, computer-generation of Tablebases have REFUTED human knowledge, and modern Tablebases are way stronger than the entirety of chess knowledge that existed before computer analysis. Building Chess AIs "without human knowledge" has been going on for a long time now. The thing is, its very difficult to beat the SPEED of an assembly-language tuned count of bishop or rook moves. IE: The Magic Multiply / Bitboard method: https://chessprogramming.wikispaces.com/Magic+Bitboards https://chessprogramming.wikispaces.com/Magic+Bitboards ---------- The Chess AI game is played very differently from the Go AI game. In Go AI, "superhuman" programming techniques are still in its infancy. In Chess AIs, the game is mostly settling down upon speed, speed, SPEED. In many cases, a weaker heuristic that sees +1 or +2 moves into the future (due to being a little bit faster) is far better than a stronger heuristic that takes a bit longer to calculate. As such, a huge amount of Chess AI effort is in optimizing routines at the assembly level. Or perhaps data-structures that allow Opening Databases and Endgame Tablebases to be more efficiently utilized. In contrast, a lot of Go AI effort is in representing search trees... but not so much in speed or optimization right now.
- ZirconiumX 9y agoWe actually had an engine which was based on neural networks, called Giraffe. It used an alpha-beta search with a neural network evaluation. The Computer Chess Rating List put it at 2500 Elo, which is a strong human level. It was very slow, searching thousands of positions per second compared to the millions that even weak programs can do, but it's widely agreed that the NNs were worth about 300-400 elo - if Giraffe could search at Stockfish speeds, and given the rule of thumb that a doubling of speed is worth 70 elo, that's 2500 + 70 * log2(3000000/3000) = 3270 elo. That puts it in the top 20. Sadly the developer was pinched by Google to work in DeepMind. We suspect this was to help work on AlphaGo.
- supermdguy 9y agoJust curious, who's "we"?
- ZirconiumX 9y agoI was referring to the computer chess community as "we". My apologies.
- forgot-my-pw 9y agoGiraffe is open source. The author, Matthew Lai, was not part of the AlphaGo team. Current chess algorithm to evaluate board position is already very fast. A deep learning version needs to be trained for a long time and might still not be as fast. Maybe one day when training can be done faster and cheaper, there will be more interest in deep learning chess engines. PS: The estimated hardware cost to train AlphaGo Zero is around $25M (2000 TPU over 40 days, or 1700 GPU years).
- thom 9y agoI think the correct way to go with this is to possibly use deep learning to find better patterns and weightings for position evaluation, but then incorporate that into one of the existing (fast) engines. The throughput really matters, but I don't think anyone would state that (outside of tablebases) current evluators have been anywhere near perfected.