3 ms·

In your comment here and below it sounds like you're saying: "if you take a brute force algorithm and make it more efficient than brute force by not brute forci

In your comment here and below it sounds like you're saying: "if you take a brute force algorithm and make it more efficient than brute force by not brute forcing the solution then it's just a brute force algorithm!" If AlphaZero is brute force than any use of a non-exhaustive planning mechanism (pruned MCTS in this case) is brute force which is honestly ridiculous. Search and planning have a long history in both computer science _and_ neuropsychology because that is what we call the methods that are more efficient than brute force at the expense of some accuracy. There are some problems with the article but it isn't that AlphaZero is just some overhyped brute force algorithm.

ikeboy 8y ago
I never suggested it's overhyped. I think the specific terms being used to compare it to humans are inaccurate. On a related note, AlphaZero used quite a lot of processing power - even with the optimizations, if it had to run on human hardware it would be pretty worthless.
- lern_too_spel 8y ago
  > AlphaZero used quite a lot of processing power It ran on a single machine with four TPUs. In a few years with a few more optimizations, I can imagine an equal strength implementation on a handheld chess computer. If you're talking about training hardware, the correct comparison is against the processing time used by all serious human chess players through history because an apples to apples comparison would have both training from scratch (just the rules).
ikeboy 8y ago
If we had a halting oracle and used it to output the best move for any situation, I would also call that brute force, even if it's actually only computing a handful of bits per move. Compressing a computation doesn't change the nature of what's being done meaningfully.
- soraki_soladead 8y ago
  Your understanding of what brute force means is incorrect. It is an exhaustive algorithm. Any non-exhaustive algorithm is no longer brute force. An algorithm (like AlphaZero) that can locally generalize, even to small degrees, is also not brute force. Your argument is that a brute force algorithm is simply being compressed by a neural network but that isn't how AlphaZero works at all. You can't prune a brute force algorithm's branching and still call it brute force. In fact, if it was, then games like Go wouldn't be approachable by the same algorithm.
  - ikeboy 8y ago
    https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up_brute-force_searches https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up... >One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class. The term brute force is clearly used for algorithms besides for ones that literally try every possible solution. Want more? I found http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00038/Lecture23MRM.pdf http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00038/... from a google search, lecture notes which says >Minimax is pretty slow even for a modest depth. It is basically a brute force search As we can see, brute force can be used as a statement about how much computation is required, Hell, here's Kasparov himself (cited in TFA as an authority) using the term for minimax https://twitter.com/kasparov63/status/867586759412068352?lang=en https://twitter.com/kasparov63/status/867586759412068352?lan... The term is clearly used widely to refer to more than just exhaustive algorithms. The article portrays this as a battle between engines like stockfish, which are brute force (note that they explicitly call previous chess programs brute force, although clearly one based on your definition would be useless), against AlphaZero, which supposedly does more than brute force and has principles and insight etc. I think this gets it exactly backwards - stockfish had a lot of principles baked in by humans, as the article acknowledges, but alphazero was given 0 knowledge of chess other than the rules. Seems like this is properly viewed as a triumph of efficient algorithms over ones with principles, which is nearly opposite to the article's framing.
    - 8y ago

ikeboy 8y ago

I never suggested it's overhyped. I think the specific terms being used to compare it to humans are inaccurate. On a related note, AlphaZero used quite a lot of processing power - even with the optimizations, if it had to run on human hardware it would be pretty worthless.

lern_too_spel 8y ago
> AlphaZero used quite a lot of processing power It ran on a single machine with four TPUs. In a few years with a few more optimizations, I can imagine an equal strength implementation on a handheld chess computer. If you're talking about training hardware, the correct comparison is against the processing time used by all serious human chess players through history because an apples to apples comparison would have both training from scratch (just the rules).

ikeboy 8y ago

If we had a halting oracle and used it to output the best move for any situation, I would also call that brute force, even if it's actually only computing a handful of bits per move. Compressing a computation doesn't change the nature of what's being done meaningfully.

soraki_soladead 8y ago
Your understanding of what brute force means is incorrect. It is an exhaustive algorithm. Any non-exhaustive algorithm is no longer brute force. An algorithm (like AlphaZero) that can locally generalize, even to small degrees, is also not brute force. Your argument is that a brute force algorithm is simply being compressed by a neural network but that isn't how AlphaZero works at all. You can't prune a brute force algorithm's branching and still call it brute force. In fact, if it was, then games like Go wouldn't be approachable by the same algorithm.
- ikeboy 8y ago
  https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up_brute-force_searches https://en.wikipedia.org/wiki/Brute-force_search#Speeding_up... >One way to speed up a brute-force algorithm is to reduce the search space, that is, the set of candidate solutions, by using heuristics specific to the problem class. The term brute force is clearly used for algorithms besides for ones that literally try every possible solution. Want more? I found http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00038/Lecture23MRM.pdf http://www.cs.cmu.edu/~ab/Desktop/15-211%20Archive/res00038/... from a google search, lecture notes which says >Minimax is pretty slow even for a modest depth. It is basically a brute force search As we can see, brute force can be used as a statement about how much computation is required, Hell, here's Kasparov himself (cited in TFA as an authority) using the term for minimax https://twitter.com/kasparov63/status/867586759412068352?lang=en https://twitter.com/kasparov63/status/867586759412068352?lan... The term is clearly used widely to refer to more than just exhaustive algorithms. The article portrays this as a battle between engines like stockfish, which are brute force (note that they explicitly call previous chess programs brute force, although clearly one based on your definition would be useless), against AlphaZero, which supposedly does more than brute force and has principles and insight etc. I think this gets it exactly backwards - stockfish had a lot of principles baked in by humans, as the article acknowledges, but alphazero was given 0 knowledge of chess other than the rules. Seems like this is properly viewed as a triumph of efficient algorithms over ones with principles, which is nearly opposite to the article's framing.
  - 8y ago