> 2^32 bytes is 4GiB so a bitmap would be 512MiB. Yes, sorry, 2**27 32-bit words, so 512 MB. >However a downside of A* is that I need to store the depth in th

> 2^32 bytes is 4GiB so a bitmap would be 512MiB. Yes, sorry, 2**27 32-bit words, so 512 MB. >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.) There is a 1:1 correspondence between visited configurations and queue entries, so for total RAM usage it actually doesn't matter what information you'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. 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/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'm aware of is 27 moves. See this example: +---+-----------------+---------+ | | | | | + +-+ + + | | | | | | + +-+ +-+ | | |G| | + + | | | | | + +-+ + | | | | | | +-+ +-+ +-+ | | +-+ +-+ +-+ | | | | | | + +---+ + | | | | | | | | | | | | | | +-+ +---+ +-+ | | | | | | + + + | | | | | + +-+ +-+ | | | | +-+ + +-+ | | | g| | | +-+ + | | | +-+ +-+ + | |Y R| | | | + + + +-+ | |B | | | +-----------+---------+---------+ 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). 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/deduplication. Using rotational symmetry, and storing four bits per board/goal/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't fit in RAM, but it is certainly achievable. Another fun property of solutions to consider is what we term the solution "complexity", 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 "must" 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 "causality": the amount by which a solution's complexity exceeds the number of robots it moves. Optimizing for minimum complexity is pretty straightforward, but of course the "fun" solutions are the ones with maximal complexity/causality...