How are Heuristics made?

Kalugny · 2002-05-10T16:36:38

I want to make a program that will solve the Rotation puzzle that you can find on Nokia cellphones. For those of you who do not know it, it''s a 9x9 board with numbers 1-9 and you can rotate each 2x2 square. You need to arrange the board so that the numbers are in the correct order. It seems easy enough to use A* to do it, but for that I need a heuristic. That is, I need to know how close I am to the solution. I tried many things but it''s quite diffcult finding a mathmatical way to evaluate this, since the board changes quite drastically every move. Is there a way to make a heuristic or is it all trial-and-error? Thanks, Kalugny

bangz

119

May 07, 2002 12:09 PM

quote: Original post by edotorpedo

Bangz,

Why did you code this with an octree? The way I see it you only have 4(!) choices with the puzzle. As you said you sometimes calculate some options twice, so you don''t recurse with this node. When you only calculate using say left-turnes, you don''t have his problem, making the tree a lot simpler with the same (or less?) number of calculations.

Know what I mean?

Edo

I think i''m getting you, but say u needed only one right turn to solve the solution, the program would return a result of 3 left turns. Maybe an alogrithm could be written to then tidy up the solution?! But seems like too much hard work! ;-)

bangz.

Here''s my solution...

  #include <iostream.h>struct SNode{	unsigned int grid[4][4];	int level;	unsigned int parent;};class CTree{public:	SNode node[12000];	int nodePointer;	void addNode(SNode node, int parent, int level);	// Adds node to tree	int solve(SNode start, SNode finish);	// Solves puzzel	bool rotateL(int read, int store, int type, int checkExist);	// Rotate puzzel left	bool rotateR(int read, int store, int type);	// Rotate puzzel right	void output(int out);	// Output node[out]	void cpy(SNode read, int store);	// Copy a node from node[read] to node[store]	bool cmp(int a, SNode b);	// Compare node[a] with b	bool isExist(int i);	// Check to see if node exists elsewhere on the tree};// Check to see if node exists elsewhere on the tree//// node to check with other entries in the tree<br></font><br><font color="blue">bool</font> CTree::isExist(<font color="blue">int</font> i)<br>{<br>	<font color="blue">for</font>(<font color="blue">int</font> j=1; j&lt;nodePointer; j++)<br>	{<br>		<font color="blue">if</font>(cmp(nodePointer, node[<font color="purple">j</font>]))<br>		{<br>			<font color="blue">return</font> true;<br>		}<br>	}<br><br>	<font color="blue">return</font> false;<br>}<br><br><font color="gray">// Output node[out]<br></font><br><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray">//<br></font></font></font></font></font></font><br><font color="gray">// basically outputs node[out].grid[][]<br></font><br><font color="blue">void</font> CTree::output(<font color="blue">int</font> out)<br>{<br>	cout &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">1</font>][<font color="purple">1</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">2</font>][<font color="purple">1</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">3</font>][<font color="purple">1</font>] &lt;&lt; endl;<br>	cout &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">1</font>][<font color="purple">2</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">2</font>][<font color="purple">2</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">3</font>][<font color="purple">2</font>] &lt;&lt; endl;<br>	cout &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">1</font>][<font color="purple">3</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">2</font>][<font color="purple">3</font>] &lt;&lt; <font color="darkred">" "</font> &lt;&lt; node[<font color="purple">out</font>].grid[<font color="purple">3</font>][<font color="purple">3</font>] &lt;&lt; endl;<br>	cout &lt;&lt; endl;<br>}<br><br><font color="gray">// Compares two node grids<br></font><br><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray">//<br></font></font></font></font></font></font><br><font color="gray">// if both grids are the same, will return true<br></font><br><font color="blue">bool</font> CTree::cmp(<font color="blue">int</font> a, SNode b)<br>{<br>	<font color="blue">for</font> (<font color="blue">int</font> i=1; i&lt;4; i++)<br>	{<br>		<font color="blue">for</font>(<font color="blue">int</font> j=1; j&lt;4; j++)<br>		{<br>			<font color="blue">if</font> (node[<font color="purple">a</font>].grid[<font color="purple">i</font>][<font color="purple">j</font>]!=b.grid[<font color="purple">i</font>][<font color="purple">j</font>])<br>				<font color="blue">return</font> false;<br>		}<br>	}<br>	<font color="blue">return</font> true;<br>}<br><br><font color="gray">// Copy grid to another location<br></font><br><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray">//<br></font></font></font></font></font></font><br><font color="gray">// copy read to node[store]<br></font><br><font color="blue">void</font> CTree::cpy(SNode read, <font color="blue">int</font> store)<br>{<br>	<font color="blue">for</font> (<font color="blue">int</font> i=1; i&lt;4; i++)<br>	{<br>		<font color="blue">for</font>(<font color="blue">int</font> j=1; j&lt;4; j++)<br>		{<br>			node[<font color="purple">store</font>].grid[<font color="purple">i</font>][<font color="purple">j</font>]=read.grid[<font color="purple">i</font>][<font color="purple">j</font>];<br>		}<br>	}<br>}<br><br><font color="gray">// Rotate 2x2 Left<br></font><br><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray">//<br></font></font></font></font></font></font><br><font color="gray">// copies read to node[store] then rotates depending on the passed type<br></font><br><font color="gray">// checkExist = 1 used when on final right rotation and all left rotations<br></font><br><font color="blue">bool</font> CTree::rotateL(<font color="blue">int</font> read, <font color="blue">int</font> store, <font color="blue">int</font> type, <font color="blue">int</font> checkExist)<br>{<br>	cpy(node[<font color="purple">read</font>], nodePointer);<br>	<font color="blue">int</font> startx=0;<br>	<font color="blue">int</font> starty=0;<br>	<font color="blue">switch</font>(type)<br>	{<br>		<font color="blue">case</font> 1:		<font color="gray">//top left<br></font><br>			break;<br>		<font color="blue">case</font> 2:		<font color="gray">//top right<br></font><br>			startx=1;<br>			break;<br>		<font color="blue">case</font> 3:		<font color="gray">//bottom right<br></font><br>			starty=1;<br>			startx=1;<br>			break;<br>		<font color="blue">case</font> 4:		<font color="gray">//bottom left<br></font><br>			starty=1;<br>			break;<br>	}<br><br>	node[<font color="purple">nodePointer</font>].grid[<font color="purple">1+startx</font>][<font color="purple">1+starty</font>]=node[<font color="purple">read</font>].grid[<font color="purple">2+startx</font>][<font color="purple">1+starty</font>];<br>	node[<font color="purple">nodePointer</font>].grid[<font color="purple">1+startx</font>][<font color="purple">2+starty</font>]=node[<font color="purple">read</font>].grid[<font color="purple">1+startx</font>][<font color="purple">1+starty</font>];<br>	node[<font color="purple">nodePointer</font>].grid[<font color="purple">2+startx</font>][<font color="purple">2+starty</font>]=node[<font color="purple">read</font>].grid[<font color="purple">1+startx</font>][<font color="purple">2+starty</font>];<br>	node[<font color="purple">nodePointer</font>].grid[<font color="purple">2+startx</font>][<font color="purple">1+starty</font>]=node[<font color="purple">read</font>].grid[<font color="purple">2+startx</font>][<font color="purple">2+starty</font>];<br>	node[<font color="purple">nodePointer</font>].level=node[<font color="purple">read</font>].level+1;<br>	node[<font color="purple">nodePointer</font>].parent=read;<br><br>	<font color="blue">if</font>(checkExist==1)<br>	{<br>		<font color="blue">if</font>(isExist(nodePointer))<br>			<font color="blue">return</font> false;<br>		nodePointer++;<br>	}<br>	<font color="blue">return</font> true;<br>}<br><br><font color="gray">// Warning… &gt;12pm humor within…<br></font><br><font color="blue">bool</font> CTree::rotateR(<font color="blue">int</font> read, <font color="blue">int</font> store, <font color="blue">int</font> type)<br>{<br>	<font color="gray">//2 wrongs mite not make a right, but 3 lefts do!!! :-D<br></font><br>	rotateL(read, store, type, 0);<br>	rotateL(read, store, type, 0);<br>	rotateL(read, store, type, 1);<br><br>	<font color="blue">return</font> true;<br>}<br><br><font color="gray">// The brain of the puzzel solver :-)<br></font><br><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray"><font color="gray">//<br></font></font></font></font></font></font><br><font color="gray">// pass the start and end nodes for the solution - so it knows wot 2 work<br></font><br><font color="gray">// from and what 2 wrk 2!<br></font><br><font color="blue">int</font> CTree::solve(SNode start, SNode finish)<br>{<br>	<font color="blue">int</font> level=1;	<font color="gray">//level in tree… top level = 1<br></font><br>	<font color="blue">int</font> parent=0;	<font color="gray">//parent = daddy node<br></font><br>	<br>	node[<font color="purple">1</font>].level=1;	<font color="gray">//setup root node<br></font><br>	node[<font color="purple">1</font>].parent=0;<br>	cpy(start, 1);<br><br>	nodePointer=2;	<font color="gray">//setup nodePointer - points 2 next availble node in node[]<br></font><br><br>	<font color="blue">int</font> i=0;<br>	<font color="blue">int</font> iLimit=0;<br><br>	<font color="gray">//Here we loop round all the bottom level nodes, calculate and store<br></font><br>	<font color="gray">//the answers in the tree - until we get our result<br></font><br>	<font color="blue">do</font><br>	{<br>		i=0;<br>		iLimit=nodePointer;	<font color="gray">//used 2 break loop @ appropiate time<br></font><br>		<font color="blue">do</font><br>		{<br>			i++;<br>			<font color="blue">if</font>(node[<font color="purple">i</font>].level==level)<br>			{<br>				parent=i;<br>				<br>				<font color="gray">//8 possible outcomes for each node<br></font><br>				<font color="blue">for</font> (<font color="blue">int</font> a=1; a&lt;5; a++)<br>				{<br>					rotateR(i, i+a, a);<br>					<font color="blue">if</font> (cmp(nodePointer-1, finish)==true)<br>						<font color="blue">return</font> (nodePointer-1);<br>				}<br>				<br>				<font color="blue">for</font> (a=5; a&lt;9; a++)<br>				{<br>					rotateL(i, i+a, (a-4), 1);<br>					<font color="blue">if</font> (cmp(nodePointer-1, finish)==true)<br>						<font color="blue">return</font> (nodePointer-1);<br>				}<br>			}<br>		} <font color="blue">while</font> (i&lt;iLimit);<br>		level++;<br>	} <font color="blue">while</font>(1==1);<br><br>	<font color="blue">return</font> 0;<br>}<br><br><font color="gray">// Main program<br></font><br><font color="blue">void</font> main()<br>{<br>	CTree AI;<br><br>	SNode start;<br>	SNode finish;<br><font color="gray">/*<br>tested nodes:<br>421<br>756<br>983<br><br>253<br>146<br>789<br><br>413<br>825<br>796<br>*/</font><br>	<font color="gray">//setup arrays<br></font><br>	start.grid[<font color="purple">1</font>][<font color="purple">1</font>]=4;<br>	start.grid[<font color="purple">2</font>][<font color="purple">1</font>]=1;<br>	start.grid[<font color="purple">3</font>][<font color="purple">1</font>]=3;<br><br>	start.grid[<font color="purple">1</font>][<font color="purple">2</font>]=8;<br>	start.grid[<font color="purple">2</font>][<font color="purple">2</font>]=2;<br>	start.grid[<font color="purple">3</font>][<font color="purple">2</font>]=5;<br><br>	start.grid[<font color="purple">1</font>][<font color="purple">3</font>]=7;<br>	start.grid[<font color="purple">2</font>][<font color="purple">3</font>]=9;<br>	start.grid[<font color="purple">3</font>][<font color="purple">3</font>]=6;<br><br><br>	finish.grid[<font color="purple">1</font>][<font color="purple">1</font>]=1;<br>	finish.grid[<font color="purple">2</font>][<font color="purple">1</font>]=2;<br>	finish.grid[<font color="purple">3</font>][<font color="purple">1</font>]=3;<br><br>	finish.grid[<font color="purple">1</font>][<font color="purple">2</font>]=4;<br>	finish.grid[<font color="purple">2</font>][<font color="purple">2</font>]=5;<br>	finish.grid[<font color="purple">3</font>][<font color="purple">2</font>]=6;<br><br>	finish.grid[<font color="purple">1</font>][<font color="purple">3</font>]=7;<br>	finish.grid[<font color="purple">2</font>][<font color="purple">3</font>]=8;<br>	finish.grid[<font color="purple">3</font>][<font color="purple">3</font>]=9;<br><br>	<font color="blue">int</font> nextNode=AI.solve(start, finish);<br><br>	<font color="gray">//output solution from tree<br></font><br>	cout &lt;&lt; <font color="darkred">"Solution:"</font> &lt;&lt; endl;<br>	<font color="blue">do</font><br>	{<br>		AI.output(nextNode);<br>		nextNode=AI.node[<font color="purple">nextNode</font>].parent;<br>	} <font color="blue">while</font> (nextNode!=0);<br><br>	cout &lt;&lt; <font color="darkred">"Number of Nodes: "</font> &lt;&lt; AI.nodePointer-1 &lt;&lt; endl;<br><br>}<br>  </pre></DIV><!–ENDSCRIPT–>

