King-Pen! (Pontos e caixas)

23

Este é um desafio do tipo rei da colina para Dots and Boxes (também conhecido como Pen the Pig). O jogo é simples, por sua vez, basta desenhar uma linha em uma cerca vazia. Toda vez que você completar um quadrado, você ganha um ponto. Além disso, como jogamos de acordo com as regras do campeonato , se você completar pelo menos um quadrado no seu turno, terá um turno extra. Este é um torneio round robin, em que cada bot joga um com o outro duas vezes 12 vezes em uma grade 9x9. Confira esta partida entre dois titãs pesados, onde o ChainCollector faz carne picada do co-campeão Asdf: insira a descrição da imagem aqui

Regras

  1. 0,5 segundo limite de tempo por movimento.
  2. Não interfere com outros bots.
  3. Use PigPen.random () e PigPen.random (int) para aleatoriedade.
  4. Nenhuma gravação em arquivos.
  5. O Bot e todos os seus dados persistentes serão redefinidos toda vez que o oponente mudar (a cada 12 rodadas).

Bots

Cada bot estende o Player.java:

package pigpen;

public abstract class Player {

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

}

Boardé o tabuleiro de jogo, que serve principalmente para dar acesso às Penclasses, e idé o seu ID do jogador (informa se você é o primeiro ou o segundo), roundinforma qual rodada você joga contra o mesmo oponente (1 ou 2). O valor de retorno é um int[], onde o primeiro elemento é o penID (indexado a 1) e o segundo elemento é o fenceID (indexado a 0). VejoPen.pick(int) uma maneira fácil de gerar esse valor de retorno. Veja a página do Github para exemplo de players e JavaDoc. Como estamos usando apenas uma grade quadrada, ignore quaisquer funções e campos relacionados aos hexágonos.

