Искусственный интеллект для змейки. Часть 1: Кратчайший/длиннейший путь, Гамильтонов цикл

Публикация № 1073386

Разработка - Математика и алгоритмы

Змейка поиск в глубину ширину гамильтонов цикл

Различные варианты алгоритмов для игры "Змейка".

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

 

 1. Кратчайший путь. Поиск в ширину (Breadth-first search) Вики

Представим поле игры в виде графа. Каждая ячейка поля связана как минимум с 2-мя соседями. Таким образом, перебирая соседей можно найти ячейку с "едой". А после восстановить путь по которому мы до нее дошли. 

Поиск в ширину - один из методов обхода графа. Заключается в том, что сначала рассматриваются все подчиненные узлы одного уровня, а после все подчиненные подчиненных и т.д. Под узлом понимается адрес ячейки со ссылкой на "Родителя" (ячейку через которую мы добрались до узла).

Примерный алгоритм действий:

  1. Создать пустой стек и поместить в него узел-источник
  2. Пока стек не пустой извлекать по одному узлу с вершины стека
  3. Проверить не является ли текущий узел целевым. Если да, то завершить поиск.
  4. Перебрать все подчиненные узлы, которые еще не были просмотрены. Добавить их в конец стека и пометить как просмотренные.

Алгоритм отлично работает до тех пор пока "хвост" змеи не начинает перекрывать кратчайший путь.

Серым цветом выделен рассчитанный путь.

 
 Графики

 

2. Поиск в глубину (Depth-first search) Вики

Другой способ обхода графа, который ,как правило, будет приводить к более запутанному и сложному пути.

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

Отличие алгоритма от поиска в ширину будет минимальным: на шаге 2 берем узел не с вершины, а со дна стека.

 
 Графики

3. Длиннейший путь

Если наша цель максимизировать количество очков, то можно удлинить путь к еде включая в него максимальное число соседних узлов.

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

 

 
Графики

Результат увеличился, тем не менее, хвост все еще продолжает мешать.

4. Гамильтонов цикл Вики

Гамильтонов цикл - замкнутый цикл, который проходит через каждую вершину графа по одному разу.

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

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

 
 Графики

5. Гамильтонов цикл 2

Самый простой алгоритм из описанных, обладает 100% эффективностью и не требует никаких расчетов.

Подойдет для любого прямоугольного поля на котором нет препятствий.

Если нас действительно не волнует число шагов, то можно просто ходить по зацикленному пути:

 
 Графики

 

Обработка протестирована на 8.3.12.1595, 8.3.12.1855

 

Скачать файлы

Наименование Файл Версия Размер
ИИ для змейки. Часть 1: Кратчайший\длиннейший путь, Гамильтонов цикл:

.epf 14,69Kb
06.06.19
3
.epf 1 14,69Kb 3 Скачать

Специальные предложения

Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. VmvLer 07.06.19 17:25 Сейчас в теме
Ок, но при чем тут Искусственный интеллект - просто для словца?

Сначала такие проги писали на Бейсик под синклеры, сейчас на 1С под РС.
Те же шары, только вид сбоку
Perfolenta; BigB; +2 Ответить
2. Oldsad 10.06.19 02:56 Сейчас в теме
Мде, подвела ассоциативная цепочка "искусственный интеллект" -> "нейронные сети" и я пришел читать статью
А тут привет из 90-х, когда компьютеры были квадратными и оперативка измерялась килобайтами
Оставьте свое сообщение

См. также

Многопоточность. Универсальный «Менеджер потоков» (фреймворк) с отслеживанием зависимости объектов Промо

Практика программирования Математика и алгоритмы Универсальные функции Производительность и оптимизация (HighLoad) v8 1cv8.cf Россия Абонемент ($m)

Восстановление партий, расчет зарплаты, пакетное формирование документов или отчетов - теперь все это стало доступнее. * Есть желание повысить скорость работы медленных алгоритмов! Но... * Нет времени думать о реализации многопоточности? * о запуске и остановке потоков? * о поддержании потоков в рабочем состоянии? * о передаче данных в потоки и как получить ответ из потока? * об организации последовательности? Тогда ЭТО - то что надо!!!

26.05.2017    49154    DarkAn    86    

Еще раз о рабочих днях. Быстрый способ расчета в запросах

Практика программирования Математика и алгоритмы Разработка v8 Абонемент ($m)

В статье рассмотрен механизм учета производственных графиков и рабочих дней. Предложен простой и быстрый алгоритм решения типичных задач: добавление рабочих дней к дате и нахождение разницы между датами в рабочих днях. Все вычисления производятся исключительно запросом, т.е. решение пригодно для СКД и динамических списков.

1 стартмани

20.06.2019    7533    Alxby    11    

