AI for a logic game

This is a clone of KNetwalk.  I got addicted to this game when I got my Netbook.  Some of my daily train rides were spent adding a feature to my compiler, but equally often they culminated in a slightly improved KNetwalk high score.  When the hardest level (15×15, wraparound) because passé, did I stop there and recover from my obsession?  No, I wrote my own version, with harder maps!

This version is a little different from KDE’s.  It doesn’t penalise unnecessary moves or a slow solution time.  And the interface is still primitive: change the source code around line 480 to specify a different map.  It’s enough for me to enjoy playing it, and it lets me experiment with AI strategies for solving it.  (N.B. I mean AI in the very weak sense of a set of rules for solving a particular problem.)

The map is an array of cells.  It can optionally be a torus, i.e. the sides wrap round.  One (or optionally several) sources are placed on the map.  A tree of edges is grown from this, the leaves of which become sinks.  Cells into which an edge does not grow become voids.

My version does not generate the same kinds of maps as the original: it leaves more voids.  I’ve not seen the original generation algorithm so I can only guess the reason for this.  My algorithm seems pretty obvious, so who knows what they’re doing. :p

The cells are defined with two sets of edge states:

• true_ports – initialised when the map is generated, not changed.  (Not used except when the map is finished by the player.)
• ports – a rotation of true_ports; rotated randomly when the map is scrambled, rotated when a cell is clicked on.

Heat is propagated from the sources.  When two adjacent cells are connected (by each having a port to the other), heat flows between them.  Unconnected cells lose their residual heat.  The aim is for all sinks to be warm, i.e. in a steady state of receiving some heat.

A human playing network.py

Simple AI player

Each cell records two additional sets of edge states:

• necessary – the edge here is necessarily part of the solution.  Initially, no edges are necessary.
• possible – the edge here is possible.  Initially, all edges are possible.

The player uses heuristics for each cell type to populate these when appropriate.  Here are some example rules:

• If a cell with a corner tile has a necessary edge, then the opposite edge is not possible.
• If a cell with a straight tile has a necessary edge, then the opposite is also necessary.
• If a cell is adjacent to a void, then their shared edge is not possible.
• If two cells are sinks, then their shared edge is not possible (because if that edge was in use, they would connect only to each other and be isolated from the source).
• If an edge for one cell is necessary, then the same edge for the neighbouring cell is also necessary.
• If an edge for one cell is not possible, then the same edge is the neighbouring cell is not possible.
• If num(ports) = num(necessary) or num(ports) = num(possible), then the cell is solved.

The AI player does a pretty good job, but usually cannot solve the whole map.  One problem is that progress is made only at the local level, using local information.  The partial solution is propagated, but only through necessary and possible.  Information about distant cells is unavailable unless it can be expressed in terms of these variables.  (The logic game Minesweeper has similar strategies.  In that case, the information propagated is usually the number printed on each revealed cell.  See http://web.mat.bham.ac.uk/R.W.Kaye/minesw/ for more info on Minesweeper logic, including papers regarding its Turing- and NP-completeness)

An AI player ruthlessly sweeping over the map, but then failing at a cycle of mutually-insoluble cells.

An additional heuristic slightly extends the neighbourhood of visible cells to eliminate simple cycles, which are not strictly necessary for lighting all sinks, and which cannot be part of the generated solution since the generation algorithm uses a tree.  It identifies sets of three mutually incident edges that are each necessary, and hence marks the fourth edge as not possible.

AI player eliminating simple cycles; pink bars indicate necessary edges, pink cross indicates not possible

The next attempt was to exploit the tree structure of the map, in particular the fact that there is exactly one path from a sink to it source.  Live and dead flags are maintained for each cell, indicating that the cell is known to be live (i.e. has a solved path to the source), and dead (i.e. only one edge leads to the source; all others are dead ends).  Ultimately, each cell should be marked both live and dead.  A heuristic that uses this information is:

• If all but one neighbouring cells are dead, then the remaining one is necessary.
• If this cell is live and a neighbouring cell is also live, and the edge between them is not necessary, then that edge is not possible.  (As each cell is live, each already has a solved path to the source; they are on different branches of the tree.)

However, as currently implemented these heuristics lead to unsound behaviour by the AI player, so I’ve disabled them.  The problem is likely a faulty concept of “deadness”.

Another trickier problem is that the AI solves things by eliminating alternatives until there is only one choice.  But sometimes maps are generated with more than one possible solution!  People I’ve discussed this with have been astonished that the AI doesn’t simply pick a solution and be done with it.  It’s as if the computer is suffering from the “tyranny of choice” — though in this case it’s not so much fear of picking the wrong choice that holds the machine up, as simply being unable to identify a viable solution because the presence of alternatives casts doubt on it.

A tricky problem: which of two solutions do we pick?

Backtracking AI?

The simple AI is fairly efficient: it makes progress based on local (i.e. finite) information only, and does not backtrack.  However as explained it is not complete.  A full depth-first solver could fill in the holes left by the simple AI.  Additionally, it would stop at the first solution found, thus taking an Alexandrian swipe at the multiple-solution issue.

Could it treat each remaining hole as a self-contained problem, deducing its solution from its cells and the known edges on its periphery?  I don’t think so — at least, not without correct liveness/deadness information.  Because some parts of the periphery may be disconnected from the source, and need a connection running through the hole.  It is difficult to recognise this without liveness/deadness, or non-local examination of the paths through the whole maze.

A more appropriate language for a backtracking AI might be Prolog.  But it should be feasible in Python; the main issue with nondeterministic programs in Python is managing huge sets of possible values.  Luckily, Python’s generators provide a natural technique for doing this more efficiently.