Это Fortnightly Challenge # 3. Тема: Генетические алгоритмы
Этот вызов - эксперимент. Мы хотели посмотреть, что мы можем сделать, с помощью генетических алгоритмов. Не все может быть оптимальным, но мы старались сделать его доступным. Если это сработает, кто знает, что мы можем увидеть в будущем. Может быть, генетический король горы?
Спецификация довольно длинная! Мы попытались разделить спецификацию на Основы - необходимый минимум, чтобы начать играть с фреймворком и представить ответ - и подробности The Gory - полную спецификацию со всеми подробностями о контроллере, на основе которых вы мог написать свой.
Если у вас есть какие-либо вопросы, присоединяйтесь к нам в чате!
Вы исследователь в поведенческой психологии. Это вечер пятницы, и вы и ваши коллеги решили повеселиться и использовать своих лабораторных крыс для небольшой крысиных гонок. На самом деле, прежде чем мы будем слишком эмоционально привязаны к ним, давайте назовем их образцами .
Вы создали небольшую гоночную трассу для образцов, и чтобы сделать ее более интересной, вы разместили несколько дорожек, ловушек и телепортеров по всей трассе. Теперь ваши образцы все еще крысы ... они понятия не имеют, что такое ловушка или телепорт. Все, что они видят, это вещи разных цветов. У них также нет никакой памяти - все, что они могут сделать, - это принимать решения, основываясь на их текущем окружении. Я предполагаю, что естественный отбор выберет образцы, которые знают, как избежать ловушки из тех, которые этого не делают (эта гонка займет некоторое время ...). Да начнется игра! †
† 84 465 особей были повреждены при постановке этой задачи.
Основы
Это однопользовательская игра (вы и ваши коллеги не хотели смешивать население, поэтому каждый из них создал свой собственный гоночный трек). Ипподром представляет собой прямоугольную сетку высотой 15 ячеек и шириной 50 ячеек. Вы начинаете с 15 образцов на случайных (не обязательно отличных) ячейках на левом краю (где x = 0 ). Ваши образцы должны попытаться достичь цели, которой является любая ячейка при x ≥ 49 и 0 ≤ y ≤ 14 (образцы могут отклониться от пути вправо). Каждый раз, когда это происходит, вы получаете очко. Вы также начинаете игру с 1 очком. Вы должны попытаться максимизировать свои очки после 10 000 ходов.
Несколько образцов могут занимать одну и ту же ячейку и не будут взаимодействовать.
На каждом ходу каждый образец видит сетку 5x5 своего окружения (с самим собой в центре). Каждая ячейка этой сетки будет содержать цвет -1
к 15
. -1
представляет клетки, которые находятся за пределами. Ваш образец умирает, если он выходит за пределы. Что касается других цветов, они представляют собой пустые клетки, ловушки, стены и телепорты. Но ваш образец не знает, какой цвет представляет, и вы тоже. Однако есть некоторые ограничения:
- 8 цветов будут представлять пустые ячейки.
- 4 цвета будут представлять телепорт. Телепортер отправит образец в определенную ячейку в своем районе 9x9. Это смещение будет одинаковым для всех телепортеров одного цвета.
- 2 цвета будут представлять стены. Двигаться в стену - все равно, что стоять на месте.
- 2 цвета будут представлять ловушку. Ловушка указывает, что одна из 9 клеток в ее непосредственной близости является летальной (не обязательно сама клетка ловушки). Это смещение будет одинаковым для всех ловушек одного цвета.
Теперь об этом естественном отборе ... у каждого экземпляра есть геном, представляющий собой число из 100 битов. Новые образцы будут созданы путем скрещивания двух существующих образцов, а затем с незначительным изменением генома. Чем успешнее образец, тем больше у него шансов на воспроизведение.
Итак, вот ваша задача: вы напишите одну функцию, которая получает в качестве входных данных сетку цветов 5x5, которую видит образец, а также его геном. Ваша функция вернет ход (Δx, Δy) для образца, где Δx и Δy будут каждый из {-1, 0, 1}
. Вы не должны сохранять какие-либо данные между вызовами функций. Это включает в себя использование ваших собственных генераторов случайных чисел. Ваша функция будет обеспечена засеянным ГСЧ, который вы можете использовать по своему усмотрению.
Оценка вашего представления будет средним геометрическим числом баллов по 50 случайным трекам. Мы обнаружили, что эта оценка подвержена значительным отклонениям. Поэтому эти оценки будут предварительными . Как только этот вызов исчезнет, будет объявлен крайний срок. По истечении крайнего срока, 100 досок будут выбраны случайным образом, и все заявки будут перенесены на эти 100 досок. Не стесняйтесь ставить оценку в вашем ответе, но мы будем оценивать каждую подачу самостоятельно, чтобы никто не обманывал.
Мы предоставили программы контроллеров на нескольких языках. В настоящее время вы можете написать свою заявку на Python (2 или 3), Ruby , C ++ , C # или Java . Контроллер генерирует доски, запускает игру и обеспечивает основу для генетического алгоритма. Все, что вам нужно сделать, это обеспечить функцию перемещения.
Подождите, так что же мне делать с геномом?
Задача состоит в том, чтобы понять это!
Поскольку у образцов нет памяти, все, что у вас есть в данном ходу, - это сетка цветов 5х5, которая ничего для вас не значит. Таким образом, вам придется использовать геном, чтобы достичь цели. Общая идея заключается в том, что вы используете части генома для хранения информации о цветах или компоновке сетки, а ваш бот основывает свои решения на дополнительной информации, хранящейся в геноме.
Теперь, конечно, вы не можете хранить там что-либо вручную. Таким образом, фактическая информация, хранящаяся там, изначально будет полностью случайной. Но генетический алгоритм скоро выберет те образцы, чей геном содержит правильную информацию, и убьет те, у которых неправильная информация. Ваша цель - найти соответствие между битами генома и вашим полем зрения движением, которое позволяет быстро найти путь к цели и которое последовательно развивается в выигрышной стратегии.
Этого должно быть достаточно, чтобы вы начали. Если вы хотите, вы можете пропустить следующий раздел и выбрать нужный контроллер из списка контроллеров внизу (который также содержит информацию о том, как использовать этот конкретный контроллер).
Читайте дальше, если хотите все ...
Гори Детали
Эта спецификация завершена. Все контроллеры должны выполнять эти правила.
Вся случайность использует равномерное распределение, если не указано иное.
Генерация треков:
- Дорожка представляет собой прямоугольную сетку, шириной X = 53 ячейки и высотой Y = 15 ячеек. Ячейки с x ≥ 49 являются целевыми ячейками (где x основано на нуле).
- Каждая клетка имеет один цвет и может быть или не быть летальной - клетки не являются летальными, если это не указано одним из типов клеток ниже.
- Существует 16 различных цветов ячеек, помеченных от
0
до15
, значение которых будет меняться от игры к игре. Кроме того,-1
представляет клетки, которые находятся за пределами - это смертельно . - Выберите 8 случайных цветов . Это будут пустые ячейки (которые не имеют никакого эффекта).
- Выберите еще 4 случайных цвета . Это телепорты. Для двух из этих цветов выберите ненулевое смещение в окрестности 9x9 (от (-4, -4) до (4,4) за исключением (0,0)). Для других двух цветов инвертируйте эти смещения. Если образец наступает на телепорт, он немедленно перемещается на это смещение.
- Выберите еще 2 случайных цвета . Это ловушки. Для каждого из этих цветов выберите смещение в окрестности 3х3 (от (-1, -1) до (1,1)). Ловушка указывает на то, что ячейка с таким смещением смертельна . Примечание. Сама ловушка не обязательно смертельна.
- В 2 остальных цветами являются стенами, которые препятствуют движению. Попытка перейти на клетку стены превратит движение в неподвижность. Сами клеточные стенки смертельны .
- Для каждой нецелевой ячейки сетки выберите случайный цвет. Для каждой клетки цели выберите случайный пустой цвет.
- Для каждой ячейки на левом краю дорожки определите, можно ли достичь цели в течение 100 ходов (в соответствии с приведенными ниже правилами порядка хода ). Если это так, эта ячейка является допустимой стартовой ячейкой . Если начальных ячеек меньше 10, откажитесь от дорожки и создайте новую.
- Создайте 15 экземпляров, каждый со случайным геном и возрастом 0 . Поместите каждый образец в случайную начальную ячейку.
Порядок поворота:
- Следующие шаги будут выполнены, по порядку, для каждого образца. Образцы не взаимодействуют и не видят друг друга и могут занимать одну и ту же клетку.
- Если возраст образца составляет 100 лет , он умирает. В противном случае увеличьте его возраст на 1.
- Образцу предоставляется его поле зрения - сетка цветов 5x5, центрированная на образце, и он возвращает движение в своей окрестности 3x3. Выход за пределы этого диапазона приведет к прекращению работы контроллера.
- Если целевой ячейкой является стена, то ход изменяется на (0,0).
- Если целевая ячейка является телепортом, образец перемещается по смещению телепорта. Примечание. Этот шаг выполняется один раз , а не итеративно.
- Если ячейка, занятая в настоящее время образцом (возможно, после использования одного телепорта), смертельна, образец погибает. Это единственный раз, когда образцы умирают (кроме шага 1.1. Выше). В частности, новый образец, который появляется на смертельной клетке, не погибнет немедленно, но имеет шанс сначала покинуть опасную клетку.
- Если образец занимает целевую ячейку, наберите одно очко, переместите образец в случайную начальную ячейку и установите его возраст равным 0.
- Если на доске осталось менее двух экземпляров, игра заканчивается.
- Создайте 10 новых экземпляров с возрастом 0 . Каждый геном определяется (индивидуально) по правилам разведения ниже. Поместите каждый образец в случайную начальную ячейку.
Разведение:
Когда создается новый образец, выбирайте двух разных родителей наугад, с уклоном в сторону образцов, которые продвинулись дальше вправо. Вероятность того, что образец будет выбран, пропорциональна его текущей оценке пригодности . Оценка пригодности образца
1 + x + 50 * сколько раз он достиг цели
где x - горизонтальный индекс на основе 0. Образцы, созданные в том же порядке, не могут быть выбраны в качестве родителей.
Из двух родителей выберите случайного, чтобы взять первый бит генома.
- Теперь, когда вы идете по геному, поменяйте родителей с вероятностью 0,05 и продолжайте брать биты у получающегося родителя.
- Мутируйте полностью собранный геном: для каждого бита переверните его с вероятностью 0,01 .
Подсчет очков:
- Одна игра длится 10000 ходов.
- Игроки начинают игру с 1 очком (чтобы разрешить использование среднего геометрического).
- Каждый раз, когда образец достигает цели, игрок получает очко.
- На данный момент каждый игрок подаст заявку на 50 игр, каждая из которых имеет свой случайный трек.
- Вышеуказанный подход приводит к большей дисперсии, чем желательно. Как только этот вызов исчезнет, будет объявлен крайний срок. По истечении крайнего срока, 100 досок будут выбраны случайным образом, и все заявки будут перенесены на эти 100 досок.
- Общий счет игрока является средним геометрическим значением очков этих отдельных игр.
Контроллеры
Вы можете выбрать любой из следующих контроллеров (так как они функционально эквивалентны). Мы протестировали все из них, но если вы обнаружили ошибку, хотите улучшить код или производительность, или добавили такую функцию, как графический вывод, отправьте сообщение об ошибке или отправьте запрос на GitHub! Также вы можете добавить новый контроллер на другом языке!
Нажмите на название языка для каждого контроллера, чтобы перейти к нужному каталогу на GitHub, который содержит README.md
точные инструкции по использованию.
Если вы не знакомы с git и / или GitHub, вы можете загрузить весь репозиторий в виде ZIP-файла с первой страницы (см. Кнопку на боковой панели).
питон
- Наиболее тщательно проверено. Это наша эталонная реализация.
- Работает как с Python 2.6+, так и с Python 3.2+!
- Это очень медленно. Мы рекомендуем запустить его с PyPy для существенного ускорения.
- Поддержка графического вывода с использованием либо
pygame
илиtkinter
.
Рубин
- Протестировано с Ruby 2.0.0. Должен работать с более новыми версиями.
- Это также довольно медленно, но Ruby может быть удобен для прототипирования идеи для представления.
C ++
- Требуется C ++ 11.
- Опционально поддерживает многопоточность.
- Безусловно, самый быстрый контроллер в связке.
C #
- Использует LINQ, поэтому он требует .NET 3.5.
- Скорее медленно.
Ява
- Не особенно медленно. Не особенно быстро.
Предварительная таблица лидеров
Все оценки являются предварительными. Тем не менее, если что-то не так или устарело, пожалуйста, дайте мне знать. Наш пример представления приведен для сравнения, но не для утверждения.
Score | # Games | User | Language | Bot
===================================================================================
2914.13 | 2000 | kuroi neko | C++ | Hard Believers
1817.05097| 1000 | TheBestOne | Java | Running Star
1009.72 | 2000 | kuroi neko | C++ | Blind faith
782.18 | 2000 | MT0 | C++ | Cautious Specimens
428.38 | | user2487951 | Python | NeighborsOfNeighbors
145.35 | 2000 | Wouter ibens | C++ | Triple Score
133.2 | | Anton | C++ | StarPlayer
122.92 | | Dominik Müller | Python | SkyWalker
89.90 | | aschmack | C++ | LookAheadPlayer
74.7 | | bitpwner | C++ | ColorFarSeeker
70.98 | 2000 | Ceribia | C++ | WallGuesser
50.35 | | feersum | C++ | Run-Bonus Player
35.85 | | Zgarb | C++ | Pathfinder
(34.45) | 5000 | Martin Büttner | <all> | ColorScorePlayer
9.77 | | DenDenDo | C++ | SlowAndSteady
3.7 | | flawr | Java | IAmARobotPlayer
1.9 | | trichoplax | Python | Bishop
1.04 | 2000 | fluffy | C++ | Gray-Color Lookahead
кредиты
Эта задача была огромным совместным усилием:
- Натан Меррил: Написал контроллеры Python и Java. Превратила концепцию испытаний из King-of-the-Hill в крысиные бега.
- Трихоплакс: тестирование. Работал на контроллере Python.
- feersum: Написал C ++ контроллер.
- VisualMelon: написал C # контроллер.
- Мартин Бюттнер: Концепция. Написал Ruby контроллер. Тестируем. Работал на контроллере Python.
- Т Авраам: тестирование. Протестировал Python и рассмотрел C # и C ++ контроллер.
Все вышеперечисленные пользователи (и, возможно, еще пара, о которых я забыл) внесли свой вклад в общий дизайн задачи.
Обновление контроллера C ++
Если вы используете C ++ с Visual Studio и многопоточностью, вы должны получить последнее обновление из-за ошибки с заполнением генератора случайных чисел, которая позволяет создавать дубликаты плат.
источник
'In particular, a new specimen which spawns on a lethal cell will not die immediately, but has a chance to move off the dangerous cell first.'
Ответы:
Слепая вера - C ++ - кажется, набирает более 800 (!) Баллов за 2000
Геном цветового кодирования с загадочной обратной связью и эффективным сдерживающим фактором
Пример результатов:
Основываясь на непроизвольно продолжительном тесте feersum, я считаю, что 2000 прогонов достаточно, чтобы получить приемлемо стабильный результат.
Поскольку мой модифицированный контроллер отображает текущее геометрическое среднее значение после каждого прогона, я визуально подтвердил, что отклонение за последние 50 прогонов было относительно небольшим (+ - 10 баллов).
Что заставляет этих твари тикать
Вместо того, чтобы давать равные приоритеты каждому цвету, я рассматриваю эти возможные значения:
Хотя я слишком ленив, чтобы переименовать его, это скорее «детектор опасности», указывающий (предполагаемое) местоположение реальной ловушки, стены, телепорта, ожидающего отправки ничего не подозревающего странника в неприятное место или даже вход мертвого -конец. Короче говоря, место, куда бы мудрая крыса не пошла.
Хорошие или плохие гены хранят только 2 бита (например,
11
и10
), но для ловушек требуется 4 бита (0ttt
гдеttt
представляет одно из 8 возможных «опасных» мест).Для того, чтобы сохранить каждый ген последовательно (т.е. сохранение его значение после того, как были смешаны в совершенно другой геном, который требует каждого цветового кодирования гена , чтобы быть в фиксированном месте), все значения кодируются на 4 бита (так хорошо , кодируется как
11xx
и плохо , как10xx
), всего 16 * 4 = 64 бита.Остальные 36 битов используются как «антистенгеры» (подробнее об этом позже). 25 окружающих цветов хэшируются в индекс из этих 36 битов. Каждый бит указывает предпочтительное вертикальное направление (вверх или вниз), которое используется, когда возможен выбор между двумя ячейками.
Стратегия заключается в следующем:
Вы грызуны, вот враги вашего рода
Худшее, что может случиться с популяцией, - это еще не выиграть ни одного победителя, но множество крыс прилипло либо к стене, либо к бесконечной петле телепортации, достаточно близко к цели, чтобы иметь доминирующий шанс быть выбранным для размножения .
Вопреки тому, что крысы были зажаты в ловушке или телепортированы в стены, эти грызуны будут убиты только к старости.
Они не имеют конкурентного преимущества перед своими кузенами, которые с самого начала застряли на 3 клетки, но у них будет достаточно времени, чтобы размножаться поколение за поколением кретинов, пока их геном не станет доминирующим, что нанесет серьезный вред генетическому разнообразию без веской причины.
Чтобы смягчить это явление, идея состоит в том, чтобы сделать потомков этих плохих, плохих крыс более вероятными, чтобы избежать следования на этапах своего происхождения.
Указатель вертикального направления имеет длину всего 1 бит (в основном, говоря «попробуйте идти вверх или вниз первым в этих условиях»), и довольно много битов, вероятно, окажут влияние на пройденный путь, поэтому мутации и / или пересечения должны иметь значительное влияние.
Многие потомки будут вести себя по-разному и не будут биться головой об одну и ту же стену (среди трупов своих голодных предков).
Тонкость здесь в том, что этот признак не является доминирующим фактором в поведении крысы. Интерпретация цвета все еще будет преобладать в большинстве случаев (выбор вверх / вниз будет иметь значение, только если действительно есть два «хороших»).и то, что крыса считает безвредным цветом, не телепорт, ожидающий, чтобы бросить его в стену).
Почему это (кажется) работает?
Я до сих пор не знаю точно, почему.
Абсолютной удачей, которая остается неразгаданной тайной, является логика картирования ловушек. Без сомнения, это краеугольный камень успеха, но он работает по-своему таинственным образом.
При использовании кодирования случайный геном будет производить 25% «хороших», 25% «плохих» и 50% «ловушечных» идентификаторов цвета.
идентификаторы «ловушки», в свою очередь, будут давать «хорошие» и «плохие» оценки в корреляции с окружением 5x5.
В результате крыса в данном месте «увидит» мир как смесь стабильных и контекстных цветов «не ходи».
Как показывает довольно успешный механизм анти-ударов, наихудшим элементом на трассе является страшная стена (и ее двоюродный брат - телепортационная петля, но я думаю, что они встречаются гораздо реже).
Вывод заключается в том, что успешная программа должна, прежде всего, иметь возможность развивать крыс, способных обнаруживать позиции, которые приведут к медленному голоданию, не достигая цели.
Даже без «угадывания» двух цветов, представляющих стены, цвета «ловушек», по-видимому, способствуют обходу стен, позволяя крысе обходить несколько препятствий не потому, что она «видела» стены, а потому, что оценка «ловушки» исключала их конкретные клеточные стенки в этом конкретном окружении.
Несмотря на то, что крыса пытается двигаться к цели (что может привести к тому, что наиболее «полезными» индикаторами ловушек являются те, которые указывают на опасность впереди), я думаю, что все направления ловушек имеют примерно одинаковое влияние: ловушка, указывающая «опасность позади» «Расположение 2 клеток перед крысой имеет такое же влияние, как и указание на« опасность впереди », когда крыса стоит прямо над ней.
К сожалению, почему эта смесь обладает свойством так успешно сближать геном, это далеко не моя математика.
Я чувствую себя более комфортно с помощью сдерживающего средства. Это сработало, как и планировалось, хотя и намного превзошло мои ожидания (счет был в основном умножен на четыре)
Я сильно взломал контроллер для отображения некоторых данных. Вот несколько прогонов:
Здесь порода супер-крыс появилась рано (след, вероятно, позволял бегать по прямой линии, и у некоторых счастливых крыс в самых первых поколениях была правильная ДНК, чтобы воспользоваться этим). Количество образцов в конце составляет примерно половину теоретического максимума около 100 000 крыс, что означает, что почти половина тварей приобрела способность выживать на этом конкретном пути бесконечно (!).
Конечно, итоговая оценка просто непристойна, как, впрочем, и время вычислений.
Здесь мы можем увидеть уточнение генома на работе. Родословная между двумя последними геномами проявляется четко. В хорошие и плохие оценки являются наиболее значимыми. Индикаторы ловушек, кажется, колеблются, пока они не стабилизируются до «полезной» ловушки или не превращаются в хорошие или плохие .
Кажется, у цветовых генов есть несколько полезных характеристик:
(определенный цвет должен обрабатываться определенным образом).
Каждое цветовое кодирование может быть добавлено в совершенно другой геном без существенного изменения поведения - если только цвет не является фактически решающим (обычно стена или телепорт, ведущий к бесконечной петле).
Это в меньшей степени относится к базовому кодированию приоритетов, поскольку наиболее приоритетный цвет - это единственная информация, используемая для определения, куда двигаться. Здесь все «хорошие» цвета равны, поэтому данный цвет, добавленный в «хороший» список, будет иметь меньшее влияние.
хорошее / плохое кодирование имеет только 2 значащих бита из 4, и местоположение ловушки может изменяться большую часть времени без существенного изменения поведения крысы.
. Мутант, изменяющийся на «добро», либо малоэффективен (если, например, он соответствует пустой клетке, он может позволить найти новый, более короткий путь, но это также может привести крысу прямо в ловушка), или драматическая (если цвет представляет стену, новая крыса очень вероятно застрянет где-нибудь).
Ген, переключающийся на «ловушку», либо лишит крысу существенного цвета, либо не окажет заметного эффекта.
Мутация местоположения ловушки будет иметь значение только в том случае, если впереди действительно есть ловушка (или что-то вредное), которая имеет относительно небольшую вероятность (я бы сказал, что-то вроде 1/3).
Наконец, я предполагаю, что последние 36 битов способствуют не только предотвращению застревания крыс, но и более равномерному распределению крыс на дорожке, таким образом сохраняя генетическое разнообразие, пока не появится победный геном и не станет доминирующим в части кодирования цвета.
Дальнейшая работа
Я должен сказать, что нахожу этих маленьких тварей очаровательными.
Еще раз спасибо всем, кто внес вклад в этот прекрасный вызов.
Я подумываю о том, чтобы разделить контроллер дальше, чтобы отобразить более важные данные, например, происхождение успешной крысы.
Я также очень хотел бы видеть этих крыс в действии, но этот язык C ++ b ** ch делает создание - не говоря уже о анимации - изображений (среди многих других вещей) грязной рутиной.
В конце я хотел бы дать хотя бы объяснение системы ловушек и, возможно, улучшить ее.
Контроллер взлома
Если кому-то интересно, я могу опубликовать сделанные мной изменения в контроллере.
Они грязные и дешевые, но они делают свою работу.
Я не разбираюсь в GitHub, так что придется пройти через простой пост.
источник
^^v^vvv^^^vv^^v^vvv^v^^vvvv^^^^^^^^^
значите? Остальное я могу догадаться, но у меня проблемы с этим?Жестокие верующие - C ++ - (улучшенные телепорты): 10.000+ за 2000 запусков
(это эволюция слепой веры , поэтому вы можете подняться на другую стену текста до этой)
Эпизод IV: ориентируемся на решетке
Результаты
Я перешел на g ++ / MinGW и 3 потока.
Код, сгенерированный GNU, более чем в два раза быстрее кода Microsoft.
Не удивительно, что с их ужасающей реализацией STL.
Телепорт
Эффект телепорта сильно зависит от позиции. До сих пор я был рад, что телепортер всегда считался либо хорошим (если смотреть как пустое пространство), либо всегда плохим (если рассматривать его как стену, чтобы ни один грызун никогда его не взял).
Это слишком грубая модель.
Данный телепорт может продвигать крысу вперед на несколько клеток от цели, но когда тот же телепортер может сбросить крысу с доски.
Такой телепорт, скорее всего, будет признан сносным (так как он повышает физическую форму быстрее, чем когда «идет» к одному и тому же месту х), станет частью доминирующего генома и убьет почти всех крыс, которые считают его «всегда безопасным».
Поскольку крысы не имеют возможности узнать свое положение Х, единственное решение для обнаружения этих коварных телепортов - решить, наступать ли на них, основываясь на единственных доступных контекстных данных, то есть на цветовой сетке 5x5.
Для этого я определил 4 типа цветовых генов:
Идея состоит в том, чтобы попытаться отличить телепорта, посмотрев на его ближайших 8 соседей. Поскольку вероятность наличия 8 идентичных соседей в данном месте очень мала, это должно позволить идентифицировать уникальный экземпляр каждого телепорта.
8 соседних цветов можно объединить, чтобы сформировать локальную подпись, которая инвариантна относительно положения в лабиринте. К сожалению, 8 соседей видны только для ячеек, расположенных в пределах внутреннего квадрата поля зрения 3х3, поэтому подписи на краях поля зрения будут неточными.
Тем не менее, это даст нам постоянную контекстную информацию в непосредственной близости, которой достаточно, чтобы увеличить вероятность успешной навигации по телепортам.
Генные пучки имеют 2-битное переменное поле.
Для данной локальной сигнатуры телепорта существует один шанс из четырех, что ячейка луча будет считаться непроходимой. Каждое значение поля выбирает одну из этих четырех возможностей.
В результате мутация гена луча на этих 2 битах будет циклически проходить через 4 возможных контекстных значения цвета.
Кроме того, самые важные цвета, которые нужно угадать - это стены и ловушки. Это означает, что мы должны разрешить обнаружение телепорта только после того, как крысы узнают, где находятся стены и ловушки.
Это делается путем обновления локальных подписей только спарринг. Текущий критерий для обновления локальной подписи должен быть в непосредственной близости от цвета, определенного как потенциальный телепорт.
Кодирование использует 5 бит на цветовой ген и группирует типы, чтобы освободить 3 менее значимых бита для кодирования значения 0,7:
Каждый ген луча имеет 1/4 вероятности того, что его считают блоком, и 3/4 вероятности того, что его считают пустым, поэтому 4 луча представляют в среднем 1 блок и 3 пустых.
Таким образом, средняя доля, представленная случайным разбросом в 16 цветов:
Этот микс, похоже, пока дает лучшие результаты, но я еще не закончил его настройку.
Изменчивость гена
Одно можно сказать наверняка: значения кода, выбранные для представления типов генов, имеют решающее значение. Обращение двух значений может стоить 2000 и более очков.
Здесь снова причина, почему это за пределами моей математики.
Я предполагаю, что вероятности мутации от одного типа к другому должны быть сбалансированы, или, как в матрице Маркова, совокупные вероятности имеют тенденцию ограничивать значения подмножеством, имеющим самые высокие вероятности входящего перехода.
Путь к спасению
Поиск путей значительно сократит количество посещаемых ячеек, позволяя проверять только наиболее вероятные результаты для достижения цели. Таким образом, не только избегаются некоторые частые тупики, но и неправильные цветовые коды также гораздо чаще обнаруживаются ранее.
В результате время сходимости сильно уменьшается.
Тем не менее, это не помогает решить карты, где геном не может дать правильное представление дорожки.
Что делать с дебилами?
Посмотрев визуально на трассу, я понял, почему стратегия по умолчанию, которая пытается двигаться вперед, даже когда кажется, что перед стенами ничего нет, действительно лучше, чем сдерживаться.
«Стены» в действительности могут быть телепортами, которые производят так много неприятных результатов, что геном отображает их как препятствия, которые никогда не будут преодолены, но в редких случаях конкретный случай этого непослушного телепорта может иметь положительный (или, по крайней мере, не смертельный) эффект таким образом, взятие этого вместо того, чтобы двигаться назад, увеличивает шансы найти путь к победе.
Ранняя конвергенция
Мне кажется, что уровень мутаций немного ниже (по крайней мере, для моих грызунов).
Текущее значение 0,01 дает ДНК 37% шансов выжить в неизменном мутационном процессе. Изменение параметра на 0,0227 снижает эту вероятность примерно до 10%.
Я повторил тот же тест (используя фиксированную последовательность случайных семян) с вероятностью 10%.
На многих картах предыдущие неудачи превратились в (ограниченные) успехи. С другой стороны, огромных демографических взрывов было меньше (что имело интересный побочный эффект ускорения вычислений).
Несмотря на то, что очень высокие баллы (один миллион +) были менее частыми, количество более успешных пробежек было более чем достаточно, чтобы компенсировать это.
В итоге среднее значение выросло с 1400+ до 2000.
Установка P на 5%, напротив, дала среднее значение около 600.
Я предполагаю, что частота мутаций была настолько высока, что геном победивших крыс слишком часто превращался в менее эффективные варианты.
Как это работает
С добавленными детекторами телепортов количество неудачных игр (оценка <10) значительно сократилось.
На 2000 пробных запусках было только 1/3 отказов.
Среднее геометрическое значение выросло только с 2900 до 3300, но это число не отражает улучшение.
Пустые цвета часто угадываются как лучи и опасности (обычно от 2 до 5). Геном «использует» эти цвета, чтобы заблокировать пути, из-за которых у крыс могут возникнуть проблемы.
Геном довольно хорошо угадывает ловушки (т. Е. Как только крысы способны достичь цели, цвета, представляющие фактические детекторы ловушек, предполагаются примерно в 90% случаев).
Он также использует новые коды лучей для телепортов, хотя и реже (возможно, потому, что «коварные» телепортеры встречаются реже, чем ловушки, а другие цвета лучей / опасности эволюционируют, чтобы заблокировать путь к последним экземплярам этих предателей).
Судя по количеству игр, в которых победивший геном появляется после 5000 ходов или более, я считаю, что эта новая порода сильно выиграет от увеличения частоты мутаций.
источник
ColorScorePlayer, предварительная оценка ≈ 22
Это бот, которого вы видите на работе в GIF в испытании.
Это был наш тестовый бот на этапе разработки. Он использует геном для хранения показателя качества для каждого из 16 цветов. Затем он делает движение вперед, которое перемещает его в цвет с лучшим счетом (и никогда не перемещается на
-1
). В случае ничьей выбирается случайный ход между ячейками связывания.Мы портировали этот проигрыватель на все языки контроллера, поэтому он служит примером того, как их использовать:
питон
Рубин
C ++
C #
Ява
Игрок забивает довольно непоследовательно. Вот 50 случайных прогонов:
источник
ColorFarSeeker, C ++ ≈ 74,7
Эта задача действительно довольно забавная и простая, если вы попробуете ее.
Не откладывайтесь на длинное описание.
Просто зайдите на GitHub и проверьте все ... все будет намного понятнее! :)
Симулятор C ++ настоятельно рекомендуется для его скорости. Даже после того, как я закончил перевод своей программы на C ++, симуляция Python все еще не остановилась.
Это улучшенный вариант ColorScorePlayer. Чтобы эффективно использовать свое представление 5x5, он рассматривает шаги в 2 шагах от него, используя взвешенную функцию. Шаги на 1 шаг впереди имеют больший вес, так как они оказывают более непосредственное влияние на выживание. Движение на 2 шага впереди дает меньший вес.
Пытается двигаться вперед, но если безопасного движения не видно ... то пытается вбок ... а если все остальное терпит неудачу, перемещается назад случайным образом.
Гол:
Есть довольно много единиц ... которые могут быть немного удручающими, когда вы видите консоль, извергающую 1 после друг друга. Как планета со всем необходимым для жизни, но без признаков продвинутой цивилизации крыс ...
Тогда случайный всплеск. :)
Хм ... видимо, мне повезло в моей первой серии пробежек, получив геометрическую форму 300+. Баллы действительно сильно колеблются. Но в любом случае, с большим количеством прогонов симулятора, он, вероятно, ближе к ≈ 74. (Спасибо за помощь в симуляции и его невероятно быстрой программе)
источник
Епископ - Питон, предварительная оценка 1.901
Епископ всегда движется по диагонали, поэтому половина доски недоступна на данном треке по доске, но это означает, что меньше потенциальных ходов для кодирования, поэтому каждый отдельный бит генома может представлять ход (слон никогда не отступает). Какой бит ссылаться, определяется на основе блока квадратов 3х3 впереди (справа) от образца. Лучший ход в данной ситуации - это всего лишь одна мутация.
Этот бот сначала быстро учится, но потом часто достигает потолка, прежде чем достичь финиша, по-видимому, когда возникает одна из следующих двух проблем:
Код
Несмотря на эти ограничения, в редких случаях епископ преуспевает, с отдельными образцами, заканчивающими несколько кругов доски каждый. Я думал, что на данном круге образец может двигаться только на половине доски (эквивалентно только черным квадратам или только белым квадратам на шахматной доске). Однако, как отметил Мартин Бюттнер, телепортер может перемещать образец из черного квадрата в белый или наоборот, поэтому на большинстве досок они не будут ограничены.
(Есть две пары совпавших типов телепортов, и у каждого есть вероятность 0,5 смещения, которое перемещает образец в другую половину черного и белого квадратов. Таким образом, вероятность того, что на доске есть только телепорты, ограничивающие образец одним половина доски за круг составляет всего 0,25.)
Очки показывают, что случайные победы чередуются с длительными периодами, не дотягивающими до финиша:
источник
Игрок с призовым бонусом: среднее геометрическое 50,35 (тест на 5000 игр)
Этот бот подсчитывает квадраты по отдельным цветам на основе 6-битной секции ДНК, как у игрока с цветовой шкалой, но с другой системой счисления. Этот бот был мотивирован мыслью, что довольно произвольно, что один из битов изменяет значение оценки на 32, а другой - только на 1. Он присваивает значение n (n + 1) / 2 серии n последовательных 1 бит. Кроме того, он добавляет механизм рандомизации в попытке избежать застревания. Это сделает случайное движение вперед с вероятностью 1 к 30.
Для сравнения, игрок с цветовой шкалой набрал от 30 до 35 баллов в паре тестов из 1000 игр. Интересно, что максимальный игровой счет игрока с цветовой шкалой находился в диапазоне 3-5 миллионов, а максимальный бонус за бег - всего 200 тысяч. Бонус за прогон выигрывает от логарифмической средней системы подсчета очков, получая ненулевой результат более последовательно.
Запуск 5000 игр занял около 20 минут с 6 потоками на контроллере C ++.
источник
StarPlayer | C ++ | Оценка: 162 (на основе 500 пройденных игр)
Этот игрок пытается использовать A *, чтобы найти лучший путь вперед. Он назначает веса таким же образом, как ColorScorePlayer, и пытается найти путь к правому краю представления. Реализация не самая красивая, которую я когда-либо делал, но она не слишком медленная, по крайней мере.
Примерные оценки:
источник
WallGuesser - набрал 113,266 в тесте 1000 игр
кодирование
Я сделал действительно простое 6-битное / цветное кодирование. Расшифровать цвет [n]
Распределяя биты для цвета по всему геному, я увеличиваю вероятность того, что биты от обоих родителей будут использоваться для каждого цвета.
движение
Я использую (я уверен, что не очень эффективный) поиск на основе *, чтобы найти путь с наименьшей стоимостью к любому из квадратов правого края. Если цвет отображается как «заблокированный», то он никогда не будет введен при поиске. Если поиск не может найти путь, он предполагает, что эта крыса не подходит для воспроизведения, и пытается закончить его, перемещая один влево.
Уменьшение количества непригодных крыс
Поскольку мой геном эффективно угадывает, какие квадраты являются настенными или отсталыми телепортами, крысы, у которых нет догадок (нет цветов, которые отображаются на заблокированные), не очень подходят. Чтобы попытаться удалить этих крыс, если ни один цвет не будет помечен как заблокированный, тогда КАЖДЫЙ цвет помечается как заблокированный, и крыса всегда будет перемещаться на одну влево.
СДЕЛАТЬ
В настоящее время в поведении нет случайности, поэтому крысам легко застрять.
источник
g++ -std=c++11 .\wallguesser.cpp -O2 -o .\wallguesser.exe
. Я получаю много ошибок, но первая.\wallguesser.cpp:47:19: error: 'dna_t' has no member named 'at' if (d.at(i) == true){
at
чтобы[]
исправить это.FITTEST - средний геометрический балл: ~ 922 (2K пробежек)
Мой подход заключается в следующем:
Я протестировал более 2000 наборов параметров с теми же 50 семенами. Наиболее многообещающие наборы были отобраны и были оценены с использованием 250 идентичных семян, а наборы с самым высоким рангом были введены для следующего раунда теста. Поэтому мне удалось создать генетический алгоритм, чтобы найти оптимальный генетический алгоритм для этой проблемы, как это было предложено пользователем mbomb007 .
Желаемое поведение:
Методы хранения данных:
Мы хотим, чтобы виды научились чему-то, адаптировались к окружающей среде и стали наиболее приспособленными. Это неизбежно работает только в том случае, если обучение можно как-то сохранить. Обучение будет «сохранено» в 100 битах ДНК. Это странный способ хранения, потому что мы не можем изменить ценность нашей ДНК. Итак, мы предполагаем, что ДНК уже хранит информацию о плохих и хороших ходах. Если для определенного вида правильная информация хранится в его ДНК, он будет быстро двигаться вперед и производить много новых видов с его ДНК.
Я выяснил, что среднее геометрическое значение чувствительно к тому, как хранится информация. Предположим, мы читаем первые 4 бита из 100 бит ДНК и хотим сохранить это в целочисленной переменной. Мы можем сделать это несколькими способами:
dnarange
функции, пример: 4 биты1011
станут `1x2 ^ 3 + 0x2 ^ 2 + 1x2 ^ 1 + 1x2 ^ 0 = 15. Возможные значения (для 4 бит): [0, 1 , 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15]dnaStreakRange
штрихов : с помощью функции (определенной ниже), например: 4bit 1011 станет1x1 + 0x1 + 1x1+ 1x2 = 4
. Возможные значения (для 4 бит): [0, 1, 2, 3, 6, 10]dnaCountRange
функции (определенной ниже), например: 4bit 1011 станет1x1 + 0x1 + 1x1 + 1x1 = 3
. Возможные значения (для 4 бит): [0, 1, 2, 3, 4]Разница между способами хранения:
Приоритет решения.
Когда ColorScorePlayer определил два движения вперед с одинаковыми баллами, делается произвольный выбор. ИМХО, вы никогда не должны использовать функцию случайной
v.rng.rint()
функции . Вместо этого вы должны использовать эту возможность равных баллов в качестве ловушки для оценки решений для эффектов второго порядка.Эффект первого порядка получает наивысший приоритет. Если достигнуты равные баллы, преобладает решение с приоритетом 2 и так далее. Изменяя параметры решения, вы можете повлиять на вероятность того, что произойдут равные оценки, и таким образом изменить вес решений с приоритетом 1 и приоритетом 2.
Реализация желаемого поведения
Узнайте, какие цвета безопасны:
threshold = 63/3=21
, где 63 - максимальный балл для 6 битов и 33% = 1/3 (можно посмотреть на графике выше).Если хороших ходов нет, двигайтесь вертикально или назад:
weightMove
переменной.Посмотрите, что находится за пределами:
x2
иy2
зацикливаться), какой вариант лучше (черезmainSubScore
переменную). Самый правый столбец в этом квадрате 3x3 является ведущим.Определить ловушки:
Я исследовал ДНК вида с наивысшей оценкой, когда произвольная игра завершилась с использованием хранилища битов (так что цветовая шкала имеет диапазон [0,4]):
Из этого можно сделать вывод, что стены и телепорты получают правильную оценку. Ловушки не идентифицируются, поскольку они зависят от направления и цвета источника, тогда как оценка производится по цвету пункта назначения. Поэтому необходимо также хранить данные о цвете происхождения, поэтому
v(0,0)
. В идеальном мире мы хотели бы хранить информацию для 16 цветов x 8 направлений x 3 бита = 384 бита.К сожалению, доступно только 100 бит, и мы не можем использовать все это, так как нам также нужно немного памяти для решения, описанного выше. Поэтому мы сделаем 4 цветных бункера:
и 4 корзины направления движения
Когда десятичная оценка равна 4 или выше (100 101 101 110 111), предполагается, что ловушка связана с этой ячейкой, в результате этот ход не будет выбран при возникновении равных оценок. Таким образом, идентификация ловушек - это эффект второго порядка, а «посмотри, что дальше» будет решением с третьим приоритетом.
Неправильное предположение о стене многократно повторяется дебилами на новорожденных:
Некоторые виды ошибочно полагают, что стены хороши, и пытаются все время двигаться к ним и поэтому застревают перед стенами. Они также могут застрять в бесконечных петлях телепортов. Эффект одинаков в обоих случаях.
Основная проблема заключается в том, что после нескольких сотен итераций некоторые гены становятся очень доминирующими . Если это «правильные» гены, вы можете получить очень высокие оценки (> 1 млн. Баллов). Если это не так, вы застряли, так как вам нужно разнообразие, чтобы найти «правильные» гены.
Борьба дебилов: Решение 1: инверсия цвета
Первое решение, которое я попробовал, было попыткой использовать часть неиспользуемой памяти, которая все еще очень разнообразна. Предположим, вы выделили 84 бита в свою цветовую память и память поиска ловушек. Остальные 16 бит будут очень разнообразными. Мы можем заполнить 2 десятичные8 переменных, которые имеют значения в интервале [0,255], и они являются однородными, что означает, что каждое значение имеет вероятность 1/256. Будут называться переменные
inInverse
иinReverse
.Если
inInverse
равно 255 (шанс 1/256), то мы будем инвертировать интерпретацию цветовых показателей . Таким образом, стена, которую придурок считает безопасной из-за высокой оценки, получит низкую оценку и, следовательно, станет плохим ходом. Недостатком является то, что это также повлияет на гены «прав», поэтому у нас будет меньше очень высоких результатов. Кроме того, этотinInverse
вид должен будет размножаться сам, и его дети также получат части доминирующей ДНК. Наиболее важной частью является то, что он возвращает разнообразие.Если
inReverse
равно 255 (шанс 1/256), то мы изменим порядок хранения позиций цветовых показателей . Поэтому до того, как цвет 0 был сохранен в битах 0-3. Теперь цвет 15 будет сохранен в этой позиции. Разница сinInverse
подходом заключается в том, чтоinReverse
воля отменит проделанную до сих пор работу. Мы вернулись на круги своя. Мы создали вид, который имеет схожие гены, как и в начале игры (за исключением памяти для поиска ловушек)С помощью оптимизации опробовано , если разумно использовать
inInverse
иinReverse
в то же время. После оптимизации был сделан вывод, что оценка не увеличилась. Проблема в том, что у нас более разнообразная популяция генов, но это также влияет на «правильную ДНК». Нам нужно другое решение.Борьба дебилов: Решение 2: хэш-код
У вида есть 15 возможных стартовых позиций, и в настоящее время существует слишком большой шанс, что он пойдет точно по тому же пути, если он стартует в той же стартовой позиции. Если он придурок, который любит стены, он будет снова и снова застревать на одной и той же стене. Если ему, по счастливой случайности, удастся достичь далеко впереди стены, он начнет доминировать в пуле ДНК со своими ошибочными предположениями. Нам нужно, чтобы его потомки пошли по несколько иному пути (поскольку для него все равно слишком поздно) и не застрянут на дальней стене, а на более близкой стене . Это может быть достигнуто путем введения хеш-кода .
Хэш - код должен иметь цель , чтобы однозначно идентифицировать и маркировать текущее положение на доске. Цель не в том, чтобы узнать, какова позиция (x, y), а в том, чтобы ответить на вопросы, были ли мои предки раньше в этом месте?
Предположим, у вас перед вами будет полная доска, и вы будете делать jpg каждого возможного квадрата 5 на 5 ячеек. В итоге вы получите (53-5) x (15-5) = 380 изображений. Давайте дадим этим изображениям номера от 1 до 380. Наш хэш-код должен рассматриваться как такой идентификатор, с той разницей, что он не работает от 1 до 330, но в нем отсутствует IDS, например, 563, 3424, 9424, 21245 и т. Д.
Простые числа
17
и31
находятся там, чтобы предотвратить исчезновение информации, добавленной в начале цикла. Позже подробнее о том, как интегрировать наш хэш-код в остальную часть программы.Заменим механизм подсчета «посмотри, что выходит» на другой механизм подсчета. Когда две или три ячейки имеют одинаковые основные оценки, вероятность того, что верхняя будет выбрана, будет равна 50%, вероятности выбора нижних ячеек - 50%, а средней - 0%. Шанс будет определяться не случайным генератором, а битами из памяти , поскольку таким образом мы гарантируем, что в той же ситуации будет сделан тот же выбор.
В идеальном мире (где у нас бесконечное количество памяти), мы вычислим уникальный хэш-код для нашей текущей ситуации, например, 25881, и перейдем в ячейку памяти 25881 и прочитаем там, если мы должны выбрать верхнюю или нижнюю ячейку (когда там равный счет). Таким образом, мы окажемся в точно такой же ситуации (когда мы, например, переместимся на доску во второй раз и начнем с одной и той же позиции), примем одинаковые решения. Поскольку у нас нет бесконечной памяти, мы будем применять модуль хеш-кода по модулю размера доступной памяти . Текущий хэш-код хорош в том смысле, что распределение после операции по модулю является однородным.
Когда потомок путешествует по той же доске со слегка измененной ДНК, он в большинстве случаев (> 99%) принимает точно такое же решение. Но чем дальше он продвигается, тем больше вероятность того, что его путь будет отличаться от его предков. Так что вероятность того, что он застрянет на этой далеко идущей стене, невелика. Хотя застрять на той же ближайшей стене, что и его предок, относительно велика, но это не так уж и плохо, так как он не будет производить много потомства. Без подхода с использованием хэш-кода вероятность застрять на ближайшей и удаленной стене практически одинакова
оптимизация
После оптимизации был сделан вывод, что таблица идентификации ловушек не нужна и достаточно 2 бит на цвет. Остальная часть памяти 100-2х16 = 68 бит используется для хранения хеш-кода. Кажется, что механизм хеш-кода способен избежать ловушек.
Я оптимизировал для 15 параметров. Этот код включает лучший набор параметров (пока что):
Это моя самая первая программа на C ++. У меня, как и у большинства из вас, сейчас опыт в гномическом анализе. Я хочу поблагодарить организаторов, так как мне очень понравилось работать над этим.
Если у вас есть какие-либо отзывы, пожалуйста, оставьте комментарий ниже. Извиняюсь за длинные тексты.
источник
Pathfinder, C ++, предварительная оценка 35,8504 (50 раундов)
Капитальный ремонт! Я перенес свой алгоритм на C ++ и немного подправил его, но результат все еще не очень высок, вероятно потому, что крысы продолжают биться головой о стены. Я устал от попыток улучшить это, поэтому я просто позволю этому быть сейчас.
объяснение
Общая идея состоит в том, чтобы классифицировать каждый цвет как ловушку или нет, затем назначать направления для ловушек и веса для не-ловушек и пытаться следовать по пути минимального веса к правой границе сетки видения.
В первых 80 битах генома каждый цвет классифицируется с использованием 5 битов
abcde
. Еслиab = 01
цвет является ловушкой, иcde
кодирует его направление (восемь возможностей). Еслиab ≠ 01
цвет не ловушка, а его весa + b + 2*(c + d + e)
.Затем мы инициализируем сетку 3х7, которая представляет поле зрения крысы справа, дополненное «неизвестными» цветами. Биты 80-84 кодируют вес неизвестных ячеек аналогично цветам без ловушек, а биты 85-89 кодируют общий вес для ловушек. Мы заполняем сетку весами, вычисляем кратчайшие пути и добавляем некоторый дополнительный вес (закодированный в битах 90-95) в ячейки непосредственно над и под крысой, чтобы препятствовать обходу. Биты 95-99 кодируют целевой вес, Если минимальный вес пути ниже его, крыса, вероятно, где-то застряла и продолжает двигаться случайным образом (но никогда не возвращается). В противном случае следует минимальный весовой путь. С небольшой вероятностью, зависящей от веса, предотвращающего боковые шаги, крыса вместо этого выбирает путь веса со вторым минимальным весом. Это сделано для того, чтобы не застрять на стенах (но сейчас это не очень хорошо работает).
источник
LookAheadPlayer C ++ ≈ 89.904
Моей первоначальной мыслью было найти 4 бита, которые соответствуют цвету, который я искал, и использовать следующие несколько бит в качестве оценки. Это оказалось ужасной идеей, вероятно, из-за мутаций.
Поэтому я подумал о способах защиты от мутаций и кроссоверов, и это напомнило мне о работе, которую я проделал над декодированием QR-кода. В QR-кодах данные разбиваются на блоки и чередуются, чтобы избежать ошибок, связанных с уничтожением слишком большой части данных.
Поэтому, как и ColorScorePlayer, я разрезал ДНК на 16 кусков и использовал их в качестве заданного значения. Однако оценки чередуются так, что отдельные биты каждой оценки не являются смежными. Затем я суммирую количество текущих возможных ходов и следующих возможных ходов и выбираю лучший ход, который нужно сделать.
Примечание: это было закодировано / протестировано на MinGW. Он не будет компилироваться с оптимизацией или с многопоточностью. У меня нет реальной установки Linux или Visual Studio, удобной для использования компилятора, где они будут работать. Завтра утром я собираюсь быстро его протестировать, но, пожалуйста, дайте мне знать, если у вас возникнут какие-либо проблемы.
источник
SlowAndSteady C ++ (оценка 9,7)
Мы не можем полагаться на интерпретацию фрагментов генома как чисел, потому что один переворот может иметь радикально разные эффекты в зависимости от его положения. Вот почему я просто использую 16 6-битных сегментов и оцениваю их по количеству
1
s. Первоначально111111
было хорошо и000000
было плохо, и хотя это не имеет значения в долгосрочной перспективе (после того, как геном полностью эволюционировал), в начальной конфигурации ДНК большинство сегментов имеют 2-4, поэтому я перешел на использование9 - (#1 - 3)^2
для подсчета, это обеспечивает гораздо большую свободу передвижения в первых раундах и ускоряет эволюцию.Прямо сейчас я смотрю только на 7 ближайших соседей, добавляю смещение направления к цветовой шкале и двигаюсь в одном из самых высоких направлений случайным образом.
Хотя сам счет не очень высок, мои твари достигают финиша и набирают> 1 в 3/4 случаев.
И пример выигрыша на 100 досках
Средний геометрический балл: 9,76557
источник
WeightChooser | C # | Результаты: 220,8262 в 1520 играх
Вычисляет вес для возможного следующего хода (синий) на основе среднего веса возможных последующих ходов (желтый)
источник
Крысы в действии (не ответ, а графический инструмент для ботов C ++)
С самого начала этого испытания у меня были трудности с выяснением того, с чем на самом деле сталкивались крысы на трассе.
В конце я взломал контроллер и написал вспомогательный инструмент, чтобы получить некоторое графическое представление трека.
В конце концов я сделал еще несколько взломов и добавил визуализацию возможных путей ДНК данной крысы.
Карта чрезвычайно загромождена и требует некоторого привыкания, но мне было очень полезно понять, как работают мои боты.
Вот пример:
Вам, вероятно, понадобится увеличить изображение, чтобы увидеть что-нибудь, так что вот только первая половина:
Сначала давайте посмотрим на пути крысы. Существует один путь для каждого возможного начального местоположения (обычно 15, иногда немного меньше). Обычно они имеют тенденцию сливаться, в идеале приводя к единой победной локации.
Пути представлены большими прямыми стрелками. Цвет описывает результат:
В этом примере у нас 12 выигрышных стартовых позиций, одна из которых ведет к бесконечному циклу, а две - к изнурительной смерти (будучи телепортированным в ловушку, как кажется).
Прерывания пути происходят из-за телепортации, которой вы можете следовать с помощью соответствующих изогнутых стрелок.
Теперь о цветных символах. Они представляют значение 16 цветов (серые представляют то, что видит крыса).
пустые цвета ... ну ... пустые.
У телепортеров есть исходящие стрелки, указывающие на их пункт назначения.
Детекторы ловушек также имеют стрелки, указывающие ловушку, которая обозначена красным кружком.
В одном случае из 9 ловушка расположена в той же ячейке, что и ее детектор, и в этом случае вы увидите маленький октогон поверх красного круга.
Это случай бледно-желтой ловушки в этом примере.
Вы также можете увидеть лиловые детекторы ловушек, указывающие вниз на указанную ловушку.
Обратите внимание, что иногда красный круг ловушки будет скрыт под стеной. Оба смертельны, поэтому результат в случае телепортации одинаков.
Также обратите внимание, что ловушка может быть расположена на телепорте, и в этом случае телепорт имеет преимущество (т.е. крыса телепортируется перед тем, как попасть в ловушку, что фактически нейтрализует ловушку).
Наконец, серые символы представляют то, что видят мои крысы (то есть значение их геномных атрибутов для цветов).
По сути, все клетки, сидящие на сером квадрате, считаются крысами стенами.
Большие X представляют клетки, рассматриваемые как ловушки, с соответствующими октогонами, указывающими детектор, сообщивший о них.
В этом примере обе стены идентифицированы как таковые, как и бледно-желтая ловушка (действительно указывающая на смертельную клетку, поэтому правильное представление ее как стены).
Детектор сиреневых ловушек был идентифицирован как таковой (он расположен на сером восьмиугольнике), но местоположение ловушки неверно (вы можете видеть, что у некоторых красных кружков нет крестиков под ними).
Из 4 телепортеров 2 считаются стенами (бирюзовый и желто-коричневый), а 2 - пустыми клетками (красноватые и желтоватые).
Несколько пустых ячеек считаются ловушками или стенами. Присмотревшись внимательно, вы можете увидеть, что эти «неисправные детекторы» действительно запрещают вход в клетки, которые могут привести к проблемам у крысы, поэтому даже если они не соответствуют реальным цветам, у них есть определенная цель.
Код
Ну, это беспорядок, но он работает довольно хорошо.
Исходя из кода игрока, я добавил только один интерфейс: функция трассировки, используемая для сообщения о значении данной ДНК. В моем случае я использовал 3 типа (стена, детектор ловушек и пустой), но вы можете в основном выводить что-либо, связанное с цветом (или вообще ничего, если вы не хотите графики, связанной с геномом).
Я взломал контроллер, чтобы сгенерировать огромную строку символов, сопоставляющую описание дорожки и цвета с «пробным прогоном» ДНК крысы из всех возможных мест.
Это означает, что результаты будут действительно значимыми, только если бот не использует случайные значения. В противном случае отображаемые пути будут представлять только один возможный результат.
Наконец, все эти следы помещаются в большой текстовый файл, который позже читается утилитой PHP, которая производит графический вывод.
В текущей версии я делаю снимок каждый раз, когда крыса умирает после достижения новой максимальной пригодности (которая довольно хорошо показывает прогрессивное уточнение генома, не требуя слишком много снимков), и окончательный снимок в конце игры (который показывает самая удачная ДНК).
Если кому-то интересно, я могу опубликовать код.
Очевидно, что это работает только для ботов C ++, и вам нужно будет написать функцию трассировки и, возможно, изменить код PHP, если вы хотите отобразить некоторые специфичные для генома данные (серые цифры в моем случае).
Даже без информации, специфичной для ДНК, вы можете без особых усилий увидеть пути, по которым идет ваша ДНК, на данной карте.
Почему промежуточный выход?
Прежде всего, C ++ не имеет приличной переносимой графической библиотеки, особенно при использовании MSVC. Даже если сборки Win32 обычно доступны, они часто приходят в качестве запоздалой мысли, а количество внешних библиотек, пакетов и других необходимых unix-подобных тонкостей делает написание простого и быстрого графического приложения ужасной болью в части тела, которую порядочность мешает я от имени.
Я рассматривал возможность использования Qt (о единственной среде , что делает портативный GUI / графическое развитие в C ++ просто и даже приятно задач, ИМХО - вероятно , потому что это добавляет систему обмена сообщениями а - ля Objective C , что C ++ катастрофически не хватает , и делает невероятную работу ограничивающего памяти управления до минимума), но это выглядело как излишнее решение стоящей перед нами задачи (и любой, кто хотел бы использовать код, должен был бы установить biggish SDK - вряд ли это стоило бы усилий, я думаю).
Даже если принять переносную библиотеку, не нужно говорить о скорости (примерно одной секунды для создания изображения достаточно), и с ее общеизвестной жесткостью и присущей ей запутанностью C ++, безусловно, не лучший инструмент для работы.
Кроме того, наличие промежуточного текстового вывода добавляет большую гибкость. Как только данные есть, вы можете использовать их для других целей (например, анализируя производительность ботов).
Почему PHP?
Я нахожу язык чрезвычайно простым и адаптируемым, очень удобным для создания прототипов. Я сделал это своим любимым языком для задач кода, которые не требуют экстремальных характеристик.
Это ужасный язык для игры в гольф, но гольф все равно никогда не был моей чашкой чая.
Я полагаю, что python или Ruby было бы так же приятно использовать для тех же целей, но у меня никогда не было возможности поработать с ними серьезно, и в последнее время я работал над веб-сайтами, так что PHP это так.
Даже если вы не знаете язык, не должно быть слишком сложно изменить код в соответствии с вашими потребностями. Только не забывайте
$
s перед переменными, как в старые добрые базовые дни :).источник
SkyWalker - Python - результаты менее 231 в 50 играх
Итак, сначала код, а затем несколько пояснений. Я надеюсь, что ничего не сломалось при копировании.
Некоторое объяснение
На мой взгляд, главное отличие в том, что я не кодирую каждый цвет. Вместо этого я стараюсь сохранить количество цветов, которые важны. На мой взгляд, эти цвета - ловушки, стены и телепорты. Образцу не нужно знать цвет хорошей клетки. Поэтому мой геном структурирован следующим образом.
Это составляет в общей сложности 52 используемых бита. Однако я использую только первый бит из трех решателей телепортов (я проверяю, больше ли число 3). Таким образом, другие 2 могут быть удалены, в результате чего у меня будет использоваться 44 бита.
На каждом ходу я проверяю каждое поле моего зрения, если это один из плохих цветов (+ вне поля -1), и добавляю его в список полей, в которые образец не хочет перемещаться. В случае ловушки я добавляю поле с сохраненным смещением для этого цвета ловушки.
На основе списка этих плохих полей рассчитывается следующий ход. Порядок предпочтительных полей:
Если два поля категории применимы, одно выбирается случайным образом.
Результаты
мысли
Я понятия не имею, повезло ли мне с 50 пробежками или есть ли какая-то мудрость в моей стратегии.
Мои пробежки, кажется, никогда не взлетают и получают супер высокие баллы, но они также стремятся найти хотя бы несколько раз цель
Небольшая случайность хороша, чтобы не застрять в ловушке где-то ближе к концу гонки
Я думаю, что не специальные цвета никогда не бывают плохими. Однако их экземпляры могут быть плохими, когда они находятся на смещении ловушки. Таким образом, маркировка цвета плохо, если это не ловушка, стена или плохой телепорт, не имеет смысла.
Стены - величайшие враги
улучшения
Во-первых, даже при том, что я не буду видеть, как черные квадраты все ближе и ближе к цели, порт C ++ необходим для проведения большего количества тестов и получения более значимого результата.
Одна из основных проблем заключается в том, что если перед крысой появляются плохие клетки (или те, которые образец считает плохими), он легко начинает двигаться вверх и вниз по кругу. Это может быть остановлено или уменьшено, если смотреть в этих случаях на 2 шага вперед и помешать ему переместиться в поле, где он просто снова вернется.
Часто проходит довольно много времени, пока крыса с хорошими генами достигает цели и начинает распространять ее гены. Может быть, мне нужна стратегия для увеличения разнообразия в этих случаях.
Так как телепорты трудно подсчитать, возможно, мне следует разделить население на тех, кто рискован, и всегда брать хороших телепортов и тех, кто более обеспокоен, и брать их только в том случае, если другого выбора нет.
Я должен как-то использовать вторую половину моего генома.
источник
self.bit_chunk(16, 4)
иself.bit_chunk(20, 4)
имеют оба значения,0010
вы фактически сохранили информацию только об одной из двух ловушек.itervalues
наvalues
.Python, NeighboursOfNeighbors, счет = 259,84395 более 100 игр
Это вариант ColorScorePlayer. Каждые 6 бит хранят показатель качества для квадрата. Когда бот делает ход, он оценивает каждый из 3 квадратов вперед - по диагонали вверх, вперед и вниз. Оценка - это качество квадрата плюс половина среднего качества следующих 3 квадратов. Это дает боту некоторый взгляд вперед, не подавляя качество первого квадрата. Алгоритм похож на LookAheadPlayer, который я не видел до написания этого решения.
источник
else None
кelse 0
на предыдущей строке , чтобы вычислить ваш счет. Надеюсь, это оставит вашу логику без изменений (я не внес изменений в ваш код здесь, на SE, кроме добавления потерянного отступа).ROUS (Грызун необычного размера), Java, счет = 0
Это окружает, чтобы решить, куда идти.
Из-за неработающего контроллера Java у меня нет баллов за это. Это будет очень далеко, только если он найдет несколько телепортов, чтобы помочь ему.Это имеет тенденцию вымирать и сбивать контроллер время от времени. Вероятно, это связано с тем, что природной средой является Огненное Болото.источник
Серо-цветной взгляд (C ++, ~ 1.35)
Этот не очень хорошо в среднем, но в редких случаях он работает блестяще. К сожалению, мы получаем средние геометрические показатели (1,35), а не максимальные (20077).
Этот алгоритм работает, просто используя 4-битные коды серого для отображения оценки каждого цвета где-то от -2 до 2 (с уклоном в сторону диапазона [-1..1]), и вычисляет оценку плитки каждого хода и его следующих ходов , Он также использует 2-битный серый код, чтобы определить множитель для самого тайла, а также коэффициент смещения для перемещения вправо. (Серые коды гораздо менее восприимчивы к большим скачкам из-за мутаций, хотя на самом деле они не оказывают никакого влияния на пересечение средней точки кода ...)
Он также абсолютно ничего не делает для того, чтобы пытаться обрабатывать ловушки специально, и я подозреваю, что это может привести к падению (хотя я не добавил никаких инструментов в контроллер для проверки этой теории).
Для каждого возможного хода он определяет счет, и среди всех ходов с наибольшим количеством очков он выбирает случайным образом.
В моем последнем заезде я получил очки: 1 1 1 1 1 1 1 46 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 20077 1 1 1 2 1 1 1 1 1
Я хотел бы получить больше из 20077-х и меньше из 1-х. :)
источник
C ++, TripleScore, счет: 100 ~ 400
Во-первых, мой результат сильно различается за несколько запусков (в основном из-за количества единиц).
Ядро рассчитывает оценку по 5 направлениям: вверх, вниз, вперед-вверх, вперед и вниз-вниз. Сначала вычисляются оценки «вверх» и «вниз», затем результаты сравниваются со стоимостью пребывания на месте. Если оставаться на месте лучше, чем двигаться вверх или вниз, эти направления не будут выбраны (поэтому они должны идти вперед). Это необходимо для предотвращения подпрыгивания (вверх, вниз, вверх, вниз, ...) между двумя точками.
Теперь оцениваются 3 других направления: вперед-вверх, прямо вперед и вниз-вниз. Со всех исследованных направлений сохраняются те, кто набрал наибольшее количество баллов, и 1 из них выбирается случайным образом.
Скоринг направления: TripleScore рассчитывает счет движения, используя 3 подсчета:
Как и в случае с другими ответами, оценка в значительной степени зависит от количества возвращаемых 1-баллов.
источник
Ruby - вероятностныйScorePlayer
Эта крыса с высокой степенью недетерминированности вычисляет вероятность попадания в пространство по соседству. Первые 16 слотов в геноме представляют 16 цветов. 1 в слоте означает, что цвет хорош для перехода, 0 означает плохой. Следующие 16 держат то же самое для пространства перед вашей целью и так далее.
Основным преимуществом вероятностного подхода является то, что практически невозможно долго застрять за стеной. Недостатком является то, что вы почти никогда не получите почти идеальную крысу.
источник
c
начальное значение? Кажется, он не определен при первом использованииif
.coords
это не список, вы используете&&
вместо негоand
и забываете скобки, и даже после исправления всего этого вы не ограничиваете значения ГСЧ, поэтому получаете пустое направление. Это псевдокод, или что-то, предназначенное для работы с каким-то Ruby-диалектом?Java, RunningStar, Score = 1817.050970291959 более 1000 игр
Этот бот использует цветовое кодирование Run-Bonus с техникой StarPlayer .
Обновление: исправлен контроллер Java.
источник
Прыжок вперед, Python 2
Не особенно новаторский, но это моя единственная попытка, которая прошла хорошо.
В основном, это кодирует четыре цвета (каждый 4 бита), чтобы избежать, в геноме. Затем он переходит к цвету, которого нет в этом списке. Если все цвета плохие, он все еще прыгает вперед к неизвестному.
источник
Java - IAmARobotPlayer - Оценка 3,7
Я только что создал эту крысу-робота для сравнения с другой (пока не очень интересной) программой, которую я сделал. В целом он не очень хорошо забивает, но если он где-то забьет, он получит много крыс. Идея состоит в том, что он будет смотреть только на три клетки перед собой, каждая клетка хорошая или плохая. Это дает двоичное число. Затем он будет искать это число в своем геноме, брать три последовательных бита, также преобразовывать их в число и выполнять действие, которое хранится под этим номером. Так что он всегда действует одинаково, когда сталкивается с одной и той же ситуацией.
Результат:
источник
Осторожные образцы - C ++ - оценка около 2030 за 200 пробежек
При этом используется цветная часть (16x4 бита) кодировки ДНК из Blind Faith, но остальная часть (36 бит) ДНК полностью не используется.
Кодировка для цвета:
Где Х обозначает неиспользованные биты. Учитывая, что только 2 из 16 цветов являются ловушками, которые будут использовать все 4 своих бита (и только если ловушка смещена, что будет иметь место 8 из 9 раз), то обычно будет 64 неиспользованных бита - теория состоит в том, что мутации, которые затрагивают любой из этих неиспользованных битов, не повредят геному, и стабильность лучше, чем любые причудливые решения, которые могут использовать эти оставшиеся биты.
Затем образцы используют это, чтобы спланировать безопасный маршрут в пределах сетки 7x7, центрированной на самих себе (5x5, на которую они видят, плюс 1 квадрат с каждой стороны, чтобы учесть смещенные ловушки), отдавая приоритет перемещению наибольшего расстояния вперед после 3 ходов.
Первоначально я начал строить некоторые проверки, чтобы убедиться, что тот факт, что цвет, на котором находится образец, не является летальным, соответствует геному и помечает любые ошибочные цвета как квадраты НЕИЗВЕСТНОЙ безопасности (и смежные с ними квадраты) - однако это добавило значительный сложность из-за незначительного выигрыша по сравнению с тем, чтобы пометить эти квадраты как БЕЗОПАСНЫЕ и убить несколько дополнительных образцов. Я вернусь к этому, если у меня будет время.
Примерные результаты:
Максимальный балл за время тестирования: 8 150 817 экземпляров сохранено.
источник