King-Pen! (Точки и коробки)

23

Это испытание для Точек и Ящиков с изображением короля холма (он же Свинья). Игра проста, в свою очередь просто нарисуйте линию на пустом заборе. Каждый раз, когда вы завершаете квадрат, вы получаете очко. Кроме того, поскольку мы играем по правилам чемпионата , если вы завершите хотя бы один квадрат в свой ход, вы получите дополнительный ход. Это круговой турнир, где каждый бот играет друг друга дважды 12 раз по сетке 9x9. Проверьте этот матч между двумя титанами в супертяжелом весе, где ChainCollector делает фарш из действующего со-чемпиона Asdf: введите описание изображения здесь

правила

  1. 0,5 секунды времени за ход.
  2. Не мешать другим ботам.
  3. Используйте PigPen.random () и PigPen.random (int) для случайности.
  4. Нет записи в файлы.
  5. Бот и все его постоянные данные будут сбрасываться каждый раз при смене противника (каждые 12 раундов).

Боты

Каждый бот расширяет Player.java:

package pigpen;

public abstract class Player {

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

}

Boardявляется игровой доской, которая в основном служит для того, чтобы дать вам доступ к Penклассам, и idявляется вашим идентификатором игрока (говорит вам, если вы первый или второй), roundсообщает вам, в каком раунде вы играете против одного и того же противника (1 или 2). Возвращаемое значение - это int[], где первый элемент - это penID (1-индексированный), а второй элемент - fenceID (0-indexed). Смотрите Pen.pick(int)простой способ генерирования этого возвращаемого значения. Смотрите страницу Github для примера игроков и JavaDoc. Поскольку мы используем только квадратную сетку, игнорируем любые функции и поля, связанные с шестиугольниками.

