Эта статья — углубление темы предыдущей, где уже описаны детали реализации персонажа и воздействия экипировки.
Цель: показать интересующимся, как своими силами создать виртуальную популяцию игровых агентов, сталкивать их между собой, реализовать несложный генетический алгоритм (с мутациями) и визуализировать всё это при помощи HTML, CSS и Javascript.
Что нужно:
1. Python 3 + установить модуль matplotlib; IDE (у меня PyCharm);
2. если захотите редактировать шаблон интерактивного отчёта, то базовое понимание HTML, CSS, JavaScript (jQuery).
ЭТАП 1 — ставим цель, разбираемся с ООП
Итак, конечная цель нашего кодинга — сделать так, чтобы к наилучшей экипировке можно было прийти при помощи симуляции генетики/эволюции/естественного отбора. И получить возможность визуально проследить этот путь.
Превратим нашу цель в конкретные задачи:
- продумать и реализовать генетический механизм на уровне индивида («гены» разбойника должны прямо влиять на выбор экипировки)
- реализовать механизмы рождения потомков, передачи им генов, а также случайных незначительных мутаций, чтобы обеспечить вариативность и саму возможность поиска лучшего
- реализовать генетическое «состязание», отбор генов (сталкивать их носителей между собой, чтобы исход столкновения низвергал «плохие» гены и возносил «хорошие»)
- собрать всё в целостную систему, в которой разбойники смогут эволюционировать в идеальных бойцов
- собирать и визуализировать данные, чтобы было на что полюбоваться (а то интересно же!)
- оценить полезность этих занятий
Здесь нам поможет ООП, создадим 4 фундаментальных класса:
ЭТАП 2 — заточка класса Rogue под размножение
договариваемся о терминах на берегу
В этой статье буду частить терминами «ген» (в коде — gene) и «генотип» (в коде — genotype). Также будут «мутации» (в коде — mutate, mutation), подразумевающие смену одним или несколькими генами своего значения. Размножение будет происходить просто путём «отпочковывания» потомка от родителя, поэтому кроссинговера и других подобных усложнений не будет. Генотип разбойника — это список из 7 чисел, которые являются его генами:
Итак, класс Rogue в сравнении с прошлым разом существенно разрастается.
1. Разбойник получает гены одним из возможных путей (был сгенерирован в самый первый день или унаследовал от «родителя» с мутацией или без оной). За это отвечают методы generate_random_genes, mutate_genes, mutate_gene:
# сгенерировать случайный набор генов (генотип):
def generate_random_genes(self):
dbg = DBG_rogue_generate_random_genes
self.my_genes[0] = randrange(0, len(RIGHT_HANDS)) # <-- для правой руки:
self.my_genes[1] = randrange(0, len(LEFT_HANDS)) # <-- для левой руки:
self.my_genes[2] = randrange(0, len(GLOVES)) # <-- для рукавиц:
self.my_genes[3] = randrange(0, len(HEADS)) # <-- для головы:
self.my_genes[4] = randrange(0, len(CHESTS)) # <-- для нагрудника:
self.my_genes[5] = randrange(0, len(PANTS)) # <-- для штанов:
self.my_genes[6] = randrange(0, len(BOOTS)) # <-- для обуви:
if dbg: # для отладки:
print('nf "generate_random_genes":' + 'ntgenes generated:nt', end='')
print(self.my_genes)
# унаследовать родительские гены с вероятностью мутации:
def mutate_genes(self, parent_genes):
dbg = DBG_rogue_mutate_genes
# взять за основу родительские гены:
self.my_genes = parent_genes.copy()
# произойдёт ли мутация вообще:
event_mutation = randint(1, 10)
# если мутация НЕ должна произойти, больше тут делать нечего:
if event_mutation == 10:
if dbg: # для отладки:
print('nf "mutate_genes" начата и окончена:' + 'ntмутация НЕ состояласьntold genes: ', end='')
print(parent_genes)
print('tnew genes: ', end='')
print(self.my_genes)
return 0
# если мутация должна произойти:
else:
# определить "силу" мутации = количество генов, которые должны мутировать:
mutation_volume = randint(0, 30)
mutation_iters = 1
if 22 <= mutation_volume <= 28:
mutation_iters = 2
elif 29 <= mutation_volume <= 30:
mutation_iters = 3
if dbg: # для отладки:
print('nf "mutate_genes" начата:' + 'ntмутаций запланировано: ' + str(mutation_iters))
# список генов, доступных для мутации:
genes_available = [0, 1, 2, 3, 4, 5, 6]
# список мутировавших генов:
genes_mutated = []
current_iter = 0
while current_iter < mutation_iters:
if dbg: # для отладки:
print('tw1')
# выбрать случайный ген из доступных:
gene_with_forced_mutation = choice(genes_available)
# если этот ген ещё не мутировал:
if gene_with_forced_mutation not in genes_mutated:
self.mutate_gene(gene_with_forced_mutation)
genes_mutated.append(gene_with_forced_mutation)
current_iter += 1
if dbg: # для отладки:
print('tcurrent_iter =', current_iter)
else:
if dbg: # для отладки:
print('telse, because ' + str(gene_with_forced_mutation) + ' already in genes_mutated')
if dbg: # для отладки:
genes_mutated_str = ''
if len(genes_mutated) > 1:
for x in genes_mutated:
genes_mutated_str += str(x) + ', '
else:
genes_mutated_str = str(genes_mutated[0])
print('nf "mutate_genes" окончена:' + 'ntold genes: ', end='')
print(parent_genes)
print('tgenes_mutated: ' + genes_mutated_str)
print('tnew genes: ', end='')
print(self.my_genes)
# произвести мутацию в указанном гене, изменив его значение на любое другое:
def mutate_gene(self, gene_id):
dbg = DBG_rogue_mutate_gene
current_value = self.my_genes[gene_id]
new_value = current_value
if dbg: # для отладки:
print('nf "mutate_gene":' + 'ntgene_id: ' + str(gene_id) + 'ntold gene value: ' + str(current_value))
tries = 0
while new_value == current_value:
if dbg and tries > 0: # для отладки:
print('tw2, because ' + str(new_value) + ' = ' + str(current_value) )
new_value = randrange(0, len(LINKS_TO_EQUIP_DICTS[gene_id]))
self.my_genes[gene_id] = new_value
tries += 1
if dbg: # для отладки:
print('tnew gene value: ' + str(new_value) + 'nttries: ' + str(tries))
2. Гены (генотип) определяют, какую экипировку разбойник наденет (сразу же при рождении инициализации объекта). Для этого вызывается метод apply_genes:
# "применить" гены (генотип) путём надевания обусловленной ими экипировки:
def apply_genes(self):
dbg = DBG_rogue_apply_genes
pointer = 0
for item_id in self.my_genes:
self.wear_item(pointer, item_id, LINKS_TO_EQUIP_DICTS[pointer])
pointer += 1
if dbg: # для отладки:
print('nf "apply_genes":' + 'ntприменено.')
print(self)
3. Экипировка определит конечное значение «рейтинга» разбойника. Для этого будет вызван метод calculate_rate, который рассчитывает математическое ожидание урона:
# метод для расчёта собственного рейтинга:
def calculate_rate(self):
dbg = DBG_rogue_calculate_rate
# вычислить вероятность попадания:
p_hit = self.stat_hit / 100
# вычислить вероятность скользящего и НЕскользящего удара:
p_glancing = self.stat_glancing_percent / 100
not_p_glancing = 1 - self.stat_glancing_percent / 100
# вычислить вероятность критического и НЕкритического удара:
p_crit = self.stat_crit / 100
not_p_crit = 1 - self.stat_crit / 100
# вычислить ожидание модификатора:
expectation_modificator = p_hit * (p_glancing * 0.7 + not_p_glancing * (p_crit * 2 + not_p_crit))
# вычислить ожидание урона с таким модификатором:
expectation_damage = expectation_modificator * self.stat_attackpower
expectation_damage = round(expectation_damage, 3)
if dbg:
print('tожидание модификатора =', expectation_modificator)
print('tожидание урона =', expectation_damage)
return expectation_damage
4. Рейтинг разбойника и будет определяющим фактором, ведущим к размножению или позорной смерти. Для этого введено понятие «победа» (метод embody_win) и «поражение» (метод embody_defeat):
# оформить победу в дуэли:
def embody_win(self):
dbg = DBG_rogue_embody_win
self.my_wins += 1
stats.genes_add_win(self.my_genes)
# после каждой второй победы:
if self.my_wins % population.wins_to_reproduce == 0:
# определить число рождаемых потомков:
total_borns = choice(population.possible_birth_quantities)
if dbg:
print('рождений будет ' + str(total_borns))
for x in range(0, total_borns):
if dbg:
print(self.name + ' рожает потомка...')
# родить разбойника-потомка:
new_rogue = Rogue(self.my_genes, self.my_generation, from_parent=True)
ROGUES_LIST.append(new_rogue)
Population.day_of_last_changes = current_day
# обновить рекорд количества побед у одного разбойника в популяции:
if self.my_wins > Population.record_max_wins:
Population.record_max_wins = self.my_wins
Population.max_winner_name = self.name
Population.max_winner_genes = self.my_genes
# оформить поражение в дуэли:
def embody_defeat(self):
dbg = DBG_rogue_embody_defeat
self.my_defeats += 1
# после двух поражений выпилиться:
if self.my_defeats == population.defeats_to_die:
self.alive = False
Population.how_many_rogues_alive -= 1
Population.day_of_last_changes = current_day
if dbg:
print(self.name + ' выпиливается...')
Ну и соответствующим образом переработан конструктор класса, чтобы работала эта цепочка «гены — экипировка — рейтинг»:
def __init__(self, genes_list_inherited, parent_generation, from_parent=True, genes_can_mutate=True):
# инициализация списка слотов экипировки, который должен содержать id надетых предметов:
# 0 - правая рука, 1 - левая рука, 2 - перчатки, 3 - голова, 4 - грудь, 5 - штаны, 6 - обувь
self.equipment_slots = [0] * 7
# инициализация списка слотов экипировки, который должен содержать названия надетых предметов:
self.equipment_names = ['ничего'] * 7
# БАЗОВЫЕ значения характеристик (они - точка отсчёта при смене экипировки):
self.basic_stat_agility = 50
self.basic_stat_power = 40
self.basic_stat_hit = 80
self.basic_stat_crit = 20
self.basic_stat_mastery = 0
# рассчитать текущие характеристики без вещей:
self.set_stats_without_equip()
# статистические счётчики:
Population.how_many_rogues += 1
Population.how_many_rogues_alive += 1
# номер поколения:
self.my_generation = parent_generation + 1
if self.my_generation > Population.generations:
Population.generations = self.my_generation
# "имя" разбойника:
self.name = '"' + str(Population.how_many_rogues) + '-й, из поколения ' + str(parent_generation + 1) + '"'
# жив ли:
self.alive = True
# счётчики побед и поражений:
self.my_wins = 0
self.my_defeats = 0
# инициализировать цепочку генов:
self.my_genes = [0] * 7
if genes_can_mutate:
# если этот разбойник порождён другим разбойником, его гены должны незначительно мутировать:
if from_parent:
self.mutate_genes(genes_list_inherited)
else:
self.generate_random_genes()
else:
self.my_genes = genes_list_inherited
# отобразить эти гены в статистике:
stats.genes_add_presence(self.my_genes, self.my_generation)
# надеть экипировку согласно полученным генам:
self.apply_genes()
Подытожу эту логику класса картинкой:
ЭТАП 3 — классы Population, Stats и Challenge
Класс Population нужен лишь для трёх вещей:
- создание популяции из указанного количества разбойников со случайными генами и биологическими параметрами, которые будут всегда неизменны (wins_to_reproduce — сколько побед разбойнику нужно одержать для размножения, defeats_to_die — сколько поражений заставят индивида умереть);
- «перезагрузка» популяции, т.е. когда заканчивается последний день текущей Стадии, все разбойники уничтожаются и создаются разбойники с наилучшими генотипами (см. метод reload);
- хранение некоторых данных о популяции для статистики.
class Population():
"""Класс используется для работы с популяцией."""
how_many_rogues = 0 # <-- счётчик всех разбойников
how_many_rogues_alive = 0 # <-- счётчик живых разбойников
how_many_battles = 0 # <-- счётчик битв
how_many_ties = 0 # <-- счётчик ничьих
generations = 0 # <-- счётчик поколений
day_of_last_changes = 0 # <-- день последних изменений в изменении численности популяции
max_days_without_changes = 0 # <-- счётчик дней без изменений
# рекорд количества побед у одного разбойника в популяции, а также его имя и генотип:
record_max_wins = 0
max_winner_name = 'none'
max_winner_genes = 'none'
# при создании популяции сразу же наполнить её:
def __init__(self, total, possible_birth_quantities, wins_to_reproduce, defeats_to_die):
# запомнить начальное значение:
self.initial_size = total
# сохранить биологические параметры, которые будут справедливы для каждого разбойника в популяции:
self.wins_to_reproduce = wins_to_reproduce
self.defeats_to_die = defeats_to_die
self.possible_birth_quantities = possible_birth_quantities
while total > 0:
# создать нового разбойника, передав "пустой генотип" и отметку о том, что ему нужно сгенерировать гены:
new_rogue = Rogue('', 0, from_parent=False)
# пополнить список разбойников:
ROGUES_LIST.append(new_rogue)
total -= 1
# вывести актуальную информацию о популяции:
def __str__(self):
text = 'Популяция:n'
text += 'поколений: ' + str(Population.generations) + 'n'
text += 'всего агентов: ' + str(Population.how_many_rogues) + 'n'
text += 'живых агентов: ' + str(Population.how_many_rogues_alive) + 'n'
text += 'рекорд побед: ' + str(Population.record_max_wins) + 'n'
text += 'имя рекордсмена: ' + str(Population.max_winner_name) + 'n'
text += 'генотип рекордсмена: ' + str(Population.max_winner_genes) + 'n'
return text
# перезагрузить популяцию, оставив в ней how_many_to_save разбойников с наиболее успешными генотипами:
def reload(self, how_many_to_save):
# обнулить кол-во разбойников:
Population.how_many_rogues_alive = 0
# "убить" всех существующих разбойников:
for x in ROGUES_LIST:
x.alive = False
# извлечь из словаря генотипов данные о лучших генотипах:
list_genotypes_top = stats.get_ordered_list_from_dict(LIST_FOR_DICTS_GENOTYPES[current_stage], inner_index=2)
# наполнить популяцию разбойниками с этими генотипами:
for x in range(0, how_many_to_save):
# преобразовать генотип из строки в список:
genotype_in_str = list_genotypes_top[x][0]
genotype_in_list = []
for char in genotype_in_str:
if char != '-':
genotype_in_list.append( int(char) )
# создать нового разбойника, передав генотип и отметку о том, что гены НЕ должны мутировать:
new_rogue = Rogue(genotype_in_list, 0, from_parent=True, genes_can_mutate=False)
# пополнить список разбойников:
ROGUES_LIST.append(new_rogue)
Класс Stats выполняет две основные задачи:
- сбор данных в процессе работы симуляции (например, показатели каждого дня: количество живых разбойников, количество уникальных генотипов и т.д.)
- визуализация данных (отрисовка графиков при помощи matplotlib, генерация интерактивного отчёта в формате HTML-страницы, которую можно будет открыть в браузере).
Забегая наперёд, показываю, как этот отчёт будет выглядеть:
Код HTML-шаблона для отчёта доступен на гитхабе.
Класс Stats также лучше просмотреть на гитхабе (а то больно много строк здесь окажется).
Класс Challenger отвечает за симуляцию столкновений между случайно выбираемыми разбойниками. Каждый день вызывается метод perform_battles, который формирует из живых разбойников дуэльные пары и сталкивает их при помощи метода perform_battle, и в конце концов для каждого разбойника вызывается либо метод embody_win, либо метод embody_defeat. Кстати, если окажется, что произошла ничья (генотипы, а значит и рейтинги разбойников одинаковы), то они расходятся без последствий:
class Challenger():
"""Класс обеспечивает проведение боёв между случайными разбойниками."""
# провести серию боёв:
def perform_battles(self):
dbg = DBG_challenger_perform_battles
# создать список живых разбойников:
rogues_alive = []
for x in ROGUES_LIST:
if x.alive:
rogues_alive.append(x)
# перемешать список:
shuffle(rogues_alive)
# получить количество пар живых разбойников в популяции:
pairs_total = int(len(rogues_alive) // 2)
if dbg:
print('pairs_total =', pairs_total)
# запускать бои между соседними по списку разбойниками:
counter = 0
pointer = 0
while counter < pairs_total:
a_1 = rogues_alive[pointer]
a_2 = rogues_alive[pointer + 1]
self.perform_battle(a_1, a_2)
counter += 1
pointer += 2
# провести бой между двумя разбойниками:
def perform_battle(self, rogue_1, rogue_2):
dbg = DBG_challenger_perform_battle
if dbg:
print('nновый бой между:', rogue_1.name, 'и', rogue_2.name)
# рассчитать рейтинг каждого разбойника (в более совершенной симуляции тут может быть полноценное сражение):
rating_1 = rogue_1.calculate_rate()
rating_2 = rogue_2.calculate_rate()
# счётчик боёв:
Population.how_many_battles += 1
if dbg:
print('tих рейтинг:', rating_1, 'и', rating_2, 'соответственно.')
# раскидать очки между победителем и проигравшим:
if rating_1 > rating_2:
rogue_1.embody_win()
rogue_2.embody_defeat()
elif rating_1 < rating_2:
rogue_1.embody_defeat()
rogue_2.embody_win()
else:
Population.how_many_ties += 1
if dbg:
print('tО чудо! Произошла ничья!')
Что ж, теперь переходим к телу программы, которое связывает воедино все упомянутые части кода. Сначала идут константы, которые определяют ключевые параметры симуляции: количество стадий, дней в стадии, начальное количество разбойников в популяции и т.д. Затем идут вспомогательные константы для отладки. И сами вызовы:
# КОНСТАНТЫ:
MAX_STAGES = 8 # <-- сколько стадий перезагрузки популяции должно пройти
MAX_DAYS_AT_STAGE = 20 # <-- сколько дней будет содержать одна стадия перезагрузки популяции
SLIDING_FREQUENCY = 10 # <-- как часто нужно создавать HTML-слайды с полями генотипов (1 = раз в день, 10 = раз в 10 дней)
ROGUES_AT_BEGIN = 10 # <-- начальное население популяции (для каждой стадии)
WINS_TO_REPRODUCE = 2 # <-- сколько побед разбойнику нужно одержать, чтобы размножиться
DEFEATS_TO_DIE = 2 # <-- сколько поражений приведёт разбойника к смерти
POSSIBLE_BIRTH_QUANTITIES = [1] # <-- варианты количеств потомков, которые могут родиться у разбойника за раз, например:
# [1, 2] означает, что с 50%-ной вероятностью родится либо 1, либо 1 потомка
# [1, 1, 2] означает, что с 66%-ной вероятностью родится 1 потомок
HTML_GSQUARE_SIDE = 10 # <-- ширина стороны квадратика, обозначающего генотип в интерактивном отчёте
HTML_GSQUARE_MARGIN = 3 # <-- отступы между квадратиками, обозначающими генотип в интерактивном отчёте
# список ссылок на словари экипировки:
LINKS_TO_EQUIP_DICTS = [RIGHT_HANDS, LEFT_HANDS, GLOVES, HEADS, CHESTS, PANTS, BOOTS]
# список для хранения словарей со статистикой по генотипам (отдельный словарь для каждой стадии):
LIST_FOR_DICTS_GENOTYPES = [{}] * MAX_STAGES
# словарь для хранения перечня всех появившихся разновидностей генотипов:
DICT_UNIQUE_GENOTYPES = {}
# словарь для хранения статистики по дням:
DICT_DAYS = {}
# список, где будут храниться ссылки на всех когда-либо появившихся разбойников:
ROGUES_LIST = list()
# переменная для хранения значения текущей стадии (должна находиться в глобальной области видимости)
current_stage = 0
# КОНСТАНТЫ для точечного управления "отладкой" (выводом отчётов о работе функций/методов):
DBG_rogue_mutate_genes = False
DBG_rogue_generate_random_genes = False
DBG_rogue_apply_genes = False
DBG_rogue_calculate_rate = False
DBG_rogue_mutate_gene = False
DBG_rogue_embody_win = False
DBG_rogue_embody_defeat = False
DBG_rogue_wear_item = False
DBG_challenger_perform_battles = False
DBG_challenger_perform_battle = False
DBG_days_report = False # <-- общий отчёт о каждом дне
# ЗАПУСК:
if __name__ == '__main__':
# засечь время:
time_begin = time()
# запустить цикл на указанное количество стадий перезагрузки популяции:
max_days_for_current_stage = 0
current_day = 1
while current_stage < MAX_STAGES:
# на старте первой стадии:
if current_stage == 0:
# создать объект статистики:
stats = Stats()
# создать объект популяции и наполнить его разбойниками в указанном количестве, а также указать их биологические параметры:
population = Population(ROGUES_AT_BEGIN, POSSIBLE_BIRTH_QUANTITIES, wins_to_reproduce=WINS_TO_REPRODUCE, defeats_to_die=DEFEATS_TO_DIE)
# создать объект для управления состязаниями:
challenger = Challenger()
# "прочитать" популяцию:
print(population)
# высчитать новый максимум с учётом наступления новой стадии:
max_days_for_current_stage += MAX_DAYS_AT_STAGE
# запустить/продолжить цикл на доступное количество дней (1 день = 1 столкновение у каждого (почти*) разбойника)
# * - когда в популяции в какой-то день нечётное количество разбойников, кто-то из них остаётся без пары и не дерётся в этот день
while current_day <= max_days_for_current_stage:
print('st ' + str(current_stage) + ', day ' + str(current_day))
if DBG_days_report:
print('nnДЕНЬ/DAY', current_day)
# выполнить серию соревнований:
challenger.perform_battles()
if DBG_days_report:
print('nДень', current_day, 'завершён.')
print(population)
# статистика для этого дня:
stats.add_new_day(current_day)
# сколько дней подряд нет изменений в численности популяции:
if current_day - Population.day_of_last_changes > Population.max_days_without_changes:
Population.max_days_without_changes = current_day - Population.day_of_last_changes
# в конце каждого SLIDING_FREQUENCY дня (а также в первый и последний) отрисовывать слайды по распространённости генотипов:
if current_day % SLIDING_FREQUENCY == 0 or current_day == 1 or current_day == MAX_DAYS_AT_STAGE * MAX_STAGES:
stats.draw_genes_distribution(current_day)
# в конце каждого SLIDING_FREQUENCY дня (а также в первый и последний) отрисовывать слайды по победам генотипов:
if current_day % SLIDING_FREQUENCY == 0 or current_day == 1 or current_day == MAX_DAYS_AT_STAGE * MAX_STAGES:
stats.draw_genes_wins(current_day)
current_day += 1
# когда НЕпоследняя стадия подходит к концу, перезагрузить популяцию, оставив в ней указанное кол-во лучших генотипов:
if current_stage < MAX_STAGES - 1:
population.reload(ROGUES_AT_BEGIN)
current_stage += 1
# теперь понизить назад счётчик текущей стадии, чтобы удобно работать со списком LIST_FOR_DICTS_GENOTYPES:
current_stage -= 1
# вывести статистику дней:
print('nДНИ:')
print(DICT_DAYS)
# нарисовать график о динамике одновременно живущих разбойников:
stats.draw_and_put_line_chart_to_file(DICT_DAYS, 1, 'живое население', 'дни', 'разбойников', 'charts/chart_population_demography.png')
# нарисовать график о динамике общей численности когда-либо живших разбойников:
stats.draw_and_put_line_chart_to_file(DICT_DAYS, 0, 'родившихся всего', 'дни', 'разбойников', 'charts/chart_population_total.png')
# нарисовать график о динамике разнообразия генотипов:
stats.draw_and_put_line_chart_to_file(DICT_DAYS, 2, 'разнообразие генотипов', 'дни', 'уникальных генотипов', 'charts/chart_genotypes_variety.png')
# нарисовать график о динамике ничьих (= столкновение одинаковых генотипов):
stats.draw_and_put_line_chart_to_file(DICT_DAYS, 3, 'динамика ничьих', 'дни', 'ничьих', 'charts/chart_genotypes_ties.png')
# создать общий HTML для изучения сессии:
stats.create_index_html()
# вычислить затраченное время:
time_session = time() - time_begin
duration_info = 'работа программы длилась: ' + str(round(time_session, 2)) + ' сек.'
print('n' + duration_info)
else:
print('__name__ is not "__main__".')
В конце симуляции в папке с программой сгенерируется файл с названием типа «report 2020-04-25_10-33-54.html». О нём подробнее в следующей части статьи.
ЭТАП 4 — визуализируем данные
Для дальнейших объяснений буду использовать такой набор экипировки:
# Эти словари содержат перечни предметов соответствующего типа.
# Каждый элемент содержит кортеж, в котором значения означают следующее:
# 0 - название, 1 - атака, 2 - ловкость, 3 - сила, 4 - меткость, 5 - крит, 6 - мастерство
EQUIPMENT_COLLECTION = 'obvious_strong'
RIGHT_HANDS = dict()
RIGHT_HANDS[1] = ('Сильнейший меч', 5000, 0, 0, 0, 0, 0)
RIGHT_HANDS[2] = ('Средний меч', 800, 0, 0, 0, 0, 0)
RIGHT_HANDS[3] = ('Слабый меч', 20, 0, 0, 0, 0, 0)
LEFT_HANDS = dict()
LEFT_HANDS[1] = ('Сильнейший кинжал', 4000, 0, 0, 0, 0, 0)
LEFT_HANDS[2] = ('Слабый кинжал', 10, 0, 0, 0, 0, 0)
GLOVES = dict()
GLOVES[1] = ('Сильнейшие перчатки', 300, 0, 0, 0, 0, 0)
GLOVES[2] = ('Слабые перчатки', 1, 0, 0, 0, 0, 0)
HEADS = dict()
HEADS[1] = ('Сильнейший шлем', 300, 0, 0, 0, 0, 0)
HEADS[2] = ('Слабый шлем', 1, 0, 0, 0, 0, 0)
CHESTS = dict()
CHESTS[1] = ('Сильнейший нагрудник', 300, 0, 0, 0, 0, 0)
CHESTS[2] = ('Слабый нагрудник', 1, 0, 0, 0, 0, 0)
PANTS = dict()
PANTS[1] = ('Сильнейшие поножи', 300, 0, 0, 0, 0, 0)
PANTS[2] = ('Слабые поножи', 1, 0, 0, 0, 0, 0)
BOOTS = dict()
BOOTS[1] = ('Сильнейшие сапоги', 300, 0, 0, 0, 0, 0)
BOOTS[2] = ('Слабые сапоги', 1, 0, 0, 0, 0, 0)
Здесь возможных комбинаций наборов 192 (3 * 2 * 2 * 2 * 2 * 2 * 2). Соответственно, возможных генотипов будет тоже 192.
Главная идея визуализации: представить всё пространство возможных генотипов как прямоугольное поле, где каждый квадратик представляет отдельный генотип. Несложный алгоритм находит два средних делителя числа 192, это 16 и 12:
# выписать в список все делители числа-суммы генотипов:
list_divisors = list()
current_number = int(self.genotypes_total // 2)
while current_number >= 2:
if self.genotypes_total % current_number == 0:
list_divisors.append(current_number)
current_number -= 1
print('list_divisors:', list_divisors)
# взять индекс примерно из середины полученного списка делителей:
somewhere_in_the_middle = len(list_divisors) // 2
# получить длины сторон будущего прямоугольника:
side_1 = list_divisors[somewhere_in_the_middle]
side_2 = self.genotypes_total / side_1
# определить, какая сторона длиннее, чтобы в будущем прямоугольник "положить" на бок:
self.side_x = int(side_1 if side_1 >= side_2 else side_2)
self.side_y = int(self.genotypes_total / self.side_x)
print('side_x =', self.side_x, 'side_y =', self.side_y)
Получаем область 16х12:
Список возможных генотипов генерируется этим кодом:
# создать список возможных генотипов:
self.list_of_possible_genotypes = list()
# для каждого оружия в правой руке:
for g1 in RIGHT_HANDS:
# для каждого оружия в левой руке:
for g2 in LEFT_HANDS:
# для каждых перчаток:
for g3 in GLOVES:
# для каждого шлема:
for g4 in HEADS:
# для каждого нагрудника:
for g5 in CHESTS:
# для каждых штанов:
for g6 in PANTS:
# для каждой обуви:
for g7 in BOOTS:
current_genotype = str(g1-1)+'-'+str(g2-1)+'-'+str(g3-1)+'-'+str(g4-1)+'-'+str(g5-1)+'-'+str(g6-1)+'-'+str(g7-1)
self.list_of_possible_genotypes.append(current_genotype)
Поэтому квадратики на поле представляют генотипы в таком порядке:
Это важная особенность, ведь, например, генотипы, которые содержат «ген Сильнейшего меча» (голубой уголок) находятся в верхней части поля, а те из них, которые также содержат «ген Сильнейшего кинжала» (синий уголок) — занимают ещё более верхнюю область:
Таким образом, наиболее сильный генотип (0-0-0-0-0-0-0) находится в верхнем левом углу, а наиболее слабый (2-1-1-1-1-1-1) — в противоположном. Это поможет нам при наблюдении за развитием ситуации в динамике, ведь мы будем знать, что в процессе симуляции «доминирующий генофонд» должен смещаться в верхний левый угол поля:
Теперь запустим симуляцию с такими параметрами:
MAX_STAGES = 5
MAX_DAYS_AT_STAGE = 40
SLIDING_FREQUENCY = 1
ROGUES_AT_BEGIN = 8
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1]
HTML_GSQUARE_SIDE = 16
HTML_GSQUARE_MARGIN = 3
То есть 8 разбойников на старте,
Открываем сгенерированный HTML-отчёт и видим такую картину для 1-го и 10-го дня:
Итак, в первый день у нас сгенерировалось 8 разбойников, их квадратики до конца симуляции будут отбрасывать тень. Далее видим, что они начали драться, а значит, появляются первые победы, приводящие к размножению. Размножение с большой вероятностью сопряжено с мутациями, поэтому окрашенных квадратиков становится больше.
Заглянем в последующие дни. На 44-й день появился генотип "0-0-0-0-0-0-0" (см. за синей стрелкой). На 59-й день он уже вырвался вперёд по победам (см. за красной стрелкой).
На 137-й день видно, что "0-0-0-0-0-0-0" выбился в лидеры и по количеству появлений в популяции (см. за синей стрелкой). И на слайде последнего дня у него появилась золотая тень, так как он удержал за собой первое место по количеству побед.
Как видим, действительно, естественный отбор смещает «генофонд» популяции влево и вверх, то есть в сторону более сильной экипировки. "Нижеправые" генотипы слабее "верхнелевых", поэтому они исчезают, едва появившись (красный цвет означает отсутствие побед). Более чётко это видно на большем масштабе:
Ну и вердикт в отчёте выдан верный: генотип-победитель — 0-0-0-0-0-0-0:
Графики, полученные при помощи matplotlib, помогут дополнительно оценить происходящее:
1. график "живое население" показывает динамику изменения количества одновременно живущих разбойников;
2. график "родившихся всего" в основном близится к прямой линии, если не начать играться с демографическими параметрами:
3. график "разнообразие генотипов" — обычно быстрый рост сначала, затем замедляется, постепенно приближаясь к максимуму;
4. график "динамика ничьих" — показывает, как с течением времени меняется количество ничьих (это бои, когда в бессмысленной схватке сталкиваются два одинаковых генотипа):
Бывает такое, что популяция «застаивается», когда в ней остаются разбойники с одинаковыми генотипами (на графиках наблюдается: резкий рост количества ничьих, неизменность в численности населения и численности уникальных генотипов).
Застой популяции означает, что вычисление и отрисовка слайдов происходит зря. Чтобы сократить периоды застоя, нужно снизить значение константы MAX_DAYS_AT_STAGE, и будет видно, что застой сократился, а местами вовсе исчез:
ЭТАП 5 — испытываем большие пространства генотипов
Теперь попробуем запустить симуляцию для рассматриваемого в прошлой статье набора экипировки evolution_equipment_custom чуть с другими параметрами. Здесь значение POSSIBLE_BIRTH_QUANTITIES = [1, 2] означает, что при акте размножения с 50%-ой вероятностью на свет появится либо 1, либо 2 потомка. Это усилит динамику происходящего:
MAX_STAGES = 20
MAX_DAYS_AT_STAGE = 50
SLIDING_FREQUENCY = 10
ROGUES_AT_BEGIN = 8
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1, 2]
HTML_GSQUARE_SIDE = 10
HTML_GSQUARE_MARGIN = 3
Здесь паттерн распределения генотипов на слайдах будет иным, ведь наиболее значимая для общего результата экипировка («Меч Мастера») теперь находится в «других местах». Для визуализации этого набора экипировки уже характерно появление ряда «очагов силы» в разных местах, где сила экипировки выше, чем в соседних «районах».
Кстати, этот алгоритм безошибочно определил топовый набор экипировки (3-3-0-0-0-0-1), совпадающий с тем, который определялся комбинаторным алгоритмом с прошлой статьи:
И, наконец, я запустил тест для расширенного набора, который даёт 18432 комбинации:
MAX_STAGES = 30
MAX_DAYS_AT_STAGE = 50
SLIDING_FREQUENCY = 100
ROGUES_AT_BEGIN = 20
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1, 2]
HTML_GSQUARE_SIDE = 4
HTML_GSQUARE_MARGIN = 1
В общем, можно продолжать с этим забавляться, но остаётся неизменной тенденция: в ходе симуляции генотипы довольно быстро начинают скапливаться в этих самых «очагах силы». И доминирующий генотип оказывается в одном из самых ярких «очагов».
ЭТАП 6 — а имеет ли это всё смысл?
Если обратиться теперь к практической стороне вопроса, то нужно понять, способен ли этот генетический алгоритм найти правильный ответ ценой меньшего количества боёв, чем простой комбинаторный перебор всех генотипов. Ответ: да, способен. Доказательство под катом:
Комбинаторному алгоритму достаточно подсчитать рейтинг экипировки по одному разу для каждой комбинации, т.е. 1728 раз.
Итак, генетический алгоритм должен найти ответ менее чем за 1728 таких же расчётов. Один «бой» между двумя разбойниками — это сразу 2 расчёта (для каждого из них). Итак, боёв должно быть не больше, чем 1728 / 2 = 864. Поехали.
Подобрал такие параметры:
MAX_STAGES = 8
MAX_DAYS_AT_STAGE = 20
SLIDING_FREQUENCY = 10
ROGUES_AT_BEGIN = 10
WINS_TO_REPRODUCE = 2
DEFEATS_TO_DIE = 2
POSSIBLE_BIRTH_QUANTITIES = [1]
HTML_GSQUARE_SIDE = 10
HTML_GSQUARE_MARGIN = 3
Специально для наглядности выбрал результат, где начальные генотипы расположены подальше от будущего лидера 3-3-0-0-0-0-1:
Отчёт:
Итак, получилось прийти к ответу 3-3-0-0-0-0-1 за 547 боёв. Причём 87 боёв оказались напрасными (ничьи), что составляет 16% бесполезной работы.
На генофондах больших размеров выгода должна быть более ощутима.
P.S. На правильный ответ удаётся выйти даже при ROGUES_AT_BEGIN = 2 и POSSIBLE_BIRTH_QUANTITIES = [1]. Это кажется удивительным, ведь численность популяции ни разу не поднимается выше 2 разбойников. Потому что один проигрывает, другой выигрывает, первый умирает, а второй рождает одного потомка. И родитель начинает состязаться уже с этим потомком. Потомок либо сильнее, либо слабее. И таким образом движется безжалостное колесо отбора между родителем и его же потомком, пока не придёт в лучшую точку (которой сумеет достичь за отведённое время, поэтому это не всегда наилучшая).
Итоги
- Поставленная задача решаема при помощи генетических алгоритмов.
- Визуализация происходящего таким «псевдокартографическим» методом позволяет наблюдать тенденции и динамику в отыскивании эффективных генотипов на всех этапах симуляции.
- При оптимальной комбинации начальных параметров можно добиться того, чтобы генетические алгоритмы использовали меньше ключевых операций, чем это сделает простой перебор всех возможных вариантов (здесь таковой операцией был расчёт силы персонажа в методе calculate_rate класса Rogue, который в иных случаях может быть гораздо более дорогостоящим).
- Разумеется, над этой программой можно ещё экспериментировать и экспериментировать, улучшая эффективность. Например, в какой-то момент начать «банить» явно проигрышные генотипы, не позволяя их владельцам сражаться или даже появляться. Таким образом, будет сужаться воронка «лидеров», где они между собой должны точно определить, кто «сильнейший».
Весь код проекта я выложил на гитхабе.
Уважаемое сообщество, буду рад обратной связи по этой теме.