Функциональное программирование в 1С

Практика программирования Математика и алгоритмы Разработка v8 1cv8.cf Абонемент ($m)

Статья о функциональном программировании в 1С. Добавляем новые возможности. Пример передачи функций в качестве аргумента.

1 стартмани

28.03.2019    8392    alexey.kutya    26    

Иерархия библиотек. Автоматическое обновление или как отказаться от переопределяемых модулей

Практика программирования Математика и алгоритмы Разработка v8 Абонемент ($m)

В статье рассмотрен один из вариантов библиотечного подхода к разработке, позволяющий организовать иерархический вызов библиотечных процедур и упростить автоматическую сборку готового продукта из нескольких библиотек. Предлагаемый подход может служить одним из элементов CI/CD при разработке ПО на платформе 1С.

1 стартмани

04.03.2019    5763    Alxby    4    

Агрегатное суммирование строк в запросе – сложно, но не невозможно Промо

Математика и алгоритмы v8 Абонемент ($m)

Описывается метод соединения строк из одной колонки таблицы в единую результирующую строку в запросе на языке 1С. Метод сложный и по сравнению с внезапросной техникой представляет больше спортивный, чем практический интерес.

1 стартмани

09.09.2013    78691    ildarovich    54    

Жизненный цикл управляемой формы. Шпаргалка разработчика

Практика программирования Математика и алгоритмы v8::УФ 1cv8.cf Абонемент ($m)

Прочитав когда-то давно книжку "Разработка управляемых форм", составил для себя такую схемку-напоминалку для обращения в процессе разработки. С тех пор не раз выручала и избавляла от необходимости лезть в гуглы.

1 стартмани

29.06.2018    31094    stas_ganiev    26    

Принципы ООП в 1С на примере реализации pattern Decorator

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

В данной статье будет рассмотрен пример реализации GoF паттерна проектирования decorator в среде разработки 1С. Основная цель данного шаблона, это возможность динамического расширения функциональности базового класса. Сразу оговорюсь, т.к. в 1С нет ООП, это будет не чистый пример реализации данного шаблона, однако свою задачу данный пример будет решать.

1 стартмани

21.06.2018    11544    lazarenko    6    

Строим "фасады" в 1С

Практика программирования Математика и алгоритмы v8 Россия Абонемент ($m)

Как реализовать функционал, чтобы не было “мучительно больно” при расширении требований.

1 стартмани

04.05.2018    17574    ktb    41    

Демо связи веб сервисов 1С и php Промо

Практика программирования Математика и алгоритмы WEB v8 1cv8.cf Абонемент ($m)

Демонстрация обращения к веб сервису 1С из php. Пример простейший, уровня hello world. Дана одна страница и информационная база 1С с одним справочником и одним веб сервисом. Веб сервис выдаёт содержимое справочника по запросу странички.

1 стартмани

19.07.2013    32186    Трактор    20    

Случайность, совпадение, закономерность. Генератор случайных чисел

Практика программирования Математика и алгоритмы Игры v8 1cv8.cf Абонемент ($m)

Объект ГенераторСлучайныхЧисел удобно выдает случайные числа в заданном интервале значений. Исследование особенностей, рассуждения на тему случайных чисел, практика применения. Увлекательно в игровой форме можно исследовать работу генератора случайных чисел.

1 стартмани

20.01.2018    25798    Ликреонский    58    

Github и 1С. Пошаговая инструкция на конкретном примере

Математика и алгоритмы v8 Абонемент ($m)

Статья для тех, у кого есть неудержимое желание программировать и хочется доработать какую-то конфигурацию (или проект на 1С), выложенный на Github, но останавливают незнакомые слова Git, Github, Fork, Commit, Pull request, Merge, Issue.

1 стартмани

26.10.2017    44549    BlizD    51    

Пишем игру 21 (очко). Пример использования 1С и ActiveX

Практика программирования Игры v8 1cv8.cf Россия Абонемент ($m)

Пишем игру "очко". Программный код состоит из двух частей: 1.Разработка компоненты работы с графикой на Delphi 2.Логическая реализация игрового процесса на 1С

1 стартмани

23.05.2017    19858    user621724_Dimav1979    17    

115 полезностей от Буравова Андрея по курсу СКД Евгения Гилёва Промо

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Посмотрел 5,5 часовой курс по системе компоновки данных. Нашел невероятное количество не только необходимого, но и примеры не очевидного поведения СКД. У многих не хватает времени и терпения досмотреть курс до конца. Прочитав 115 полезностей, вы сможете понять в каком уроке освещен интересующий вас вопрос и быстро открыть его, чтобы посмотреть видео.

1 стартмани

08.04.2012    38574    Flashill    70    