Как запустить

  1. Скачать источник с Github.
  2. Напишите свой бот-контроллер (обязательно включите package pigpen.players) и поместите его в src/папку;
  3. Компилировать с javac -cp src/* -d . src/*.java. Выполнить с java pigpen.Tournament 4 9 9 false(последние два числа можно изменить, чтобы настроить размер сетки. Последняя переменная должна быть установлена ​​только, trueесли вы хотите использовать программное обеспечение pp_record.)

множество

  1. ChainCollector: 72
  2. Asdf: 57
  3. Ленивые: 51
  4. Финишер: 36
  5. = LinearPlayer: 18
  6. = BackwardPlayer: 18
  7. RandomPlayer: 0

Смотрите также:

Примечание : эта игра - соревновательный вызов, и ее нелегко решить из-за того, что она дает игрокам дополнительный ход для завершения бокса.

Спасибо Натану Мерриллу и Даррелу Хоффману за консультацию по этому вопросу!

Обновления :

  • Добавлен moves(int player)метод в класс Board, чтобы получить список каждого хода, который сделал игрок.

Неограниченная награда (100 представителей) :

Первый человек, который публикует решение, которое выигрывает каждый раунд и использует стратегию (корректирует игру, основываясь на наблюдении за тем, как играет противник).

geokavel
источник
2
GOODNESS. Финишер это вааайыыы ОП! : P
El'endia Starman
@ El'endiaStarman Lol, все, что он делает, заканчивает ручку с одним доступным забором, или иным образом выбирает ручку с большинством оставшихся заборов. RandomPlayer просто случайный.
геокавель
2
Да, знаю. Просто итоговый счет 79-2, и RandomPlayer получил только последние два ящика, потому что это было необходимо. : P
El'endia Starman
Здравствуйте! Я хочу сделать своего собственного бота, но у меня есть вопрос. Будет ли Pen.BOTTOM в строке 0 col 0 возвращать те же значения, что и Pen.TOP в строке 1 col 0?
Tuskiomi
@tusk Да, это так
geokavel

Ответы:

6

лентяй

Этот бот ленивый. Он выбирает случайное место и направление и продолжает строить в этом направлении, не двигаясь слишком сильно. Есть только 2 случая, когда он делает что-то другое:

  • «заработать деньги», закрыв колышек только с 1 оставшимся забором
  • выберите новое место и направление, если установка забора невозможна или позволит другому боту "заработать деньги"
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
источник
Вау, хорошая работа! LazyBones владеет финишером (см. Новую анимацию).
геокавель
Кстати, просто, чтобы все знали, еще один способ поместить перо слева от заданного пера - это pen.n(Pen.LEFT)(функция соседей).
геокавель
Кроме того, я думаю, что нет необходимости, когда вы проверяете нижний забор ручки и верхний забор того, что ниже ее, они гарантированно имеют одинаковое значение!
геокавель
У pick()метода теперь есть int roundпараметр в конце, поэтому, пожалуйста, добавьте его.
геокавель
Я должен проверить оба забора, потому что любой из объектов пера может быть вне доски (id == -1). По той же причине я не могу использовать функцию соседа.
Sleafar
6

ChainCollector

Этот бот любит цепочки 1 . Он хочет как можно больше из них. Иногда он даже жертвует маленькой частью цепи, чтобы выиграть большую.

[1] Цепочка состоит из ручек, соединенных открытыми заборами, где каждая ручка имеет 1 или 2 открытых забора. Если можно закончить одну ручку, принадлежащую цепочке, то из-за правила чемпионата можно закончить и всю цепочку.

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
источник
Вау, спасибо за вашу запись. Я смирился, что кто-то вложил так много времени в проект, который я создал. Я думаю, что введение этого бота повлияло на генерацию случайных чисел, так что теперь Asdf с небольшим отрывом побеждает Lazybones оба раза.
геокавель
Ну, идея для бота выглядела довольно простой до того, как я начал, а затем я хотел закончить это. ;) Учитывая случайность, вы, вероятно, должны позволить ботам играть более чем в 2 игры, чтобы получить более точные результаты.
Sleafar
Хорошая мысль. Я увеличил его до 12 раундов за матч, и теперь, как вы видите, Asdf имеет небольшое преимущество. Даже в 100 раундах он выигрывает только на 13 игр больше, чем Lazybones.
геокавель
3

финишер

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


}

Использует Comparator, чтобы выбрать ручку с большинством доступных заборов, но отдает приоритет ручкам с только 1 доступным забором. (7 используется вместо 5, чтобы этот код работал и в режиме шестиугольника)

geokavel
источник
3

Asdf

Назначает оценку каждому забору и затем выбирает лучшее из них. Например: ручка с одним открытым забором имеет 10 баллов, а ручка с 2 открытыми заборами - 8 баллов.

Кажется, что Lazybones использует похожую стратегию, потому что это связано с этим ботом.

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
источник
Вот результаты. Интересно, что тот, кто идет вторым, получает в два раза больше очков. Асдф против Ленивых: 27 - 54; Ленивые против Асдфа: 27 - 54
геокавель
@geokavel Да, потому что тогда боты вынуждены делать «плохой ход», поэтому противник может закрыть ручку.
CommonGuy
Тогда это лучший алгоритм?
полугодие
@justhalf Это не так, потому что люди играют в эту игру на чемпионатах. Я думаю, что эти алгоритмы могут быть расширены. Смотрите ссылки, которые я предоставил для получения дополнительной информации.
геокавель
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};
    } 
}

На самом деле проще всего написать этого бота return null, потому что неверная запись автоматически выберет первый доступный забор. Этот код не использует ярлыки и вручную генерирует возвращаемое значение.

geokavel
источник
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};
}
}

Этот код использует метод ярлыка Pen.pick(int)для генерации возвращаемого значения. Если верхний забор недоступен, он выберет ближайший забор, идущий по часовой стрелке.

geokavel
источник
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);
    }
}

Та же идея, что и у BackwardPlayer, но случайным образом выбирается перо. Обратите внимание, +1потому что Pen's 1-indexed.

geokavel
источник