KOTH assimétrico: pegue o gato (linha do apanhador)

17

KOTH assimétrico: pegue o gato

ATUALIZAÇÃO : Os arquivos gist são atualizados (incluindo novas submissões), pois o Controller.java não capturou Exceções (apenas erros). Agora ele captura erros e exceções e também os imprime.

Este desafio consiste em duas linhas, esta é a linha de captura, a linha de gato pode ser encontrada aqui .

O controlador pode ser baixado aqui .

Este é um KOTH assimétrico: Cada envio é um gato ou um coletor . Existem jogos entre cada par de gato e apanhador. Os gatos e os coletores têm classificações separadas.

Apanhador

Há um gato em uma grade hexagonal. Sua tarefa é capturá-lo o mais rápido possível. A cada turno, você pode colocar um balde de água em uma célula da grade para impedir que o gato possa ir para lá. Mas o gato não é (talvez) tão burro, e sempre que você coloca um balde, ele se move para outra célula da grade. Como a grade é hexagonal, o gato pode ir em 6 direções diferentes. Seu objetivo é cercar o gato com baldes de água, quanto mais rápido, melhor.

Gato

Você sabe que o apanhador quer pegá-lo colocando baldes de água ao seu redor. Claro que você tenta fugir, mas como você é um gato preguiçoso (como os gatos), você dá exatamente um passo de cada vez. Isso significa que você não pode ficar no mesmo lugar que você, mas você precisa se mudar para um dos seis pontos circundantes. Sempre que vir que o apanhador colocou um novo balde de água, você vai para outra célula. Claro que você tenta fugir o maior tempo possível.

Rede

A grade é hexagonal, mas como não temos estruturas de dados hexagonais, pegamos uma 11 x 11matriz quadrada em 2d e imitamos o 'comportamento' hexagonal de que o gato só pode se mover em 6 direções:

insira a descrição da imagem aqui

A topologia é toroidal, ou seja, se você pisar em uma célula 'fora' da matriz, você será transferido para a célula correspondente do outro lado da matriz.

jogos

O gato começa em uma determinada posição na grade. O apanhador pode fazer o primeiro movimento, depois o gato e seu apanhador se movem alternadamente até o gato ser pego. O número de etapas é a pontuação para esse jogo. O gato tenta obter uma pontuação o melhor possível, o apanhador tenta obter uma pontuação o mais baixa possível. A soma média de todos os jogos em que você participou será a pontuação do seu envio. Existem dois rankings separados, um para o gato e outro para os coletores.

Controlador

O controlador fornecido é escrito em Java. Como apanhador ou gato, cada um de vocês precisa implementar uma classe Java (já existem alguns exemplos primitivos) e colocá-la no playerspacote (e atualizar a lista de gatos / apanhadores na classe Controller), mas você também pode escrever funções adicionais dentro dessa classe. O controlador vem com cada dois exemplos de trabalho de classes simples de gatos / coletores.

O campo é uma matriz 11 x 112D intque armazena os valores dos estados atuais das células. Se uma célula estiver vazia, ela terá valor 0, se houver um gato, ela terá valor -1e, se houver um balde, haverá a 1.

Existem algumas funções que você pode usar: isValidMove()/ serve isValidPosition()para verificar se a sua jogada (gato) / posição (apanhador) é válida.

Cada vez que é a sua vez, sua função takeTurn()é chamada. O argumento contém uma cópia da grade atual e métodos como read(i,j)para ler a célula em (i,j), além de isValidMove()/ isValidPosition()verificar a validade de sua resposta. Isso também gerencia o encapsulamento da topologia toroidal, ou seja, mesmo que a grade seja apenas 11 x 11, você ainda pode acessar a célula (-5,13).

O método deve retornar uma intmatriz de dois elementos, que representam possíveis movimentos. Para os gatos, estes são os {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}que representam a posição relativa de onde o gato quer ir, e os coletores retornam as coordenadas absolutas de onde querem colocar um balde {i,j}.

Se seu método produzir uma movimentação inválida, seu envio será desqualificado. A movimentação é considerada inválida, se o seu destino já for um depósito ou a movimentação não for permitida / destino já ocupado (como um gato) ou se já houver um depósito / gato (como um coletor). Você pode verificar isso antes com as funções fornecidas.

Seu envio deve funcionar razoavelmente rápido. Se o seu método demorar mais de 200 ms para cada etapa, ele também será desqualificado. (De preferência muito menos ...)

