Parallel independent domain decomposition

[eliasboegel]

Whenever multiple separated islands of unexplored cells develop, the linear problem can be decomposed into multiple entirely decoupled linear subproblems, one for each island of unexplored cells. This means the following properties can be exploited:

1. Each linear subproblem is fully decoupled from the others, meaning all linear subproblems can be solved in parallel.
2. Each linear subproblem is smaller (sometimes much smaller) than the original problem, and could be in the realm of performant direct solutions.

Some of the possible problems to figure out are:

1. Detection of islands (unrevealed & revealed) based on matrix and finding the right indices
2. When solver makes an action, how to append to an action list with parallel/different python processes

[wingos80]

Also doesn't need to be independently solved i think. Would be interesting to exchange estimate info from the solver of one island to another, e.g. in cases where there are overlapping neighbouring cells.

[eliasboegel]

Also doesn't need to be independently solved i think. Would be interesting to exchange estimate info from the solver of one island to another, e.g. in cases where there are overlapping neighbouring cells.

I'm not sure I understood you correctly. If there is any information shared (e. g. an explored/numbered cell) between the islands, then the linear problem won't be separable, so in that case both cells would be solved together as one problem.

[wingos80]

i mean if the islands both neighbour one unrevealed cell, then information (solution) on that cell from one island might be interesting to share with the other island. Not shared cells as in explored/numbered cells.

[eliasboegel]

i mean if the islands both neighbour one unrevealed cell, then information (solution) on that cell from one island might be interesting to share with the other island. Not shared cells as in explored/numbered cells.

How can two islands share an unexplored cell without sharing an explored cell?

[wingos80]

E.g:

So in this case it's actually critical that information is shared between two islands. Because the bigger island on the left would have had enough information to determine that there is a bomb in that cell which i circled, which tells the other island that there cannot be any cells in any of its neighbours.

[eliasboegel]

E.g:

So in this case it's actually critical that information is shared between two islands. Because the bigger island on the left would have had enough information to determine that there is a bomb in that cell which i circled, which tells the other island that there cannot be any cells in any of its neighbours.

This is not two islands. "Island" refers to an island of unknowns, not knowns. In this case there would only be a single linear problem with no separation possible.

[wingos80]

ah i was thinking of islands of explored cells not islands of unexplored cells. Sounds like we need to setup a dictionary.

[wingos80]

Closed with commit 646f4c2. Solver win rate and runtime not improved by much, if at all.