IA con salarios mínimos: escribimos nuestro Sokoban y enseñamos a la computadora a resolverlo

En este artículo te diré cómo escribir tu propia implementación del famoso juguete Sokoban, así como un algoritmo para resolverlo desde cero. Al mismo tiempo, pondré en práctica algunos patrones de diseño y principios SÓLIDOS.

Todo el código se encuentra en

Antecedentes

Utilizo un teléfono de botón. De entretenimiento en él solo radio y el único juego Sokoban de 15 niveles. De estos, solo resolví 10 y me quedé atascado en el undécimo. Una vez tomé el tren todo el día y resolví este desafortunado nivel 11, pero no lo logré. Entonces decidí usar una computadora, ya que tengo suficiente experiencia en programación para esta tarea. Fíjese un objetivo: escriba usted mismo una implementación con la solución de este juguete. Como resultado, apareció este artículo.

El mismo nivel 11 (solución al final del artículo):

El juguete en sí es un campo 2D rectangular en el que se encuentran dispersas cajas, paredes y etiquetas. Las cajas se pueden empujar, pero no tirar, esta es toda la dificultad. Tu objetivo: mover todos los cuadros a celdas con marcas. Ejemplo de juego:

Escribimos la implementación

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 un nuevo algoritmo de IA, escribí un nuevo controlador AIControllerque no lee los comandos de la consola, pero resuelve el nivel con el algoritmo especificado y pierde la solución en un temporizador. solo necesita cambiar una línea en main. Nuestra inversión en arquitectura ha dado sus frutos:

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();
    }
}

conclusiones

Hemos creado nuestra propia implementación del juguete Sokoban, aplicamos los patrones de diseño Abstract Factory, Factory Method y Strategy en la práctica, examinamos los principios S, O y D de SOLID e implementamos los algoritmos BFS y A *.

Me encantaría tener comentarios tanto sobre el código como sobre el artículo en sí. ¡Nos vemos!

Estoy en telegrama: @outofbound