King-Pen! (Punkte und Kästchen)

23

Dies ist ein König der Hügel Herausforderung für Dots and Boxes (auch bekannt als Pen the Pig). Das Spiel ist einfach, wenn Sie an der Reihe sind, ziehen Sie einfach eine Linie auf einen leeren Zaun. Jedes Mal, wenn Sie ein Quadrat vervollständigen, erhalten Sie einen Punkt. Da wir nach den Regeln der Meisterschaft spielen , erhalten Sie einen zusätzlichen Zug, wenn Sie mindestens ein Feld in Ihrem Zug vervollständigen. Dies ist ein Round-Robin-Turnier, bei dem jeder Bot zweimal zwölf Mal in einem 9x9-Raster gegeneinander spielt . Schauen Sie sich dieses Match zwischen zwei Schwergewichts-Titanen an, bei dem ChainCollector das Hackfleisch des amtierenden Co-Champions Asdf zubereitet: Bildbeschreibung hier eingeben

Regeln

  1. 0,5 Sekunden Zeitlimit pro Zug.
  2. Keine Beeinträchtigung anderer Bots.
  3. Verwenden Sie PigPen.random () und PigPen.random (int) für die Zufälligkeit.
  4. Kein Schreiben in Dateien.
  5. Der Bot und alle seine persistenten Daten werden jedes Mal zurückgesetzt, wenn sich der Gegner ändert (alle 12 Runden).

Bots

Jeder Bot erweitert Player.java:

package pigpen;

public abstract class Player {

public abstract int[] pick(Board board, int id, int round); 

}

Boardist das Spielbrett, das hauptsächlich dazu dient, Ihnen den Zugang zu PenKlassen zu ermöglichen, und idist Ihre Spieler-ID (gibt an, ob Sie der Erste oder der Zweite sind) und roundgibt an, in welcher Runde Sie gegen denselben Gegner spielen (1 oder 2). Der Rückgabewert ist ein int[], wobei das erste Element die penID (1-indiziert) und das zweite Element die fenceID (0-indiziert) ist. In finden Sie Pen.pick(int)eine einfache Möglichkeit, diesen Rückgabewert zu generieren. Auf der Github- Seite finden Sie Beispiele für Player und JavaDoc. Da wir nur ein quadratisches Gitter verwenden, ignorieren Sie alle Funktionen und Felder, die sich auf Sechsecke beziehen.

