3
votes
What is a good heuristic function for A* to solve the "blocks world" game?
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 ...
- 176
3
votes
How do we determine whether a heuristic function is better than another?
In the A* algorithm, at each iteration, a node is chosen which minimizes a certain function, called the evaluation function, which, in the case of A*, is defined as
$$f(n)=g(n)+h(n)$$
where $g(n)$ ...
- 39.5k
2
votes
If an heuristic is not admissible, can it be consistent?
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 ...
- 39.5k
2
votes
If an heuristic is not admissible, can it be consistent?
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 ...
- 9,207
2
votes
Accepted
Why is the effective branching factor used for measuring performance of a heuristic function?
I also walked into that trap the first few times. The difference is the following:
$N$ is the number of expanded nodes
$b^*$ is the effective branching factor
$b^*$ depends on the depth $d$ of the ...
- 136
2
votes
Accepted
What is the difference between the heuristic function and the evaluation function in A*?
What is the difference between the heuristic function and the evaluation function in A*?
The evaluation function, often denoted as $f$, is the function that you use to choose which node to expand ...
- 39.5k
1
vote
Is $\min(h_1(s),\ h_2(s))$ consistent?
You can easily find a counterexample. Suppose that there are three nodes $s$, $p$, and $goal$ such that $s \rightarrow p \rightarrow goal$. The real cost of going from $s$ to $p$ is $c(s,p) = 10$ and $...
- 1,751
1
vote
If $h_1(n)$ is admissible, why does A* tree search with $h_2(n) = 3h_1(n)$ return a path that is at most thrice as long as the optimal path?
The sketch of the proof for your first question:
for an open node $n$, if $f_1(n) = g(n) + h_1(n)$, in the same situation in using $h_2$, it will be $f_2(n) = g(n) + 3 h_1(n)$. Hence, all the time ...
- 1,751
1
vote
Strategy for playing a board game with Minimax algorithm
I'm not familiar with your game so I can't tell you what a good heuristic woul be in your specific case, but I can give you some advice on how to look for a good heuristic function.
As a rule of thumb,...
- 26
1
vote
If $h_i$ are consistent and admissible, are their sum, maximum, minimum and average also consistent and admissible?
The issue is that you must include assumptions about hopping into your heuristic. In particular, if you are considering individual cars then you must assume that they might be able to hop all of the ...
- 371
1
vote
Why is the effective branching factor used for measuring performance of a heuristic function?
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 ...
- 1,751
1
vote
Accepted
Why isn't Nilsson's Sequence Score an admissible heuristic function?
I will use the 8-puzzle game to show you why Nilson's sequence score heuristic function is not admissible. In the 8-puzzle game, you have a $3 \times 3$ board of (numbered) squares as follows.
...
- 39.5k
Only top scored, non community-wiki answers of a minimum length are eligible