# Tag Info

Accepted

### Why is A* optimal if the heuristic function is admissible?

This is well covered in the corresponding chapter of Russell & Norvig (chapter 3.5, pages 93 to 99 (Third Edition)). Check that out for more details. First, let's review the definitions: Your ...
• 9,267

### Are methods of exhaustive search considered to be AI?

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 ...
• 4,272

### Are methods of exhaustive search considered to be AI?

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 ...
• 2,609

### How does A* search work given there are multiple goal states?

Yes. If you leave A* running (i.e. do not impose a goal condition on a newly-encountered state), all states will be explored, just as they would be in breadth- or depth- first search.
• 7,266

### Is the summation of consistent heuristic functions also consistent?

No, it will not necessary be consistent or admissible. Consider this example, where $s$ is the start, $g$ is the goal, and the distance between them is 1. s --1-- g Assume that $h_0$ and $h_1$ are ...
• 371
Accepted

### Can two admissable heuristics not dominate each other?

This is possible. Admissibility only asserts that the heuristic will never overestimate the true cost. With that being said, it is possible for one heuristic in some cases to do better than another ...
• 1,106

### What are some common heuristics that might be innate?

Perhaps Occam's razor counts. Occam's razor is the meta-heuristic that "the simplest explanation is the most likely to be correct". I consider it a meta-heuristic because itself doesn't provide ...
• 2,101

### What is the definition of a heuristic function in the BayesChess paper?

By far the most common form of heuristic evaluation functions for Chess-playing (or, really, any game-playing) agents are simple linear functions. At least when we're talking about handcrafted ...
• 10.3k

### What else can boost iterative deepening with alpha-beta pruning?

First thing you're going to want to add is probably a Transposition Table, as also suggested by SmallChess. Afterwards, I'd look into Aspiration Search and/or Principal Variation Search (also see ...
• 10.3k
Accepted

### More effective way to improve the heuristics of an AI... evolution or testing between thousands of pre-determined sets of heuristics?

Hmmm, I see some issues that are actually present in both of the approaches you propose. It is important to note that the depth level that your Minimax search process manages to reach, and therefore ...
• 10.3k

### Are methods of exhaustive search considered to be AI?

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

### Are methods of exhaustive search considered to be AI?

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

### How to find proper parameter settings for a given optimization algorithm?

How to find the best configuration for an algorithm is an open research question in AI. The topic in general is known as `hyper-parameter optimization' and there are a range of possible methods: One ...
• 7,266
Accepted

### How do you calculate the heuristic value in this specific case?

The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y...
• 10.3k

### What are state-of-the-art ways of using greedy heuristics to initially set the weights of a Deep Q-Network in Reinforcement Learning?

You can check out Bootstrapped DQN, with a demonstration video. Without reading much of the paper, it seems the authors use a different sampling strategy and an action-guide for specific instances. ...
• 906
Accepted

### How does A* search work given there are multiple goal states?

Question 1: First of all, you state that that the goal G2 will be found first by relying on the expansion order R, B, D, G2. This is wrong. It is extremely easy to ...
• 210
Accepted

• 1,031
1 vote

### What else can boost iterative deepening with alpha-beta pruning?

Try cache or transposition table. Without it, your search tree might explode.
• 1,411
1 vote

### What else can boost iterative deepening with alpha-beta pruning?

To make boost iterative deepening with alpha-beta pruning you can use the SSS* Search algorithm, its a best first strategy algorithm. The SSS* Algorithm can improve the time efficiency of the overall ...
• 11
1 vote

### Strategic planning and multi dimensional knapsack problem

Here is a speculative cast of the problem to a travelling salesman problem, which would lead to shortest-path algorithms. Please note this idea suggests different constraints to explore. Given the ...
• 1,510
1 vote
Accepted

### Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

Since you mention the A* algorithm, then you are definitely using a heuristic somewhere in there, at least with the A* algorithm while solving the subproblems using the straight-line distance as your ...
• 56
1 vote

### Is a subset of a problem solution, used to recreate complete solution considered a heuristic?

A 'heuristic' is simply a 'rule-of-thumb', i.e. something which doesn't guarantee an optimal solution to a problem. Beyond the above notion (certainly within the discipline of optimization), the ...
• 7,266

Only top scored, non community-wiki answers of a minimum length are eligible