🔒 A* Suitable for this problem?

[sharp sorrel]

I have a chess board where some squares have chips on them. Each chip can move in one space at a time (not diagonally). I want to get all the chips into one connected group (edge to edge, diagonals don't connect) in the least amount of moves. Running A* with using this goal condition of being connected instead of a single goal state should work fine I believe. I'm just not sure if there is a better approach or what heuristic h() to use. Since h() can't be an over-estimate, my only idea so far for making h() is considering the X coordinates in isolation and figured out how many moves would be required to make all the x's connected, and then do the same for Ys and add them together, which will certainly be less (potentially way less) than the real solution. Though programming that h() isn't even as trivial as I was originally thinking and may need its own A*...

I also can't help thinking that there is probably some relatively simple algorithm for moving the pieces into one connected group that will always do so in the optimal number of moves, but the more examples I look at the more it seems like that isn't the case, though maybe I'm just not thinking about it right.

[magic grail]

@sharp sorrel

Python help channel opened

Remember to:

• Ask your Python question, not if you can ask or if there's an expert who can help.
• Show a code sample as text (rather than a screenshot) and the error message, if you've got one.
• Explain what you expect to happen and what actually happens.

:warning: Do not pip install anything that isn't related to your question, especially if asked to over DMs.

Closes after a period of inactivity, or when you send !close.

[torpid shard]

I don't have a lot of experience with A*.. what is your graph here, the possible board states?

[sharp sorrel]

Yes, exactly, each node of the graph is a full board state. The "neighboring" nodes any of the board states that are reachable in one move.

[torpid shard]

Sounds pretty big. Are you culling it somehow? Like not adding vertices that obviously distance you from the goal

[sharp sorrel]

I'm removing blank rows at the top, bottom, left, and right so that the board essentially becomes smaller in those case allowing state lookups to match for just shifting the board. I'm also doing same basic flipping where the top row needs to have at least as many chips as the bottom row, left more than the right, and throw in a diagonal flip if the left has more than tho top after those flips are done. I'm not sure that'll be enough though, its still a huge space and I need to rely on the magic of A* to not search the whole space, but that magic really only works when you have a good h().

Also, checking if each new node is fully connected isn't the cheapest thing to do. Certainly it could be optimized to only considered the piece that moved, but not super easy to do that within the context of running it through A*.

Another thing that I've considered doing is removing blank rows from the middle by shifting all the pieces on the smaller side of the blank row towards the larger, but I'm not 100% sure that would never waste any moves.

[torpid shard]

My current thinking is in the direction of: For each chip, find the chip closest to it and connect them, if there's a tie connect to them all. You end up with several connected components, so connect them in the same way you connect the chips. Keep going until you have one connected component remaining. The heuristic value is the sum of edge lengths in the resulting graph

Not cheap though

[sharp sorrel]

If I had a board like oo.o......o.oo, wouldn't that suggest the singletons need to move outward, though ultimately those would be wasted moves since the groups need to get together in the end.

[torpid shard]

Not sure I understand

One side needs to move to the other

[torpid shard]

It might be the same as MST in a clique

[sharp sorrel]

I'm might just not be understanding your suggestion. If you have a single row: 11.2.......3.44 "for each chip find the chip closest to it and connect them" would imply 2 would move to 1 and 3 would move to 4, but that would be counter-productive.

[torpid shard]

I don't mean connect as in move them. What I mean is to build a graph where the chips are vertices and the edges have weights which are the distances between them. And you create an edge according to who is closest to which chip

Basically I'm trying to build a score for how connected the chips are

[sharp sorrel]

Currently my naive algorithm is find the largest group (if there is a tie just pick one) and the move the other pieces one at a time to the group starting with the pieces that need the fewest number of moves and hopefully accidentially building that largest group out in a good direction. This was the first h() when I thought h() was supposed to always be an over-estimate, but I had just remembered that wrong as it is really supposed to always be an under-estimate

[torpid shard]

That wouldn't be the case because the sum of weights stays the same. If 3 moved toward 4 it moves away from 2

So the 3 moving in either direction has the same score, which admittedly is not good

[torpid shard]

If your heuristic involves simulating a naive solution, won't A* just follow that solution to minimize the heuristic?

[sharp sorrel]

A* technically tries all neighbors, so I think it could still work better than a naive heuristic because it'll try positions my simulation may have never tried, but the bigger problem is that using a naive solution for h() will always give you an over-estimate (or tied with the best solution), so then A* is no longer guaranteed to result in returning a good solution since you might have a optimal position that is 1 space away from the solve, but its never explored because the h() is 100.

[sharp sorrel]

Okay, now I think I'm following. I think its a better h() and certainly in the ballpark of expense to the other things I've been considering.

[torpid shard]

It adds all neighbors, but each iteration it chooses the node with the smallest score, which in your case is just the heuristic, since each edge has the same weight. So at each stage it will follow your naive algorithm to reduce the score, until it reaches the goal

[sharp sorrel]

If, for example, you have connected blocks of size 4, 5, and 6 and my naive simulation would move everything towards the 6, but maybe the 4 and 5 can be connected by a single move from the starting point and would serve as a better target for all the pieces to move to, when that neighbor is tried with my naive simulation, it'll have a 10 block and a 6 block and it'll see that moving everything to the 10 block is cheaper.

[torpid shard]

Ok, I see how it makes things a bit more flexible, but that's a bit of an edge case

[torpid shard]

Yeah, although it's not the best approach, as you have demonstrated above

[sharp sorrel]

I think I may give up going for optimal. I'll probably take out any empty rows in the middle like I suggested (even if I'm not 100% sure that that never waste moves). Hopefully that occasionally fix when the wrong largest group is targetted. Then I'll take the closest piece to the new larger group and move it. I may branch on each of the equal distance places it can move to touch the largest group and see which of those connection points do a better job at reducing the rest of the run.

