Why you shouldn't rely entirely on Machine Learning

In this post, I'm going to build an example of artificial intelligence in the form of a Constraint Satisfaction Problem (or CSP), showing how much mathematics, logic skills, and computer science knowledge can help in the process.

For this purpose, I took a puzzle game called Hitori on the popular logic puzzle website Nikoli. I didn't choose Hitori because it was convenient, I literally chose a random game precisely because it didn't matter what the game was for what I wanted to show.

What is a CSP

Let's begin by learning what a CSP actually is. As the name (and Wikipedia) suggests:

CSPs are mathematical problems defined as a set of objects whose state must satisfy a number of constraints or limitations.

Okay, that was pretty cryptic. I would say, in a more informal way, that we can think about CSPs as made up of three components:

• Variables: something we need to find out in order to solve the problem.
• Domains: what values we can assign to the variables.
• Constraints: this is clear.

We also need to clarify the terms state, complete, solved and legit or, more formally, consistent. You can think of a CSP state as a snapshot of one of the steps involved in the solution. A state is said to be consistent or legit if it doesn't break any of the constraints. It is said to be complete if it determines a value for each variable involved, and it is said to be a solution if it is both consistent and complete.

Don't let this formulation mislead you, though: you can think about variables, domains, and constraints in a really general way. For example, one of the constraints could well be what you may call (somewhat naïvely) to find a solution of the problem itself.

