Асимметричный КОТ: поймай кота
ОБНОВЛЕНИЕ : Гист-файлы обновляются (включая новые подпункты), так как Controller.java не перехватывает исключения (только ошибки). Теперь он перехватывает ошибки и исключения, а также печатает их.
Эта задача состоит из двух потоков, это нить ловца, нить кошки можно найти здесь .
Контроллер можно скачать здесь .
Это асимметричный КОТ: каждое представление является либо кошкой, либо ловцом . Есть игры между каждой парой каждой кошки и ловца. Кошки и ловцы имеют отдельные рейтинги.
ловец
На гексагональной сетке стоит кот. Ваша задача - поймать его как можно быстрее. Каждый ход вы можете поместить ведро воды в одну ячейку сетки, чтобы кошка не могла туда попасть. Но кошка (возможно) не настолько глупа, и всякий раз, когда вы кладете ведро, кошка перемещается в другую ячейку сетки. Поскольку сетка является шестиугольной, кошка может двигаться в 6 разных направлениях. Ваша цель - окружить кота ведрами с водой, чем быстрее, тем лучше.
Кот
Вы знаете, что ловец хочет поймать вас, поместив вокруг себя ведра с водой. Конечно, вы пытаетесь уклониться, но поскольку вы ленивый кот (как и кошки), вы точно делаете один шаг за раз. Это означает, что вы не можете оставаться на том же месте, что и вы, но вам нужно переместиться в одно из шести окружающих мест. Всякий раз, когда вы видите, что ловец положил новое ведро с водой, вы идете в другую камеру. Конечно, вы пытаетесь уклониться как можно дольше.
сетка
Сетка является шестиугольной, но поскольку у нас нет шестиугольных структур данных, мы берем 11 x 11
квадратный двумерный массив и имитируем шестиугольное «поведение», которое кошка может перемещать только в 6 направлениях:
Топология является тороидальной, это означает, что если вы наступите на ячейку «вне» массива, вы просто будете перенесены в соответствующую ячейку на другой стороне массива.
Игра
Кошка начинает с заданной позиции в сетке. Ловец может сделать первый ход, затем кошка и ее ловец попеременно ходят, пока кошка не будет поймана. Количество шагов - это результат этой игры. Кошка старается набрать как можно больше очков, ловец пытается набрать как можно меньше очков. Средняя сумма по всем играм, в которых вы участвовали, будет оценкой вашего участия. Есть два отдельных рейтинга, один для кошки, один для ловцов.
контроллер
Данный контроллер написан на Java. Как ловец или кошка каждый из вас должен каждый реализовать класс Java (уже есть несколько примитивных примеров) и поместить его в players
пакет (и обновить список кошек / ловцов в классе Controller), но вы также можете написать дополнительные функции в этом классе. Контроллер поставляется с каждыми двумя работающими примерами простых классов кошек / ловцов.
Поле представляет собой 11 x 11
2D- 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
PRINT_STEPS = true
более подробные настройки в файлеMyFrame.java
). Затем я записал это с помощью LICEcap и отредактировал с помощью GIMP . Если у вас есть дополнительные вопросы, просто задавайте!Ответы:
Ахиллес
Ахиллес не слишком яркий, но он безжалостно эффективен. Сначала он не дает кошке использовать обертку вокруг доски, затем он делит доску на две части. Затем он продолжает делить часть доски, на которой кошка пополам, до тех пор, пока кошка не окажется в ловушке.
Демонстрация RandCat против Ахиллеса
источник
Агамемнон
Агамемнон делит область кошек пополам вертикальной линией, пока у кошки не появляется полоса шириной 2 для перемещения, после чего он ловит кошку.
Агамемнон против RandCat:
Этот ловец работает лучше, чем Ахилл, и я думаю, что он достаточно отличается, чтобы дать новый ответ.
источник
HexCatcher
Если ловец может доставить кошку внутрь большого шестиугольника с трех сторон, где углы шестиугольника уже заняты ведрами, ловец может удержать кошку в этой области и поймать его. Шестигранник выглядит так:
Это то, что пытается достичь HexCatcher. Он мысленно разбивает поле этими большими шестиугольниками так, что каждая угловая ячейка является частью 3 больших шестиугольников.
Если есть возможность удержать кота в текущей области, соединив два угла рядом с котом, бот сделает это. (Например, на изображении, если у кота 7,5, мы выбираем 7,6, даже если только 6,6 и 8,5 клеток заняты.)
Если предыдущий вариант не подходит, мы выбираем угол, который является частью области, где находится кот. Если все такие углы уже выбраны (как на картинке), мы выбираем клетку рядом с кошкой.
Возможны несколько небольших улучшений, таких как лучшая обработка переноса (там разбивается черепица) или оптимальное выполнение последней пары. Я мог бы сделать некоторые из них. Если это не разрешено, я просто добавлю его (вне конкурса) для тех, кто заинтересован.
DijkstrasCat против HexCatcher:
источник
CloseCatcher
Выбирает одну из позиций, где кошка может перейти на следующий шаг. Он выбирает тот, который дал бы наиболее возможные пути после 3 шагов для кошки, если бы он двигался туда, и поле не изменилось бы.
Код почти идентичен моей записи Cat, FreeCat , которая выбирает направление очень похожим образом.
SpiralCat против CloseCatcher:
источник
Дейкстра
Он не очень любит кошек (:
v{ >
FreeCat vs Dijkstra
(необходимо обновить):Как он пытается поймать кота:
Он анализирует все квадраты доски и пытается найти квадрат, который минимизирует открытость доски и максимизирует, насколько доска вытянута; по отношению к кот. Открытость и жесткость доски вычисляются с использованием модификации его знаменитого алгоритма .
Открытость:
Открытость доски относительно позиции - это количество достижимых позиций из этой позиции.
тягучесть:
Строгость доски относительно позиции - это сумма расстояний между достижимыми позициями и позицией.
С последним обновлением:
Теперь он намного лучше ловит
FreeCat и его собственную кошкувсех кошек.К сожалению, он также намного хуже ловит сумасшедших неработающих кошек. Его можно улучшить, обнаружив, является ли кошка одним из сумасшедших, и затем действовать как CloseCatcher.Ошибка в программе исправлена.
источник
error: cannot infer type arguments for PriorityQueue<>
в этой строкеPriorityQueue<int[]> open = new PriorityQueue<>(new Comparator<int[]>() {
.int[]
между двумя пустыми бриллиантами послеPriorityQueue
.ForwordCatcher
Помещает ведро перед кошкой, или, если оно взято, помещает позади.
RabidCat против ForwordCatcher:
источник
ChoiceCatcher
Использует тот же механизм подсчета очков, что и моя запись ChoiceCat . Есть небольшая модификация, которая помогает выбирать релевантные ячейки на первых нескольких шагах, так как ChoiceCat не заботится о первых нескольких сегментах, поскольку он не видит их как угрозу.
ChoiceCatcher, кажется, выигрывает значительно лучше, чем нынешние ловцы.
ChoiceCat против ChoiceCatcher:
источник
RandCatcher
Это было сделано только для тестирования контроллера и просто случайным образом размещает сегменты (очень неэффективно).
источник
StupidFillCatcher
Это было сделано только для тестирования контроллера. Это просто заполняет столбец за столбцом, пока кошка не поймана.
источник