[torpid shard]

This reminds a bit of the mobile games where you have to extricate a car from a parking lot. You move other cars to give your car space to move. So here you need to move the second 1 to the right to see that you can now move the first 1 to the right to make your chips closer to each other

[sharp sorrel]

In fact, I just came up with a board where removing the blank line in the middle does waste moves... oh well, I think that may be where I'm heading

[torpid shard]

And I'm wondering if there's an A*-based algorithm that solves that game

Or alternatively one of those games where a picture is split into a grid with one tile missing, and you shuffle the tiles, and then need to find how to arrange it back

[sharp sorrel]

I think with those car puzzles you can do a total search. Its probably really hard to quantify if you're making progress in those, but fortunately the tree of possible positions I think is pretty limited, at least for the hard ones where it is mostly full.

[torpid shard]

I'm wondering if you can do here something with the variance of weights to improve the accuracy of the score

[sharp sorrel]

Thinking more about your graph approach, I figured out a way to sum the weights so it translates into an actual solve, but even if that is a better approach for simulating a solution than when I've said, being an actual solution means its going to be at least as many moves as an optimal solve, which isn't the kind of h() we want. I'm having trouble picturing how to do it in a way that guarantees it'll be an under estimate, especially since, for example, the initial graph could've been drawn wrong if there is a piece that may be better connected to a group that is 1 further away, like if I could connect it to the base group that doesn't move instead of connecting it to a slightly closer group, but one that moves to the base.

[torpid shard]

It's even worse. You can move one chip several squares to the edge of the base so that each chip in another group has to move one square less

[sharp sorrel]

Thanks @torpid shard, this has really helped me think about the problem. I appreciate the discussion. I'm going to close the chat for now.

!close

[magic grail]

Python help channel closed

This help channel has been closed and it's no longer possible to send messages here. If your question wasn't answered, feel free to create a new post in #1035199133436354600. To maximize your chances of getting a response, check out this guide on asking good questions.