Ricochet Robots Solver
<i>&gt; 2^32 bytes is 4GiB so a bitmap would be 512MiB.</i><p>Yes, sorry, 2**27 32-bit words, so 512 MB.<p><i>&gt;However a downside of A* is that I need to store the depth in the visited map as they may be found out of order. I also store the move that got there to allow quick reconstruction. (It is within the same byte as the depth.)</i><p>There is a 1:1 correspondence between visited configurations and queue entries, so for total RAM usage it actually doesn&#x27;t matter what information you&#x27;re storing in which one. Storing the moved robot and previous robot position (10 or 11 bits) will be more efficient than storing a 32-bit queue index for the back-pointer, though.<p>I agree the bitmap is harder to scale for 5 robots, but 256 * 0.5 GB is just 128 GB, not terabytes, and there are machines with that much RAM. Sorting and deduplicating non-goal robots should reduce this to around 5.6 GB. The challenge is that the actual reachable states are quite dense (2&#x2F;3rds of all possible states with 4 robots and no deduplication, and probably an even higher percentage with 5 robots and deduplication), so there is not actually a lot of room to make this smaller if you want to allow searching the full (~100 move) configuration space. That is not necessary to reach any single-robot goal, of course. The worst 4-robot single-goal solution I&#x27;m aware of is 27 moves. See this example:<p><pre><code>    +---+-----------------+---------+
    |   |                 |         |
    |   + +-+         +   +         |
    |     |           |             |
    |     +           +-+       +-+ |
    |                             |G|
    |             +               + |
    |             |                 |
    | +         +-+       +         |
    | |                   |         |
    | +-+               +-+       +-+
    |                               |
    +-+     +-+             +-+     |
    |         |             |       |
    |         +   +---+     +       |
    |             |   |             |
    |             |   |             |
    |             |   |             |
    |     +-+     +---+         +-+ |
    |       |                   |   |
    |       +             +     +   |
    |                     |         |
    | +                   +-+     +-+
    | |                             |
    | +-+         +   +-+           |
    |             |    g|           |
    |           +-+     +           |
    |                               |
    +-+ +-+                     +   |
    |Y R|                       |   |
    |   +       +         +   +-+   |
    |B          |         |         |
    +-----------+---------+---------+
</code></pre>
My solver on my laptop finds a solution in 67 seconds using 666 MB of RAM after examining 82,872,901 configurations, so just 2.1% of the possible configuration space. Only 316 MB is needed for the queue, so that means it was using ~350 MB for the bitmap, which is not particularly efficient (~35.4 bits of RAM mapped per visited state).<p>This example was found by Pieter Wuille, who wrote a reverse-state-space explorer (given a board layout and a goal, it finds the optimal number of moves to the goal for every initial robot position combination in about a minute). www.robotreboot.com allowed for 20,736 board configurations and 20 possible goal locations per board. With four robots there are 656,239,500 possible robot configurations after sorting&#x2F;deduplication. Using rotational symmetry, and storing four bits per board&#x2F;goal&#x2F;configuration combination to say what robot to move and in which direction, he estimates you could store the solutions for all possible games in around 31 TB with about a year of CPU time. That won&#x27;t fit in RAM, but it is certainly achievable.<p>Another fun property of solutions to consider is what we term the solution &quot;complexity&quot;, defined as the minimal number of times you must switch from moving one robot to moving a different one (plus one, since originally you are not moving any robot). The &quot;must&quot; there is important, since if two robots do not interact, you could just alternate moving between them, but the goal of complexity is to measure the amount of interaction. A related property is the &quot;causality&quot;: the amount by which a solution&#x27;s complexity exceeds the number of robots it moves.<p>Optimizing for minimum complexity is pretty straightforward, but of course the &quot;fun&quot; solutions are the ones with <i>maximal</i> complexity&#x2F;causality...