Comment
Comments
Comments in green were written by me. Comments in blue were not written by me.
@Lord Sméagol: Great job! I guess VB is pretty slow.
The world record in single thread mode for the '8' puzzle is 9.5 min, which can be further improved by taking the diagonal symmetry into account.
You can find the code in the comments to my article: https://habr.com/ru/articles/889410/
The world record in single thread mode for the '8' puzzle is 9.5 min, which can be further improved by taking the diagonal symmetry into account.
You can find the code in the comments to my article: https://habr.com/ru/articles/889410/
Dan
on /blog/119
on /blog/119
@Dan: I have added symmetry optimization (still in VB.Net):
(Scanning for free space from top to bottom, left to right)
Only place 1x1 in one octant; The tests are simple, the savings are huge.
Even size: 8->36, 11->66, 12->78, 15->120
. . . . . . . . . .
. . . . . . . . . .
. . \ x x x x x . .
. . + \ x x x x . .
. . + + \ x x x . .
. . # # # # # # . .
. . # # # # # # . .
. . # # # # # # . .
. . . . . . . . . .
. . . . . . . . . .
Odd size: 9->45, 10->55, 13->91, 14->105
. . . . . . . . . . .
. . . . . . . . . . .
. . \ x x x x x x . .
. . + \ x x x x x . .
. . + + \ x x x x . .
. . = = = * x x x . .
. . # # # # # # # . .
. . # # # # # # # . .
. . # # # # # # # . .
. . . . . . . . . . .
. . . . . . . . . . .
+ No symmetry check needed
\ Check transpose only
= Check vertical flip only
* Check all 7 symmetries
. 1x1 impossible here
x don't place 1x1 here
# backtrack if 1x1 not placed yet
'8' 2,332 distinct: (12c/24t) 26 sec, (1t) 3m56s
'9' 216,285 distinct: (12c/24t) 3h32m41s, (1t) [32.2 hours estimated]
12c/24t is only getting a 9x improvement over single thread :(
I need to think about making an asm version :)×1
(Scanning for free space from top to bottom, left to right)
Only place 1x1 in one octant; The tests are simple, the savings are huge.
Even size: 8->36, 11->66, 12->78, 15->120
. . . . . . . . . .
. . . . . . . . . .
. . \ x x x x x . .
. . + \ x x x x . .
. . + + \ x x x . .
. . # # # # # # . .
. . # # # # # # . .
. . # # # # # # . .
. . . . . . . . . .
. . . . . . . . . .
Odd size: 9->45, 10->55, 13->91, 14->105
. . . . . . . . . . .
. . . . . . . . . . .
. . \ x x x x x x . .
. . + \ x x x x x . .
. . + + \ x x x x . .
. . = = = * x x x . .
. . # # # # # # # . .
. . # # # # # # # . .
. . # # # # # # # . .
. . . . . . . . . . .
. . . . . . . . . . .
+ No symmetry check needed
\ Check transpose only
= Check vertical flip only
* Check all 7 symmetries
. 1x1 impossible here
x don't place 1x1 here
# backtrack if 1x1 not placed yet
'8' 2,332 distinct: (12c/24t) 26 sec, (1t) 3m56s
'9' 216,285 distinct: (12c/24t) 3h32m41s, (1t) [32.2 hours estimated]
12c/24t is only getting a 9x improvement over single thread :(
I need to think about making an asm version :)
Lord Sméagol
on /blog/119
on /blog/119
×1 @Danila P.: I think I have pushed VB.Net to its limit!
I moved the board from byte cells to 64 bit integer bitmaps (1 for each row);
using 8, 9, 10 variables for the 'active' rows instead of an array to reduce memory access.
I also partitioned the '9' and '10' search so other computers (I have a 6c/12t i7 3930K and a few quad cores) can assist using a mapped network drive.
All 2,332 distinct solutions of the '8' puzzle (12c/24t) now 16 secs (was 26 sec).
I have ported most of it to C ... just need to get the multi-threading working!
I moved the board from byte cells to 64 bit integer bitmaps (1 for each row);
using 8, 9, 10 variables for the 'active' rows instead of an array to reduce memory access.
I also partitioned the '9' and '10' search so other computers (I have a 6c/12t i7 3930K and a few quad cores) can assist using a mapped network drive.
All 2,332 distinct solutions of the '8' puzzle (12c/24t) now 16 secs (was 26 sec).
I have ported most of it to C ... just need to get the multi-threading working!
Lord Sméagol
on /blog/119
on /blog/119
@Dan: 9.5 min on what CPU, RAM ? My rig is 3.5 GHz single thread Ivy Bridge, DDR3 1600, which will be holding me back quite a lot compared to modern kit!
The main problem with VB.Net (well, .Net itself) is only allowing you to disable integer overflow checks.
I remember VB6 let you also disable array bounds checking. That option SHOULD be available in .Net!
--> Test your code in Debug mode ... ok, it works, release mode with no checking --> let it rip!
My VB.Net prog spits out solutions as it finds them, but this hardly impacts performance. There is a single render thread that waits for a solution from a shared queue that [24 in my case] worker threads are feeding.
I would like to keep all the hot stuff in registers, but I don't think C will give me enough control over that, so maybe it's asm time! ×1
The main problem with VB.Net (well, .Net itself) is only allowing you to disable integer overflow checks.
I remember VB6 let you also disable array bounds checking. That option SHOULD be available in .Net!
--> Test your code in Debug mode ... ok, it works, release mode with no checking --> let it rip!
My VB.Net prog spits out solutions as it finds them, but this hardly impacts performance. There is a single render thread that waits for a solution from a shared queue that [24 in my case] worker threads are feeding.
I would like to keep all the hot stuff in registers, but I don't think C will give me enough control over that, so maybe it's asm time!
Lord Sméagol
on /blog/119
on /blog/119
×1
It finds all 18,656 solutions for the '8' puzzle in 2 minutes and all 1,730,280 solutions for the '9' puzzle in 21 hours, which isn't too bad for a 13 year old PC :)
Testing the '8' solver on a single thread took just under 24 minutes (only 12 times 2 minutes, not 24 times), hinting that Hyper-threading memory bandwidth is the bottleneck, so another board storage method is needed to improve the scalability!
on /blog/119