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:

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:

• Código mais rápido de pontos e caixas
• Página da Wikipédia sobre pontos e caixas

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

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

ChainCollector

Este bot gosta de cadeias ¹ . 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();
    }
}

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)

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

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.

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.

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.