Занимательные задачки и загадки

Персональный раздел Странник34. Вопросы и ответы. Поиск Истины.

Модератор: Странник34

Аватара пользователя
BDK
Сообщения: 3491
Зарегистрирован: 17 май 2015, 23:27
Откуда: Беларусь
Благодарил (а): 149 раз
Поблагодарили: 362 раза

Re: Занимательные задачки и загадки

Сообщение BDK » 13 апр 2020, 21:17

Итак, сначала опишу суть эволюционного алгоритма вообще, а потом конкретно применительно к нашей задаче.

Суть эволюционного алгоритма:

Создаётся популяция из некоторого количества особей. Особь - это виртуальное существо. Цель - найти наилучший вариант существа.
Выполняем цикл:
{
1.Оцениваем каждую особь в популяции и присваиваем особям оценку.
2.Сортируем все особи в популяции в порядке убывания их оценки.
3.Первую половину популяции оставляем не тронутой а вторую половину удаляем.
4.Выполняем размножение оставшихся особей чтобы заместить удаленную половину популяции новыми особями.
Операция размножения имеет такой вид:
4.1.Берем две случайные особи из сохраненной половины популяции и копируем часть генов от одной особи и от второй и составляем из этих генов новую особь - это называется скрещивание.
4.2. В новой особи случайно изменяем небольшую часть генов - это называется мутация.
Это проделываем столько раз сколько нужно чтобы восполнить популяцию новыми созданными особями.
5.Повторяем цикл с начала - каждый цикл называется поколением
}

После некоторого количества циклов берем первую особь в отсортированной популяции - это и есть искомое наилучшее решение.
=====

Теперь как это применить к нашей задаче. Нам нужно найти наилучшую возможную стратегию игры. Стратегия игры - это алгоритм. Таким образом нам нужно найти наилучший алгоритм. Таким образом особью будет такое виртуальное существо которое содержит в себе алгоритм.

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

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

С сортировкой и удалением половины популяции всё понятно - делаем это для одной и для второй популяции.

Далее размножение - берем две случайные особи из оставшихся в популяции и берем часть алгоритма от одной и часть от другой и составляем новый алгоритм из этих частей. А затем случайно искажаем какие-то участки этого алгоритма - так мы создаём новые особи. Делаем это так же отдельно для одной и для второй популяции. Разумеется не смешивая - это разные популяции и в них мы ищем разных существ - поэтому смешивать их нельзя. То есть в одной популяции у нас должны формироваться существа которые наилучшим образом играют в игру а в другой популяции должны формироваться существа которые наилучшим образом играют в контр игру.

Ну и остальные пункты цикла понятны
=====

Еще немного о том в какой форме описывать алгоритм внутри особи. Это не обязательно должен быть некий сложный язык программирования. Можно выбрать какой нибудь простой язык описания правил, или допустим некий формат описания стратегии в виде блок-схемы. Или лучше - мой любимый вариант - в виде нейросети. В общем здесь на что хватить фантазии . И конечный результат будет получен именно в таком формате. Так что смотри в каком виде ты хочешь получить эту наилучшую стратегию игры ( и контр игры) - и именно в таком формате должна описываться стратегия внутри особи. Но главное на что нужно сделать упор - этот формат должен позволять выполнять скрещивание и мутации. Это удобно можно делать с нейросетями. Но можно придумать и другие форматы описания стратегии - здесь уже свобода для твоей фантазии.