АСИММЕТРИЧЕСКИЙ КОТ: Поймай кота (Нить ловца)

17

Асимметричный КОТ: поймай кота

ОБНОВЛЕНИЕ : Гист-файлы обновляются (включая новые подпункты), так как Controller.java не перехватывает исключения (только ошибки). Теперь он перехватывает ошибки и исключения, а также печатает их.

Эта задача состоит из двух потоков, это нить ловца, нить кошки можно найти здесь .

Контроллер можно скачать здесь .

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

ловец

На гексагональной сетке стоит кот. Ваша задача - поймать его как можно быстрее. Каждый ход вы можете поместить ведро воды в одну ячейку сетки, чтобы кошка не могла туда попасть. Но кошка (возможно) не настолько глупа, и всякий раз, когда вы кладете ведро, кошка перемещается в другую ячейку сетки. Поскольку сетка является шестиугольной, кошка может двигаться в 6 разных направлениях. Ваша цель - окружить кота ведрами с водой, чем быстрее, тем лучше.

Кот

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

сетка

Сетка является шестиугольной, но поскольку у нас нет шестиугольных структур данных, мы берем 11 x 11квадратный двумерный массив и имитируем шестиугольное «поведение», которое кошка может перемещать только в 6 направлениях:

введите описание изображения здесь

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

Игра

Кошка начинает с заданной позиции в сетке. Ловец может сделать первый ход, затем кошка и ее ловец попеременно ходят, пока кошка не будет поймана. Количество шагов - это результат этой игры. Кошка старается набрать как можно больше очков, ловец пытается набрать как можно меньше очков. Средняя сумма по всем играм, в которых вы участвовали, будет оценкой вашего участия. Есть два отдельных рейтинга, один для кошки, один для ловцов.

контроллер

Данный контроллер написан на Java. Как ловец или кошка каждый из вас должен каждый реализовать класс Java (уже есть несколько примитивных примеров) и поместить его в playersпакет (и обновить список кошек / ловцов в классе Controller), но вы также можете написать дополнительные функции в этом классе. Контроллер поставляется с каждыми двумя работающими примерами простых классов кошек / ловцов.

Поле представляет собой 11 x 112D- intмассив, в котором хранятся значения текущих состояний ячеек. Если ячейка пуста, она имеет значение 0, если есть кошка, она имеет значение, -1а если есть область, то есть 1.

Существует несколько функций, которые вы можете использовать: isValidMove()/ isValidPosition()для проверки правильности вашего хода (кошка) / позиции (ловец).

Каждый раз, когда ваша очередь, ваша функция takeTurn()вызывается. Аргумент содержит копию текущей сетки и имеет методы, такие как read(i,j)чтение ячейки (i,j), а также isValidMove()/ isValidPosition()проверяет правильность вашего ответа. Это также управляет наложением тороидальной топологии, что означает, что даже если сетка имеет размер только 11 x 11, вы все равно можете получить доступ к ячейке (-5,13).

Метод должен возвращать intмассив из двух элементов, которые представляют возможные ходы. Для кошек это те, {-1,1},{0,1},{-1,0},{1,0},{0,-1},{1,-1}которые представляют относительное положение того, куда кошка хочет пойти, а ловцы возвращают абсолютные координаты того, где они хотят поместить ведро {i,j}.

Если ваш метод приводит к неверному ходу, ваша заявка будет дисквалифицирована. Движение считается недействительным, если в вашем пункте назначения уже есть ведро или движение не разрешено / пункт назначения уже занят (как кошка), или если уже есть ведро / кошка (как ловец). Вы можете проверить это заранее с помощью данных функций.

Ваше представление должно работать достаточно быстро. Если ваш метод занимает больше 200 мс для каждого шага, он также будет дисквалифицирован. (Желательно намного меньше ...)

Программы могут хранить информацию между этапами.

Материалы

  • Вы можете сделать столько заявок, сколько захотите.
  • Пожалуйста, не вносите существенных изменений в материалы, которые вы уже отправили.
  • Пожалуйста, каждый представленный в новом ответе.
  • Каждое представление должно иметь свое уникальное имя.
  • Представление должно состоять из кода вашего класса, а также описания, которое говорит нам, как работает ваше представление.
  • Вы можете написать строку <!-- language: lang-java -->для исходного кода, чтобы получить автоматическую подсветку синтаксиса.