bangz

119

May 07, 2002 12:09 PM

sry... posted twice...

[edited by - bangz on May 7, 2002 1:10:05 PM]

declspec

126

May 07, 2002 12:29 PM

original poster said its 9x9 board. 3x3?

bangz

119

May 07, 2002 12:56 PM

quote: Original post by Kalugny
Well, of course.
But that''s no good.
Look at this:

2 5 3
1 4 6
7 8 9

You can solve this in one move: rotate the top-left 2x2 square clockwise. But there are 4 numbers not in place.
Here:

1 2 3
5 4 6
7 8 9

There are only 2 out of place but you can''t solve this in a few easy steps.

I was assuming the original post had a typo in it... As he gave these examples!

bangz.

declspec

126

May 07, 2002 01:01 PM

lol =)

Kalugny

Author

122

May 07, 2002 03:44 PM

Hehe...
Sorry about that. Yes, the original puzzle is a 3x3 puzzle. It has 9 squares.

Anyway, bangz, I took a good look at your code. It seems to work great, but the thing you were just arguing about, the right and left turns, doesn''t do it''s job so well.

In the second example you tested (and the one currently in the code) a single right turn would have solved it but it still rotates left 3 times.

Amazingly enough, it seems to do it''s job in a very small amount of time. It makes me feel all this heuristic stuff is quite irrelevant...

