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

07.06.19

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

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

Скачать файл

ВНИМАНИЕ: Файлы из Базы знаний - это исходный код разработки. Это примеры решения задач, шаблоны, заготовки, "строительные материалы" для учетной системы. Файлы ориентированы на специалистов 1С, которые могут разобраться в коде и оптимизировать программу для запуска в базе данных. Гарантии работоспособности нет. Возврата нет. Технической поддержки нет.

Наименование По подписке [?] Купить один файл
ИИ для змейки. Часть 1: Кратчайший\длиннейший путь, Гамильтонов цикл:
.epf 14,69Kb ver:1
5
5 Скачать (1 SM) Купить за 1 850 руб.

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

 

 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С v8.3 1C:Бухгалтерия Бесплатно (free)

Я Федор, ведущий разработчик 1С. На хакатоне компании команда под моим руководством перенесла игру «Герои меча и магии III» на платформу 1С. Расскажу, как устроена конфигурация «1С: Герои меча и магии» с технической точки зрения.

10.10.2024    49359    PROSTO-1C    55    

166

Игры Пользователь Платформа 1С v8.3 Управляемые формы 1C:Бухгалтерия Бесплатно (free)

Игра "Змейка" в классическом варианте на управляемых формах в 1С. Собирайте яблоки и ставьте рекорд!

09.02.2024    5076    303    emilyabochkova    15    

31

Математика и алгоритмы Программист Платформа 1C v8.2 1C:Бухгалтерия Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    4940    stopa85    12    

39

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    9943    user1959478    54    

37

Математика и алгоритмы Инструментарий разработчика Программист Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    12509    8    SpaceOfMyHead    20    

62

Игры Платформа 1С v8.3 1C:Бухгалтерия 1С:Управление торговлей 11 Абонемент ($m)

Одномерный или "устный" вариант игры Балда.

1 стартмани

05.12.2022    4475    2    Alexei_Siva    1    

39

Игры Программист 8.3.14 1C:Бухгалтерия ИТ-компания Россия Абонемент ($m)

Сетевая игра "Захват клеток" с возможностью играть на время, а также с поддержкой игры оффлайн против компьютера.

1 стартмани

12.09.2022    6812    13    Sergey_Borisovi4    10    

34

Игры Платформа 1С v8.3 Россия Абонемент ($m)

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

1 стартмани

07.06.2022    8041    19    user676027_svikator    16    

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

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