Can't solve nonogram (10x10) or Rubik's cube

[arr28]

Appeared in the 2015 Tiltyard Open. Nobody solved them (although several did better on the Rubik's cube).

[arr28]

For Nonogram 10x10, something similar to the PartionedChoiceAnalyser might help (although the game might still be way too big).

This is a pure marking game. Each legal move affects exactly 1 positively latching base proposition. Moves remain legal until we play them, at which point they aren't legal any more. So, we can massively cut down the search by always considering the moves in a particular order. However, that might still leave ~2^100 states to test. To do better, we'd also need to set that order intelligently. For Sudoku, we examine the most constrained cells first. Doing the same here might involve identifying any moves that result in immediate termination. It might also involve more complex latch analysis.

[arr28]

Thinking about the Rubik's cube...

• There are ~4*10^19 positions.
• In the half-turn metric (used in the .kif), there are 18 legals and 20 moves suffice.
• From any given position, in 20 moves, we can reach 18^20 ~= 1*10^25 positions - more than the number of distinct positions, as expected.

However, working from both ends and growing two trees, an upper bound on the number of leaf nodes after 10 moves is 2*18^10 ~= 7*10^12 (7 trillion). Including all the inner nodes, it's 8x10^12. If the tree nodes were also stored in the hash table (as usual), that would mean that we'd be bound the find an overlap between the two trees - giving a solution.

Space

7 trillion is quite a lot larger than would fit in memory, but not necessarily fatally so. In our favour...

1. It's likely that the position given isn't a 20-move position. Alex describes it as "Some random state of my cube (didn't record generating sequence)". 20-move positions are rarer than 1 in a billion. There's a 97% chance of it requiring 18 moves or fewer. There's a 3% chance of it requiring 16 moves or fewer. Assuming it's an 18 move position, the trees would only need ~4*10^11 (400 billion) nodes.
2. Transpositions will considerably reduce the number of nodes in each tree. (e.g. no moves starting L,L', R,R', etc. will be examined. These 6 transpositions alone remove 2% of the nodes.)
3. On average, we'll find the solution about half way through.

That's sad though - it looks a few orders of magnitude out of reach. Even at just 40 billion nodes (unlikely to achieve as low as this), every byte of tree node occupancy costs 40GB.

Time

My weediest machine does 2.1K iterations/s single-threaded (gamesearcher). My desktop can probably do about 7.5K iterations/s all-in. However, these are full rollouts (which will be 50 moves long). We might be able to get near 350K state transitions/s.

At 40 billion tree nodes (again, likely to be an underestimate), that would take ~32 hours. Again, that's just a few orders of magnitude out.