Sunday 9 October 2016

Faster algorithm solving minesweeper puzzles (1)

Minesweeper is something that I'm always addicted to. This is obvious when this blog contains multiple entries talking about different aspects of this absolute classic. Last time, I talked about solving minesweeper using logical deduction generalised as a satisfiability problem. That was quite a long time ago -- when I was playing mienfield. 3 years after that I am now addicted to another minesweeper game called Minesweeper: Collector, that you can find on the Google play store.

Yes of course. Using ILP (integer linear programming) or even SAT (satisfiability) to solve minesweeper is not a very smart idea. Since we are working with equations and we know integral solution exists, we can simply employ linear algebra to make our life easier.

It is a bit hard to define how useful a deduction is by solving all the equations. For instance if we can conclude from 100 equations that now the space of possible solutions has dimension 68, then probably a faster way to solve the puzzle could be done by performing an educated guess in terms of probability. However probability is not something that linear algebra can handle easily so we would simply look for any definite deduction here. The most desirable result from the algorithm is that we can deduce the solution of some particular grids.

For the classic rectangular minesweeper we can think the whole puzzle as a matrix $M\in \mathbb{R} ^{m\times n}$, then we can setup variables $v_{11},...,v_{mn}$. Of course the same idea applies to different kinds of minesweeper shape [hexagonal etc] it is just the naming/coordinate setup that differs. They are supposed to be binary, but this is some technicality that we must handle later.

If a certain grid [for example row $s$ column $t$] is known but its neighborhoods are not all revealed then the grid yields an equation denoted by $E_{st}$. It has the form

$E_{st} ~:~ \sum _{p=s\pm 1, q = t\pm 1}^{1\leq p \leq m, 1\leq q \leq n} \delta _{pq}v_{pq} = c_{st}$

Where $c_{st}$ is the number of mines surrounded, and $\delta _{st} = 1$ if the grid $(s,t)$ is concealed, 0 otherwise. The aim of course, is to identify the mines [i.e. solving $v$] and receive more hints, eventually solving the whole puzzle.

Here is our first algorithm:

Algorithm 1.
-----
Input: A partially solved minesweeper matrix $M\in \mathbb{R}^{m\times n}$ provided that solution exists
Output: Any definite deduction

- Convert puzzle into linear eqautions
- RREF and solve $M$
- Interpret the solution
- Return any conclusion

For example we look at a classic 1-2 combination

$\begin{pmatrix}
\square & \square & \square & \square & \square & \square & \square & \square \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & \square
\end{pmatrix}$

that should give you deduction like

$\begin{pmatrix}
\square & X & O & O & X & X &O & O \\
\square & 2 & 1 & 1 & 2 & 2 & 1 & O
\end{pmatrix}$

[where X represents mine and O is safe.] Let $v_1,...,v_{10}$ be the variables naming from left to right, top to bottom. Loot at the matrix reduction:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 2\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix} 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 1 & 0 & 1\\
0 & 1 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 1 & 0 & 0 & 0 & 1 & 1 & 0 & 1 & 0\\
0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0\\
0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 1\\
0 & 0 & 0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 1 \end{pmatrix}$

What a mess! But we can still interpret the solution.

From row 3 we have $v_3+v_7+v_8+v_{10} = 0$, then by non-negativity they are all zero. By removing column 3,7,8,10 and row 3 we instantly get $v_2 = v_5 = v_6 = 1, v_4 = 0$. Now the solution space is given by:

$v = (0,1,0,0,1,1,0,0,1,0)^t + t(1,0,0,0,0,0,0,0,-1,0)^t$ where $t \in \mathbb{R}$, or simply $t \in \left\{ 0,1\right\}$.

as expected. However the deduction is very messy that it cannot be automated in an obvious way. Things get worse if the solution space is more complicated. Look at this simple example:

$\begin{pmatrix}
\square & \square &  \square & \square & \square & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

that yields immediately the following [this should be really obvious for any experienced player!]

$\begin{pmatrix}
\square & O &  \square & \square & X & \square \\
\square & 1 & 1 & 2 & 2 & \square
\end{pmatrix}$

assign the names $v_1,...,v_8$ as before, reduce the matrix:

$\begin{pmatrix}
1 & 1 & 1 & 0 & 0 & 0 & 1 & 0 & 1\\
0 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 1\\
0 & 0 & 1 & 1 & 1 & 0 & 0 & 0 & 2\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2
\end{pmatrix}

\xrightarrow[~]{rref}

\begin{pmatrix}1 & 0 & 0 & 0 & 1 & 1 & 1 & 1 & 2\\
0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & -1\\
0 & 0 & 1 & 0 & 0 & -1 & 0 & -1 & 0\\
0 & 0 & 0 & 1 & 1 & 1 & 0 & 1 & 2 \end{pmatrix}$

