0
$\begingroup$

Let's call this the Path Game.

For this example, lets imagine a 16x16 grid:

The Example of the Game.

Some of the squares in this grid are "deadly." If you step on it, you must restart and try to go over again. We will assume that the placement of these deadly squares is random.

However, if you pick a "friendly" grid you will be allowed to "mark" it. In logical terms this means that we know that the square is safe. If you need to start over again, you have knowledge that the square is not deadly.

You may only start from one of the 4 sides of the large 6x6 square and only go horizontal, vertical, or diagonal. No skipping squares.

I have 2 questions:

1.: What is the complexity class of this game? I know that when done by brute force, it should be in the NP class of problems, but with heuristics, it seems to be EXPTIME or PSPACE. By "heuristics" I want the complexity class with when the algorithm can take into account the squares it knows is safe. I already know that with brute force without taking into account the friendly squares it is in NP but I am unaware of the complexity class of this question when memory of the safe squares are taken into account.

2.: Is the complexity class and name of the game known already If so, where?

Thank you for your time!

$\endgroup$
8
  • $\begingroup$ Minor comment: in order to discuss whether the problem is within classes such as NP, PSPACE or else, you might want to parameterize the input size (e.g. either the size $n$ of the largest side of the grid (16 in your example) or the number of points of the grid (256 in your example)), or to redefine the problem on an infinite grid (as Elkhanan Mossel did for the Minesweeper game). $\endgroup$
    – J..y B..y
    Sep 2, 2022 at 11:02
  • $\begingroup$ I don't understand the part of the question " I want the complexity class with heuristics specifically"? And the complexity of remembering ALL squares is just polynomial ($n^2$) in the size $n$ of the largest side of the grid? $\endgroup$
    – J..y B..y
    Sep 2, 2022 at 11:42
  • 4
    $\begingroup$ "What is the complexity class of this game?" Games don't belong to complexity classes, decision problems do. What decision problem do you have in mind? Can you please state it explicitly? And (as mentioned in another comment) what does "with heuristics" mean? $\endgroup$
    – Neal Young
    Sep 2, 2022 at 13:13
  • $\begingroup$ @J..yB..y What I mean by "with heuristics" is if the algorithm can remember which squares are safe. I hope that answers it. Sorry for not clarifying, I was tired when i wrote this. $\endgroup$
    – Bapcap
    Sep 2, 2022 at 16:16
  • $\begingroup$ @NealYoung I edited my question to make it clear. I hope the reply to J..y B..y's comment also helps you understand. $\endgroup$
    – Bapcap
    Sep 2, 2022 at 16:22

1 Answer 1

1
$\begingroup$

The game that you describe (let's call it "MineFreePath") is (very) similar to the "MineSweeper" game, a logic puzzle video game, created by Microsoft in the 1990s, where one search for the mines in a mine field. The differences would be that 1) MineSweeper allows to jump to a random position at any time, and that 2) MineFreePath allows to iterate on the same map. The second difference is interesting, but I think that the first difference is negligible:

  • in practice any winning strategy for MineSweeper follows a path in the mine field (Figure shamelessly taken from 2): a path in the mine field:
  • the decision problem versions of both problems (deciding if the field can be de-mined) would be of similar complexity, using the same kind of gadgets to show reductions to other problems: for instance, a gadget to reduce a dis-junction to a MineSweep sub-instance is similar to that one would imagine for reducing it to a MineFreePath sub-instance (Figure shamelessly taken from 2): Gadget to reduce a dis-junction to a MineSweep or MineFreePath

Elkhanan Mossel studied the percolation complexity of a version of the Minesweeper game on an infinite grid in a 2002 article (which you should not download from SciHub as it would probably be unethical), which is even more relevant to the analysis of the MineFreePath game: check it for yourself, but I am pretty sure that Elkhanan's results (or at least his approach) will generalize, namely that the probability that an instance can be solved depends on the density of the mines in the map.

Should you prove formally any results about this version of MineSweeper, I think that the academic community who gathers every two years at the italian conference Fun with Algorithms would be interested :)

I hope it helps!

$\endgroup$
1
  • $\begingroup$ This helped me go to the right track. I know now to reduce it to a decision problem! Thanks for helping a beginner! $\endgroup$
    – Bapcap
    Sep 4, 2022 at 15:26

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.