Beating ZX Spectrum game "Logo: Part 1" with Picat

There was an interesting puzzle game on ZX Spectrum computer called Logo: Part 1 (part 2 never materialized).

The game can be seen as a variant of Lights Out. Starting with an empty game board, the player needs to transform it into a target state by taking actions on empty cells. When the player affects a cell, it switches from empty to '1', and all orthogonally adjacent non-empty cells' values are increased by 1, but '4' becomes '1' again, not '5'.

This kind of puzzles is easy to solve with Picat – new logic-based programming language similar to Prolog – and its planner module.

Let's define an input format for our program. First line has 2 space-separated integers, MaxR and MaxC: number of rows and columns. Then MaxR lines of length MaxC follow; each line represents a row in the target position, and consists of '1', '2', '3', '4', or '.' (empty cell).

Here is the target of the ZX Spectrum game's first level in this format:

6 10
..........
....2.....
...212....
....2.....
..........
..........

We want to find a plan – sequence of cells to take actions on – to get from initial empty board to the target position.

For the level above a plan could be:

4 5
3 6
3 4
2 5
3 5

First, take action of a cell in fourth row and fifth column, then in third row and sixth columns, and so on. There are other possible plans for this level, because for some cells the actions can be taken in arbitrary order.

To solve the puzzle with Picat's planner module we need to define final and action predicates.

final is a predicate that has current problem state as a parameter and is true when the goal of the planning problem is reached. In our case the predicate is true when the current state of the game board is the same as the target state.

action defines what actions are possible and how the state is transformed after applying the action. We can define an action that gets a current board, finds coordinates of a cell that currently empty but not empty on the target board, and returns new board where the cell with these coordinates has '1' and all adjacent cells are updated according to the game rules ('1' → '2', etc.)

Here is a Picat program that implements these ideas:

import planner.
import util.

next('.') = '.'.
next('1') = '2'.
next('2') = '3'.
next('3') = '4'.
next('4') = '1'.

final(Board) =>
    target(Target),
    Board == Target.

action(Board, NewBoard, Action, Cost) =>
    MaxR = Board.length(),
    MaxC = Board[1].length(),
    between(1, MaxR, R),
    between(1, MaxC, C),
    Board[R, C] == '.',
    target(Target),
    Target[R, C] != '.',
    NewBoard = copy_term(Board),
    NewBoard[R, C] := '1',
    foreach ((DR, DC) in [(0, 1), (0, -1), (1, 0), (-1, 0)])
        NR = R + DR, NC = C + DC,
        if (NR > 0, NR <= MaxR, NC > 0, NC <= MaxC) then
            NewBoard[NR, NC] := next(NewBoard[NR, NC])
        end
    end,
    Action = (R, C),
    Cost = 1.

main =>
    MaxR = read_int(), MaxC = read_int(),
    Board = new_array(MaxR, MaxC),
    foreach (R in 1..MaxR)
        Line = read_line(),
        foreach (C in 1..MaxC)
           Board[R, C] = Line[C]
        end
    end,
    cl_facts([$target(Board)]),
    EmptyBoard = new_array(MaxR, MaxC),
    foreach (R in 1..MaxR)
        foreach (C in 1..MaxC)
           EmptyBoard[R, C] = '.'
        end
    end,
    plan_unbounded(EmptyBoard, Plan),
    foreach ((R, C) in Plan)
        printf("%d %d%n", R, C)
    end.

GitHub: https://github.com/kit1980/sdymchenko-com/blob/master/logo-part1-picat/logo_slow.pi

The game state (board) can be represented as a 2-dimensional array, every element of which is '.', '1', '2', '3', or '4'.

final predicate just compares the current board with the target board, and is true only if they are equal.

action predicate has 4 parameters: current board, new board after action, name of the action, and cost of the action. Predicate between works the same way as in Prolog: non-deterministically chooses value for the third parameter from the range determined by the first two parameters; effectively, between(1, MaxR, R), between(1, MaxC, C) loops through all possible row/column combinations.

To update all adjacent cells we can use foreach loop and if – then – else construct, which are similar to what is used in imperative languages; next functional facts define how these cells are transformed according to the game rules. It's important to distinguish unification = and destructive assignment := – the latter is used to update value of a variable that already has a value assigned. The name of the action is a tuple of row and column numbers (R, C), and the cost is 1 – all actions are equally costly.

