12
$\begingroup$

Some programs do exhaustive searches for a solution while others do heuristic searches for a similar answer. For example, in chess, the search for the best next move tends to be more exhaustive in nature whereas, in Go, the search for the best next move tends to be more heuristic in nature due to the much larger search space.

Is the technique of brute force exhaustive searching for a good answer considered to be AI or is it generally required that heuristic algorithms be used before being deemed AI? If so, is the chess-playing computer beating a human professional seen as a meaningful milestone?

$\endgroup$
  • 1
    $\begingroup$ It depends on your perspective. Check out is the transistor the first artificial intelligence?. $\endgroup$ – Jaden Travnik Feb 20 '18 at 3:57
  • 6
    $\begingroup$ There is a phenomenon, John McCarthy describes: “As soon as it works, no one calls it AI anymore.” So, it is AI if no one has done it. People might not call exhaustive search AI nowadays unless the algorithm is learning and limiting the search space with time. $\endgroup$ – Ugnes Feb 20 '18 at 12:24
  • $\begingroup$ @Ugnes was gonna add that quote but you were way ahead of me! $\endgroup$ – hisairnessag3 Apr 14 '18 at 8:27
8
$\begingroup$

If one thinks of intelligence as a continuous measure of optimization power (that is, how much better are outcomes for any unit of cognitive effort expended), then exhaustive search has non-zero intelligence (in that it does actually give better outcomes as more effort is expended) but very, very low intelligence (as the outcomes are better mostly by luck, and the amount of effort expended can be impossibly large).

$\endgroup$
7
$\begingroup$

If a computer is just brute-forcing the solution, it's not learning anything or using any kind of intelligence at all, and therefore it shouldn't be called "artificial intelligence." It has to make decisions based on what's happened before in similar instances. For something to be intelligent, it needs a way to keep track of what it's learned. A chess program might have a really awesome measurement algorithm to use on every possible board state, but if it's always trying each state and never storing what it learns about different approaches, it's not intelligent.

$\endgroup$
  • 4
    $\begingroup$ Storing information doesn't make an algorithm intelligent either. Windows stores information and I think we can exclude it from the set of all things that could possibly be considered intelligent. $\endgroup$ – dynrepsys Aug 2 '16 at 17:33
  • $\begingroup$ @Dynrepsys You're right; I've clarified my answer :) $\endgroup$ – Ben N Aug 2 '16 at 17:34
  • $\begingroup$ There are people who cannot create any new memories. That doesn't mean they are not intelligent. It is not the learning itself that is necessary for intelligence, it is the internal model of the world. Of course that usually is learned. But sometimes it isn't. And sometimes the entity looses the ability to learn but retains the model. $\endgroup$ – BlindKungFuMaster Feb 20 '18 at 13:32
  • $\begingroup$ @BlindKungFuMaster How are internal models of the world constructed but through learning? Even if it's "merely" a biological process, it's still learning in the technical sense of the word. $\endgroup$ – Dave Newton Feb 20 '18 at 16:32
  • $\begingroup$ Learning doesn't seem like a necessary condition for intelligence. Would an automated theorem prover, or a system that generates the laws of physics from first principles, or an optimal chess player be discounted as intelligence behavior simply because it doesn't learn/adapt? $\endgroup$ – user48956 Dec 13 '18 at 17:27
3
$\begingroup$

The answer is yes, exhaustive search is a fundamental principle in AI. Like the OP recognized it is used for solving chess-like games and can also be used in many other domains like pathplanning or PDDL-solving. From a theoretical point of view, a brute-force search is an elegant method for solving every problem. The reason, why heuristics are used in real-life programs is, because of current computerhardware is to slow in calculating. So heuristics are used as a speed-booster.

$\endgroup$
  • $\begingroup$ Elegant? The word "brute" is even in the name; there's nothing particularly "elegant" about it--probably about the least elegant problem solving strategy there is. Effective (in some solution spaces), sure, but elegant? Meh. $\endgroup$ – Dave Newton Feb 20 '18 at 16:34
  • $\begingroup$ Possibly "elegant" in terms of simplicity of the method? I like that you reinforce how important the technique has been, and how it's sort of necessary to check certain solutions. (i.e. Go can never be fully solved b/c you can't brute force it. Didn't stop useful, end-game analysis where the tree is tractable.) But I do have to agree with Ben N that it probably needs to make a decision to qualify as AI. $\endgroup$ – DukeZhou Apr 14 '18 at 2:07
  • $\begingroup$ I elegance a necessary condition for intelligence? $\endgroup$ – user48956 Dec 13 '18 at 17:27
2
$\begingroup$

Brute force approach is certainly the first step of many in AI programming. But using these experiences the program must learn to find the best solution or at least a closer solution to the problem. Since the first goal in AI is to find any solution, nothing can beat the brute force approach. But then using the previous results of brute force approaches, the program must develop its own heuristics and use this data along with brute force to find the optimal solution.

$\endgroup$
  • $\begingroup$ "Nothing can beat the brute force approach"? Beat in which sense? $\endgroup$ – Dave Newton Feb 20 '18 at 16:33
  • $\begingroup$ Welcome to AI I might supplement this answer by noting that some problems are intractable, and can't be solved by brute force. But I certainly agree that brute force algorithms are a fundamental form and function of AI. In a combinatorial game theory, it seems that a game or puzzle, such as Sudoku, may only be said to be solved through brute force (exhaustion). $\endgroup$ – DukeZhou Feb 20 '18 at 21:54
2
$\begingroup$

Really any 'intelligence' exhibited by a computer is deemed AI, regardless of brute force or use of smart heuristics. For example, a chat bot can be coded to respond to most responses using many, many if statements. This is an AI no matter how poorly coded/designed it is.

The chess playing computer beating a human professional can be seen as a meaningful milestone. I mean, someone programmed a computer to beat grandmaster chess players and chess geniuses. Many thought that wasn't possible since chess is such a complex game. This kind of work likely segued into more complex AI, for if a computer could play chess, then it surely complete other complex tasks as well.

Note how refined chess programming is: magic bitboards, Zobrist hashing, pruning, lazy SMP, and many more. This is perhaps not the sort of milestone of AI that you thought, but again, the things that can be considered AI are pretty broad.

$\endgroup$
  • $\begingroup$ Nice thoughts. However, the thesis is problematic unless you define intelligence (See Ben N's and Matthew Graves' answers.) Address that and you'll definitely get an upvote from me! $\endgroup$ – DukeZhou Apr 14 '18 at 2:12
1
$\begingroup$

I dont know why you wouldnt consider it ai since every single thing has used something like it thats been in the recent news.

evolving a neural network is very similar to brute force search, just it hits local optima, because its not exhaustive.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.