I think I know how making 12 space lookup tables can be made easier.

[1h0si]

I think if you split the lookup tables into each individual layer by the sum of tiles, you will need much less memory to create the large tables. This could allow 12 space lookup tables with two free rows and columns, which would allow for some much better strategies to appear

[macroxue]

Thanks for thinking about it. I'm not sure if I understand the proposal though. Can you please be more specific? Diagrams showing individual layers with calculations on the memory usage will definitely help.

[1h0si]

If you make these lookup tables the same way I would think they're made (generating positions in ascending order then solving them descending), then you would only need to consider three layers at any given time.

When you're generating positions, for example, you might be generating positions from a sum of 4. You'd generate all of the 2 spawns and all of the 4 spawns, which are on layers 6 and 8 respectively. You'll never need to consider layer 2 again, and the same applies anywhere else. When solving a position, for example, on layer 386, you only need to consider 2 spawns leading to 388 and 4 spawns leading to 390. No other layers besides those three need to be considered at this time.

To show the difference I've made LL12-512 and LL12-1024 Tables in the past, using a tool that only had three layers in memory at a time, and the difference was much greater. while the tables were about 300 and 900 GB respectively, the program never used more than 10 GB of memory. Unfortunately, this program is also significantly slower (DPDF10 taking 2 hours versus your 25 minutes). I'm unsure whether there's any correlation between the two. LL12-1024 has approximately 55 billion positions in the tree

I hope this made it clearer

[macroxue]

I think I get the idea, which is a breath-first traversal and friendly to swapping.

Since you were able to move two rows and two columns, did you manage to get higher scores?

[1h0si]

I haven't been able to see exactly how helpful this is in real games, but LL12-512 outperforms DPDF10-128 (0.999975455 vs 0.99989) and LL12-1024 outperforms DPDF10-256 (0.99519 vs 0.9938). DPDF10-512 surprisingly outperforms LL12-2048 (0.8337 vs 0.829), although if you are forcing strict DPDF/gap with 12 spaces, DPDF would probably have a success rate closer to 0.821, lower than LL-2048. We currently do not know how well LL-4096 performs, but using endgames alone, we have a lower bound of about 3.6% for the 65536 tile

[macroxue]

3.6% sounds about right. The lower bound seems pretty tight already. I was a bit lucky to get 3.5% with 1000 runs of DPDF, which gives me less motivation to shoot for 3.6% or maybe 3.7%. :)