Wie man läuft

  1. Quelle von Github herunterladen.
  2. Schreiben Sie Ihren Controller-Bot (achten Sie darauf, ihn einzuschließen package pigpen.players) und legen Sie ihn in den src/Ordner.
  3. Kompilieren mit javac -cp src/* -d . src/*.java. Ausführen mit java pigpen.Tournament 4 9 9 false(Die letzten beiden Zahlen können geändert werden, um truedie Rastergröße anzupassen. Die letzte Variable sollte nur festgelegt werden, wenn Sie die Software pp_record verwenden möchten.)

Scores

  1. ChainCollector: 72
  2. Asdf: 57
  3. Lazybones: 51
  4. Finisher: 36
  5. = LinearPlayer: 18
  6. = BackwardPlayer: 18
  7. RandomPlayer: 0

Siehe auch:

Hinweis : Dieses Spiel ist eine Herausforderung für den Wettbewerb und nicht leicht zu lösen, da die Spieler einen zusätzlichen Zug zum Ausfüllen einer Schachtel erhalten.

Vielen Dank an Nathan Merrill und Darrel Hoffman für die Beratung zu dieser Herausforderung!

Aktualisierungen :

  • Der moves(int player)Klasse "Brett" wurde eine Methode hinzugefügt , um eine Liste aller von einem Spieler ausgeführten Züge abzurufen.

Unbestimmte Prämie (100 Wiederholungen) :

Die erste Person, die eine Lösung veröffentlicht, die jede Runde gewinnt und eine Strategie anwendet (Anpassung des Spiels basierend auf der Beobachtung, wie der Gegner spielt).

Geokavel
quelle
2
GÜTE. Finisher ist waaayyyy OP! : P
El'endia Starman
@ El'endiaStarman Lol, er beendet nur einen Stift mit einem verfügbaren Zaun oder wählt auf andere Weise einen Stift mit den meisten verbleibenden Zäunen aus. RandomPlayer ist nur zufällig.
Geokavel
2
Ja ich weiß. Es ist nur so, dass das Endergebnis 79-2 ist und RandomPlayer nur die letzten beiden Boxen hat, weil es sein musste . : P
El'endia Starman
Hallo! Ich möchte meinen eigenen Bot machen, habe aber eine Frage. Gibt Pen.BOTTOM in Zeile 0, Spalte 0 dieselben Werte zurück wie Pen.TOP in Zeile 1, Spalte 0?
Tuskiomi
@ Tusk Ja, das tut es
Geokavel

Antworten:

6

Faulpelz

Dieser Bot ist faul. Er wählt einen zufälligen Punkt und eine zufällige Richtung und baut in dieser Richtung weiter, ohne sich zu sehr zu bewegen. Es gibt nur 2 Fälle, in denen er etwas anderes macht:

  • "Verdiene Geld", indem du einen Pflock mit nur einem verbleibenden Zaun schließt
  • wähle einen neuen Ort und eine neue Richtung, wenn das Platzieren des Zauns nicht möglich ist oder der andere Bot "Geld verdienen" könnte
package pigpen.players;

import java.util.ArrayList;
import java.util.List;
import java.util.stream.Collectors;

import pigpen.Board;
import pigpen.Pen;
import pigpen.PigPen;
import pigpen.Player;

public class Lazybones extends Player {
    private static class Fence {
        private static boolean isOk(Board board, boolean vertical, int row, int col) {
            if (vertical) {
                Pen left = board.getPenAt(row, col - 1);
                Pen right = board.getPenAt(row, col);
                if (left.id() < 0 && right.id() < 0 ||
                        left.fences()[Pen.RIGHT] > 0 ||
                        right.fences()[Pen.LEFT] > 0 ||
                        left.remaining() == 2 ||
                        right.remaining() == 2) {
                    return false;
                }
            } else {
                Pen top = board.getPenAt(row - 1, col);
                Pen bottom = board.getPenAt(row, col);
                if (top.id() < 0 && bottom.id() < 0 ||
                        top.fences()[Pen.BOTTOM] > 0 ||
                        bottom.fences()[Pen.TOP] > 0 ||
                        top.remaining() == 2 ||
                        bottom.remaining() == 2) {
                    return false;
                }
            }
            return true;
        }

        private static Fence pickRandom(Board board) {
            List<Fence> ok = new ArrayList<>();
            List<Fence> notOk = new ArrayList<>();
            for (int row = 0; row < board.rows; row ++) {
                for (int col = 0; col < board.cols; col ++) {
                    (isOk(board, false, row, col) ? ok : notOk)
                            .add(new Fence(false, row, col));
                    (isOk(board, true, row, col) ? ok : notOk)
                            .add(new Fence(true, row, col));
                }
                (isOk(board, true, row, board.cols) ? ok : notOk)
                        .add(new Fence(true, row, board.cols));
            }
            for (int col = 0; col < board.cols; col ++) {
                (isOk(board, false, board.rows, col) ? ok : notOk)
                        .add(new Fence(false, board.rows, col));
            }
            if (ok.isEmpty()) {
                return notOk.get(PigPen.random(notOk.size()));
            } else {
                return ok.get(PigPen.random(ok.size()));
            }
        }

        private final boolean vertical;
        private final int row;
        private final int col;

        public Fence(boolean vertical, int row, int col) {
            super();
            this.vertical = vertical;
            this.row = row;
            this.col = col;
        }

        private Fence next(Board board, boolean negative) {
            int newRow = vertical ? (negative ? row - 1 : row + 1) : row;
            int newCol = vertical ? col : (negative ? col - 1 : col + 1);
            if (isOk(board, vertical, newRow, newCol)) {
                return new Fence(vertical, newRow, newCol);
            } else {
                return null;
            }
        }

        private int[] getResult(Board board) {
            if (vertical) {
                if (col < board.cols) {
                    return board.getPenAt(row, col).pick(Pen.LEFT);
                } else {
                    return board.getPenAt(row, col - 1).pick(Pen.RIGHT);
                }
            } else {
                if (row < board.rows) {
                    return board.getPenAt(row, col).pick(Pen.TOP);
                } else {
                    return board.getPenAt(row - 1, col).pick(Pen.BOTTOM);
                }
            }
        }
    }

    private Fence lastFence = null;
    private boolean negative = false;

    @Override
    public int[] pick(Board board, int id, int round) {
        List<Pen> money = board.getList().stream()
                .filter(p -> p.remaining() == 1).collect(Collectors.toList());
        if (!money.isEmpty()) {
            return money.get(PigPen.random(money.size())).pick(Pen.TOP);
        }
        if (lastFence != null) {
            lastFence = lastFence.next(board, negative);
        }
        if (lastFence == null) {
            lastFence = Fence.pickRandom(board);
            negative = PigPen.random(2) == 0;
        }
        return lastFence.getResult(board);
    }
}
Sleafar
quelle
Wow, gute Arbeit! LazyBones besitzt einen Finisher (siehe neue Animation).
Geokavel
Übrigens, damit jeder weiß, ist eine andere Möglichkeit, den Stift links von einem bestimmten Stift zu platzieren pen.n(Pen.LEFT)(Nachbarfunktion).
Geokavel
Ich halte es auch für unnötig, wenn Sie den unteren Zaun eines Stifts und den oberen Zaun des darunterliegenden Zauns überprüfen, denn sie haben garantiert den gleichen Wert!
Geokavel
Die pick()Methode hat jetzt einen int roundParameter am Ende, wenn Sie das also bitte hinzufügen könnten.
Geokavel
Ich muss beide Zäune überprüfen, da sich jedes der Stiftobjekte außerhalb der Tafel befinden kann (id == -1). Aus dem gleichen Grund kann ich die Nachbarfunktion nicht verwenden.
Sleafar
6

ChainCollector

Dieser Bot mag Ketten 1 . Er will so viel wie möglich von ihnen. Manchmal opfert er sogar einen kleinen Teil einer Kette, um einen größeren zu gewinnen.

[1] Eine Kette besteht aus Stiften, die durch offene Zäune verbunden sind, wobei jeder Stift 1 oder 2 offene Zäune hat. Wenn ein einzelner Stift der Kette fertiggestellt werden kann, kann aufgrund der Meisterschaftsregel auch die gesamte Kette fertiggestellt werden.

package pigpen.players;

import java.util.ArrayList;
import java.util.Collections;
import java.util.List;
import java.util.TreeMap;

import pigpen.Board;
import pigpen.Pen;
import pigpen.Player;

public class ChainCollector extends Player {
    private enum Direction {
        TOP, RIGHT, BOTTOM, LEFT;

        public Direction opposite() {
            return values()[(ordinal() + 2) % 4];
        }
    }

    private enum ChainEndType {
        OPEN, CLOSED, LOOP
    }

    private static class PenEx {
        private final int id;
        private final List<Fence> openFences = new ArrayList<>();
        private boolean used = false;

        public PenEx(int id) {
            super();
            this.id = id;
        }

        public void addOpenFence(Direction direction, PenEx child) {
            openFences.add(new Fence(this, direction, child));
            if (child != null) {
                child.openFences.add(new Fence(child, direction.opposite(), this));
            }
        }
    }

    private static class Fence {
        public final PenEx parent;
        public final Direction direction;
        public final PenEx child;

        public Fence(PenEx parent, Direction direction, PenEx child) {
            super();
            this.parent = parent;
            this.direction = direction;
            this.child = child;
        }

        public int[] getMove() {
            if (parent == null) {
                return new int[] { child.id, direction.opposite().ordinal() };
            } else {
                return new int[] { parent.id, direction.ordinal() };
            }
        }
    }

    private static class Moves {
        private final TreeMap<Integer, List<Fence>> map = new TreeMap<>();

        public void add(int score, Fence move) {
            List<Fence> list = map.get(score);
            if (list == null) {
                list = new ArrayList<>();
                map.put(score, list);
            }
            list.add(move);
        }

        public boolean isEmpty() {
            return map.isEmpty();
        }

        public boolean hasExactlyOne() {
            return map.size() == 1 && map.firstEntry().getValue().size() == 1;
        }

        public int getLowestScore() {
            return map.firstKey();
        }

        public int[] getLowMove() {
            return map.firstEntry().getValue().get(0).getMove();
        }

        public int[] getHighMove() {
            return map.lastEntry().getValue().get(0).getMove();
        }
    }

    private static class BoardEx {
        private final List<PenEx> pens = new ArrayList<>();
        private final Moves neutralMoves = new Moves();
        private final Moves finisherMoves = new Moves();
        private final Moves safeFinisherMoves = new Moves();
        private final Moves sacrificeMoves = new Moves();
        private final Moves badMoves = new Moves();

        public BoardEx(Board board) {
            super();
            PenEx[][] tmp = new PenEx[board.rows][board.cols];
            for (int row = 0; row < board.rows; ++row) {
                for (int col = 0; col < board.cols; ++col) {
                    Pen pen = board.getPenAt(row, col);
                    int[] fences = pen.fences();
                    PenEx penEx = new PenEx(pen.id());
                    tmp[row][col] = penEx;
                    pens.add(penEx);
                    if (fences[Pen.TOP] == 0) {
                        penEx.addOpenFence(Direction.TOP, row == 0 ? null : tmp[row - 1][col]);
                    }
                    if (row == board.rows - 1 && fences[Pen.BOTTOM] == 0) {
                        penEx.addOpenFence(Direction.BOTTOM, null);
                    }
                    if (fences[Pen.LEFT] == 0) {
                        penEx.addOpenFence(Direction.LEFT, col == 0 ? null : tmp[row][col - 1]);
                    }
                    if (col == board.cols - 1 && fences[Pen.RIGHT] == 0) {
                        penEx.addOpenFence(Direction.RIGHT, null);
                    }
                }
            }
        }

        private ChainEndType followChain(Fence begin, List<Fence> result) {
            Fence current = begin;
            for (;;) {
                current.parent.used = true;
                result.add(current);
                if (current.child == null) {
                    return ChainEndType.OPEN;
                }
                List<Fence> childFences = current.child.openFences;
                switch (childFences.size()) {
                    case 1:
                        current.child.used = true;
                        return ChainEndType.CLOSED;
                    case 2:
                        if (current.child == begin.parent) {
                            return ChainEndType.LOOP;
                        } else {
                            current = current.direction.opposite() == childFences.get(0).direction ?
                                    childFences.get(1) : childFences.get(0);
                        }
                        break;
                    case 3:
                    case 4:
                        return ChainEndType.OPEN;
                    default:
                        throw new IllegalStateException();
                }
            }
        }

        public void findChains() {
            for (PenEx pen : pens) {
                if (!pen.used && pen.openFences.size() > 0) {
                    if (pen.openFences.size() < 3) {
                        List<Fence> fences = new ArrayList<>();
                        ChainEndType type1 = pen.openFences.size() == 1 ?
                                ChainEndType.CLOSED : followChain(pen.openFences.get(1), fences);
                        if (type1 == ChainEndType.LOOP) {
                            badMoves.add(fences.size(), fences.get(0));
                        } else {
                            Collections.reverse(fences);
                            ChainEndType type2 = followChain(pen.openFences.get(0), fences);
                            if (type1 == ChainEndType.OPEN && type2 == ChainEndType.CLOSED) {
                                type1 = ChainEndType.CLOSED;
                                type2 = ChainEndType.OPEN;
                                Collections.reverse(fences);
                            }
                            if (type1 == ChainEndType.OPEN) {
                                badMoves.add(fences.size() - 1, fences.get(fences.size() / 2));
                            } else if (type2 == ChainEndType.CLOSED) {
                                finisherMoves.add(fences.size() + 1, fences.get(0));
                                if (fences.size() == 3) {
                                    sacrificeMoves.add(fences.size() + 1, fences.get(1));
                                } else {
                                    safeFinisherMoves.add(fences.size() + 1, fences.get(0));
                                }

                            } else {
                                finisherMoves.add(fences.size(), fences.get(0));
                                if (fences.size() == 2) {
                                    sacrificeMoves.add(fences.size(), fences.get(1));
                                } else {
                                    safeFinisherMoves.add(fences.size(), fences.get(0));
                                }
                            }
                        }
                    } else {
                        pen.used = true;
                        for (Fence fence : pen.openFences) {
                            if (fence.child == null || fence.child.openFences.size() > 2) {
                                neutralMoves.add(fence.child == null ? 0 : fence.child.openFences.size(), fence);
                            }
                        }
                    }
                }
            }
        }

        public int[] bestMove() {
            if (!neutralMoves.isEmpty()) {
                if (!finisherMoves.isEmpty()) {
                    return finisherMoves.getHighMove();
                }
                return neutralMoves.getHighMove();
            }
            if (!safeFinisherMoves.isEmpty()) {
                return safeFinisherMoves.getHighMove();
            }
            if (badMoves.isEmpty() && !finisherMoves.isEmpty()) {
                return finisherMoves.getHighMove();
            }
            if (!sacrificeMoves.isEmpty()) {
                if (sacrificeMoves.hasExactlyOne()) {
                    if (badMoves.getLowestScore() - sacrificeMoves.getLowestScore() >= 2) {
                        return sacrificeMoves.getLowMove();
                    } else {
                        return finisherMoves.getHighMove();
                    }
                } else {
                    return finisherMoves.getHighMove();
                }
            }
            if (!badMoves.isEmpty()) {
                return badMoves.getLowMove();
            }
            return null;
        }
    }

    @Override
    public int[] pick(Board board, int id, int round) {
        BoardEx boardEx = new BoardEx(board);
        boardEx.findChains();
        return boardEx.bestMove();
    }
}
Sleafar
quelle
Wow, danke für deinen Eintrag. Ich bin demütig, dass jemand so viel Zeit in ein Projekt gesteckt hat, das ich erstellt habe. Ich denke, die Einführung dieses Bots hat die Zufallszahlengenerierung beeinflusst, so dass Asdf Lazybones nun beide Male mit einem kleinen Vorsprung schlägt.
Geokavel
Nun, die Idee für den Bot sah ziemlich einfach aus, bevor ich anfing, und dann wollte ich sie beenden. ;) Mit einbezogener Zufälligkeit sollten Sie die Bots wahrscheinlich mehr als 2 Spiele spielen lassen, um genauere Ergebnisse zu erhalten.
Sleafar,
Guter Gedanke. Ich habe es auf 12 Runden pro Matchup erhöht, und jetzt hat Asdf, wie Sie sehen, einen leichten Vorteil. Selbst nach 100 Runden gewinnt es nur 13 Spiele mehr als Lazybones.
Geokavel
3

Finisher

package pigpen.players;

import pigpen.*;

import java.util.*;

/**
 * Picks a Pen with only one fence remaining. 
 * Otherwise picks one with the most fences remaining
 */