счет

Все кошки будут соревноваться со всеми ловцами одинаковое количество раз. Я постараюсь регулярно обновлять текущие оценки, победители будут определены, когда активность снизится.

Этот вызов вдохновлен этой старой флеш игрой

Спасибо @PhiNotPi за тестирование и конструктивную обратную связь.

Текущие результаты (100 игр за пару)

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
источник
Какая программа делает анимацию?
MegaTom
Анимация - это просто графический интерфейс (при запуске контроллера необходимо установить PRINT_STEPS = trueболее подробные настройки в файле MyFrame.java). Затем я записал это с помощью LICEcap и отредактировал с помощью GIMP . Если у вас есть дополнительные вопросы, просто задавайте!
flawr
Если вы добавите пользовательский ввод в контроллер, он может создать хорошее программное обеспечение с графическим интерфейсом и уже написанными ботами. Было бы также интересно посмотреть, насколько люди могут взломать / злоупотребить конкретными стратегиями ботов.
Рандомра
Кроме того, может ли мой бот хранить информацию из предыдущего матча, чтобы попытаться найти лучшую последовательность действий против того же бота? Я полагаю, не потому, что чем больше раундов вы делаете, тем лучше. Также нужно было бы угадать, играет ли он против нового бота, поэтому порядок выполнения тоже будет иметь значение.
Рандомра
1
Почему оценки кошек не заказаны?
Spikatrix

Ответы:

6

Ахиллес

Ахиллес не слишком яркий, но он безжалостно эффективен. Сначала он не дает кошке использовать обертку вокруг доски, затем он делит доску на две части. Затем он продолжает делить часть доски, на которой кошка пополам, до тех пор, пока кошка не окажется в ловушке.

Демонстрация RandCat против Ахиллеса

Рэндкат против Ахилла

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
источник
Ну, кто это сейчас, Ахилл или Гектор? (Или кто-то с диссоциативным расстройством личности? =)
flawr
@flawr Ахиллес, лол Я изменил имя на полпути (более подходяще назвать ловца Ахиллеса и кота Гектора), но забыл сменить java - это то, что происходит, когда вы программируете после чая :(
euanjt
Но Гектор скорее будет именем собаки =) Спасибо за ваше представление, отлично работает. Надеюсь, вы не против, чтобы я включил в ваш код и «преамбулу».
flawr
Да, нет проблем. Гектор звучит как имя собаки ...
euanjt
Я только что провел симуляцию (10000 игр для каждой пары), и Ахиллес был дисквалифицирован из-за повторного StackOverflowError. Я думаю, что рекурсия не закончилась: pastebin.com/9n6SQQnd
flawr
5

Агамемнон

Агамемнон делит область кошек пополам вертикальной линией, пока у кошки не появляется полоса шириной 2 для перемещения, после чего он ловит кошку.

Агамемнон против RandCat:

введите описание изображения здесь

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

Этот ловец работает лучше, чем Ахилл, и я думаю, что он достаточно отличается, чтобы дать новый ответ.

