## Any hints?

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

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

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
}
```

Code: Select all

```
$b1==00001001
$b2==00010010
Adding piece:
00000111
$b1==00001100
$b2==00010001
```

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., ...

I have not speeded up the hashing, yes it costs the "rounding rectangle size" for modulo > 2.camel wrote: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?

Of course you could precompute the piece positions for the modulo = 2 case and than the hashing would be O(1).

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

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

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);
}
```

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

Last edited by camel on Wed Sep 14, 2016 11:46 pm, edited 2 times in total.

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);
```

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.