public class Finisher extends Player implements Comparator<Pen> {


  public int[] pick(Board board, int id) {
     return Collections.max(board.getList(),this).pick(Pen.TOP);

  }

  @Override
  public int compare(Pen p1, Pen p2) {
    //1 remaining is best, all remaining is second.
    int r1 = p1.remaining();
    int r2 = p2.remaining();
    if(r1 == 1) r1 = 7;
    if(r2 == 1) r2 = 7;
    return Integer.compare(r1,r2);
 }


}

Verwendet einen Komparator, um den Stift mit den meisten verfügbaren Zäunen auszuwählen. Stiften mit nur einem verfügbaren Zaun wird jedoch Vorrang eingeräumt. (7 wird anstelle von 5 verwendet, damit dieser Code auch im Hexagon-Modus funktioniert.)

Geokavel
quelle
3

Asdf

Weist jedem Zaun eine Punktzahl zu und wählt dann das Beste aus ihnen aus. Beispiel: Ein Stift mit einem offenen Zaun hat eine Punktzahl von 10, während ein Stift mit zwei offenen Zäunen eine Punktzahl von -8 hat.

Es scheint, als würde Lazybones eine ähnliche Strategie anwenden , weil sie mit diesem Bot verbunden ist.

package pigpen.players;

import java.util.*;
import pigpen.*;

