undefined | Better HN

0 pointsikeboy7y ago0 comments

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.

0 comments

3 comments · 1 top-level

soraki_soladead7y ago· 2 in thread

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.

ikeboyOP7y ago

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/... 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?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.

falcor847y ago

>>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.

My reading of that sentence from Wikipedia is that this is the step by which a brute force approach is transformed into a "clever" approach. The hard part is to find valid and useful heuristics, which often also involve switching data structures in some way.

j / k navigate · click thread line to collapse