Kalugny

Author

122

May 07, 2002 03:50 PM

Just as I finished writing the last post I tried another square in the program:

5 8 1
9 2 6
3 4 7

I just chose it randomly.
And it didn''t work.
It took it a lot of time and in the end it crashed (probably passed the 12000 places allocated for it...).

That raises the question, Is it that the program just isn''t far-seeing enough or is it that you can''t solve just any 3x3 board?

Kalugny

Author

122

May 07, 2002 04:27 PM

Yeah, I know, third post in the past half-hour.

Whoever wants to play the game (also in other difficulty settings, but we'll keep that for later...) can find it in:
http://www.nokia.com/games/rotation.html

I don't know why I hadn't thought of that before. The maximum number of nodes that can be in bangz's BFS program, without stack overflow, is about 14000.
A quick calculation will show that even with only 4 option per level, you can only calculate about 6-7 steps ahead. That's hardly enough.
It seems that the heuristic is needed after all...

[edited by - Kalugny on May 7, 2002 5:35:14 PM]

bangz

119

May 07, 2002 04:57 PM

yeah, it looks that way... Anyone got any idea how you would calculate ''heuristic'' for this situation, its not quite as str8 forward as path finding problems, its difficult to tell if your heading in the correct direction!

This problem really is starting 2 bug me now

bangz.

Anonymous

May 07, 2002 11:45 PM

Perhaps read the rest of this topic and you will find your answers...we''ve already discussed possible heuristics for this problem.

"to prove that a heuristic can over estimate all we have to do is find a _specific_ case where it said result a is closer then result b? correct? im asking."
No, you only have to find a case where the heuristic estimates the number of moves (or cost) to the goal state to be more than the actual cost.

"hmm got to get down to what it means to overestimate in a tile game. tad confused better look at some code."
In a tile gome, overestimating means that the heuristic estimates the number of moves (or roatations if you like) is more than the actual moves (or rotations) that are actually required to reach the goal.

"humph. what does "never over estimate" actually mean in this context? there i''ll just ask the question."
It means exactly that, in no (legal) state will the heuristic overestimate if it is admissible.

"typically heuristics just order the results from good to bad. but "never over estimates" implies that with A* heuristics need to estimate how close you are to the end? asking again. AI suffers from vocabulary. "
What else would an A* heuristic estimate other then how close (or far away) you are from the goal. If you''ve read something that says otherwise i''d be interested to know. Remember that in A* it is not just the heuristic that you use to order the nodes (for order of expansion) it is the heuristic estimate + the actual path cost to that node.

How are Heuristics made?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

How are Heuristics made?

This topic is closed to new replies.

Popular Topics

Recommended Tutorials

Reticulating splines