public class Asdf extends Player {
    private final List<Score> scores = new ArrayList<>();

    @Override
    public int[] pick(Board board, int id, int round) {
        scores.clear();
        List<Pen> pens = board.getList();

        pens.stream().filter(x -> !x.closed()).forEach((Pen p) -> evaluate(p));
        Optional<Score> best = scores.stream().max(Comparator.comparingInt(p -> p.points));

        if (best.isPresent()) {
            Score score = best.get();
            return score.pen.pick(score.fence);
        }
        return null;
    }

    private void evaluate(Pen pen) {
        int[] fences = pen.fences();
        for (int i = 0; i < fences.length; i++) {
            if (fences[i] == 0) {
                int points = getPoints(pen);
                Pen neighbour = pen.n(i);
                if (neighbour.id() != -1) {
                    points += getPoints(neighbour);
                }
                scores.add(new Score(pen, i, points));
            }
        }
    }

    private int getPoints(Pen pen) {
        switch (pen.remaining()) {
            case 1: return 10;
            case 2: return -1;
            case 3: return 1;
        }
        return 0;
    }

    class Score {
        private Pen pen;
        private int fence;
        private int points;

        Score(Pen pen, int fence, int points) {
            this.pen = pen;
            this.fence = fence;
            this.points = points;
        }
    }
}
CommonGuy
quelle
Hier sind die Noten. Interessant ist, dass jeder Zweite doppelt so viele Punkte bekommt. Asdf vs. Lazybones: 27 - 54; Lazybones vs. Asdf: 27 - 54
Geokavel
@geokavel Ja, denn dann müssen die Bots einen "Bad Turn" machen, damit der Gegner einen Stift schließen kann.
CommonGuy
Ist das der bestmögliche Algorithmus?
Nur der halbe
@justhalf Es ist nicht, weil die Leute dieses Spiel in Meisterschaften spielen. Ich denke, diese Algorithmen können definitiv erweitert werden. Siehe die Links, die ich für weitere Informationen zur Verfügung gestellt habe.
Geokavel
0