euanjt
источник
Очень хорошее решение, я был уверен, что Ахиллес был близок к оптимальному, но теперь я думаю, что даже Агамемнона можно немного улучшить =)
flawr
Да, у Агамемнона гораздо лучший алгоритм захвата в конце игры, чем у Ахилла, но я уверен, что есть некоторые хитрости ... Теперь я попробую поработать над кошкой :)
euanjt
@flawr добавлен очень маленький твик для ускорения отлова в некоторых особых случаях, это не влияет на анимацию здесь (хотя я думаю, что это может повлиять на анимацию
SpiralCat
Вопрос! Что произойдет, если вы собираетесь закрыть линию, но кошка стоит на последнем месте?
Мистер Лама
@ Mr.Llama начинает следующую строку, как если бы эта строка была заполнена (т. Е. Кот был фактически ведром) - не самое эффективное использование поворота, но очень редко случается, что это на самом деле не имеет значения - Кошка должна затем отойти в свой следующий ход, чтобы я мог поставить туда свое ведро
euanjt
5

HexCatcher

Если ловец может доставить кошку внутрь большого шестиугольника с трех сторон, где углы шестиугольника уже заняты ведрами, ловец может удержать кошку в этой области и поймать его. Шестигранник выглядит так:

введите описание изображения здесь

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

Если есть возможность удержать кота в текущей области, соединив два угла рядом с котом, бот сделает это. (Например, на изображении, если у кота 7,5, мы выбираем 7,6, даже если только 6,6 и 8,5 клеток заняты.)

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

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

DijkstrasCat против HexCatcher:

введите описание изображения здесь

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
источник
3

CloseCatcher

Выбирает одну из позиций, где кошка может перейти на следующий шаг. Он выбирает тот, который дал бы наиболее возможные пути после 3 шагов для кошки, если бы он двигался туда, и поле не изменилось бы.

Код почти идентичен моей записи Cat, FreeCat , которая выбирает направление очень похожим образом.

SpiralCat против CloseCatcher:

SpiralCat против 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
источник
Ницца +1. CloseCatcher легко захватывает StraightCat
Spikatrix
3

Дейкстра

Он не очень любит кошек (:v{ >

FreeCat vs Dijkstra (необходимо обновить) :

введите описание изображения здесь

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

Как он пытается поймать кота:

Он анализирует все квадраты доски и пытается найти квадрат, который минимизирует открытость доски и максимизирует, насколько доска вытянута; по отношению к кот. Открытость и жесткость доски вычисляются с использованием модификации его знаменитого алгоритма .

Открытость:

Открытость доски относительно позиции - это количество достижимых позиций из этой позиции.

тягучесть:

Строгость доски относительно позиции - это сумма расстояний между достижимыми позициями и позицией.

С последним обновлением:

Теперь он намного лучше ловит FreeCat и его собственную кошку всех кошек. К сожалению, он также намного хуже ловит сумасшедших неработающих кошек. Его можно улучшить, обнаружив, является ли кошка одним из сумасшедших, и затем действовать как CloseCatcher.

Ошибка в программе исправлена.

Номер один
источник
Могу подтвердить, что пока это работает, но, на мой взгляд, самый медленный, но один из лучших на данный момент. Требуется 134 секунды для 100 игр против RandCat, в то время как в общей сложности всего 4406 ходов! Я думаю, что в один из следующих дней мне придется позволить моему компьютеру работать всю ночь ... Не могли бы вы рассказать нам немного больше о том, как это работает?
flawr
@flawr Добавил описание.
TheNumberOne
Все еще не работает для меня. Дает мне одну ошибку: error: cannot infer type arguments for PriorityQueue<>в этой строке PriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {.
Spikatrix
@CoolGuy Вы используете Java 6? Я думаю, что вам нужно обновить свой JDK.
TheNumberOne
@CoolGuy Вы также можете поставить int[]между двумя пустыми бриллиантами после PriorityQueue.
TheNumberOne
2

ForwordCatcher

Помещает ведро перед кошкой, или, если оно взято, помещает позади.

RabidCat против ForwordCatcher:

RabidCat против 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
источник
1
Есть довольно много ошибок, которые приводят меня к предположению, что вы не тестировали свою программу. Пожалуйста, исправьте это ...
flawr
@ Flawr исправлено. извините за ошибки. Я не проверял это, и моя Java не слишком хороша.
MegaTom
Хорошо, пока все идет гладко, но я все еще не уверен, будут ли они всегда давать правильные ходы =)
flawr
1
@flawr Пространство за кошкой всегда будет пустым для ловца :)
TheNumberOne
2

ChoiceCatcher

Использует тот же механизм подсчета очков, что и моя запись ChoiceCat . Есть небольшая модификация, которая помогает выбирать релевантные ячейки на первых нескольких шагах, так как ChoiceCat не заботится о первых нескольких сегментах, поскольку он не видит их как угрозу.

ChoiceCatcher, кажется, выигрывает значительно лучше, чем нынешние ловцы.

ChoiceCat против ChoiceCatcher:

ChoiceCat против 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
источник
1

RandCatcher

Это было сделано только для тестирования контроллера и просто случайным образом размещает сегменты (очень неэффективно).

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
источник
1

StupidFillCatcher

Это было сделано только для тестирования контроллера. Это просто заполняет столбец за столбцом, пока кошка не поймана.

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