The only thing we can deduce is the second equation. Since we know $v_2,v_5\in \left\{ 0,1\right\}$ we must have $v_2 = 0, v_5 = 1$ as predicted, and this is basically all we know.

The trouble here is the deduction heavily relies on facts that we have omitted by modelling the problem into a system of linear equations. Of course rearranging the columns [hence changing the RREF] could solve this problem, but recognising the rearrangement of columns is basically equivalent to knowing the grids that can be definitely [or at least almost definitely - when the solution of that grid has a very low dimension] which is the fundamental aim.

To improve our efficiency instead of adding conditionals that check whether an equation is useful for deduction, we can change the fields that we are working on. Rings wouldn't work [and that is why ILP is bad], but we can look at fields, like $F_2$ or $F_7$!. This will be addressed in the next entry.

Saturday 1 October 2016

Trauma Team review

Well not a very recent game isn't it? Some random recommendation from youtube caught my eyes then I subsequently finished the whole streaming. Back to the time I was stuck in gaming consoles [before went into MUGs] I completed the first game of the Trauma Center series almost perfected every operation, then took on the second opinion but shaking hands definitely makes the game superbly hard on Wii, and I gave up halfway.

Developing the same story line is probably not working after one or two attempts. On one hand the nature of operations being repetitive is somehow pushing the developers to raise the difficulty bar in the sequels. The population is not giving a warm reception against this act -- the precision, speed or continuity necessary to clear the later stage utilizes full functionality of the NDS pad that only a few number of games could had reach such bar. [Wii's better but not a lot, too.] Raising difficulty not only go beyond what gamers could do but also make the game more unreasonable. The story basically entered a dead end - GUILT along with its origin and associated diseases are pretty much cured. Developing something like that takes years as mentioned in the first game, and the way it was spread out decided that it is not easy to create another pandemic anymore. It just makes no sense to try to extend this linear plot.

But the whole story does not stop there. Just look at Phoenix Wright - the introduction of new character adds another layer of complexity of the whole story [in terms of mathematics it is like adding an independent vector into a subspace...right?]. Imagine that your starting pitchers are becoming old and can't be SP anymore. The introduction of a new SP definitely deliver a different game, but it's bitter and sweet finding your old player not only adapting a relief role but also helping the noobs to get through the game. To me, Trauma Center quite successfully replicate such strategy.

Derek and Angie has relieved once or twice already [so they turned into...coach?!? That make sense lol.] so Naomi is a natural choice. Her character didn't change much since her debut, but she was but in an environment with much more interaction and that exposes quite a different side of her. What a pity that the lil' guy failed to impress her enough to gain a starter at the very end.

Each of the individual stories are pretty interesting too, but I feel like getting the story done in like, 6 chapters is too rush. Don't forget that you have the main story pushing you behind so everything is just too quick for those characters to make a change [except for Gabriel who received a real shocker]. Fortunately the ending is kind of complete so I'm leaving happily from the game.

That brings another problem by dividing the whole game into different kinds of puzzles: each type of puzzles has their own significant weakness, and putting all puzzles together is enough to annoy every single player. Operations are extremely easy and generous from beginning to the end - it never escalates even with limited number of operations; endoscoped operations are even more repetitive because the opponent [virus/wounds] never 'fight back', and that is extremely unrealistic. Who would have a full kit equipped on the endoscope? The only thing I can recall from Hank's operation is the super combo that I couldn't recognize where was all the counts from; Maria's one is a nice attempt but the constraint never picks the gamer's back heavily. On the other hand, I found diagnostic and forensic puzzles extremely long and clumsy. It is good that they really collect realistic evidences with details [that stands out from other detective games], but the progress is simply too slow because you cannot reach some obvious conclusion just because the game does not allow you to. The frequent switching scene is also kind of annoying. Why am I going from by office to the scene just to collect 2 pieces of evidence and decided that it's sufficient then go back? I know all of them are logical but redundant logical induction is really bringing any wow factor to the story.

Some other elements of the game is worth mentioning as well. The graphic is nice - American comic styled slides handled the pace well and giving enough details [and easter eggs] given the limited budget [well you know, it's atlus after all...], I definitely like the Japanese styled graphics. Credits must be given to those [Japanese] producer who merged the two together well. Music's average I would say, not that grand and intense as the previous games. A remix of O Fortuna would be a great punch on the old players' stomach, but probably the producer decided not to do so because everything is relaxing and easy here :P

In overall, this is a game that is worth to have a look, especially if you've played similar stuff in the past. Probably too old to buy but streaming videos are worth a shot [say, Karin & Omega's Channel?], and something can be expected from the sequel, if there will be one -- kind of doubtful because it's been 6 years since the last one.