# Tag Info

## Hot answers tagged heuristics

9

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 definitions of admissible and consistent are correct. An admissible heuristic is basically just "optimistic". It never overestimates a distance. A consistent ...

8

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

7

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

5

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.

5

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 perfect heuristics. Then $h_0(s) = 1$ and $h_1(s) = 1$. In this case the heuristic is inadmissible because $h_0(s)+h_1(s) = 2 > d(s, g)$. Similarly, as an ...

4

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 and vice-versa. Think of it as a game of rock paper scissors. Specifically, you may find that sometimes $h_1 < h_2$ and in other times $h_2 < h_1$, where $... 3 You may start assigning penalties for undesirable conditions in a state like: 1) Number of blocks outside stack 0. Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score 2) Number of blocks in the stack 0 in a position different than in the goal state. Supose you penalize with 50 ... 3 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 this page). Then I'd look into things like the Killer Move Heuristic, and maybe also see if you can simply implement existing parts of your engine more ... 3 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 features that's the case, of course all the hype with Deep Neural Networks in more recent years is different. So, when it's not specified in a paper like this exactly ... 3 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 explanations, only means of comparing them among another. It is a heuristic because like all heuristics, it can lead to false conclusions, but is usually right. 2 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 ... 2 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 ... 2 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 of the most popular is IRace, but other possibilities include: Spearmint: uses wrappers in Matlab or Python. It uses MongoDb, and Bayesian optimisation ... 2 Heuristics can be understood aas rules. Typically heuristics are thought of as problem-specific strategies. Expert systems were an early form of AI that utilized rules-based decisions. In a game-playing context, heuristics can be pure strategies. A heuristic function would be one that includes a some predefined decision rules. Russell and Norvig have a ... 2 If by "visit multiple targets", you mean "visit several points in the fastest order", you are no longer in a simple path-finding-style search problem, but instead in an optimization problem. This is roughly the difference between chapters 3 & 6 of Russell & Norvig's section on search. To do this, you can't just change your heuristic, instead you ... 2 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 also the speed with which it can traverse the tree, is extremely important for the algorithm's performance. Therefore, when evaluating how good or bad a ... 2 The most obvious heuristic would indeed simply be the straight-line distance. In most cases, where you have, for example, x and y coordinates for all the nodes in your graph, that would be extremely easy to compute. The straight-line distance also fits the requirements of an admissible heuristic, in that it will never overestimate the distance. The travel-... 2 Yes, in both cases. Below I give two very simple proofs that directly follow from the definitions of admissible and consistent heuristics. However, in a nutshell, the idea of the proofs is that$h_{\max}(n)$and$h_{\min}(n)$are, by definition (of$h_{\max}$and$h_{\min}$), equal to one of the given admissible (or consistent) heuristics, for all nodes$n$, ... 2 Welcome to AI.SE @hpr16! Your understanding of when a heuristic is admissible is correct, but your heuristic is inadmissible. An admissible heuristic must always underestimate the cost to move from a given state to a goal state. Notice that states in the search are not the same as positions on the circle in your problem. A state needs to capture all the ... 2 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. Another way to initially set weights for the network is to create a dataset of moves (correct, incorrect, etc, as long as they are relevant) and have the network ... 2 The key phrase here is because heuristics are admissible In other words, the heuristics never overestimate the path length: $$cost(n) + heuristic(n) \le cost(\text{any path going through n})$$ And since the frontier is ordered by$\textbf{cost + heuristic}$, when a completed path$p$is dequeued from the frontier, we know that it must necessarily be$\...

1

As you found $N$ is the number of nodes that are expanded. The cost of expansion of each node is equal to the number of children of that node. Hence, we use $b^*$ for each node. In other words, the total number of nodes that are involved in the expansion process is $N \times b^*$.

1

If a heuristic is not admissible, can it be consistent? No. Consistency implies admissibility. In other words, if a heuristic is consistent, it is also admissible. However, admissibility does not imply consistency. In other words, an admissible heuristic is not necessarily consistent. Definitions Given a graph $G=(V, E)$ representing the search space, ...

1

For a heuristic to be admissible, it must never overestimate the distance from a state to the nearest goal state. For a heuristic to be consistent, the heuristic's value must be less than or equal to the cost of moving from that state to the state nearest the goal that can be reached from it, plus the heurstic's estimate for that state. What this means is ...

1

What you are doing when calculating $d'(x,y)$: $d(x,y)$: calculating the original edge distance from $x$ to $y$ $h(y)$: plus the heuristic from $y$ to the goal $h(x)$: minus the heuristic from $x$ to the goal So, using this recalculation of the original edge-values ($1.$) in Dijkstra's algorithm you are inherently accounting for the heuristic component of ...

1

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 see that this is wrong, because A* is a search algorithm that guarantees to find an optimal solution given that only admissible heuristics are used. (A heuristic is being admissible if it never ...

1

Try cache or transposition table. Without it, your search tree might explode.

1

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 algorithm but it increases the space complexity. I am linking the wiki to it https://en.wikipedia.org/wiki/SSS* I will update the answer as soon as i get a ...

1

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 knowledge vectors and efforts, build a acyclic directed graph (acyclic, as we are not supposed to unlearn). A vertex is an article, represented by its knowledge ...

1

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 heuristic function. Although your approach does not seem to incorporate a "shortcut mathematical formula" as a heuristic after that, it does us a precalculated ...

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