Os programas têm permissão para armazenar informações entre as etapas.

Submissões

  • Você pode fazer quantos envios quiser.
  • Não altere significativamente os envios que você já enviou.
  • Por favor, cada envio em uma nova resposta.
  • Cada envio deve preferencialmente ter seu nome exclusivo.
  • O envio deve consistir no código da sua turma, bem como uma descrição que nos diga como o seu envio funciona.
  • Você pode escrever a linha <!-- language: lang-java -->antes do código fonte para obter o realce automático da sintaxe.

Pontuação

Todos os gatos competirão contra todos os coletores no mesmo número de vezes. Vou tentar atualizar as pontuações atuais com frequência, os vencedores serão determinados quando a atividade diminuir.

Este desafio é inspirado neste jogo flash antigo

Agradecemos à @PhiNotPi por testar e fornecer alguns comentários construtivos.

Pontuações atuais (100 jogos por emparelhamento)

Name              Score      Rank   Author

RandCatcher       191674     8      flawr   
StupidFill        214246     9      flawr
Achilles          76820      6      The E
Agamemnon         74844      5      The E
CloseCatcher      54920      4      randomra
ForwordCatcher    94246      7      MegaTom  
Dijkstra          46500      2      TheNumberOne
HexCatcher        48832      3      randomra
ChoiceCatcher     43828      1      randomra

RandCat           77928      7      flawr
StupidRightCat    81794      6      flawr
SpiralCat         93868      5      CoolGuy
StraightCat       82452      9      CoolGuy
FreeCat           106304     3      randomra
RabidCat          77770      8      cain
Dijkstra's Cat    114670     1      TheNumberOne
MaxCat            97768      4      Manu
ChoiceCat         113356     2      randomra
flawr
fonte
Que programa faz as animações?
MegaTom 02/06/2015
A animação é apenas a GUI (ao iniciar o controlador, é necessário definir configurações PRINT_STEPS = truemais detalhadas no arquivo MyFrame.java). Então gravei isso no LICEcap e editei no GIMP . Se você tiver mais perguntas, basta perguntar!
flawr
Se você adicionar a entrada do usuário ao controlador, ele poderá criar um bom software com a GUI e os bots já gravados. Também seria interessante ver quanto os seres humanos podem quebrar / abusar das estratégias específicas de bots.
randomra
Além disso, meu bot pode manter as informações da partida anterior para tentar encontrar uma melhor sequência de movimentos contra o mesmo bot? Suponho que não, porque fica melhor quanto mais rodadas você faz. Também teria que adivinhar se está jogando contra um novo bot, para que a ordem de execução também importe.
randomra
11
Por que a pontuação dos gatos não está ordenada?
Spikatrix

Respostas:

6

Aquiles

Aquiles não é muito inteligente, mas ele é implacavelmente eficiente. Primeiro, ele impede que o gato use o envoltório do tabuleiro e depois divide o tabuleiro em dois. Então ele continua dividindo a parte do tabuleiro em que o gato está dividido ao meio até que ele fique preso.

Demonstração RandCat vs Achilles

randcat vs achilles

package players;
/**
 * @author The E
 */
import main.*;



public class Achilles implements Catcher
{
    public Achilles() {

    }
    @Override
    public String getName() {

        return "Achilles";
    }

