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 » Thu Apr 17, 2008 3:17 pm

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 8-12 minute range, I just make multiple runs until I find the parameters that produce a solution to match what others have found.

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

Re: numbrosia

Post by Sir Niko » Wed Apr 23, 2008 9:59 am

Are you still optimal, luke_g?

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

Re: numbrosia

Post by luke_g » Fri Apr 25, 2008 1:54 am

Sir Niko wrote:Are you still optimal, luke_g?
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.

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

Re: numbrosia

Post by spurious_ai » Sat Apr 26, 2008 3:44 pm

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?

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

Re: numbrosia

Post by luke_g » Sat Apr 26, 2008 6:46 pm

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" (4-5 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 moves--it's just that everything lines up nicely in the end--so 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.

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

Re: numbrosia

Post by spurious_ai » Tue Apr 29, 2008 3:44 pm

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.

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.

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

Re: numbrosia

Post by spurious_ai » Fri May 09, 2008 3:10 pm

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 re-run.

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.

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

Re: numbrosia

Post by luke_g » Sat May 10, 2008 5:48 am

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)

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

Re: numbrosia

Post by spurious_ai » Sun May 11, 2008 8:05 pm

luke_g, does that mean you not going to work on Numbrosia anymore?

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

Re: numbrosia

Post by luke_g » Mon May 12, 2008 12:15 am

spurious_ai wrote:luke_g, does that mean you not going to work on Numbrosia anymore?
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!)

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!

Post Reply