numbrosia

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
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 13 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?
I have replayed all the boards with my new evaluation and improved almost all the boards 13 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?

 Posts: 113
 Joined: Tue Feb 12, 2008 8:31 pm
 Contact:
Re: numbrosia
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 1012. So you can generate plenty of them, and tune parameters on them.
Rémi
It is rather fast to solve positions at depth 1012. So you can generate plenty of them, and tune parameters on them.
Rémi
Re: numbrosia
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.

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
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 suboptimal? 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
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 suboptimal? 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
Re: numbrosia
Yes, unless I still have some bugs, the solutions should be the minimum possible.spurious_ai wrote:Do you know if all the boards you have solved so far you have the optimal solution?
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.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?
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 120, the heuristic has usually been off 35 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...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 suboptimal?
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.
I can get back to you on this. Both will surely be well into the 20's though.These 2 boards took my program 44 moves. Can you get an estimate of the optimal score?

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
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
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
Re: numbrosia
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:{{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 34. 400mm nodes show there is no length 34 solution, so 35 is a lower bound.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}}
Re: numbrosia
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
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
Re: numbrosia
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 nearlysolved 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)
Re: numbrosia
Congratulations spurious!
Do you like to tell us what you improved?
Do you like to tell us what you improved?