numbrosia

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
No improvements. I just went back to the boards where I didn't have the lowest score and ran them with different parameters until I found the solution.
I use an equal weight of the sum of squares and the variance on the rows and columns. Some boards need more variance reduction pressure. With runtimes in the 812 minute range, I just make multiple runs until I find the parameters that produce a solution to match what others have found.
I use an equal weight of the sum of squares and the variance on the rows and columns. Some boards need more variance reduction pressure. With runtimes in the 812 minute range, I just make multiple runs until I find the parameters that produce a solution to match what others have found.
Re: numbrosia
Yes, should be. I haven't made any improvements the past two weeks  I'm just letting it run for now. Puzzle 20 took 3 days to solve. Puzzle 21 is still running, and 19 should be the optimum.Sir Niko wrote:Are you still optimal, luke_g?

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
I would be interested to see how many moves reduce the sum of squares evaluation for the puzzles I can't match your score. Another way my solver will fail is if there are many rotations early in the solution.
I changed my evaluation so I use the sum of the variations squared instead of just the sum. In the first 100 puzzles I have improved about 20% by 1 move.
What depth do you think I would have to search in my evaluation function to get past the horizon of negative moves?
I changed my evaluation so I use the sum of the variations squared instead of just the sum. In the first 100 puzzles I have improved about 20% by 1 move.
What depth do you think I would have to search in my evaluation function to get past the horizon of negative moves?
Re: numbrosia
Hmm, not sure what depth you'd need to search. The solution I found for 22 and 23 might be difficult to find, because both have "long" (45 moves) sequences of rotations followed by long sequences of additions (of course there may be other solutions). Otherwise, I haven't noticed any strange or inhuman movesit's just that everything lines up nicely in the endso I don't see why a simpler search couldn't find the solutions.
I suppose you could try an experiment of how much additional depth tends to help: run a bunch of puzzles with depth 3, then 4, then 5.... Would be interesting to see the results.
Anyway, I think my advice would be to come up with a stronger evaluation function. I like the idea of variance being part of it, but I'm not sure about sum of squares. As I posted a while ago, a key part of the evaluation I'm using for A* is the number of additions required to solve the puzzle, given an unlimited number of rotations. It will penalize a lone +5 more than a +5 with a +4 (the former will leave a lot of negative numbers after doing the 5 subtractions), which might help (or maybe it won't ). A good approximation to this may be much more difficult to compute than sum of squares, but it also might help narrow your searches significantly.
I suppose you could try an experiment of how much additional depth tends to help: run a bunch of puzzles with depth 3, then 4, then 5.... Would be interesting to see the results.
Anyway, I think my advice would be to come up with a stronger evaluation function. I like the idea of variance being part of it, but I'm not sure about sum of squares. As I posted a while ago, a key part of the evaluation I'm using for A* is the number of additions required to solve the puzzle, given an unlimited number of rotations. It will penalize a lone +5 more than a +5 with a +4 (the former will leave a lot of negative numbers after doing the 5 subtractions), which might help (or maybe it won't ). A good approximation to this may be much more difficult to compute than sum of squares, but it also might help narrow your searches significantly.

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
The goal of the evaluation function is to provide an estimate of the value of a board position compared to others at that ply level. Unlike depth searching, the first time a board postition is encountered, it is the best one as others will be at the same ply level or greater.
The Sum of Absolute Values (SOA) works poorly because you might end up with 20 million nodes with a 5 evaluation. Some of those nodes are better than others, so the correct ones don't make it by the truncation.
The Sum of Squares (SOS) gives a wider range of evaluations, especially in the early plys, so superior nodes make it by the truncation process.
SOA or SOS give the motivation for using the plus and minus moves. In addition there needs to be pressure to use the rotation moves.
The variation evaluations drive the solution to all cells having the same number, not 0, which we need in this puzzle.
The Sum of Absolute Value of Variation (SOAV) adds up all the variations in the rows and columns.
The Sum of Squared Variation (SOSV) gives a wider range of evaluation, but in some puzzles it causes excess rotations.
The 750 puzzles were run with SOS+SOAV. I have gone back and run the first 300 with SOS+SOSV, improving 57. There were a few that had worse solutions.
The Sum of Absolute Values (SOA) works poorly because you might end up with 20 million nodes with a 5 evaluation. Some of those nodes are better than others, so the correct ones don't make it by the truncation.
The Sum of Squares (SOS) gives a wider range of evaluations, especially in the early plys, so superior nodes make it by the truncation process.
SOA or SOS give the motivation for using the plus and minus moves. In addition there needs to be pressure to use the rotation moves.
The variation evaluations drive the solution to all cells having the same number, not 0, which we need in this puzzle.
The Sum of Absolute Value of Variation (SOAV) adds up all the variations in the rows and columns.
The Sum of Squared Variation (SOSV) gives a wider range of evaluation, but in some puzzles it causes excess rotations.
Code: Select all
PUZ OPT SOA SOS SOS+SOAV SOS+SOSV
4 9 9 9 9 9
5 4 4 4 4 4
6 14 14 14 14 14
7 13 13 14F 13 13
8 16 17F 17F 16 16
9 9 9 9 9 9
10 18 19F 18 18 18
11 12 12 12 12 12
12 12 12 12 12 12
13 18 19F 18 18 18
14 10 10 10 10 10
15 12 12 12 12 12
16 15 15 15 15 15
17 18 19F 19F 18 18
18 20 23F 22F 21F 21F
19 17 18F 18F 17 17
20 20 22F 22F 21F 21F
21 19 19 21F 19 19
22 18 22F 20F 19F 19F
23 18 19F 19F 19F 19F
Fail 9 9 4 4
The 750 puzzles were run with SOS+SOAV. I have gone back and run the first 300 with SOS+SOSV, improving 57. There were a few that had worse solutions.

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
I ran the partial depth search evaluation ( 1 ply ) for the 6 puzzles I failed to find the optimal solution. It found the solution for puzzle 26. I have only run the 2 ply on one puzzle and it did not find the optimal solution, but I found an error and will have to rerun.
puzzle 25 run times
orig 6 minutes
1 ply 28 minutes
2 ply 10.5 hours
The code to run the evaluation on the video card is taking some time to write but I hope to able to do at least a 3 ply search in a reasonable amount of time.
puzzle 25 run times
orig 6 minutes
1 ply 28 minutes
2 ply 10.5 hours
The code to run the evaluation on the video card is taking some time to write but I hope to able to do at least a 3 ply search in a reasonable amount of time.
Re: numbrosia
By the way, I will probably post my code in the next few days. I don't think puzzle 32 will finish it took 10 hours to reach depth 23. I won't search past depth 24. (Depth 27 is the best known solution)

 Posts: 34
 Joined: Fri Mar 28, 2008 8:15 pm
Re: numbrosia
luke_g, does that mean you not going to work on Numbrosia anymore?
Re: numbrosia
Well, not necessarily However, I haven't actually touched the could for a couple weeks now. I have some ideas for small improvements (which I'll list eventually), but nothing I'm excited about. My free time is very limited, and I'm thinking about moving on to Arimaa or Go (or maybe try samegame quick!)spurious_ai wrote:luke_g, does that mean you not going to work on Numbrosia anymore?
If I think of a new idea for a heuristic, I'll definitely come back to it. I still feel like there are stronger heuristics possible. For example, what has stumped me is that I can't think of any heuristic that would be exact for a board of 1s on the diagonal, and otherwise all 0s, even though this puzzle is obvious to humans!