Algorithm of winning submission

Before I start asking questions, I need to praise the people who did submit it, because it was a tough contest. I was only able to put 4 cards into the homecell at best.

I was looking at Kaulakys' submission and it seems similar to what I was trying to do.

So, there are 3 classes, state, card, and move. The main class is state.
State has a member function that generates all possible states achievable from this state.

First, does the algorithm check if a state has been reached before?

In addition, I thought classes had peformance drawbacks in PHP. Are the performance slowdowns actually less noticeable than I thought?

Oh, interesting, he keeps track of the parent nodes, so I'm guessing that once a node has solved it he actually marks all parents nodes that a child has solved from the parent nodes already?...


Hm, this is a Breadth-first-search, at least I should get points on a test for recognizing that!

Actually, I think it's actually depth-first search.

Breadth-first search would take faaaaar too much time/memory. I tried A*, which is a smarter BF search and the results were horrible (i.e. maxed out at 6 cards in homecells, and it was an easy position)...

Mine's also DF, I guess that's why the results were so similar.

Hi there!

don't analyze my code too much. It's my first PHP program I ever wrote. I realy dont know how much performance depends on usage of classes. The solution became too complicated, so I tryed useing classes so at least I could understand what is going on. :-)

My algorithm is a modified randomized depth-first search. The hardest thing to do as to find out how to evaluate every single move, so that only the few best moves are analyzed. The algorthim does the following:
1. calculates all the possible moves
2. evaluates and sorts the moves calculated
3. takes several of the best moves (this is a bit randomized) and pushes them to a stack (depth-first)
4. POP(stack); GOTO 1;

The move class is for the presentation part only, so that I know how to reach the solution.
The states allready calculated are also stored (as strings) so that I do not move in circles.
The last thing to do was to find out whitch parameter set solves best.

BYE
Tomas Kaulakys

Ah! Now I'm not even sure about what depth-first is!

I thought a stack means he's doing a breadth-first search. He's doing searches n levels deep before doing the searches n+1 level deep? (n level deep means how many times the main search function (solve I believe) has been called already)

A good rule of thumb is: stack means DF, queue means BF

If you think about it - if you push positions on stack, you will pop the most recent (stack is LIFO - last in first out), which are at the highest level you've seen so far.

If you put them in a queue, because it's a FIFO, you'll get positions from the lowest level, before you get to the next level.

BF guarantees shortest solutions, but in many cases (such as Freecell), the number of positions is far too great for BF to be effective. DF has no guarantees about optimality, but it uses much less resources and will usually find a solution faster, if you choose moves in a non-random manner.

And, to finally answer your question

Both DF and BF traverse a search tree of a given problem. For example, if you have such a search tree:
, BF will visit level n, before going to level n+1 (A, AB, AC, ABD, ABE, ACF, ACG), and DF will go to depth first (A, AB, ABD, ABE, AC, ACF, ACG).

While the difference may not seem so pronounced with such a small search tree, it makes a world of difference in bigger search trees.

Well I've programmed a recursive function that retrieves all files in all subdirectories. I used BF, but is DF faster?

Well, if you (plan to) visit all nodes (files/positions/whatever), there's not much difference in speed (theoretically none). The difference comes when you don't want to visit all nodes (such as in Freecell, where there's like a gazillion possible positions), because they choose the order of the nodes differently.

Oh, I see thanks. It's a stack he used.

I was thinking of a queue when I said BFS...
I was using a recursive search function for my DFS, so I thought most DFS would also be done using a recursive function.