The optimal solution for moving random grids on the board by two players

Question

Consider an infinite two-dimensional panel. We have two players at points P1 and P2 on the board. They need to go through the sequence of boxes on the board G1, G2, G3 .... Gn.

In the beginning, only G1 is known. G2-Gn coordinates are unknown only after the field that preceded it has passed. Players can move one at a time in one of 8 possible directions on board per unit of time. We need to find the minimum time for passing all the necessary boxes with the help of two players.

The obvious solution is a greedy approach when the player moves closer to the box that must pass. Then we calculate a closer player again for the next G. I feel that there is a better solution to this problem that I cannot recover now. Is there a better solution?

Answer 1

I think that since the board is infinite, we should try to cover the largest possible area with players within n moves (for each n). Thus, we maximize the set of fields that we can achieve within n moves.

So my strategy is:

Who is next to the next field?

Let it be P1.

Let P1 go into the field (the shortest path) and go with another player P2 in the exact opposite direction. Thus, we maximize the distance between the two players, which minimizes the overlap of the area by which they can reach n steps. Thus, we maximize the coverage of the area in which two players can reach n steps for the next window.

Answer 2

Choosing the player closest to the next field is the best heuristic you can find.

Explanation: Whenever a new target appears, there are only two options: Move player 1 or player 2 to the target due to the distance in the fields. We also prefer a situation where the players are far apart, as opposed to close to each other. The most extreme case will be that both players are on the same field, which is as good as having only one player. Since the playing field is infinite, the distance between them is always better.

If this is correct, you should ask yourself: should I really choose a player who is farther from the target and , in a situation where the players are closer to each other, than they would if I took another player?

Of course not. In an endless field, choosing the closest player helps with them, minimizing running costs and improving the situation for the next goal (players are far apart).

Answer 3

Since the problem is not deterministic, the solution must be heuristic.

The "price" at each step is the number of moves made per move. This can be PrN1 or PrN2 for the number of moves for player1 or player2, respectively, in turn N.

The “score” at each step can be considered as the probability that a certain location (the position of both players) after the moves will be a good layout for the rest of the turns.

You want to use a valuation function that takes into account both the price and the valuation for making a decision.

The problem is that the only useful counting function is a function that is some function of the distance between the players (the larger the distance, the greater the probability of approaching the next rounds), and this is precisely synchronized with the minimum price. Any choice that keeps players as far apart as possible is the one that was the cheapest.

What does all this mean if the best algorithm is simply to move the closest player, which is your first instinct.

If the board were not infinite, you could create a better scoring function that takes into account the probabilities of the next boxes, which would give lower grades for the arrangements that leave the player at the edges of the board.