numbrosia

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
Thanks for the help.
The breadthfirst search is easy to program. The hash table is simple because only the first node there matters.
Does your table store boards that have known solutions or is it something else?
The breadthfirst search is easy to program. The hash table is simple because only the first node there matters.
Does your table store boards that have known solutions or is it something else?

 Posts: 113
 Joined: Tue Feb 12, 2008 8:31 pm
 Contact:
Re: numbrosia
I compute a hash code for each position, and I keep a table, indexed by this code, of the lower bound on the number of moves necessary to reach the solution. It is only a lower bound. The table is generated by searching, at each depth (up to depth 8), all reachable positions from the goal state. More details were explained in the reddit discussion:spurious_ai wrote:Thanks for the help.
The breadthfirst search is easy to program. The hash table is simple because only the first node there matters.
Does your table store boards that have known solutions or is it something else?
http://reddit.com/r/numbrosia/info/68s3 ... ts/c03fuy4
My program found 28 and 33 in 15 moves, by the way.
Rémi

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
Once again, thanks for the help.
I would think the optimal solution is 1 or 2 less moves for the 1620 move puzzles and more for the higher move puzzles from the solutions I have found.
I would think the optimal solution is 1 or 2 less moves for the 1620 move puzzles and more for the higher move puzzles from the solutions I have found.

 Posts: 113
 Joined: Tue Feb 12, 2008 8:31 pm
 Contact:
Re: numbrosia
I implemented beam search, and it works very well. I usually get +1, 0 or 1 of your solution. I don't have the motivation to rerun all the problems, or set up an automatic system for playing.
I used a beam width of 100,000 positions. Evaluation was oneply search over SOS + 3 * Minimum_Distance, where Minimum_Distance is read from my table.
Rémi
I used a beam width of 100,000 positions. Evaluation was oneply search over SOS + 3 * Minimum_Distance, where Minimum_Distance is read from my table.
Rémi

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
I changed my evaluation function to include row and column variance. I matched all of the scores that you improved and found 1 less move on puzzle 17. It only takes a few minutes to find the optimal score you found on puzzle 8.
I still do not do any depth searching, just a static evaluation for each node. But I do have a question on depth searching. If you have a node at ply p that you a going to evaluate to depth p+n, the nodes in that depth search are put into the hash table and saved ( put in the closed list ) and the node at p+n is then put on the open list. When you are searching, do you try to process all the nodes on the beam at ply p before ply p+1? Does the beam hold ply p, p+1... p+n at the same time?
I still do not do any depth searching, just a static evaluation for each node. But I do have a question on depth searching. If you have a node at ply p that you a going to evaluate to depth p+n, the nodes in that depth search are put into the hash table and saved ( put in the closed list ) and the node at p+n is then put on the open list. When you are searching, do you try to process all the nodes on the beam at ply p before ply p+1? Does the beam hold ply p, p+1... p+n at the same time?

 Posts: 113
 Joined: Tue Feb 12, 2008 8:31 pm
 Contact:
Re: numbrosia
My oneply search is not stored anywhere at all. I just do a depthfirst search, and use the value it returns to prune the current beam.
Rémi
Rémi
Re: numbrosia
Hi Interesting to hear your approaches. I've been working on an A* approach for optimal solutions I'm not sure how far I'll get before the running time explodes and I'll share some of the heuristics I've been using in case you find them helpful.
Puzzle 10 is runningno 17 move solutions were found (76bn nodes explored). 18 should be optimal!
 Create a table of minimum number of moves for the mod2 version of the puzzle. This is pretty easy to do, is cheap, and typically gives an evaluation of ~6 moves. Overall this doesn't seem very effective except in the endgame.
I haven't tried to build a table for mod 3. This is not cheap or easy As you'll see below I think there are better ways to spend the memory.  Something similar to sumofsquares, but admissible for A*, is figuring out the minimum number of +/ moves needed to solve the puzzle, given an unlimited number of rotations. In fact getting this exactly right in an efficient loop is a bit tricky. I found that the "obvious" heuristics of max(largest positive, sum of positives/5) + max(largest negative, sum of negatives/5) worked very well most of the time; I use a better estimate now, but it only pays off on harder puzzles.
 You can add to #2 a lower bound on the number of rotate operations needed. I've found this to be very promising for getting very solid heuristics. Unfortunately this is tricky to pin down; I am looking into building hash tables for this heuristic. A mod2 hash table typically gets 3 moves.
However there is a neat, easy trick to get up to 2 moves! Look at the sums of each row and column mod 5. The invariant to consider is equality of all the row sums, and equality of all the column sums. Notice that +/ operations do not affect the equality of the row or column sums. A row rotate can only affect equality of the columns, and vice versa. Therefore, if not all row sums are equal mod 5, you need at least one rotation. If not all column sums are equal mod 5, you need at least one (more) rotation. For typical boards this will add 2 to the heuristic.
Puzzle 10 is runningno 17 move solutions were found (76bn nodes explored). 18 should be optimal!

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
Sum of squares puts pressure on the solution to use +/, the counter pressure is variance on row/column to use rotations. This change in my static evaluation has reduced the move count on most of my previous solutions by 1 or 2.
Most of my solutions look at around 1 billion nodes. Higher move count puzzles search more but it is linear.
Most of my solutions look at around 1 billion nodes. Higher move count puzzles search more but it is linear.

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
Remi, for your table, how did you handle collisions?
1GB, 4 bits per entry is 2bn possible positions. What % of your table has entries?
1GB, 4 bits per entry is 2bn possible positions. What % of your table has entries?

 Posts: 113
 Joined: Tue Feb 12, 2008 8:31 pm
 Contact:
Re: numbrosia
Each table entry contains a lower bound on the distance to solution for a position with this code. In case of a collision, I store the minimum distance of all matching positions. Here are the numbers:
In order to make this table efficient, I normalize the position before computing the hash code, using translations/rotations/symmetries. In theory there are 25 translations * 4 rotations * 2 symmetries * 2 sign flip = 400 transformations. I don't check all the possibilities, so my hash code is not as efficient as it could. I normalize by finding the square with the highest absolute value, flip the sign so that it is positive, translate so that it is on the top left, and rotate so that the number below is inferior to the number to the right. It is a compromise between speed and space. I suppose it is possible to be more clever.
Rémi
Code: Select all
tCount[0] = 1
tCount[1] = 1
tCount[2] = 31
tCount[3] = 640
tCount[4] = 11621
tCount[5] = 196153
tCount[6] = 3137072
tCount[7] = 48189589
tCount[8] = 617795983
tCount[9] = 1478152557
Rémi