    @Override
    public int[] takeTurn(Field f) {
        try{
        if(f.read(0, f.SIZE-1)!=Field.BUCKET)
        {
            //Make the first line

            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j) == Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            return WasteGo(f);

        }
        else if (f.read(f.SIZE-1, 0)!=Field.BUCKET)
        {
            //Make the second line
            for(int i = 0; i<f.SIZE; i++)
            {
                if(f.read(i, 0) == Field.EMPTY)
                {
                    return new int[]{i,0};
                }
            }
            //The cat got in the way
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(1, j) == Field.EMPTY)
                {
                    return new int[]{1,j};
                }
            }
            return WasteGo(f);
        }
        else
        {
            return TrapCat(1,1,f.SIZE-1, f.SIZE-1, false, f);

        }
        }
        catch (Exception e)
        {
            return WasteGo(f);
        }
    }
    private int[] TrapCat(int i1, int j1, int i2, int j2, Boolean direction, Field f) {
        for(int a = 0; a<f.SIZE+10; a++)
        {
            if(direction)
            {

                int height = j2-j1+1;
                int row = j1 + height/2;
                for(int i = i1; i<=i2; i++)
                {
                    if(f.read(i, row)==Field.EMPTY)
                    {
                        return new int[]{i,row};
                    }
                }

                    //Done that Row
                    //Find cat
                    if(f.findCat()[1]>row)
                    {
                        //he's above the line
                        j1 = row+1;
                        direction = !direction;
                        //return TrapCat(i1, row+1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's below the line
                        j2 = row - 1;
                        direction = !direction;
                        //return TrapCat(i1, j1, i2, row-1, !direction, f);
                    }


            }
            else
            {
                int bredth = i2-i1+1;
                int column = i1 + bredth/2;
                //Continue making the line
                for(int j = j1; j<=j2; j++)
                {
                    if(f.read(column,j)==Field.EMPTY)
                    {
                        return new int[]{column,j};
                    }
                }

                    //Done that Column
                    //Find cat
                    if(f.findCat()[0]>column)
                    {
                        //he's right of the line
                        i1 = column + 1;
                        direction = !direction;
                        //return TrapCat(column+1, j1, i2, j2, !direction, f);
                    }
                    else
                    {
                        //he's left of the line
                        i2 = column -1;
                        direction = !direction;
                        //return TrapCat(i1, j1, column-1, j2, !direction, f);
                    }

            }
        }
        return WasteGo(f);
    }
    private int[] WasteGo(Field f) {
        for (int i = 0; i<f.SIZE;i++)
        {
            for(int j=0;j<f.SIZE;j++)
            {
                if(f.read(i,j)==Field.EMPTY)
                {
                    return new int[]{i,j};
                }
            }
        }
        //Something drastic happened
        return new int[]{0,0};
    }



}
euanjt
fonte
Bem, qual é agora, Aquiles ou Hector? (Ou alguém com um transtorno de identidade dissiociative =?)
flawr
@flawr Achilles, lol Eu mudei o nome no meio do caminho (é mais adequado nomear o apanhador de Aquiles e o gato Hector), mas esqueci de mudar o java - é o que acontece quando você programa depois do chá :(
euanjt
Mas Hector prefere ser um nome de cachorro =) Obrigado pela sua apresentação. Espero que você não se importe de incluir também o 'preâmbulo' no seu código.
Flawr 30/05
Sim, não há problema. Hector soa como o nome de um cachorro ...
euanjt 30/05
Acabei de executar uma simulação (10000 jogos para cada emparelhamento) e o Achilles foi desclassificado, devido ao StackOverflowError repetido. Eu acho que a recursividade não terminou: pastebin.com/9n6SQQnd
flawr
5

Agamenon

Agamenon divide a área dos gatos ao meio com uma linha vertical até que o gato tenha apenas uma faixa de largura 2 para se mover, e nesse ponto ele prende o gato.

Agamemnon vs RandCat:

insira a descrição da imagem aqui

package players;
/**
 * @author The E
 */
