hacker.org Forum Index
RegisterSearchFAQMemberlistUsergroupsLog in
Any hints?
Goto page Previous  1, 2, 3
 
Reply to topic    hacker.org Forum Index » Modulo Puzzle View previous topic
View next topic
Any hints?
Author Message
Hippo



Joined: 01 Feb 2014
Posts: 280
Location: Praha 5

Post Reply with quote
I have decided to change a bit the task selection ... roughly 200 days without success is too much Wink

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 Wink
Thu Jun 11, 2015 4:10 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 280
Location: Praha 5

Post Reply with quote
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 ...
Tue Jun 30, 2015 5:35 pm View user's profile Send private message
Isaev



Joined: 16 Dec 2008
Posts: 33
Location: Germany

Post Reply with quote
Cool Hippo!
I can't 41 Smile
Thu Jul 02, 2015 10:40 am View user's profile Send private message ICQ Number
Hippo



Joined: 01 Feb 2014
Posts: 280
Location: Praha 5

Post Reply with quote
Wow Ivhao945 already solved level 58 ... maybe I have to start working on it again ...
Fri May 06, 2016 3:23 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
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:
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:

$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., ...
Sun Sep 04, 2016 11:40 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
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 ... Razz
Sun Sep 04, 2016 11:58 pm View user's profile Send private message
Hippo



Joined: 01 Feb 2014
Posts: 280
Location: Praha 5

Post Reply with quote
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?


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).
Mon Sep 05, 2016 8:42 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
So still no hint from you guys? Razz

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

Code:
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. Razz This could help in certain situations ... if the level doesn't expect you to place a lot of "chaos" inducing pieces that is ... Razz


Last edited by camel on Wed Sep 14, 2016 11:46 pm; edited 2 times in total
Fri Sep 09, 2016 8:27 pm View user's profile Send private message
camel



Joined: 26 Dec 2007
Posts: 50
Location: Austria

Post Reply with quote
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:

// 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:

// 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:

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

Wed Sep 14, 2016 11:40 pm View user's profile Send private message
Display posts from previous:    
Reply to topic    hacker.org Forum Index » Modulo Puzzle All times are GMT
Goto page Previous  1, 2, 3
Page 3 of 3

 
Jump to: 
You cannot post new topics in this forum
You cannot reply to topics in this forum
You cannot edit your posts in this forum
You cannot delete your posts in this forum
You cannot vote in polls in this forum


Powered by phpBB © 2001, 2005 phpBB Group
Design by Freestyle XL / Flowers Online.