numbrosia

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

Re: numbrosia

Post by Rémi Coulom » Mon May 12, 2008 4:17 pm

luke_g wrote: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!
Isn't a 2^25-entry table of minimum number of rotations indexed by tile parities enough ? I believe you suggested this idea yourself some time ago.

Rémi

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

Re: numbrosia

Post by luke_g » Wed May 14, 2008 2:54 am

Rémi Coulom wrote: Isn't a 2^25-entry table of minimum number of rotations indexed by tile parities enough ? I believe you suggested this idea yourself some time ago.
Nope, although it does help a lot in practice, it still comes short on a lot of simple positions. In fact I'm using a 4^16-entry table for mod 4, but this only gives up to 4 rotations (and about 90% of positions do give 4 rotations) when unlimited additions are allowed. I wonder if there is something unlucky about mod 4, or if there's a mathematical reason why so few rotations are needed.

I figure a mod 5 table is doable with 4GB ram, but wouldn't be easy--that would be one of the next things I'd try.

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

Re: numbrosia

Post by luke_g » Wed May 21, 2008 11:40 pm

I've uploaded my code. It's messy (in particular I unrolled many loops to help performance), but maybe it'll be useful :)

http://www.luke-g.com/numbrosia/

You will need the 5 .rar files to run the program--these uncompress to 2+GB and contain the lookup tables. I don't think I'll upload the code used to generate these files because it's too scattered. The program itself requires over 2GB ram, so must be linked with LARGEADDRESSAWARE on win32 platforms. The code wasn't written to be portable, although I think changing int's to int32's is the only big thing. Note, the program crashes on bad input--I never bothered to fix that.

The heuristic is the function PlusMod5Mod4Heuristic. In particular, you might want to check out the code for computing the minimum number of additions needed:

Code: Select all