import main.*;



    public class Agamemnon implements Catcher {
        boolean up = true;
        @Override
        public String getName() {
            return "Agamemnon";
        }

        @Override
        public int[] takeTurn(Field f) {
            //First Make Line in column 1
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(0, j)==Field.EMPTY)
                {
                    return new int[]{0,j};
                }
            }
            //Then in column SIZE/2
            for(int j = 0; j<f.SIZE; j++)
            {
                if(f.read(f.SIZE/2, j)==Field.EMPTY)
                {
                    return new int[]{f.SIZE/2,j};
                }
            }
            //Then work out where the cat is
            int left, right;
            int cati = f.findCat()[0];
            if(cati<f.SIZE/2)
            {
                left = 1;
                right = f.SIZE/2-1;
            }
            else
            {
                left = f.SIZE/2+1;
                right = f.SIZE-1;
            }
            while(right-left>1)
            {
                //If the cat is not in a two width column
                //Split the area the cat is in in half
                int middleColumn = (left+right)/2;
                for(int j = 0; j<f.SIZE; j++)
                {
                    if(f.read(middleColumn, j)==Field.EMPTY)
                    {
                        return new int[]{middleColumn,j};
                    }
                }
                //If we got here we had finished that column
                //So update left and/or right
                if(cati<middleColumn)
                {
                    //he's left of the middle Column
                    right = middleColumn - 1;
                }
                else
                {
                    //he's right of the middle Column
                    left = middleColumn+1;
                }
                //Repeat
            }
            //Otherwise try to trap the cat
            //Make a line up and down on the opposite side of the cat
            int catj = f.findCat()[1];
            if(left!=right){
                if(cati==left)
                {
                    if(f.read(right, catj)==Field.EMPTY)
                    {
                        return new int[]{right, catj};
                    }
                    if(f.read(right, catj-1)==Field.EMPTY)
                    {
                        return new int[]{right, catj-1};
                    }
                    if(f.read(right, catj+1)==Field.EMPTY)
                    {
                        return new int[]{right, catj+1};
                    }


                }
                else
                {
                    if(f.read(left, catj)==Field.EMPTY)
                    {
                        return new int[]{left, catj};
                    }
                    if(f.read(left, catj-1)==Field.EMPTY)
                    {
                        return new int[]{left, catj-1};
                    }
                    if(f.read(left, catj+1)==Field.EMPTY)
                    {
                        return new int[]{left, catj+1};
                    }

                }
            }
            //Alternate between above and below
            if(up)
            {
                up = !up;
                if(f.read(cati, catj+1)==Field.EMPTY)
                {

                    return new int[]{cati, catj+1};
                }
            }
            up = !up;
            if(f.read(cati, catj-1)==Field.EMPTY)
            {

                return new int[]{cati, catj-1};
            }
            return WasteGo(f);
        }

        private int[] WasteGo(Field f) {
            for (int i = 0; i<f.SIZE;i++)
            {
                for(int j=0;j<f.SIZE;j++)
                {
                    if(f.read(i,j)==Field.EMPTY)
                    {
                        return new int[]{i,j};
                    }
                }
            }
            //Something drastic happened
            return new int[]{0,0};
        }
    }

Esse apanhador é consistentemente melhor que Aquiles e acho que ele é diferente o suficiente para justificar uma nova resposta.

euanjt
fonte
Very nice solução, eu tinha certeza de que Aquiles estava perto de ideal, mas agora eu acho que até Agamenon poderia ser melhorado ligeiramente =)
flawr
Sim, Agamenon tem uma muito melhor jogo final prendendo algoritmo de Aquiles, mas eu tenho certeza que existem alguns ajustes ... Agora eu vou tentar e trabalhar em um gato :)
euanjt
@flawr muito pequeno ajuste adicional para acelerar a captura em alguns casos especiais, isso não afeta a animação aqui (elthough Eu acho que poderia afetar a animação do SpiralCat)
euanjt
Questão! O que acontece se você está prestes a fechar uma linha, mas o gato está de pé no último ponto?
Llama
@ Mr.Llama, ele começa a fazer a próxima linha como se essa linha tivesse sido preenchida (ou seja, o gato era de fato um balde) - não é o uso mais eficaz de um turno, mas acontece muito raramente que isso realmente não importa. gato tem que, em seguida, afastar-se de seu próximo turno para que eu possa colocar meu balde lá
euanjt
5

HexCatcher

Se o apanhador conseguir colocar o gato dentro de um grande hexágono com 3 unidades laterais, onde os cantos do hexágono já estão ocupados por baldes, o apanhador pode manter o gato nessa área e pegá-lo. O hexágono fica assim:

insira a descrição da imagem aqui

É isso que o HexCatcher tenta alcançar. Ele mentalmente ladrilha o campo com esses grandes hexágonos de maneira que cada célula de canto faça parte de três grandes hexágonos.

Se houver uma chance de manter o gato na área atual conectando dois cantos ao lado do gato, o bot fará isso. (Por exemplo, na imagem, se o gato estiver em 7,5, escolhemos 7,6, mesmo que apenas as células 6,6 e 8,5 ainda estejam ocupadas.)

Se o anterior não for uma opção, escolhemos tocar um canto que faz parte da área onde o gato está. Se todos esses cantos já tiverem sido escolhidos (como na imagem), escolhemos uma célula ao lado do gato.

São possíveis vários pequenos aprimoramentos, como lidar melhor com o acondicionamento (o lado a lado é quebrado) ou fazer o último par de movimentos otimizados. Eu posso fazer algumas delas. Se não for permitido, apenas o anexarei (fora de competição) aos interessados.

DijkstrasCat vs HexCatcher:

insira a descrição da imagem aqui

package players;
/**
 * @author randomra
 */
import main.Field;

public class HexCatcher implements Catcher {
    public String getName() {
        return "HexCatcher";
    }