The main predicate reads the input, constructs target predicate and commits it to Picat's fact database with cl_facts (to be later used in final and action), runs plan_unbounded – plan finding predicate from the planning module that never re-explore already visited states, and outputs the result.

The above program works, but it's very slow for larger inputs. Even for the third level it takes several seconds to solve, and it gets much slower for the later levels. The program is slow because at every step it needs to try every cell that is empty in current position but not empty in the target position. Most of these tries lead to dead ends, and need to be backtracked.

To come up with a better program we can think about the problem "backwards", from end to start: if we already have the target position on the board, what was the last move? the penultimate move? and so on. Then we just reverse this plan and get a plan to solve the original problem. This will work much faster because we need to consider only '1' tiles on each step.

New version:

import planner.
import util.

prev('.') = '.'.
prev('2') = '1'.
prev('3') = '2'.
prev('4') = '3'.
prev('1') = '4'.

final(Board) =>
    MaxR = Board.length(),
    MaxC = Board[1].length(),
    foreach (R in 1..MaxR, C in 1..MaxC)
        Board[R, C] == '.'
    end.

action(Board, NewBoard, Action, Cost) =>
    MaxR = Board.length(),
    MaxC = Board[1].length(),
    between(1, MaxR, R),
    between(1, MaxC, C),
    Board[R, C] == '1',
    NewBoard = copy_term(Board),
    NewBoard[R, C] := '.',
    foreach ((DR, DC) in [(0, 1), (0, -1), (1, 0), (-1, 0)])
        NR = R + DR, NC = C + DC,
        if (NR > 0, NR <= MaxR, NC > 0, NC <= MaxC) then
            NewBoard[NR, NC] := prev(NewBoard[NR, NC])
        end
    end,
    Action = (R, C),
    Cost = 1.

main =>
    MaxR = read_int(), MaxC = read_int(),
    Board = new_array(MaxR, MaxC),
    foreach (R in 1..MaxR)
        Line = read_line(),
        foreach (C in 1..MaxC)
           Board[R, C] = Line[C]
        end
    end,
    plan_unbounded(Board, PlanRev),
    foreach ((R, C) in reverse(PlanRev))
        printf("%d %d%n", R, C)
    end.

GitHub: https://github.com/kit1980/sdymchenko-com/blob/master/logo-part1-picat/logo.pi

This new version is very similar to the previous version, but we use prev facts instead of next, check that the board is empty in final, try only '1's for possible next move, and reverse the plan in the end. This version works very fast for most of the ZX Spectrum game levels.

Now we can use our planner-based solver to actually beat the game: we can load the game into a ZX Spectrum emulator, make screenshots and send keypresses to automate the game.

The code for the actual bot (https://github.com/kit1980/sdymchenko-com/blob/master/logo-part1-picat/logo-part1.pi) is rather ugly and mostly deals with reading particular pixels from screenshots to get the target board for each level, locate cursor position, and wait if the game is in transition between levels.

Initially I wanted to just send a sequence of keypresses corresponding to the plan and assume it will be followed without errors by the game. Unfortunately, at least on my computer and with my operating system/emulator setup, it's not reliable. Even when playing the game manually, too often keypresses are not registered or registered twice. So after sending keypresses to move the cursor, we need to locate the actual position of the cursor, and send more keypresses if it's not at the expected position.

For screenshots I used import command from ImageMagic and PPM format, which is easy to read without using specialized libraries. For sending keypresses I used xdotool. Fuse was my emulator of choice, mostly because it's easy to produce video with it (but I needed to use SDL version, because GTK version ignores keystrokes sent by xdotool).

Here is the video of the complete walkthrough using the bot (almost an hour long):

Some improvements are possible for this program.

One problem is that the solver tries to find a cell to act on starting from top left corner column-by-column, row-by-row. This may be too far from optimal: currently level 94 of the ZX Spectrum game – which has no empty cells on the target boards – takes about 15 seconds to solve on my machine. Because it's more likely that a good '1' to action on will be on the border, it may be more efficient to iterate in a spiral fashion, from the outer border to the center.

Another idea, more difficult to implement, is to construct the plan that minimizes the number of keypresses: different actions will have different cost depending on how far current step's cell is from previous step's cell. Solving this optimally is probably infeasible.

To learn more about Picat see the official web site http://picat-lang.org/, Hakan Kjellerstrand's Picat page http://www.hakank.org/picat/, and picat tag on this blog. And I'll be at LambdaConf with "Introduction to Tabled Logic Programming with Picat" workshop (May 26 2016 in Boulder, Colorado).