AI aux salaires minimums: nous écrivons notre propre Sokoban et apprenons à l'ordinateur à le résoudre

Dans cet article, je vais vous dire comment écrire votre propre implémentation du célèbre jouet Sokoban, ainsi qu'un algorithme pour le résoudre à partir de zéro. En même temps, je mettrai en pratique certains modèles de conception et principes SOLID.

Tout le code est situé à

Contexte

J'utilise un téléphone à bouton-poussoir. Du divertissement sur elle seule radio et le seul jeu Sokoban de 15 niveaux. Parmi ceux-ci, je n'en ai résolu que 10 et je suis resté coincé sur le onzième. Une fois, je suis monté dans le train toute la journée et j'ai résolu ce 11e niveau malheureux, mais je n'ai pas réussi. Ensuite, j'ai décidé d'utiliser un ordinateur, car j'ai suffisamment d'expérience en programmation pour une telle tâche. Fixez-vous un objectif: rédigez vous-même une implémentation avec la solution de ce jouet. En conséquence, cet article est apparu.

Le même niveau 11 (solution en fin d'article):

Le jouet lui-même est un champ 2D rectangulaire, sur lequel sont dispersés des boîtes, des murs et des marques. Les boîtes peuvent être poussées, mais pas tirées, c'est toute la difficulté. Votre objectif: déplacer toutes les cases vers des cellules marquées. Exemple de jeu:

Nous écrivons l'implémentation

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 . , .

Pour démarrer un nouvel algorithme AI, j'ai écrit un nouveau contrôleur AIControllerqui ne lit pas les commandes de la console, mais résout le niveau avec l'algorithme spécifié et perd la solution sur une minuterie. vous n'avez besoin de changer qu'une seule ligne main. Notre investissement dans l'architecture a porté ses fruits:

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

conclusions

Nous avons créé notre propre implémentation du jouet Sokoban, appliqué les modèles de conception Abstract Factory, Factory Method et Strategy dans la pratique, pris en compte les principes S, O et D de SOLID et implémenté les algorithmes BFS et A *.

Je serais heureux d'avoir des commentaires à la fois sur le code et sur l'article lui-même. À plus!

Je suis dans le télégramme: @outofbound