Итак, сначала опишу суть эволюционного алгоритма вообще, а потом конкретно применительно к нашей задаче.
Суть эволюционного алгоритма:
Создаётся популяция из некоторого количества особей. Особь - это виртуальное существо. Цель - найти наилучший вариант существа.
Выполняем цикл:
{
1.Оцениваем каждую особь в популяции и присваиваем особям оценку.
2.Сортируем все особи в популяции в порядке убывания их оценки.
3.Первую половину популяции оставляем не тронутой а вторую половину удаляем.
4.Выполняем размножение оставшихся особей чтобы заместить удаленную половину популяции новыми особями.
Операция размножения имеет такой вид:
4.1.Берем две случайные особи из сохраненной половины популяции и копируем часть генов от одной особи и от второй и составляем из этих генов новую особь - это называется скрещивание.
4.2. В новой особи случайно изменяем небольшую часть генов - это называется мутация.
Это проделываем столько раз сколько нужно чтобы восполнить популяцию новыми созданными особями.
5.Повторяем цикл с начала - каждый цикл называется поколением
}
После некоторого количества циклов берем первую особь в отсортированной популяции - это и есть искомое наилучшее решение.
=====
Теперь как это применить к нашей задаче. Нам нужно найти наилучшую возможную стратегию игры. Стратегия игры - это алгоритм. Таким образом нам нужно найти наилучший алгоритм. Таким образом особью будет такое виртуальное существо которое содержит в себе алгоритм.
Поскольку в нашей игре должны противостоять друг другу две стратегии и нам по сути нужно найти их обе - стратегию игры и контр игры - то создаём две популяции особей - в одной популяции будут особи которые играют в игру а в другой популяции будут особи которые будут играть в контр игру - соответственно для каждой популяции мы будем выполнять свой процесс эволюции в котором и будем искать наилучший алгоритм соответственно игры и контригры.
Итак, первый пункт эволюционного алгоритма - оценка особей. Для того чтобы оценить особей - нужно чтобы все особи из одной популяции сыграли в игру со всеми особями второй популяции. И по результатам этой игры начисляем каждой особи оценку - причем как особям играющим в игру так и особям играющим в контр игру.
С сортировкой и удалением половины популяции всё понятно - делаем это для одной и для второй популяции.
Далее размножение - берем две случайные особи из оставшихся в популяции и берем часть алгоритма от одной и часть от другой и составляем новый алгоритм из этих частей. А затем случайно искажаем какие-то участки этого алгоритма - так мы создаём новые особи. Делаем это так же отдельно для одной и для второй популяции. Разумеется не смешивая - это разные популяции и в них мы ищем разных существ - поэтому смешивать их нельзя. То есть в одной популяции у нас должны формироваться существа которые наилучшим образом играют в игру а в другой популяции должны формироваться существа которые наилучшим образом играют в контр игру.
Ну и остальные пункты цикла понятны
=====
Еще немного о том в какой форме описывать алгоритм внутри особи. Это не обязательно должен быть некий сложный язык программирования. Можно выбрать какой нибудь простой язык описания правил, или допустим некий формат описания стратегии в виде блок-схемы. Или лучше - мой любимый вариант - в виде нейросети. В общем здесь на что хватить фантазии . И конечный результат будет получен именно в таком формате. Так что смотри в каком виде ты хочешь получить эту наилучшую стратегию игры ( и контр игры) - и именно в таком формате должна описываться стратегия внутри особи. Но главное на что нужно сделать упор - этот формат должен позволять выполнять скрещивание и мутации. Это удобно можно делать с нейросетями. Но можно придумать и другие форматы описания стратегии - здесь уже свобода для твоей фантазии.
Занимательные задачки и загадки
Модератор: Странник34