Answers.Body: <p>You may start assigning penalties for undesirable conditions in a state like:</p>
  
  <p><strong>1) Number of blocks outside stack 0.</strong></p>
  
  <p>Supose you penalize with 10 units each block outside stack 0, then the starting state above adds 40 units to the penalty score</p>
  
  <p><strong>2) Number of blocks in the stack 0 in a position different than in the goal state.</strong></p>
  
  <p>Supose you penalize with 50 units each block in stack 0 in the wrong position of the stack 0, then the starting state adds 50 to the penalty score (block D).</p>
  
  <p><strong>And go on</strong> 
  you may add as many penalties as you find helpful for solving the problem. </p>
  
  <p>Then for each step you list all possible block moves, for each one of this moves you calculates the total penalty score that this move produces and choose the one move with the <strong>minimal</strong> score (if ties choose the first one). 
  You keep repeating above until you reach the final state (penalty 0). </p>
  
Answers.ContentLicense: CC BY-SA 3.0
Answers.CreationDate: 2017-09-25T17:53:20.840Z
Answers.LastActivityDate: 2017-09-25T17:53:20.840Z
Answers.UserDisplayName: xboard
Body: <p>I am developing a heuristic solution for the <a href="https://en.wikipedia.org/wiki/Blocks_world" rel="nofollow noreferrer">blocks world</a> problem.</p>
  <p>I tried using the number of blocks out of place as my <span class="math-container">$h(n)$</span>. It seems a little ineffective.</p>
  <p>Can someone please point out a suitable heuristic for the problem and explain with a few examples how it will work.</p>
  <p>Blocks world problem example:</p>
  <pre><code>Initial(starting State):
  Stack 0: D,B
  Stack 1: A,E
  Stack 2: C
  Stack 3: F
  
  
  Goal State:
  Stack 0: A,B,C,D,E,F
  </code></pre>
  
Tags: <search><a-star><heuristic-functions>
Title: What is a good heuristic function for A* to solve the "blocks world" game?
UserDisplayName: user3758749
ThreadText: # What is a good heuristic function for A* to solve the "blocks world" game?
  
  (Asked by: username_0 on 2017-09-24)
  
  I am developing a heuristic solution for the [blocks world](https://en.wikipedia.org/wiki/Blocks_world) problem.
  
  I tried using the number of blocks out of place as my $h(n)$. It seems a little ineffective.
  
  Can someone please point out a suitable heuristic for the problem and explain with a few examples how it will work.
  
  Blocks world problem example:
  
  ```
  Initial(starting State):
  Stack 0: D,B
  Stack 1: A,E
  Stack 2: C
  Stack 3: F
  
  Goal State:
  Stack 0: A,B,C,D,E,F
  
  ```
  
  **Tags:** search, a-star, heuristic-functions
  
  
  ---
  
  ## 1 answers
  
  ### Answer by username_1 on 2017-09-25. Score: 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 units each block in stack 0 in the wrong position of the stack 0, then the starting state adds 50 to the penalty score (block D).
  
  **And go on**
  you may add as many penalties as you find helpful for solving the problem.
  
  Then for each step you list all possible block moves, for each one of this moves you calculates the total penalty score that this move produces and choose the one move with the **minimal** score (if ties choose the first one).
  You keep repeating above until you reach the final state (penalty 0).
  
  
  ---
  
  