Any hints?

[Hippo]

I have decided to change a bit the task selection ... roughly 200 days without success is too much

I hope it will find solution faster now ...

Yes, I have an idea how to change the search (unsuccessful search would be slower, but as the solution existence is guaranted...) ... maybe after codding worm, if the level 56 would still be unbeaten ...

Finally it helped

[Hippo]

I have looked on statistics selecting task for level 58 ... it seems to be hrader than level 56.
First of tasks having solution density above 1/20 was task number 1218.

It has roughly e^60.5 states with e^57.5 posible piece placement options (other tasks were orders of magnitude harder) (56 times to reopen a square).

Seems the top 3 must have invented something smart ...

[Isaev]

Cool Hippo!
I can't 41

[Hippo]

Wow lvhao945 already solved level 58 ... maybe I have to start working on it again ...

[camel]

Any hint on what you did after the 43-ish levels? You mentioned Zobrist hashing but that's not really speeding up things - does it?

I just found out that the boost library now features very efficient "simulated" 128bit and 256bit int types and I'll try to represent the board as n=$depht-1 separate integers ... using individual bits to represent the tile's state.

For $depth==3 I got 1 integer ($b1) where every bit set to 1 means that the state of the tile is 1 and another integer ($b2) where every bit set to 1 means that the state of the tile is 2.

So adding a piece becomes 6 bit operations ... but that just gives me a lot more speed and a lot less memory overhead ... but it does not really decrease the search space.

Code: Select all

sub addPiece {
 my($b1_ref,$b2_ref,$piece_ref)=@_;
 my $bitsForB2 = $$piece_ref & $$b2_ref;    # bits of $piece which change the tile back to 0
 my $bitsForB1 = $$piece_ref ^ $bitsForB2; # bits of $piece which won't
 my $carryOver = $$b1_ref    & $bitsForB1; # carryover
 $$b1_ref = $$b1_ref ^ $bitsForB1; # xor bits into $b1
 $$b2_ref = $$b2_ref ^ $bitsForB2; # xor bits into $b2
 $$b2_ref = $$b2_ref ^ $carryOver; # xor carryOver from $b1 into $b2
}

So adding a piece "00000111" to a "00021021" $depth==3 board looks like this:

Code: Select all

$b1==00001001
$b2==00010010

Adding piece:
00000111

$b1==00001100
$b2==00010001

It's weird to represent the board via one variable per $depth (except for 0 of course) but it should work and save a ton of computational overhead ...

Reversing the board state would mean to just swap $b1 and $b2 ... no more MOD() or lookup tables ...

Checking whether the board is solved is just a "$b1==0 && $b2==0" check ... etc., etc., ...

[camel]

This was "inspired" by this post about ways to hash a board game's state ... http://stackoverflow.com/a/4301869 ... but using 2-3 sequential bits to represent a tile will cost a lot of computation (for individual access and manipulation) and so using a separate vector of bits (i.e. uint128) for every $depth level seems like a good idea. Time will tell ...

[Hippo]

Any hint on what you did after the 43-ish levels? You mentioned Zobrist hashing but that's not really speeding up things - does it?

I have not speeded up the hashing, yes it costs the "rounding rectangle size" for modulo > 2.
Of course you could precompute the piece positions for the modulo = 2 case and than the hashing would be O(1).

[camel]

So still no hint from you guys?

It seems as if representing the board as n=$depth-1 bitsets speeds up things dramatically ...

Getting the required "flippower" of a board is a matter of calling the CPU's builtin "popcount" instruction (returning the number of bits set in the bitset) and multiplying it with whatever $depth the respective bitset is representing.

Here are the required logical operations to add a piece (e.g. 001011) to a $depth=3 board represented by two bitsets. The board 022100 would be represented as $bitset1=000100 and $bitset2=011000.

Using 5-6 AND/XOR operations to add/remove a tile to/from the board should be much faster than playing around with arrays - especially once I move to C++ and some inline ASM.

Here is the Perl test code ... BXOR and BAND should be self-explanatory ...

