4 ms·
>> In computer chess, the methods that defeated the world champion, Kasparov, in 1997, were based on massive, deep search. "Massive, deep search" that started
by YeGoblynQueenne 6y ago
>> In computer chess, the methods that defeated the world champion, Kasparov, in
1997, were based on massive, deep search.
"Massive, deep search" that started from a book of opening moves and the
combined expert knowledge of several chess Grandmasters. And that was an
instance of the minimax algorithm with alpha-beta cutoff, i.e. a search
algorithm specifically designed for two-player, deterministic games like
chess. And with a hand-crafted evaluation function, whose parameters were
filled-in by self-play. But still, an evaluation function; because the minimax
algorithm requires one and blind search alone did not, could not, come up with
minimax, or with the concept of an evaluation function in a million years.
Essentially, human
expertise about what matters in the game was baked-in to Deep Blue's design
from the very beginning and permeated every aspect of its design.
Of course, ultimately, search was what allowed Deep Blue to beat Kasparov
(3½–2½; Kasparov won two games and drew another). That, in the sense that the
alpha-beta minimax algorithm itself is a search algorithm and it goes without
saying that a longer, deeper, better search will inevitably eventually
outperform whatever a human player is doing, which clearly is not search.
But, rather than an irrelevant "bitter" lesson about how big machines can
perfom more computations than a human, a really useful lesson -and one that we
haven't yet learned, as a field- is why humans can do so well without
search. It is clear to anyone who has played any board game that humans can't
search ahead more than a scant few ply, even for the simplest games. And yet,
it took 30 years (counting from the Dartmouth workshop) for a computer chess
player to beat an expert human player. And almost 60 to beat one in Go.
No, no. The biggest question in the field is not one that is answered by "a
deeper search". The biggest question is "how can we do that without a search"?
Also see Rodney Brook's "better lesson" [2] addressing the other successes of
big search discussed in the article.
_____________
[1] https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)#Design https://en.wikipedia.org/wiki/Deep_Blue_(chess_computer)#Des...
[2] https://rodneybrooks.com/a-better-lesson/ https://rodneybrooks.com/a-better-lesson/
- dreamcompiler 6y agoAre we certain that well-trained human players are not doing search? It's possible that a search subnetwork gets "compiled without debugger symbols" and the owner of the brain is simply unaware that it's happening.
- gwern 6y agoI'm not sure why YeGoblynQueenne thinks this is such a mystery. (This is not the first time I've been puzzled by their pessimism on HN.) There is no mystery here: AlphaZero shows that you can get superhuman performance by searching only a few ply by sufficiently good pattern recognition in a highly parameterized and well-trained value function, and MuZero makes this point even more emphatically by doing away with the formal search entirely in favor of an more abstract recurrent pondering. What more is there to say?
- YeGoblynQueenne 6y agoMuZero performs a "formal search". In many more ways than one, for example optimisation is still a search for an optimal search of parameters. But I guess you mean that it doesn't perform a tree search? Quoting from the abstract of the paper on arxiv [1]: In this work we present the MuZero algorithm which, by combining _a tree-based search_ with a learned model, achieves superhuman performance in a range of challenging and visually complex domains, withoutany knowledge of their underlying dynamics. (My underlining) If I remember correctly, MuZero is model-free in the sense that it learns its own evaluation function and reward policy etc (also going by the abstract). But it retains MCTS. Indeed, it wouldn't really make sense to drop MCTS from the architecture of a system designed to play games. I mean, it would be really hard to justify discarding a component that is well known to work and work well, both from an engineering and a scientific point of view. _________________ https://arxiv.org/abs/1911.08265 https://arxiv.org/abs/1911.08265
- gwern 6y agoMuZero doesn't do a search over explicit board states, MCTS (where are the playouts at the leaf nodes? where is the simulator state?) or otherwise: it does search over internal-abstract-reward-predictive-states/action pairs, much like a human does, who thinks through possible actions using an internal representation sometimes backtracking as they decide a move is bad and evaluating a different one which feels better. It's search over a tree of possible actions, sure, but this is not MCTS, even if they loosely use the phrase in places (similarly, the tree search Zero does for gameplay is not MCTS, even if people sometimes describe it that way or conflate it with the training).
- new2628 6y agoAt least in chess, if it is not the search, then it is probably the evaluation function. Expert players have likely a very well-tuned evaluation function of how strong a board "feels". Some of it is explainable easily: center domination, diagonal bishop, connected pawn structure, rook supporting pawn from behind, others are more elaborate, come with experience and harder to verbalize. When expert players play against computers, the limitation of their evaluation function becomes visible. Some board may feel strong, but you are missing some corner case that the minmax search observes and exploits.
- YeGoblynQueenne 6y agoI like to caution against taking concepts from computer science and AI and applying them directly to the way the human mind works. Unless we know that a player is applying a specific evaluation function (e.g. because they tell us, or because they vocalise their thought process etc) then even suggesting that "players have an evaluation function" is extrapolating far from what it is safe. For one thing- what does a "function" look like in the human mind? Whatever human minds do, computing is only a very general metaphor for it and it's very risky to assume we understand anything about our mind just because we understand our computers.
- burntoutfire 6y ago> No, no. The biggest question in the field is not one that is answered by "a deeper search". The biggest question is "how can we do that without a search"? My guess is that we're doing pattern recognision, where we recognize taht a current game state is similar to a situation that we've been in before (in some previous game), and recall the strategy we took and the outcomes it had lead to. With large enough body of experience, you can to remember lots of past attempted strategies for every kind of game state (of course, within some similarity distance).
- blt 6y agoThis insight is the essence of the AlphaZero architecture. Whereas a pure Monte Carlo Tree Search (MCTS) starts each node in the search tree with a uniform distribution over actions, AlphaZero trains a neural network to observe the game state and output a distribution over actions. This distribution is optimized to be as similar as possible to the distribution obtained from running MCTS from that state in the past. It's very similar to the way humans play games.
- mtgp1000 6y ago>But, rather than an irrelevant "bitter" lesson about how big machines can perfom more computations than a human, a really useful lesson -and one that we haven't yet learned, as a field- is why humans can do so well without search I think the answer is heuristics based on priors(e.g. board state), which we've demonstrated (with alphago and derivatives, especially alphago zero) that neural networks are readily able to learn. This is why I get the impression that modern neural networks are quickly approaching humanlike reasoning - once you figure out how to (1) encode (or train) heuristics and (2) encode relationships between concepts in a manner which preserves a sort of topology (think for example of a graph where nodes represent generic ideas) You're well on your way to artificial general reasoning - the only remaining question becomes one of hardware (compute, memory, and/or efficiency of architecture).