Como executar

  1. Faça o download do Source do Github.
  2. Escreva o bot do seu controlador (certifique-se de incluir package pigpen.players) e coloque-o nosrc/ pasta;
  3. Compile com javac -cp src/* -d . src/*.java. Executar com java pigpen.Tournament 4 9 9 false(os dois últimos números podem ser alterados para ajustar o tamanho da grade. A última variável deve ser configurada apenas truese você desejar usar o software pp_record.)

Pontuações

  1. Coletor de Corrente: 72
  2. Asdf: 57
  3. Lazybones: 51
  4. Finalizador: 36
  5. = Jogador linear: 18
  6. = Jogador para trás: 18
  7. RandomPlayer: 0

Veja também:

Nota : este jogo é um desafio competitivo e não é facilmente solucionável, devido a dar aos jogadores um turno extra para completar uma caixa.

Agradecemos a Nathan Merrill e Darrel Hoffman pela consultoria sobre este desafio!

Atualizações :

  • Adicionado um moves(int player)método à classe Board para obter uma lista de todos os movimentos que um jogador fez.

Recompensa indefinida (100 Rep) :

Primeira pessoa a postar uma solução que vence todas as rodadas e usa estratégia (ajustando o jogo com base na observação de como o adversário joga).

geokavel
fonte
2
BONDADE. Finalizador é waaayyyy OP! : P
El'endia Starman
@ El'endiaStarman Lol, tudo o que ele faz é terminar uma caneta com uma cerca disponível, ou então escolhe uma caneta com o maior número possível de cercas. RandomPlayer é apenas aleatório.
geokavel
2
Sim, eu sei. A pontuação final é 79-2 e o RandomPlayer só conseguiu as duas últimas caixas porque era necessário. : P
El'endia Starman
Olá! Eu quero fazer meu próprio bot, mas tenho uma pergunta. Pen.BOTTOM na linha 0 col 0 retornará os mesmos valores que Pen.TOP na linha 1 col 0?
tuskiomi
@tusk Sim, é verdade
geokavel

Respostas:

6

Lazybones

Este bot é preguiçoso. Ele escolhe um ponto e direção aleatórios e continua a construir nessa direção sem se mover muito. Existem apenas 2 casos em que ele faz algo diferente:

  • "ganhar dinheiro" fechando uma estaca com apenas 1 vedação restante
  • escolha um novo local e direção se não for possível colocar a cerca ou permitir que o outro bot "ganhe dinheiro"
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
fonte
Uau, bom trabalho! LazyBones possui finalizador (veja a nova animação).
geokavel
A propósito, para que todos saibam, outra maneira de colocar a caneta à esquerda de uma caneta é pen.n(Pen.LEFT)(função vizinha).
geokavel
Além disso, acho desnecessário quando você verifica a cerca inferior de uma caneta e a cerca superior da que está abaixo dela, elas garantem o mesmo valor!
geokavel
O pick()método agora tem um int roundparâmetro no final, portanto, se você puder adicioná-lo.
geokavel
Eu tenho que verificar as duas cercas, porque qualquer um dos objetos da caneta pode estar fora do quadro (id == -1). Pela mesma razão, não posso usar a função vizinha.
Sleafar
6

ChainCollector

Este bot gosta de cadeias 1 . Ele quer o máximo deles possível. Às vezes ele até sacrifica uma pequena parte de uma corrente para ganhar uma maior.

[1] Uma corrente consiste em canetas conectadas por cercas abertas, onde cada caneta possui 1 ou 2 cercas abertas. Se uma única caneta pertencente à cadeia puder ser finalizada, por causa da regra do campeonato, toda a cadeia também poderá ser finalizada.

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
fonte
Uau, obrigado pela sua entrada. Sinto-me humilhado por alguém ter investido tanto tempo em um projeto que criei. Eu acho que a introdução desse bot afetou a geração de números aleatórios, de modo que o Asdf agora vence o Lazybones duas vezes por uma ligeira margem.
perfil completo de geokavel
Bem, a ideia para o bot parecia bem simples antes de começar, e então eu queria terminar. ;) Com a aleatoriedade envolvida, você provavelmente deve deixar os bots jogarem mais de 2 jogos para obter resultados mais precisos.
Sleafar
Bom pensamento. Aumentei para 12 rodadas por confronto e agora, como você pode ver, o Asdf tem uma ligeira vantagem. Mesmo em 100 rodadas, ele ganha apenas mais 13 jogos que o Lazybones.
geokavel
3

Finalizador

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


}

Usa um comparador para escolher a caneta com as cercas mais disponíveis, mas prioriza as caneta com apenas 1 vedação disponível. (7 é usado em vez de 5 para permitir que esse código funcione também no modo hexagonal)

geokavel
fonte
3

Asdf

Atribui uma pontuação a cada cerca e, em seguida, escolhe o melhor deles. Por exemplo: Uma caneta com uma cerca aberta tem uma pontuação de 10, enquanto uma caneta com 2 cercas abertas tem uma pontuação de -8.

Parece que Lazybones usa uma estratégia semelhante, porque está ligada a esse bot.

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
fonte
Aqui estão as pontuações. É interessante que quem fica em segundo lugar recebe o dobro de pontos. Asdf vs. Lazybones: 27 - 54; Lazybones x Asdf:
27-54
@geokavel Sim, porque os bots são forçados a fazer uma "curva ruim", para que o oponente possa fechar uma caneta.
CommonGuy
Esse é o melhor algoritmo possível, então?
justhalf
@justhalf Não é, porque as pessoas jogam esse jogo em campeonatos. Eu acho que esses algoritmos definitivamente podem ser expandidos. Veja os links que forneci para mais informações.
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};
    } 
}

A maneira mais fácil de escrever esse bot é na verdade return null, porque uma entrada inválida selecionará automaticamente a primeira cerca disponível. Este código não usa métodos de atalho e gera manualmente o valor de retorno.

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

Este código usa o método de atalho Pen.pick(int)para gerar o valor de retorno. Se a cerca superior não estiver disponível, ela escolherá a cerca disponível mais próxima no sentido horário.

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

Mesma idéia que o BackwardPlayer, mas seleciona aleatoriamente uma caneta. Observe que as +1Canetas são indexadas em 1.

geokavel
fonte