    final int[][] o = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 }, { 0, -1 },
            { 1, -1 } };// all valid moves
    final int[][] t = { { -2, 2 }, { 0, 2 }, { -2, 0 }, { 2, 0 }, { 0, -2 },
            { 2, -2 } };// all valid double moves in one direction
    final int[][] h = { { -1, 2 }, { -2, 1 }, { -1, -1 }, { 1, -2 }, { 2, -1 },
            { 1, 1 } };// all valid moves in not one direction
    int opp = 0;

    public int[] takeTurn(Field f) {
        int[] p = f.findCat();
        // center of the hexagon the cat is in
        int[] c = { ((int) p[0] / 3) * 3 + 1, ((int) p[1] / 3) * 3 + 1 };
        // change priority of catching direction at every turn
        opp = 1 - opp;

        // check missing corner piece next to cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            boolean close = false;
            for (int k = 0; k < 6; k++) {
                if (c[0] + h[ind][0] == p[0] + o[k][0]
                        && c[1] + h[ind][1] == p[1] + o[k][1]) {
                    close = true;
                }
            }
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0 && close) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // cut off escape route if needed
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + o[ind][0], c[1] + o[ind][1]) == -1
                    && f.read(c[0] + t[ind][0], c[1] + t[ind][1]) == 0) {
                return new int[] { c[0] + t[ind][0], c[1] + t[ind][1] };
            }
        }
        // check any missing corner piece in the area
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(c[0] + h[ind][0], c[1] + h[ind][1]) == 0) {
                return new int[] { c[0] + h[ind][0], c[1] + h[ind][1] };
            }
        }
        // choose an empty cell next to the cat
        for (int i = 0; i < 6; i++) {
            int ind = (i + opp * 3) % 6;
            if (f.read(p[0] + o[ind][0], p[1] + o[ind][1]) == 0) {
                return new int[] { p[0] + o[ind][0], p[1] + o[ind][1] };
            }
        }
        return null;
    }
}
randomra
fonte
3

CloseCatcher

Escolhe uma das posições em que o gato pode pisar na próxima etapa. Ele escolhe aquele que daria os caminhos mais possíveis após 3 etapas para o gato se ele se mudasse para lá e o campo não mudasse.

O código é quase idêntico à minha entrada Cat, FreeCat , que escolhe a direção de uma maneira muito semelhante.

SpiralCat vs CloseCatcher:

SpiralCat vs CloseCatcher

package players;
/**
 * @author randomra
 */

import main.Field;
import java.util.Arrays;

public class CloseCatcher implements Catcher {
    public String getName() {
        return "CloseCatcher";
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { -1, 0 }, { 1, 0 },
            { 0, -1 }, { 1, -1 } };// all valid moves
    final int turnCheck = 3;

    public int[] takeTurn(Field f) {

        int[] pos = f.findCat();
        int[] bestMove = { 0, 1 };
        int bestMoveCount = -1;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            int moveCount = free_count(currPos, turnCheck, f);
            if (moveCount > bestMoveCount) {
                bestMoveCount = moveCount;
                bestMove = t;
            }
        }
        int[] bestPos = { pos[0] + bestMove[0], pos[1] + bestMove[1] };
        return bestPos;
    }

    private int free_count(int[] pos, int turnsLeft, Field f) {
        if (f.isValidPosition(pos) || Arrays.equals(pos, f.findCat())) {
            if (turnsLeft == 0) {
                return 1;
            }
            int routeCount = 0;
            for (int[] t : turns) {
                int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
                int moveCount = free_count(currPos, turnsLeft - 1, f);
                routeCount += moveCount;
            }
            return routeCount;
        }
        return 0;
    }

}
randomra
fonte
Nice +1. CloseCatcher capta facilmente StraightCat
Spikatrix
3

Dijkstra

