Хабр Курсы для всех
РЕКЛАМА
Практикум, Хекслет, SkyPro, авторские курсы — собрали всех и попросили скидки. Осталось выбрать!
Хабр доступен 24/7 благодаря поддержке друзей
Комментарии 26
Не играл в ВОВ, но если я правильно понял, это та же головоломка, что в братьях пилотах на открытие сейфа. Можно одно состояние представить 1, второе ноль и рассматривать четность КРЕСТОВ. То есть все поле должно быть либо четным либо нечетным, то ищем например нечетные кресты (сумма всех элементов нечетные) и меняем его. И задача решается за минимальное число шагов.
p.s. о чем речь идет в статье я не совсем понял, жесть какая-то :)
p.s. о чем речь идет в статье я не совсем понял, жесть какая-то :)
Нет, походу тут немного другая головоломка. В братьях пилотах вся строка и весь столбец менялись на противоположные.
Помню та головоломка имела занятное решение «в лоб», может именно его вы и описали — достаточно было записать состояние всех, например, вертикальных переключателей, а потом 2 раза прощелкать по ним по порядку, не задумываясь что происходит на поле, и все открывалось. Не знаю важен ли там порядок, но такое решение помогло наконец уровень пройти, ибо детских мозгов на решение не хватало…
Школьный портал habrahabr.ru не перестает радовать оригинальными исследованиями…
https://en.wikipedia.org/wiki/Lights_Out_(game)
https://en.wikipedia.org/wiki/Lights_Out_(game)
Вы, уважаемый, читать не умеете. Суть не в том, что бы решить задачу, а в написании генетического алгоритма поиска решения. Но за ссылку спасибо, добавлю в статью
Присоединяюсь к комментарию — это классическая игра, есть множество реализаций и алгоритмов решения.
Генетический алгоритм — это хорошо, но всему свой инструмент. Можно, например, с помощью машинного обучения определять четность числа, но… зачем?
Генетический алгоритм — это хорошо, но всему свой инструмент. Можно, например, с помощью машинного обучения определять четность числа, но… зачем?
Похоже, у вас вместо генетического алгоритма получился поиск в глубину («генотипы» у вас кодируют не решения головоломки, а перебираемые состояния игрового поля). Это просто полный перебор с небольшой эвристикой.
При этом получившееся решение, в отличие от полного перебора, теоретически может ещё и не закончиться: например, если среди существ останутся только те, у которых недостаёт 3 или 5 нулей, при этом из них нет решения в один ход. Тогда любая мутация приведёт к тому, что фитнесс-функция окажется не больше (а можно выбрать позиции так, что и меньше) и потомство отправится в утиль.
С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой, но это принципиально и концептуально разные алгоритмы, причем тут нет графа, мы просто мутируем матрицу в определенной последовательности. Была идею сделать это рандомно, но как-то руки не дошли
«С таким успехо даже алгоритм А-звезда, можно назвать поиском в глубину с эвристикой» — именно этим он и является. А ваше решение вообще никакого отношения к генетическим алгоритмам не имеет, вы просто некоторым объектам в вашем коде дали «генетические» названия, а потом добавили эвристику, отрезающую от дерева обхода фактически случайные ветки (необоснованные задачей, но обоснованные заблуждением о том, что что ветки дерева состояний игрового поля — это особи). И фтинесс-функция у вас не несёт никакого смысла (всё потому же — особей-решений у вас нет, есть только варианты состояния поля). ЭТО НЕ ГЕНЕТИЧЕСКИЙ АЛГОРИТМ. Постарайтесь принять факт своего заблуждения, это же не катастрофа.
Вот та же мысль возникла при чтении.
В генетическом алгоритме мы меняем и сравниваем те объекты, для которых нужно найти оптимальное состояние. И это состояние и является искомым само по себе, какими мутациями алгоритм к нему пришёл — не принципиально.
А здесь искомое состояние уже известно — это матрица из нулей, а нас интересует именно то, как к ней прийти.
Вообще, попытка применения ГА к данной задаче вызывает ассоциацию с известным рисунком про троллейбус из буханки хлеба.
В генетическом алгоритме мы меняем и сравниваем те объекты, для которых нужно найти оптимальное состояние. И это состояние и является искомым само по себе, какими мутациями алгоритм к нему пришёл — не принципиально.
А здесь искомое состояние уже известно — это матрица из нулей, а нас интересует именно то, как к ней прийти.
Вообще, попытка применения ГА к данной задаче вызывает ассоциацию с известным рисунком про троллейбус из буханки хлеба.
Вот и мне так кажется, самое интересное на самом деле сравнить затраты, и скорость на поиск с помощью этого генетеческого алгоритма и обычного перебора, чтоб потом долго не рассказывать почему в таких задачах он не нужен. А то скоро станет трендом так решать задачи с помощью модного инструмента.
Я просто оставлю это здесь:
А почему мы меняем только 3 или 5 ячеек? При выборе крайней, не являющейся угловой, мы 4 поменяем же.
Есть подозрение, что из-за ограничения на 8 экземпляров поколения алгоритм будет сходиться не всегда.
А иначе будет полный перебор.
А иначе будет полный перебор.
Почему статья до сих пор существует? Либо удалите её, либо исправьте заголовок (и удалите все упоминания в тексте всяких «генов» и «мутаций», не имеющих к брутфорсу никакого отношения), не вводите неискушённых читателей в заблуждение относительно генетических алгоритмов.
В емаксе есть такая игра. И "решатель" тоже присутствует.
Картинка
К сожалению, это не генетический алгоритм. Результатом работы генетического алгоритма будет являться решение, подходящее для любого набора входных данных (в Вашем случае — игрового поля со случайным состоянием ячеек). Вы же ищете решение для конкретного поля перебором с эволюционной эвристикой. Скромно рекомендую для ознакомления эту статью.
Я так понял — это алгоритм перебора.
А теперь объясните, как вы в итоге получаете решение в виде последовательности ходов? Сдается мне, что «генетический» подход применен неверно.
Я бы в качестве гена взял операцию клика на тотем в определенной позиции (итого 25 генов). Тогда генотип (хромосома) кодирует последовательность ходов. Для оценки берем начальное поле, применяем последовательность и смотрим что получилось. Как-то так.
Я бы в качестве гена взял операцию клика на тотем в определенной позиции (итого 25 генов). Тогда генотип (хромосома) кодирует последовательность ходов. Для оценки берем начальное поле, применяем последовательность и смотрим что получилось. Как-то так.
А почему у вас Y сверху вниз а не снизу вверх?
за тему спасибо.
за тему спасибо.
Решал такую задачу на scrath, там можно поиграть и посмотреть исходники
В ней не важна последовательность ходов, а только сами ходы. Правда мой алгоритм основывался на решении системы линейных уравнений, (просто, надежно, быстро)
В ней не важна последовательность ходов, а только сами ходы. Правда мой алгоритм основывался на решении системы линейных уравнений, (просто, надежно, быстро)
Зарегистрируйтесь на Хабре, чтобы оставить комментарий
Решаем головоломки шаманов в World of Warcraft генетическим алгоритмом