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