Планы обмена 1С: решение проблемы блокировок при помощи средств SQL Server

Практика программирования Математика и алгоритмы v8 Абонемент ($m)

Небольшое исследование возможности улучшить работу планов обмена 1С средствами SQL Server: view + triggers (представление + триггеры). В статье описывается один из приёмов SQL программирования для решения проблем блокировок, когда основные структуры данных изменить нельзя.

1 стартмани

10.01.2017    13056    zhichkin    4    

Степень сходства двух наименований справочника

Математика и алгоритмы v7.7 v8 Абонемент ($m)

Статья посвящена исследованию следующего вопроса: необходимо сравнить 2 наименования справочников с целью вычисления их степени сходства. По задумке, степень сходства должна выражаться в процентах.

1 стартмани

25.02.2015    20815    etmarket    43    

АЦРК: Многовариантный автоматический запрет редактирования (для конфигурации УТ 10.3)

Закрытие периода Математика и алгоритмы Администрирование данных 1С Закрытие периода v8 УТ10 Абонемент ($m)

В этой статье описывается усовершенствованная технология автоматической установки даты запрета редактирования Во-первых, можно определить несколько стратегий запрета редактирования с разными параметрами. Например, запрет в днях, запрет доступа в предыдущие месяцы кварталы и т.п., с указанием отступа от текущей даты. То есть для некоторых пользователей (рядовых менеджеров) при входе в базе будет устанавливаться запрет по вчерашний день, для других (старших менеджеров) на 5 дней назад, для третьих (администраторов базы или руководителей отдела) - запрет предыдущего месяца с отступом в 10 дней.. Во-вторых, запрет будет устанавливаться для ВСЕХ без исключения пользователей базы данных. Для самых привилегированных это будет максимальная глубина, но запрет будет установлен. Управление этой системой осуществляется через механизм дополнительных прав пользователей. При необходимости пользователь с полными правами может открыть для себя закрытый период, но только на текущий сеанс работы.

1 стартмани

22.07.2013    20885    acrk    9    

Технология создания коммерческих разработок на базе Базовой конфигурации "Управление Торговлей, ред.10.3" Промо

Математика и алгоритмы Рабочее место v8 v8::ОУ УТ10 УУ Абонемент ($m)

Создав однажды небольшую надстройку на базе конфигурации "УТ Базовая, ред.10.3", впоследствии разработка расширилась до неузнаваемости и приросла функционалом. Что удивительно, так это то, что разработка представляет собой внешнюю обработку вкупе со стандартными механизмами базовой версии, а значит не требует дополнительного конфигурирования БД. О том, как и что я реализовал, пойдет речь в данной статье.

1 стартмани

11.03.2012    25556    Rustig    93    

Разработка многоязычной системы

Математика и алгоритмы v8 Абонемент ($m)

В статье затронуты некоторые аспекты многоязычности системы с точки зрения их технической реализации

1 стартмани

20.06.2013    20998    YOr!k    54    

Передача аргумента, полученного по ComConnector, на сервер

Математика и алгоритмы v8 Абонемент ($m)

С точки зрения инкапсуляции, данные, переданные по COMConnector, следует обрабатывать в базе-приемнике. И тут возникает проблема, малопонятная для новичка из-за сложностей в отладке модуля внешнего соединения. Аргументы попросту не передаются в серверные модули.

1 стартмани

20.03.2013    6412    asved.ru    3    

Объектно-ориентированный взгляд на программирование в 1С

Математика и алгоритмы v8 1cv8.cf Абонемент ($m)

Рассматриваем программирование в 1С как работу с объектами и классами.

1 стартмани

18.04.2012    28903    BorisMor    241    

Использование нарастающих итогов в партионном учете и не только

Математика и алгоритмы v8 Россия Абонемент ($m)

Данный материал является иллюстрацией способов работы с запросами, использующими методику вычисления «нарастающих итогов». Также в данной статье рассматриваются вопросы практического использования запросов такого рода при партионном учете и расчете задолженностей. Фактически в данной статье рассматриваются альтернативы запросам, приведенным в статьях http://infostart.ru/public/61295/ и http://infostart.ru/public/68225/. Полный текст статьи можно также найти на http://nashe1c.ru/materials-view.jsp?id=383.

1 стартмани

25.08.2011    13883    y-str    107    

Модуль менеджера или статические методы класса?

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

Зачем в платформе 8.2 добавили модуль менеджера объекта, как его использовать? Попробуем разобраться.

1 стартмани

02.07.2010    60944    zfilin    97    

Как я победил блокировки (deadlock)

Математика и алгоритмы v8 1cv8.cf Россия Абонемент ($m)

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

1 стартмани

28.09.2009    21737    Minotavrik    64