Ele não gosta muito de gatos (:v{ >

FreeCat vs Dijkstra (necessidades atualizadas) :

insira a descrição da imagem aqui

package players;

import main.Controller;
import main.Field;

import java.util.*;

/**
 * @author TheNumberOne
 *
 * Catches the cat.
 */

public class Dijkstra implements Catcher{

    private static final int[][][] CACHE;

    static {
        CACHE = new int[Controller.FIELD_SIZE][Controller.FIELD_SIZE][2];
        for (int x = 0; x < Controller.FIELD_SIZE; x++){
            for (int y = 0; y < Controller.FIELD_SIZE; y++){
                CACHE[x][y] = new int[]{x,y};
            }
        }
    }

    private static final int[][] possibleMoves = {{-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}};
    @Override
    public String getName() {
        return "Dijkstra";
    }

    @Override
    public int[] takeTurn(Field f) {
        long startTime = System.nanoTime();

        final int[] theCat = f.findCat();
        int[] bestMove = {-1,1};
        int[] bestOpenness = {Integer.MAX_VALUE, 0};
        List<int[]> possiblePositions = new ArrayList<>();
        for (int x = 0; x < 11; x++){
            for (int y = 0; y < 11; y++){
                int[] pos = {x,y};
                if (f.isValidPosition(pos)){
                    possiblePositions.add(pos);
                }
            }
        }
        Collections.sort(possiblePositions, new Comparator<int[]>() {
            @Override
            public int compare(int[] o1, int[] o2) {
                return distance(o1, theCat) - distance(o2, theCat);
            }
        });
        for (int i = 0; i < possiblePositions.size() && System.nanoTime() - startTime < Controller.MAX_TURN_TIME/2; i++){
            int[] pos = possiblePositions.get(i);
            int before = f.field[pos[0]][pos[1]];
            f.placeBucket(pos);
            int[] openness = openness(theCat, f, true);
            if (openness[0] < bestOpenness[0] ||
                    (openness[0] == bestOpenness[0] &&
                            (openness[1] > bestOpenness[1])
                    )
                    ){
                bestOpenness = openness;
                bestMove = pos;
            }
            f.field[pos[0]][pos[1]] = before;
        }
        return bestMove;
    }


    /**
     *
     * @param pos The pos to calculate the openness of.
     * @param f The field to use.
     * @return Two integers. The first integer represents the number of reachable hexagons.
     * The second integer represents how strung out the squares are relative to the pos.
     */
    public static int[] openness(int[] pos, Field f, boolean catZeroWeight){
        Map<int[], Integer> lengths = new HashMap<>();
        PriorityQueue<int[]> open = new PriorityQueue<>(10,new Comparator<int[]>() {
            Map<int[], Integer> lengths;
            @Override
            public int compare(int[] o1, int[] o2) {
                return lengths.get(o1) - lengths.get(o2);
            }
            public Comparator<int[]> init(Map<int[], Integer> lengths){
                this.lengths = lengths;
                return this;
            }
        }.init(lengths));
        Set<int[]> closed = new HashSet<>();
        lengths.put(pos, catZeroWeight ? 0 : 6 - pointsAround(pos, f).size());
        open.add(pos);
        while (open.size() > 0){
            int[] top = open.remove();
            if (closed.contains(top)){
                continue;
            }
            closed.add(top);
            int l = lengths.get(top);
            List<int[]> pointsAround = pointsAround(top, f);

            for (ListIterator<int[]> iter = pointsAround.listIterator(); iter.hasNext();){
                int[] point = iter.next();
                if (closed.contains(point)){
                    iter.remove();
                }
            }

            for (int[] p : pointsAround){
                int length = l + 7 - pointsAround(p, f).size();
                if (lengths.containsKey(p)){
                    length = Math.min(length, lengths.get(p));
                }
                lengths.put(p, length);
                open.add(p);
            }
        }
        int sum = 0;
        for (int integer : lengths.values()){
            sum += integer;
        }
        return new int[]{lengths.size(),sum};
    }

    public static int distance(int[] p1, int[] p2){
        p2 = Arrays.copyOf(p2, 2);
        while (p2[0] < p1[0]){
            p2[0] += 11;
        }
        while (p2[1] < p2[0]){
            p2[1] += 11;
        }
        int lowestDistance = 0;
        for (int dx = 0; dx == 0; dx -= 11){
            for (int dy = 0; dy == 0; dy -= 11){
                lowestDistance = Math.min(lowestDistance,Math.min(Math.abs(p1[0]-p2[0]-dx),Math.min(Math.abs(p1[1]-p2[1]-dy),Math.abs(p1[0]+p1[1]-p2[0]-dx-p2[1]-dy))));
            }
        }
        return Math.min(Math.abs(p1[0]-p2[0]),Math.min(Math.abs(p1[1]-p2[1]),Math.abs(p1[0]+p1[1]-p2[0]-p2[1])));
    }

    public static int[] normalize(int[] p){
        return CACHE[(p[0]%11+11)%11][(p[1]%11+11)%11];
    }

    public static List<int[]> pointsAround(int[] p, Field f){
        int[] cat = f.findCat();
        List<int[]> locations = new ArrayList<>();
        for (int[] move : possibleMoves){
            int[] location = normalize(new int[]{p[0]+move[0], p[1] + move[1]});
            if (f.isValidPosition(location) || Arrays.equals(cat, location)){
                locations.add(location);
            }
        }
        return locations;
    }
}

Como ele tenta pegar o gato:

Ele analisa todos os quadrados do quadro e tenta encontrar o quadrado que minimiza a abertura do quadro e maximiza o quanto o quadro é esticado; em relação ao gato. A abertura e rigidez de uma placa são calculadas usando uma modificação de seu famoso algoritmo .

Abertura:

A abertura de uma placa em relação a uma posição é o número de posições alcançáveis ​​a partir dessa posição.

Rigidez:

A rigidez de uma placa em relação a uma posição é a soma das distâncias entre as posições alcançáveis ​​e a posição.

Com a última atualização:

Agora, ele é muito melhor em pegar o FreeCat e seu próprio gato, todos os gatos. Infelizmente, ele também é muito pior em capturar os gatos loucos que não cooperam. Ele poderia ser melhorado, detectando se o gato é um dos loucos e depois atuando como CloseCatcher.

Erro corrigido.

O número um
fonte
Posso confirmar que funciona até agora, mas de longe o mais lento, mas um dos melhores até agora, eu acho. Precisa de 134 segundos para 100 jogos contra o RandCat enquanto realiza um total de apenas 4406 jogadas! Eu acho que vou ter que deixar meu PC rodar durante a noite em um dos próximos dias ... Você pode nos contar um pouco mais sobre como ele funciona?
achou
@flawr Adicionou uma descrição.
TheNumberOne
Ainda não funciona para mim. Dá-me um erro: error: cannot infer type arguments for PriorityQueue<>nesta linha PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.
Spikatrix 3/15
@CoolGuy Você está usando o java 6? Eu acho que você precisa atualizar seu JDK.
TheNumberOne
@CoolGuy Você também pode colocar um int[]entre os dois diamantes vazios depois PriorityQueue.
TheNumberOne
2

ForwordCatcher

Coloca um balde na frente do gato, ou, se for levado, coloca atrás.

RabidCat vs ForwordCatcher:

RabidCat vs ForwordCatcher:

package players;

import main.Field;
import java.util.Arrays;

public class ForwordCatcher implements Catcher {
    public String getName() {
        return "ForwordCatcher";
    }

    private int[] lastPos = {0,0};

    public int[] takeTurn(Field f) {
        int[] temp = lastPos;
        int[] pos = f.findCat();
        lastPos = pos;
        int[] Move = {pos[0]*2-temp[0], pos[1]*2-temp[1]};
        if(f.isValidPosition(Move)){return Move;}
        if(f.isValidPosition(temp)){return temp;}
        Move[0] = pos[0];Move[1] = pos[1]+1;
        return Move;
    }
}
MegaTom
fonte
11
Existem alguns erros, o que me levou a supor que você não testou seu programa. Corrija os ...
flawr
@flawr fixed. desculpe pelos erros. Eu não testei e meu Java não é bom.
MegaTom 01/06/2015
Bom, até agora tudo corre smoothely, mas ainda não tenho certeza se ele sempre irá produzir movimentos válidos =)
flawr
11
@flawr O espaço atrás de um gato vai sempre estar vazio para o apanhador :)
TheNumberOne
2

