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 Apr 05, 2008 9:50 pm

The translations/rotations/symmetries must be very important for Go programming. I will probably do a smaller table just to cut down on runtime.

I have replayed all the boards with my new evaluation and improved almost all the boards 1-3 moves. Now I have to try to match your score on puzzle 73. I need to try different weights on the 2 parts of the evaluation. Some boards need to reduce variation before adding and subracting. Others need to avoid excess rotations. The weights might have to change on a ply to ply basis. Can you think of a way to normalize the weights? Do you multiply the sum of squares by the weight to reduce its effect, or do you use a power other than 2?

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

Re: numbrosia

Post by Rémi Coulom » Sun Apr 06, 2008 1:06 pm

You could tune the weights of your evaluation function by trying to match the distance to solution over a set of positions whose optimal solution is known. This is what I would do.

It is rather fast to solve positions at depth 10-12. So you can generate plenty of them, and tune parameters on them.

Rémi

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

Re: numbrosia

Post by luke_g » Sat Apr 12, 2008 3:07 am

At last, the A* approach pays off :) Got 20 moves for puzzle 18, beating the previous record of 21. It took about 50bn nodes and 18 hours to find it; the original heuristic for the puzzle was 17 moves.

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

Re: numbrosia

Post by spurious_ai » Sat Apr 12, 2008 4:10 am

Do you know if all the boards you have solved so far you have the optimal solution?

Before I perfected my auto load code, I got some boards with the wrong numbers that were not solvable. What is the condition that makes a board solvable?

Will 20 moves be the limit for your solver to be optimal ( and run in our lifetime )? Can you adapt to solve longer puzzles but be sub-optimal? These 2 boards took my program 44 moves. Can you get an estimate of the optimal score?

{{-1,-5,8,2,-5},{-1,4,-7,-2,-3},{-3,-3,-6,-3,-5},{-1,-7,-10,-5,-9},{-5,-7,-5,0,-6}} // 516
{{-2,9,0,4,8},{-1,1,5,-2,-3},{-10,6,6,6,5},{-2,6,-6,9,-3},{-2,8,2,8,-2}} // 644

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

Re: numbrosia

Post by luke_g » Sat Apr 12, 2008 6:25 pm

spurious_ai wrote:Do you know if all the boards you have solved so far you have the optimal solution?
Yes, unless I still have some bugs, the solutions should be the minimum possible.
Before I perfected my auto load code, I got some boards with the wrong numbers that were not solvable. What is the condition that makes a board solvable?
Only that the sum of the numbers on the board is a multiple of 5. You can prove this by starting with two observations: (1) For any pair of numbers on the board, you can +1 to one number and -1 to the other number (2) You can change a number by a multiple of 5. Then, you can show that a combination of these techniques will solve any board: use (1) to make every number into a multiple of 5, then use (2) to eliminate multiples of five.
Will 20 moves be the limit for your solver to be optimal ( and run in our lifetime )?
Well, it depends a lot on the heuristic. If every square of the board is a 20, the programm will instantly find the solution because the heuristic is precise for this board. In levels 1-20, the heuristic has usually been off 3-5 moves, and taken from seconds to 1 day to solve. I have one big speedup left, which should increase the solve speed by at least an order of magnitude. On the other hand, I'm out of ideas for improving the heuristic (at least, with a 3GB ram limit!). I'm not quite sure what the limits of the program will be...
Can you adapt to solve longer puzzles but be sub-optimal?


Sure, I could use the heuristic as the evaluation function, and then do a search similar to your or Remi. First, however, I'd like to see how many boards I can solve optimally.
These 2 boards took my program 44 moves. Can you get an estimate of the optimal score?
I can get back to you on this. Both will surely be well into the 20's though.

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

Re: numbrosia

Post by spurious_ai » Sat Apr 12, 2008 7:03 pm

With the type of searching I am doing, a doubling of memory only doubles the nodes searched. Your method probably takes better advantage of the extra memory.

I have a quad with 8gb of memory and XP64 if you need someone to run tests.

My next step is to do a partial depth search as the evalutaion. The static evaluation works well but I believe there is a better solution for the boards with 20+ moves. My plan is to push the evaluation to my video card that has 64 processors and 1GB of memory. http://www.nvidia.com/object/cuda_home.html

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

Re: numbrosia

Post by luke_g » Sun Apr 13, 2008 8:11 am

spurious_ai wrote:{{-1,-5,8,2,-5},{-1,4,-7,-2,-3},{-3,-3,-6,-3,-5},{-1,-7,-10,-5,-9},{-5,-7,-5,0,-6}}
Heuristic of 37. I let it run for about 20 minutes, but it didn't finish exploring even 37 moves... this puzzle is definitely beyond my current solver!
spurious_ai wrote:{{-2,9,0,4,8},{-1,1,5,-2,-3},{-10,6,6,6,5},{-2,6,-6,9,-3},{-2,8,2,8,-2}}
Heuristic of 34. 400mm nodes show there is no length 34 solution, so 35 is a lower bound.

Sir Niko
Posts: 3
Joined: Sun Apr 13, 2008 1:33 pm

Re: numbrosia

Post by Sir Niko » Sun Apr 13, 2008 1:38 pm

Hi,
i just let my solver run on the data of puzzle 516 you posted above. I can give you an upper bound of 43.
On puzzle 73 I got 31.
I will now try puzzle 644.

Niko

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

Re: numbrosia

Post by luke_g » Tue Apr 15, 2008 5:15 am

I said earlier that I had a big speed improvement, but that's not correct. I didn't realize that very little time is spent on nearly-solved puzzles because of the A* algorithm. Unless I can think of ways to improve the heuristic (or pruning) and remain admissable, I might be stuck! (The next puzzle might take more than a week to finish)

Sir Niko
Posts: 3
Joined: Sun Apr 13, 2008 1:33 pm

Re: numbrosia

Post by Sir Niko » Wed Apr 16, 2008 9:58 pm

Congratulations spurious!
Do you like to tell us what you improved?

Post Reply