//Compute minimum number of additions needed.
	//First do positive numbers...
	buckets[63] = 0;  //bucket 63 and 62 will be used to store results.
	for( i = 62; i > 32; i-- )
	{
		while( buckets[i] >= 5 )
		{
			buckets[i] -= 5;
...
...
...
	if( buckets[63] > buckets[62] )
		Moves += (buckets[63] - buckets[62]) / 5;
	else
		Moves += (buckets[62] - buckets[63]) / 5;

To use this code, I think all you need to know is that buckets contains the number of puzzle entries == i-32. The minimum number of additions needed is then added to Moves.

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

Re: numbrosia

Post by Rémi Coulom » Thu May 22, 2008 4:32 pm

luke_g wrote:I've uploaded my code. It's messy (in particular I unrolled many loops to help performance), but maybe it'll be useful :)
Thanks for sharing. I also attach my code, in case anyone is interested. You have to enter the board on standard input. By default, it will do a beam search. You can tell the size of the beam on the command line. If you wish to solve a board, replace "#if 0" by "#if 1" in main. The program will generate the table if it does not find it.

Rémi
Attachments
Numbrosia.cpp
(21.21 KiB) Downloaded 350 times

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

Re: numbrosia

Post by spurious_ai » Sat May 24, 2008 4:36 pm

Looking at your code Remi, not quite sure of the difference between a breadth search and a beam search. My program is not simple because its designed to run on 2 to 16 processors. The only functions that might help others would be the auto-load and auto-play code.

Not sure if we are coming up with the same variance. Here is my eval function for reference.

Code: Select all

void  CNode::Eval()
{
/*	short  soa;

	soa  = abs( m_b[0] )  + abs( m_b[1] )  + abs( m_b[2] )  + abs( m_b[3] )  + abs( m_b[4] );
	soa += abs( m_b[5] )  + abs( m_b[6] )  + abs( m_b[7] )  + abs( m_b[8] )  + abs( m_b[9] );
	soa += abs( m_b[10] ) + abs( m_b[11] ) + abs( m_b[12] ) + abs( m_b[13] ) + abs( m_b[14] );
	soa += abs( m_b[15] ) + abs( m_b[16] ) + abs( m_b[17] ) + abs( m_b[18] ) + abs( m_b[19] );
	soa += abs( m_b[20] ) + abs( m_b[21] ) + abs( m_b[22] ) + abs( m_b[23] ) + abs( m_b[24] );*/

	short  sos;

	sos  = m_b[0] * m_b[0] + m_b[1] * m_b[1] + m_b[2] * m_b[2] + m_b[3] * m_b[3] + m_b[4] * m_b[4];
	sos += m_b[5] * m_b[5] + m_b[6] * m_b[6] + m_b[7] * m_b[7] + m_b[8] * m_b[8] + m_b[9] * m_b[9];
	sos += m_b[10] * m_b[10] + m_b[11] * m_b[11] + m_b[12] * m_b[12] + m_b[13] * m_b[13] + m_b[14] * m_b[14];
	sos += m_b[15] * m_b[15] + m_b[16] * m_b[16] + m_b[17] * m_b[17] + m_b[18] * m_b[18] + m_b[19] * m_b[19];
	sos += m_b[20] * m_b[20] + m_b[21] * m_b[21] + m_b[22] * m_b[22] + m_b[23] * m_b[23] + m_b[24] * m_b[24];

	short  var = 0;

	for( int  i = 0; i < 5; i++ )
		{
		int  q = i * 5;

		char  d01 = m_b[q]   - m_b[q+1];
		char  d02 = m_b[q]   - m_b[q+2];
		char  d03 = m_b[q]   - m_b[q+3];
		char  d04 = m_b[q]   - m_b[q+4];
		char  d12 = m_b[q+1] - m_b[q+2];
		char  d13 = m_b[q+1] - m_b[q+3];
		char  d14 = m_b[q+1] - m_b[q+4];
		char  d23 = m_b[q+2] - m_b[q+3];
		char  d24 = m_b[q+2] - m_b[q+4];
		char  d34 = m_b[q+3] - m_b[q+4];

//		var += abs( d01 ) + abs( d02 ) + abs( d03 ) + abs( d04 ) + abs( d12 ) + abs( d13 ) + abs( d14 ) + abs( d23 ) + abs( d24 ) + abs( d34 );
		var += d01 * d01 + d02 * d02 + d03 * d03 + d04 * d04 + d12 * d12 + d13 * d13 + d14 * d14 + d23 * d23 + d24 * d24 + d34 * d34;
		}

	for( int  i = 0; i < 5; i++ )
		{
		int  q = i;

		char  d01 = m_b[q]    - m_b[q+5];
		char  d02 = m_b[q]    - m_b[q+10];
		char  d03 = m_b[q]    - m_b[q+15];
		char  d04 = m_b[q]    - m_b[q+20];
		char  d12 = m_b[q+5]  - m_b[q+10];
		char  d13 = m_b[q+5]  - m_b[q+15];
		char  d14 = m_b[q+5]  - m_b[q+20];
		char  d23 = m_b[q+10] - m_b[q+15];
		char  d24 = m_b[q+10] - m_b[q+20];
		char  d34 = m_b[q+15] - m_b[q+20];

//		var += abs( d01 ) + abs( d02 ) + abs( d03 ) + abs( d04 ) + abs( d12 ) + abs( d13 ) + abs( d14 ) + abs( d23 ) + abs( d24 ) + abs( d34 );
		var += d01 * d01 + d02 * d02 + d03 * d03 + d04 * d04 + d12 * d12 + d13 * d13 + d14 * d14 + d23 * d23 + d24 * d24 + d34 * d34;
		}

	m_eval = sos + var;
}
I am not sure how these mod tables are designed Luke. There is something to be said for mechanics and speed, but finding the heuristic is the true spirit of the contest.

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

Re: numbrosia

Post by luke_g » Mon May 26, 2008 8:42 pm

spurious_ai wrote:Looking at your code Remi, not quite sure of the difference between a breadth search and a beam search.
I think "beam search" is basically a breadth-first search, but discarding nodes beyond a limit.
spurious_ai wrote: I am not sure how these mod tables are designed Luke. There is something to be said for mechanics and speed, but finding the heuristic is the true spirit of the contest.
Well, the idea for the rotations table is this. First, solving the actual puzzle means that you have also solved the puzzle modulo 4. So, the minimum number of rotations needed for the actual puzzle, is at least the number needed for the mod 4 puzzle. Now, we can create a lookup table of all mod 4 puzzles -- there are 4^25 of them. However, since we allow unlimited additions, we can zero out the first row & column with additions, leaving only 4^16 that we actually need. (You could further reduce this with symmetries.) That's just within reach if you give 4 bits per entry.

Creating the table was nothing terribly exciting, performance was the main issue (both memory access and CPU speed are major bottlenecks!). Starting with the solved puzzle, give it a value of 0. Then, compute all possible puzzles one move away, and give them values of 1. Then for each puzzle with value 1, compute all puzzles one move away and give them value 2. Et cetera. As I mentioned, it was disappointing, but only 4 rotations ever seem to be necessary. However, it's just enough to make puzzles requiring ~20 moves solvable.

Jack9
Posts: 1
Joined: Sat Oct 25, 2008 10:37 am

Re: numbrosia

Post by Jack9 » Sat Oct 25, 2008 10:39 am

http://www.geocities.com/jaapsch/puzzle ... tm#minimal

It's just a lot more complicated version of lights out.

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

Re: numbrosia

Post by Rémi Coulom » Sat Oct 25, 2008 11:41 am

Jack9 wrote:http://www.geocities.com/jaapsch/puzzle ... tm#minimal

It's just a lot more complicated version of lights out.
Thanks for the pointer. It is similar, indeed.

I would say that Numbrosia is in fact much more like Rubik's Cube than like lights out. In lights out, move order does not matter. In Numbrosia, it is very important.

Let's say it is a combination of lights out and rubiks cube :-)

Rémi

Post Reply