ChoiceCatcher

Usa o mesmo mecanismo de pontuação da minha entrada ChoiceCat . Há uma pequena modificação que ajuda a escolher células relevantes nas primeiras etapas, pois o ChoiceCat não se importa com os primeiros baldes, pois não os vê como ameaça.

O ChoiceCatcher parece ter uma pontuação consideravelmente melhor do que os atuais coletores.

ChoiceCat vs ChoiceCatcher:

ChoiceCat vs ChoiceCatcher

package players;
/**
 * @author randomra
 */
import java.util.Arrays;

import main.Field;

public class ChoiceCatcher implements Catcher {

    private class Values {
        public final int size;
        private double[][] f;

        Values(int size) {
            this.size = size;
            f = new double[size][size];
        }

        public double read(int[] p) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j];
        }

        private double write(int[] p, double v) {
            int i = p[0];
            int j = p[1];
            i = (i % size + size) % size;
            j = (j % size + size) % size;
            return f[i][j] = v;
        }
    }

    final int[][] turns = { { -1, 1 }, { 0, 1 }, { 1, 0 }, { 1, -1 },
            { 0, -1 }, { -1, 0 } };// all valid moves CW order
    final int stepCheck = 5;

    public String getName() {
        return "ChoiceCatcher";
    }

    @Override
    public int[] takeTurn(Field f) {
        int[] bestPos = null;
        double bestPosValue = Double.MAX_VALUE;
        for (int i = 0; i < f.SIZE; i++) {
            for (int j = 0; j < f.SIZE; j++) {
                if (f.read(i, j) == Field.EMPTY) {
                    Field myField = new Field(f);
                    myField.placeBucket(new int[] { i, j });
                    double posValue = catTurnValue(myField);
                    if (posValue < bestPosValue) {
                        bestPosValue = posValue;
                        bestPos = new int[] { i, j };
                    }
                }
            }
        }
        return bestPos;
    }

    private double catTurnValue(Field f) {

        int[] pos = f.findCat();
        double[] values = new double[6];
        int count=0;
        for (int[] t : turns) {
            int[] currPos = { pos[0] + t[0], pos[1] + t[1] };
            double moveValue = movePosValue(currPos, f);
            values[count++]=moveValue;
        }
        Arrays.sort(values);
        return values[5];
    }

    private double movePosValue(int[] pos, Field f) {

        Values v = new Values(f.SIZE);

        for (int ring = stepCheck; ring >= 0; ring--) {
            for (int phase = 0; phase < 2; phase++) {
                for (int sidepos = 0; sidepos < Math.max(1, ring); sidepos++) {
                    for (int side = 0; side < 6; side++) {
                        int[] evalPos = new int[2];
                        for (int coord = 0; coord < 2; coord++) {
                            evalPos[coord] = pos[coord] + turns[side][coord]
                                    * sidepos + turns[(side + 1) % 6][coord]
                                    * (ring - sidepos);
                        }
                        if (phase == 0) {
                            if (ring == stepCheck) {
                                // on outmost ring, init value
                                v.write(evalPos, -1);
                            } else {
                                v.write(evalPos, posValue(evalPos, v, f));
                            }
                        } else {
                            // finalize position value for next turn
                            v.write(evalPos, -v.read(evalPos));
                        }
                    }
                }
            }
        }

        return -v.read(pos);
    }

    private double posValue(int[] pos, Values v, Field f) {
        if (f.read(pos[0], pos[1]) == Field.BUCKET) {
            return 0;
        }
        int count = 0;
        int maxRoutes = 2;
        double[] product = new double[6];
        for (int[] t : turns) {
            int[] tPos = new int[] { pos[0] + t[0], pos[1] + t[1] };
            if (v.read(tPos) > 0) {
                product[count] = 1 - 1 / (v.read(tPos) + 1);
                count++;
            }
        }
        Arrays.sort(product);
        double fp = 1;
        for (int i = 0; i < Math.min(count, maxRoutes); i++) {
            fp *= product[5 - i];
        }
        double fp2 = 1;
        for (int i = 0; i < Math.min(count, 6); i++) {
            fp2 *= product[5 - i];
        }
        double retValue = Math.min(count, maxRoutes) + fp;
        double retValue2 = Math.min(count, 6) + fp2;
        return -retValue - retValue2 / 1000000;
    }

}
randomra
fonte
1

RandCatcher

Isso foi feito apenas para testar o controlador e coloca os baldes aleatoriamente (de maneira muito ineficiente).

package players;

import main.Field;

public class RandCatcher implements Catcher {
    public String getName(){
        return "RandCatcher";
    }
    public int[] takeTurn(Field f){
        int[] pos = {0,0};
        do {
            pos[0] = (int) (Math.random()*f.SIZE);
            pos[1] = (int) (Math.random()*f.SIZE);
        } while( f.isValidPosition(pos)==false );
        return pos;
    }

}
flawr
fonte
1

StupidFillCatcher

Isso foi feito apenas para testar o controlador. Apenas preenche coluna por coluna até o gato ser pego.

package players;

import main.Field;

public class StupidFillCatcher implements Catcher {
    public String getName(){
        return "StupidFillCatcher";
    }
    public int[] takeTurn(Field f){
        for(int i=0; i < f.SIZE; i++){
            for(int j=0; j < f.SIZE; j++){
                if(f.isValidPosition(new int[] {i,j})){
                    return new int[] {i,j};
                }
            }
        }
        return new int[] {0,0};
    }

}
flawr
fonte