Think about chess: any regular match is formally a solution of a chess match problem, because it satisfies the constraints involved in the game and reaches a conclusion (either white wins, black wins, or there's a draw) through a series of legit moves, but I'm going to bet that you want to include among the constraints that you want to win, or at least draw, against your opponent.

So, in other words, we are going to search those parameters that will allow us to solve a problem dominated by logic and intuition, a problem that a human can handle after a few tries, but a (not properly trained) machine would struggle to even begin with.

Does this sound familiar?

In a sense, this is exactly what everyone is trying to achieve when resorting to Machine Learning (ML from now on) for all sorts of problems.

I'm going to show you, in a moment, that there exists an alternative that you should actually prefer to the "standard" ML approach, and I'll explain why in the last section. Just bear with me a little more.

Hitori — rules

This is the initial state of a Hitori puzzle.

By Dan1980 - Own work, based on File:Hitori.jpg, CC BY 1.0, Link

We'll say that two squares (also called cells) are adjacent if they share a side (e.g. two cells diagonal to each other are not adjacent). The goal of the game is to blacken some of the cells in order to obtain a state where these three conditions are met:

1. Any given number can appear at most once in each row or column.
2. Black cells are not adjacent.
3. The remaining numbered cells must be all connected to each other through a path made of adjacent numbered cells.

The first two conditions are pretty much self-explanatory, but the third condition is actually a well-known topological property called path connectedness, which you can pragmatically think of as connecting any two cells with a pen that can't move diagonally and can only pass through numbered cells.

You can easily see that all of these conditions are verified in the solution of the previous Hitori puzzle.

By Dan1980 - Own work, based on File:Hitori_completed.jpg, CC BY 1.0, Link

The basic structure and a naïve approach

In what follows, I'll assume the programming language is Java 8, even though I tried to write the code in the most portable way, and I won't focus on trivial details like getters, setters and imports if not absolutely necessary, so it will look like a sort of pseudocode. I'm sure if you're reading this, you're confident enough to follow me on this journey without further ado.

So, let's get to code. We will, of course, need a basic Cell class, and a game class, which I'm going to call GameState since we will pass from one state of the game to another, and we can consider a partially solved game as a new game itself.

In the Cell class, I decided to keep track of the number that appears on that cell (value) and its position on the grid (x and y). I also found useful to keep a reference to the gameState that the cell belongs to, together with the set of its neighbors, that are simply its adjacent cells.

Finally, black is true if a cell is black (duh?) and white is true whenever we are sure that a cell can't be black: I'll refer to these cells, in fact, as white cells.

I know what you're wondering about right now. Is a non-black cell necessarily white and vice versa? The answer is no: in a given state (actually, often) a cell could be in an undetermined state where we simply don't know if it's black or white even if, in the end, it will be one of these two. What it's true is that a cell cannot be black and white simultaneously, obviously.

public class Cell {
    private final int value;
    private final int x;
    private final int y;
    private final GameState gameState;
    private final Set<Cell> neighbors = new HashSet<>();
    private boolean black = false;
    private boolean white = false;
}

In the GameState class, instead, I simply put the cell grid (implemented as a simple 2D array) and the size of the Hitori puzzle.

public class GameState {
    private final Cell[][] grid;
    private final int size;
}

Now, a really naïve approach would be to use a Depth First Search (or DFS), or a Breadth First Search (or BFS), or any method that just tries every possible combination.

Pretending that checking if a state is legit and/or solved is an operation that doesn't require much time, with elementary math, we know that any of those algorithms is going to be extremely slow as the size grows.

Every possible combination means that for each cell we have to choose if it will be black or not, and if $n$ is the size of the grid, that means that the possible combinations are $2^{n^2}$, (not to be confused with "just" $4^n$: $\; 2^{8^2} \simeq 2\cdot 10^{19}$ while $4^8 = 65536$).

There is also another problem: checking if a state is legit and/or solved isn't a simple operation. In fact, there are several things we need to check in both cases. Let's add the isLegit method to the GameState class: we can say that a state is legit if it has no adjacent black cells and if it is path-connected. Breaking any of these would break the second or third rule specified before.

public class GameState {
    private final Cell[][] grid;
    private final int size;
    
    
    private boolean isLegit() {
        return !connectedBlacksInRows() && !connectedBlacksInColumns() && this.isConnected();
    }

    private boolean connectedBlacksInRows() {
        for (int i = 0; i < size; i++) {
            for (int j = 0; j < size - 1; j++) {
                if (grid[i][j].isBlack() && grid[i][j + 1].isBlack()) return true;
            }
        }
        return false;
    }

    private boolean connectedBlacksInColumns() {
        /* similar */
    }

    boolean isConnected() {
        Set<Cell> nonBlackCells = getNonBlackCells();
        
        /* This takes the cells that result to be path connected to the 
        first non black cell we take into consideration */
        Set<Cell> reachableCells = nonBlackCells.iterator().next().getReachableCells(); 
        
        /* If I can reach all non-black cells from any of the other ones, 
        then they are all path connected. Otherwise, the grid isn't connected. */
        return nonBlackCells.equals(reachableCells);
    }
}

If we want to know if a state is a solution for the problem, then we simply have to check if it is legit and if there is any repetition among the rows and columns (remember? A state is a solution if it is legit and complete), so we're adding the isSolved method too.

public class GameState {

    ...
    
    private boolean isLegit() {
        return !connectedBlacksInRows() && !connectedBlacksInColumns() && this.isConnected();
    }
    
    ...

    boolean isSolved() {
        return this.isLegit() && !this.repetitionsInRows() && !this.repetitionsInColumns();
    }
    
    private boolean repetitionsInRows() {
        Set<Integer> numbers;
        for (int i = 0; i < size; i++) {
            numbers = new HashSet<>();
            for (int j = 0; j < size; j++) {
                if (grid[i][j].isBlack()) continue;
                Integer number = grid[i][j].getValue();
                if (numbers.contains(number)) return true;
                else numbers.add(number);
            }
        }
        return false;
    }
    
    private boolean repetitionsInColumns() {
        /* similar */
    }

Been there, done that — we're not wasting our time with slow methods like DFS or BFS.

Refining the structure in order to introduce Backtracking

The standard way to use Backtracking is to perform a DFS, during which you prune the tree of possible solutions, discarding on the fly the branches that do not meet the constraints defined by the problem.
Actually, I find it much more readable to put the pruning directly inside the method that gives you the next possible candidates for the solution.

public class GameState {

    ...

    Set<GameState> getNextStepOptions() {
        Set<GameState> options = new HashSet<>();
        Set<Cell> cellOptions = getNonColoredCells(); // Neither black nor white
        for (Cell c : cellOptions) {
            try {
                GameState g = c.setBlackAndGetState();
                options.add(g);
            } catch (ImpossibleStateException ignored) {}
        }
        return options;
    }
}

Here, of course, the point is in the try-catch block, and in particular in the setBlackAndGetState method of the Cell class, which throws the ImpossibleStateException whenever blackening that cell would result in a explicit impossible state (e.g. two adjacent black cells or a cell that results in both black and white).

Of course, this alone would make things a lot faster, but given the constraints, you can clearly figure out yourself that there are still too many candidates out there, if only for the path connectedness constraint.

I won't dance around the issue anymore.

The wait is over. Here's the math.

What I'm actually about to do here is infer and propagate topology constraints, but let's not get too technical. I'll just point out five simple facts, that I will call rules to distinguish them from the constraints of the game that I managed to discover and prove in about an hour. This will improve the speed dramatically.

1. If a cell is black, all adjacent cells must be white.
   This is actually trivial: there can't be two adjacent black cells.
2. If a cell is white, all cells having its same number within its same row or its same column have to be black.
   This follows directly from the first constraint of the game: no repetitions!
3. If there is an XYX pattern, then Y has to be white.
   What I mean here is that if you have three adjacent cells (like $828$ in the image below) the one in the middle (e.g. the $2$) has to be white. If it were black at the end of the game, based on rule $1$ that we just discovered, both the "X" (e.g. the $8$) should be white, but this contradicts the first constraint of the game.

XYX pattern

4. If there is an XX...X...X pattern, then all the Xs not in the first couple have to be black.
   Similar to the previous point. If one of the Xs not in the first couple (e.g. one of the blue squared $7$ in the image below) were white, then, by rule $2$, the two Xs in the couple (e.g. the red squared $7$) should be black, but (once more) there can't be two adjacent black cells.

XX...X...X pattern

5. If all except one of the neighbors of a cell are black, then the cell is white and the last neighbor is white too.
   Here the proof is a bit more tedious because of corners and side squares, so I'll leave it to the reader. The point is that you would have disconnected the cell from the rest of the grid.

If you want, take the time to try to solve a Hitori yourself and see how simple that is now that you know these five rules.

And here is the turning point.

What we're going to do is just add these new pieces of information (actually, constraints) to the code, but first, let's sink into the mysterious setBlackAndGetState method that seems to do most of the work.

public class Cell {
    
    ...
    
    GameState setBlackAndGetState() throws GameState.ImpossibleStateException {
        if (neighbors.stream().anyMatch(Cell::isBlack)) 
            throw new GameState.ImpossibleStateException(); // Constraint 2

        try {
            GameState g = new GameState(this.gameState);
            g.getGrid()[x][y].setBlack();
            
            /* Constraint 3 */
            if (!g.isConnected()) throw new GameState.ImpossibleStateException(); 

            return g;
        } catch (AlreadyColoredException e) {
            throw new GameState.ImpossibleStateException();
        }
    }
    
    void setBlack() throws AlreadyColoredException {
        if (this.black) return; // Nothing to do here
        if (this.white) throw new AlreadyColoredException(); // Both white and black?
        else {
            this.black = true;
            /* Rule 1. */
            for (Cell c : neighbors) {
                c.setWhite();
            }
        }
    }

    void setWhite() throws AlreadyColoredException {
        if (this.white) return; // Nothing to do here
        if (this.black) throw new AlreadyColoredException(); // Both white and black?
        else {
            this.white = true;
            /* Rule 2. */
            for (Cell c : this.getRow()) {
                if (c.getValue() == this.value && !c.equals(this)) c.setBlack();
            }
            for (Cell c : this.getColumn()) {
                if (c.getValue() == this.value && !c.equals(this)) c.setBlack();
            }
        }
    }
    
}

See what I'm doing there? I apply the first and second rules immediately (and recursively) every time I try to blacken a new square. As noted before, if this takes to an inconsistent state, I throw a new ImpossibleStateException. And now the final part:

public class GameState {

    ...
    
    void infer() throws ImpossibleStateException {
        GameState original = new GameState(this);
        this.inferSurroundedCell(); // Rule 5.
        this.inferXYXPattern(); // Rule 3.
        this.inferXXYZXPattern(); // Rule 4.
        
        /* If I did change the state, I try to do that again because there could 
        be that new rules can be applied */
        if (!this.equals(original)) this.infer();
    }
}

The BST (Backtracking Search Tree) method itself is actually in the Main, it's just inferring as much as possible before even trying to take a new road.

private static GameState BST(GameState state) {
    Stack<GameState> stack = new Stack<>();
    stack.push(state);
    
    while (stack.size() != 0) {
        GameState element = stack.pop();
        /* Note that, apart from this try-catch block, this is the standard BST */
        try {
            element.infer();
        } catch (GameState.ImpossibleStateException e) {
            return null;
        }

        if (element.isSolved()) {
            return element;
        }

        for (GameState g : element.getNextStepOptions()) {
            stack.push(g);
        }
    }
    return null;
}

I put below three snapshots (just by way of example) of Hitori puzzles of size 5, 6, and 7 respectively, to show how fast solving it is compared to generating random solvable puzzles (which is similar to how long the naïve approach would take).

Also, note how the time to solve them isn't increasing expontially, unlike the naïve approach. Actually, it seems that the solve time isn't increasing at all. Out of curiosity, calculating the exact complexity of algorithms like the one described is extremely difficult.

Size 5

Size 6

Size 7

It was my intention to put also a size 8 snapshot for the naïve approach, but (ironically) it didn't finish in time, so here's just the solving time.

Size 8

Okay, sounds good. But why can't I just use Machine/Deep Learning, Tensorflow, or something similar in order to solve tasks like that?

It's not that you can't, but this way you can actually spare a lot of time, resources, and (ultimately) money.

Machine learning of (almost) every kind, in fact, requires a dataset. And for a non popular topic like Hitori, you would have to create that yourself.

That would be time-consuming without the process we just explained (which, in turn, you can actually use to let a machine learn about the path connectedness property which backtracking is actually taken care of).

So if you got this far reading and you're still wondering what this post was about, the short answer is: always ask yourself what the options are, and choose the right approach.
And a bit of math(ematician) always helps in this.

Oh, yeah. I also taught you how to solve a Hitori puzzle by learning some pretty advanced Artifical Intelligence concepts and practices. Not bad.

You can find the complete source code (updated and upgraded) here.