numbrosia

Any topic that does not fit elsewhere
Rémi Coulom
Posts: 113
Joined: Tue Feb 12, 2008 8:31 pm
Contact:

numbrosia

Post by Rémi Coulom » Thu Mar 13, 2008 1:34 am

Cool little puzzle:
http://numbrosia.com/
Finding the optimal solution does not seem easy. This puzzle is discussed in the numbrosia google group:
http://groups.google.com/group/numbrosia

Rémi

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

Re: numbrosia

Post by luke_g » Sat Mar 22, 2008 5:00 am

Thanks, this is rather addictive!

I'm going to see how far I can get with depth-first A*. lukeg_ai is my computer player; I'm working on heuristics and will let you know what I come up with. lukeg is my unassisted screenname.

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

Re: numbrosia

Post by Rémi Coulom » Sat Mar 22, 2008 10:22 am

Cool. In case you did not notice, the programming discussion is not taking place in the Google group I indicated, but rather in that reddit page:
http://reddit.com/r/numbrosia/

Rémi

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

Re: numbrosia

Post by spurious_ai » Fri Mar 28, 2008 8:18 pm

Not too much discussion going on. I like the format of this forum better.

I am using a breadth first search. It seems everyone else is using depth first search.

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

Re: numbrosia

Post by Rémi Coulom » Fri Mar 28, 2008 9:13 pm

spurious_ai wrote:I am using a breadth first search. It seems everyone else is using depth first search.
I am not sure I understand what you mean by breadth-first search. Isn't what you do more like best first?
http://www.macs.hw.ac.uk/~alison/ai3not ... 2_3_2.html
I suppose you do best first, because you must explore some branches of the tree deeper than some others.

Don't you also add a term that depends on current depth to the score of a position ? Or maybe you expand the oldest open positions first, using a FIFO data structure ? There must be something like this, otherwise your search would blow up, I guess.

I found the optimal solution of problem 8 in about 6 hours of computation with my depth-first search. But it is not possible to go much further with such an approach.

I am going to try best-first now ;-)

Rémi

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

Re: numbrosia

Post by spurious_ai » Fri Mar 28, 2008 10:11 pm

I generate all the moves from the starting point. I then take all those moves and generate the second move. You can't keep all the moves, just the best ones.

If I can store 30 million nodes, I might keep 500,000 for each move. From those 500,000 it generates on average about 15 million. Of those 15 million, I truncate it down to the best 500,000 and do the next move. I don't always get the 15 million, there is an upper bound that truncates nodes that are just getting worse.

Breadth first searching, some refer to it as a beam search. The beam size is the number of nodes ready to be searched.

I average 10 minutes a board and only 1 out of 280 boards do I not have the best score.

I can control the run time by adjusting the beam size.

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

Re: numbrosia

Post by Rémi Coulom » Fri Mar 28, 2008 10:53 pm

I see. Thanks for explaining.

You may have difficulties to solve position 8 this way, because the final 4 steps are 3 + and 1 - (at least in the solution I found). There is a lot of moving around before reaching the magic configuration where all the numbers are reduced to zero. Maybe you'd do better with a refined heuristic.

Rémi

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

Re: numbrosia

Post by spurious_ai » Fri Mar 28, 2008 11:21 pm

This was just my first version of the program. I have been looking for an application so I can learn CUDA. This is NVidia's C language for video cards. With 128 processors on the video card I should be able to do a 4 or 5 ply depth search for a better evaluation.

The power of the breadth first search is that I can do the later puzzles that have 35 moves without changing the program. The run time just climbs to 20 minutes a board.

I have code to send the mouse clicks to the puzzle window so you don't have to play the moves yourself if you need it.

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

Re: numbrosia

Post by spurious_ai » Sat Mar 29, 2008 4:21 am

If you have computer time, puzzles 27 ( 13 moves, +1 for your program ), puzzle 28 ( 16, +1 ) and puzzle 33 ( 16, +1 ) would let me know if there is a lower move count for those puzzles. That is the end of the low move count puzzles.

The sum of the squares has worked fairly well as a static evaluation, but the variance in rows and columns has to be considered.

Do you have ideas to extend your program to solve 30+ move puzzles? Is your goal like the other programmers working on Numbrosia, to get the optimal solution on a limited set of puzzles?

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 4:23 pm

spurious_ai wrote:If you have computer time, puzzles 27 ( 13 moves, +1 for your program ), puzzle 28 ( 16, +1 ) and puzzle 33 ( 16, +1 ) would let me know if there is a lower move count for those puzzles. That is the end of the low move count puzzles.
13 moves for puzzle 27 is optimal (if I don't have bugs). I started the search for puzzle 28, but it may take some time.
The sum of the squares has worked fairly well as a static evaluation, but the variance in rows and columns has to be considered.

Do you have ideas to extend your program to solve 30+ move puzzles? Is your goal like the other programmers working on Numbrosia, to get the optimal solution on a limited set of puzzles?
I don't expect it is possible to find the optimal solution for the long puzzles. I'll try your breadth-first approach. I expect I can reuse the big table I use to prune the optimal search. It gives a lower bound on the number of necessary moves to solution. Most of the time, it gives a lower bound of 9, which helps to prune a lot. It could help sum-of-squares in the final stages of the puzzle.

Rémi

Post Reply