LinearPlayer

package pigpen.players;

import pigpen.*;

/**
 * Picks the first available fence in the first available Pen
 */ 
public class LinearPlayer extends Player {


@Override
public int[] pick(Board board, int id) {
    for(int p = 1;p<=board.size;p++) {
        Pen pen = board.get(p);
            if(!pen.closed()) {
                int[] fences = pen.fences();
                    for(int i =0;i<fences.length;i++) {
                        if(fences[i] == 0) {
                            return new int[]{pen.id(),i};
                        }
                    }
                }
        }
    return new int[]{1,0};
    } 
}

Der einfachste Weg, diesen Bot zu schreiben, ist tatsächlich return null, weil ein ungültiger Eintrag automatisch den ersten verfügbaren Zaun auswählt. Dieser Code verwendet keine Verknüpfungsmethoden und generiert den Rückgabewert manuell.

Geokavel
quelle
0

BackwardPlayer

package pigpen.players;

import pigpen.*;

/**
 * Picks the first available fence in the last available Pen
 */
 public class BackwardPlayer extends Player {

public int[] pick(Board board, int id) {
    for(int i = board.size;i>0;i--) {
        Pen p = board.get(i);
        if(!p.closed()) {
            return p.pick(Pen.TOP);
        }
    }
    return new int[] {1,0};
}
}

Dieser Code verwendet die Shortcut-Methode Pen.pick(int), um den Rückgabewert zu generieren. Wenn der obere Zaun nicht verfügbar ist, wählt er den nächsten verfügbaren Zaun im Uhrzeigersinn aus.

Geokavel
quelle
0

RandomPlayer

package pigpen.players;

import pigpen.*;


/** 
 * Picks the first available fence in a random Pen 
 */
public class RandomPlayer extends Player {
    public int[] pick(Board board, int id) {
        int pen = PigPen.random(board.size)+1;
        return board.get(pen).pick(Pen.TOP);
    }
}

Entspricht dem BackwardPlayer, wählt jedoch einen Stift nach dem Zufallsprinzip aus. Beachten Sie, dass die +1Stifte 1-indiziert sind.

Geokavel
quelle