Code: Select all

sub addPiece {
 my($b1_ref,$b2_ref,$piece_ref)=@_;
 my $bitsForB2 = $$piece_ref->copy()->band($$b2_ref);
 my $bitsForB1 = $$piece_ref->copy()->bxor($bitsForB2);
 my $carryOver = $$b1_ref->copy()->band($bitsForB1);
 $$b1_ref = $$b1_ref->copy()->bxor($bitsForB1);
 $$b2_ref = $$b2_ref->copy()->bxor($bitsForB2);
 $$b2_ref = $$b2_ref->copy()->bxor($carryOver);
}

sub removePiece {
 my($b1_ref,$b2_ref,$piece_ref)=@_;
 my $bitsForB1 = $$piece_ref->copy()->band($$b1_ref);
 my $bitsForB2 = $$piece_ref->copy()->bxor($bitsForB1);
 #my $carryOver =  $$piece_ref->copy()->band($bb2_ref);
 my $carryOver = $$b2_ref->copy()->band($bitsForB2);
 $$b1_ref = $$b1_ref->copy()->bxor($bitsForB1);
 $$b2_ref = $$b2_ref->copy()->bxor($bitsForB2);
 $$b1_ref = $$b1_ref->copy()->bxor($carryOver);
}

Next thing I'll try is a heuristic based on the number of edges (between tiles with unequal values) on the board. So the algorithm prefers to go deeper at states where the tiles are less spread.

i.e.: Two adjacent tiles with the same "value", together feature 6 edges while two separate tiles feature 8 edges ... so we want to prefer the more orderly/compact states. States with a lower Kolmogorov complexity that is. This could help in certain situations ... if the level doesn't expect you to place a lot of "chaos" inducing pieces that is ...

[camel]

Here is the code for C++ for a depth of 3 ... testing it with std::bitset. Using bitsets speeds up things dramatically. I'll now work on the weighting of the new heuristic and I'll also do some early-outs based on precomputed states which won't clear the outermost tiles.

Code: Select all

// addPiece
const void addPiece(std::bitset<bitsetSize> & pieceToAdd, std::bitset<bitsetSize> & b1, std::bitset<bitsetSize> & b2)
{
	std::bitset<bitsetSize> bitsForB2 = pieceToAdd & b2;
	std::bitset<bitsetSize> bitsForB1 = pieceToAdd ^ bitsForB2;
	std::bitset<bitsetSize> carryOver = b1 & bitsForB1;
	b1 ^= bitsForB1;
	b2 ^= bitsForB2;
	b2 ^= carryOver;
}

Code: Select all

// removePiece
const void removePiece(std::bitset<bitsetSize> & pieceToRemove, std::bitset<bitsetSize> & b1, std::bitset<bitsetSize> & b2)
{
	std::bitset<bitsetSize> bitsForB1 = pieceToRemove & b1;
	std::bitset<bitsetSize> bitsForB2 = pieceToRemove ^ bitsForB1;
	std::bitset<bitsetSize> carryOver = b2 & bitsForB2;
	b1 ^= bitsForB1;
	b2 ^= bitsForB2;
	b1 ^= carryOver;
}

Code: Select all

// inverting a board or calculating the outstanding "flips" is very easy with bitsets ...
missingFlipPower = (b1.count() * 2) + (b2.count() * 1);

[Hippo]

I was concentrated on heuristics to stop the search when the remaining pieces cannot solve the puzzle, and (on later levels on chosing puzzle with high enough density of solutions). I have searched partly from the end (such that the hash table of zobrist hashes fills available memory) and I use this table to "stop the search when the remaining pieces cannot solve the puzzle" as well.

I was experimenting on search when pieces are changed on all levels (not only the bottom as in dfs), but I was not patient enough to make it work. (When you know there is a solution, you want to search in the "most perspective direction".) I bet, I have described mz aproaches here.

[lvhao945]

Wow Ivhao945 already solved level 58 ... maybe I have to start working on it again ...

I'm Lvhao945,not Ivhao945 = =!