IA com salários mínimos: nós escrevemos nosso próprio Sokoban e ensinamos o computador a resolvê-lo

Neste artigo, vou explicar como escrever sua própria implementação do famoso brinquedo Sokoban, bem como um algoritmo para resolvê-lo do zero. Ao mesmo tempo, colocarei em prática alguns padrões de projeto e princípios SOLID.

Todo o código está localizado em

fundo

Eu uso um telefone com botão de pressão. De entretenimento nele apenas rádio e o único jogo Sokoban de 15 níveis. Destes, resolvi apenas 10 e fiquei preso no décimo primeiro. Uma vez eu andei de trem o dia todo e resolvi esse malfadado 11º nível, mas não tive sucesso. Decidi então usar um computador, já que tenho bastante experiência em programação para tal. Eu defini uma meta: escrever uma implementação com a solução desse brinquedo eu mesmo. Como resultado, este artigo apareceu.

O mesmo nível 11 (solução no final do artigo):

O brinquedo em si é um campo retangular 2D, no qual caixas, paredes e marcas estão espalhadas. As caixas podem ser empurradas, mas não puxadas, essa é toda a dificuldade. Seu objetivo: mover todas as caixas para células com marcas. Jogo de exemplo:

Nós escrevemos a implementação

GUI . - Rogue-like, . . :

• # , .
• O .
• X , .
• @ .
• . .
• G .

— . , . MVC — , , . , , . . . — - . , SOLID. , . — , — , — . , . . . :

• , , GUI . .
• .

— , :

public class ConsoleController implements Controller
{
    private final Model model;
    private final View view;

    public ConsoleController(final Model model)
    {
        this.model = model;
        this.view = new ConsoleView(model);
    }
    // methods
}

model , , view . , ConsoleController View, ConsoleView, . ConsoleView ConsoleController, , :

public class ConsoleController implements Controller
{
    private final Model model;
    private final View view;

    public ConsoleController(final Model model, final View view)
    {
        this.model = model;
        this.view = view;
    }
    // methods
}

ConsoleController . D SOLID , . . , — . , - Spring , . .

. , ?

• 
  
  (row, col), row , col , . — , . , , , . .

, . , , , . "" — , , . :

, , Model. Sokoban , . move() . Sokoban . getCrates() getMarks() . , : A* (A star algorithm).

run() " -> -> -> "

, :

###########
#.@..O..X.#
###########

- . " ". : CharSokobanFactory , , , . , Sokoban , , :

    public Sokoban(final Field field, final Set<Point> crates, final Set<Point> marks, final Point player)
    {
        this.field = field;
        this.crates = crates;
        this.marks = marks;
        this.player = player;
    }

CharSokobanFactory. , . .

vi-like :

• j —
• k —
• h —
• l —

, :

class Sokoban {
    // some stuff
    public boolean solved()
    {
        return marks.equals(crates);
    }
    // other stuff
}

if- , Direction, . Move, Direction move(direction) . Move.resolve, .

" ". : , 4 .

O SOLID, Open-Closed Principle: . , . , , . - , , .

:

:

class ConsoleController {
//
    @Override
    public void run()
    {
        view.say("Sokoban Starts");
        char symbol = '0';
        view.render();
        final List<Move> history = new LinkedList<>();
        while (symbol != 'q')
        {
            final Move move = Move.resolve(symbol);
            if (move != null)
            {
                history.add(move);
                move.perform(sokoban);
                view.render();
                if (sokoban.solved())
                {
                    view.say("YOU WIN!");
                    break;
                }
            }
            try
            {
                symbol = (char) System.in.read();
            }
            catch (IOException io)
            {
                view.say("   :");
                throw new IllegalStateException(io);
            }
        }
        view.say("Your moves: " +  Move.compress(history));
    }
//
}

, , . , "" , , . .

:

class ConsoleView {
//
    @Override
    public void render()
    {
        clearConsole();
        for (int i = 0; i < sokoban.numberOfFieldRows(); i++)
        {
            for (int j = 0; j < sokoban.numberOfFieldCols(); j++)
            {
                final Point at = new Point(i, j);
                final Tile tileAt = sokoban.tile(at);
                if (tileAt == null)
                    break;
                final char symbolToPrint = tileAt == Tile.CRATE && sokoban.isMarkAt(at) ? Tile.CRATE_ON_MARK.symbol() : tileAt.symbol();
                System.out.print(symbolToPrint);
            }
            System.out.println();
        }
    }
//
}

15 . G (Good) , , . , .

. :

• , . , .

, "walkable" Tile:

public enum Tile {
    WALL('#', false),
    GRASS('.', true),
    CRATE('O', false),
    MARK('X', true),
    CRATE_ON_MARK('G', false),
    PLAYER('@', true);

    private final char symbol;
    private final boolean walkable;

    Tile(final char symbol, final boolean walkable) {
        this.symbol = symbol;
        this.walkable = walkable;
    }

    public boolean isWalkable() {
        return walkable;
    }
}

, :

public Sokoban {
//  Sokoban
    public Tile tile(final Point at) {
        if (player.equals(at))
            return Tile.PLAYER;
        //
        if (crates.contains(at))
            return Tile.CRATE;
        //
        return field.tileAt(at);
    }
    public boolean isWalkableTileAt(final Point at) {
        return tile(at).isWalkable();
    }
//  Sokoban
}

