numbrosia

Any topic that does not fit elsewhere
spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: numbrosia

Post by spurious_ai » Sat Mar 29, 2008 5:03 pm

Thanks for the help.

The breadth-first 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?

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: numbrosia

Post by Rémi Coulom » Sat Mar 29, 2008 6:39 pm

spurious_ai wrote:Thanks for the help.

The breadth-first 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?
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:
http://reddit.com/r/numbrosia/info/68s3 ... ts/c03fuy4

My program found 28 and 33 in 15 moves, by the way.

Rémi

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: numbrosia

Post by spurious_ai » Sat Mar 29, 2008 6:49 pm

Once again, thanks for the help.

I would think the optimal solution is 1 or 2 less moves for the 16-20 move puzzles and more for the higher move puzzles from the solutions I have found.

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: numbrosia

Post by Rémi Coulom » Sat Mar 29, 2008 9:38 pm

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 re-run all the problems, or set up an automatic system for playing.

I used a beam width of 100,000 positions. Evaluation was one-ply search over SOS + 3 * Minimum_Distance, where Minimum_Distance is read from my table.

Rémi

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: numbrosia

Post by spurious_ai » Sun Mar 30, 2008 2:36 am

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?

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: numbrosia

Post by Rémi Coulom » Sun Mar 30, 2008 11:57 am

My one-ply search is not stored anywhere at all. I just do a depth-first search, and use the value it returns to prune the current beam.

Rémi

luke_g
Posts: 29
Joined: Sun Feb 17, 2008 9:52 am

Re: numbrosia

Post by luke_g » Mon Mar 31, 2008 6:18 am

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.
  1. Create a table of minimum number of moves for the mod-2 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.
  2. Something similar to sum-of-squares, 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.
  3. 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 mod-2 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.
Right now I am working on getting more moves from heuristic 3. Also, I'd like to construct an end-game table so that I can shave the last few moves off the search (I think it should be a good speedup; doing a hash table lookup should be cheaper than generating all the children of the last few moves). Finally, my move generation could be more precise (I've had a lot of bugs in this part of the code!). Although I do take into account commutivity and inverses, there are a few more things I can prune.

Puzzle 10 is running--no 17 move solutions were found (76bn nodes explored). 18 should be optimal!

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: numbrosia

Post by spurious_ai » Mon Mar 31, 2008 3:03 pm

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.

spurious_ai
Posts: 34
Joined: Fri Mar 28, 2008 8:15 pm

Re: numbrosia

Post by spurious_ai » Fri Apr 04, 2008 6:44 pm

Remi, for your table, how did you handle collisions?

1GB, 4 bits per entry is 2bn possible positions. What % of your table has entries?

Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

Re: numbrosia

Post by Rémi Coulom » Fri Apr 04, 2008 8:19 pm

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:

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
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

Post Reply