Thanks, Kylotan! I'm glad to hear my proselytizing for IDA* and Fringe Search is paying off. 8^)

raft - you are correct that IDA* will re-visit many, many nodes during its iterative step. In fact, you may visit some node numerous times. The trick is that, typically, visiting a node and determining if it is the goal or not is typically much, much less expensive than maintaining all the nodes in a sorted list. A* suffers from having to sort the open list by your f(), and also from looking into the closed list.

Kylotan is absolutely right regarding the leaves being more numerous than all lower order nodes in the search tree. If you assume a branching factor of 2, a binary tree, it is very easy to prove that the number of leaves will be equal to the number of non-leaf nodes by 1. (Does anyone else out there remember induction??)

As far as I can tell you have the basic prinicple correct. My guess is you may have to ensure that you don't have futile cycles in your search. For example, if the depth cutoff isn't working properly you might end up with a sequence of left-right-left-right-left-right...

Also, on an 8-puzzle you may not have crossed over the threshhold of performance between sorting and iterating. In such a puzzle it is possible (pure speculation following) that the cost of sorting/searching in A* has not yet extended beyond the cost of iterating in IDA*. Give the 15 puzzle a try and I would fully expect IDA* to perform much faster.

if i didnt messed up IDA* implementation, this is the performance order for 8 puzzle:

1. A* with sum of manhattan distances heuristic is best (about 20 times faster than 2)
2. IDA* with caching nodes and marking visited ones
3. A* with no heuristic is sligtly slower than 2
4. IDA* with no caching performs worst (many times slower than 2)

i guess IDA* with no caching performs so bad because it cycles and cycles again between nodes.

Kirk, how did you implement IDA* for 2x2x2 rubik ? did you cache nodes to mark visited ones ? i cant really see how IDA* can perform that better than A* in your tests. maybe there was a problem with A* heuristic, have you tried it with no heuristic ?

r a f t

For the 2x2x2 Rubik's Cube I did not mark any nodes as visited. I just followed a standard depth first search increasing by one level of depth until the solution is found. For the heuristic, I used the same heuristic for both. Specifically, I have a look up table that gives the number of moves needed to solve the top corners and another table giving the number of moves needed to solve the bottom corners. I take the maximum of these two values as h().

In your description you do not mention using a heuristic for IDA*. You might get a bit of a performance boost if you include that in your child expansion. This slightly violates the depth-first search criteria, but you can easily sort the children at any particular step by their heuristic and choose to expand the child with the lowest h() first. This also doesn't cost much.

Again, I will bet that the difference in performance might be more significant in a 15 puzzle. I'd be interested to hear the results of that test, too.

For the Rubik's Cube example, there are 9 children at the first node and 6 children for each subsequent node. For the 8 puzzle I would assume the best you can hope for is 4 children at the first node and 3 at the second node if you prevent reversing the previous move. The increased branching factor is a killer for A*.

kirk, seems as we posted the previous ones at the same time ;)

i was caching to avoid such futile cycles. i changed the uncached version such that, if a neighbour is in stack (our current path) i dont expand it. what else is possible ? i guess you perform problem specific checks to avoid cycles and redundant moves

this made uncached version faster for 3x3 but still much slower than the cached version. note, i shuffle 3x3 quite a bit, say with 500 random moves. for less shuffling cached, uncached and A* difference gets smaller, still A* leading

for larger puzzles (4x4, 5x5), i could only tested them with relatively less shuffling. A* still leads far ahead. with more shuffling, all three last quite a long, so i didnt wait till end. i guess A* and cached IDA* will most likely suffer for memory in those big puzzles.

also i can say sorting neighbours according to heuristic makes no siginificant change.

there may still be flows in my implementation, i may review it later if i find time.

as a conclusion, i can say sum of distances heuristic is quite efficient for sliding puzzle. or i messed up IDA ;)

i must say i still couldnt convince myself how IDA* performs many times better for 2x2x2.

r a f t

Interesting results, for certain. Unfortunately I don't see a reason for the discrepancy. Much as you're seeing improved results with A*, my 2x2x2 Rubik's Cube solver is much improved with IDA*.

A conundrum, indeed! 8^)

Quote: Original post by kirkd
Kylotan is absolutely right regarding the leaves being more numerous than all lower order nodes in the search tree. If you assume a branching factor of 2, a binary tree, it is very easy to prove that the number of leaves will be equal to the number of non-leaf nodes by 1. (Does anyone else out there remember induction??)

Simple algebra will give you the answer. ;) Assuming a uniform branching factor of b ≥ 2, the number of nodes in a tree of depth d is bd. Hence, the number of leaf nodes in a tree of depth d is

n = bd - bd-1  = bd(b-1/b)

Thus we can see easily that the number of leaf nodes is at a minimum half the tree population.

Cheers,

Timkin

Quote: Original post by Timkin
Assuming a uniform branching factor of b ≥ 2, the number of nodes in a tree of depth d is bd.

Isn't it bd-1, assuming the root starts at level 1. The rest works out. I've usually seen the root level labeled at depth 0 which would give us b(d+1)-1.

-Kirk

Gah... sorry... I'm going daft today... that's what you get for spending 4 days straight marking exams and assignments for 12 hours per day. 8(

The number of nodes at depth d is bd. So obviously the number of leaf nodes is just bd and the number of nodes above this is

Σi=0d-1bi

Sorry for the mistake.

Cheers,

Timkin

Quote: Original post by Timkin
Gah... sorry... I'm going daft today... that's what you get for spending 4 days straight marking exams and assignments for 12 hours per day. 8(

The number of nodes at depth d is bd. So obviously the number of leaf nodes is just bd and the number of nodes above this is

Σi=0d-1bi

Sorry for the mistake.

Cheers,

Timkin

Or more simply:

bd - 1
------ = n
b - 1

Grading exams is, in my experience, more taxing than preparing for and teaching the course. Good luck getting your students through finals - and grading the final exams!! 8^)

-Kirk