, , , . :

public class Main {
    public static void main(String[] args) {
        final Sokoban sokoban = CharSokobanFactory.fromFile(args[0]).make();
        final View view = new ConsoleView(sokoban);
        final Controller game = new ConsoleController(sokoban, view);
        // 
        game.run();
    }
}

:

############
#.XO.......#
#.XO......@#
#.XO.......#
############

, :

, , , . . , — .

? . . , , :

, , . . , , , . . ,

, :

, . , (1:1), .

. — .

. . , . , , . , — Breadth-First Search (BFS).

BFS

"" — (Depth-First Search) — BFS , . , . BFS (FIFO), DFS (LIFO), . BFS:

BFS(G, s)
1.  ,    :
    * v.p = null // 
    * v.marked = false //     
2.   Q
3. Q.enqueue(s)
4.  Q  :
    4.1 v = q.poll()
    4.2 v.marked = true
    4.3  v   ,   
    4.4     v , child:
        4.4.1   child.marked, :
            4.4.1.2 child.p = v
            4.4.1.3. q.enqueue(child)

v.p v. v.marked , v . v "" v -> v.p -> v.p.p -> ... -> s -. .

. .

. , , . . , :

, :

public class BFSSolver {
//
    protected List<Pair<Sokoban, List<Direction>>> deriveChildren(final Sokoban parent) {
        final Map<Point, Point> walkablePoints = shortestPathsFromPlayer(parent);
        final List<Pair<Sokoban, List<Direction>>> result = new LinkedList<>();
        for (final Point crate : parent.getCrates()) {
            final Point[][] pairs = new Point[][]{{crate.left(), crate.right()}, {crate.right(), crate.left()},
                    {crate.up(), crate.down()}, {crate.down(), crate.up()}};
            for (Point[] pair : pairs) {
                final Point playerWillStand = pair[0];
                final Point crateWillGo = pair[1];
                if (canMoveCrate(parent, playerWillStand, crateWillGo, walkablePoints) && !isDeadPosition(parent, crateWillGo)) {
                    final LinkedList<Direction> pathToChild = unwindWalk(walkablePoints, playerWillStand);
                    pathToChild.add(crate.derive(crateWillGo));
                    final Sokoban child = parent.derive(crate, crateWillGo);
                    result.add(Pair.pair(child, pathToChild));
                }
            }
        }
        return result;
    }
//
}

shortestPathsFromPlayer parent . walkablePoints v v.p. isDeadPosition . derive Sokoban "" :

    public Sokoban derive(final Point crateToRemove, final Point crateToInsert)
    {
        final Set<Point> childConfiguration = new HashSet<>(crates);
        childConfiguration.remove(crateToRemove);
        childConfiguration.add(crateToInsert);
        return new Sokoban(this.field, childConfiguration, Collections.unmodifiableSet(this.marks), crateToRemove);
    }

, "" . , Point (immutable). "", , BFS, . v.p v.marked .

:

public class BFSSolver {
//
    public List<Move> solve(final Sokoban start) {
        final Map<Sokoban, Pair<Sokoban, List<Direction>>> childToParentAndDirection = new HashMap<>();
        final Set<Sokoban> visited = new HashSet<>();
        final Queue<Sokoban> toVisit = new LinkedList<>();
        toVisit.add(start);
        boolean found = false;
        Sokoban parent = null;
        while (!toVisit.isEmpty()) {
            parent = toVisit.remove();
            if (parent.solved()) {
                found = true;
                break;
            }
            visited.add(parent);
            for (final Pair<Sokoban, List<Direction>> pair : deriveChildren(parent)) {
                final Sokoban child = pair.first;
                final List<Direction> walkFromParentToChild = pair.second;
                if (!visited.contains(child)) {
                    childToParentAndDirection.put(child, Pair.pair(parent, walkFromParentToChild));
                    toVisit.add(child);
                }
            }
        }
        return found? unwind(parent, childToParentAndDirection) : new LinkedList<>();
    }
//
}

, , BFS , . , , , . , , . ,

"" , . , . .

* (A star), . * .. h . h . — , h .

"" . . AStarSolver . , .

Para iniciar um novo algoritmo de IA, escrevi um novo controlador AIControllerque não lê comandos do console, mas resolve o nível com o algoritmo especificado e perde a solução em um cronômetro. você só precisa mudar uma linha main. Nosso investimento em arquitetura valeu a pena:

public class Main {
    public static void main(String[] args) {
        final Sokoban sokoban = CharSokobanFactory.fromFile(args[0]).make();
        final View view = new ConsoleView(sokoban);
        final Solver solver = new AStarSolver();
        final int sleepBetweenMovesMillis = 300;
        final Controller game = new AIController(sokoban, view, sleepBetweenMovesMillis, solver);
        // 
        game.run();
    }
}

conclusões

Criamos nossa própria implementação do brinquedo Sokoban, aplicamos os padrões de projeto Abstract Factory, Factory Method e Strategy na prática, consideramos os princípios S, O e D do SOLID e implementamos os algoritmos BFS e A *.

Eu ficaria feliz em receber comentários sobre o código e o próprio artigo. Até logo!

Estou no telegrama: @outofbound