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:

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:

• Der schnellste Code für Punkte und Kästchen
• Punkte und Kästchen Wikipedia-Seite

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

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

ChainCollector

Dieser Bot mag Ketten ¹ . 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();
    }
}

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

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

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.

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.

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.