🎲 👒 🔪 Choosing the equipment for a game Persian using genetics / evolution in Python 🔦 🔥 🤣

How to choose the best equipment in your favorite game? Of course, you can banally sort through all its possible combinations (for example, for the robber from World of Warcraft) and find the best. Without any magic or machine learning. But is it possible to achieve this result not “head on”, but with the help of genetic algorithms, without trying on each combination? It is interesting to know how robbers breed and evolve? Go.

This article is a deepening of the previous topic , which already describes the details of the character's implementation and the impact of equipment.

Purpose: to show those interested how to create a virtual population of game agents on their own, push them together, implement a simple genetic algorithm (with mutations) and visualize all this using HTML, CSS and Javascript.

What you need:

1. Python 3 + install the matplotlib module ; IDE (I have PyCharm);
2. if you want to edit an interactive report template, then a basic understanding of HTML, CSS, JavaScript (jQuery).

STEP 1 - set a goal, deal with OOP

So, the ultimate goal of our coding is to make it possible to get the best outfit with a simulation of genetics / evolution / natural selection. And get the opportunity to visually trace this path.

We turn our goal into specific tasks:

to think over and implement the genetic mechanism at the individual level (the “genes” of the robber should directly affect the choice of equipment)
implement the mechanisms of the birth of descendants, the transfer of genes to them, as well as random minor mutations, to ensure variability and the very possibility of finding the best
to realize the genetic “competition”, the selection of genes (to push their carriers together, so that the outcome of the collision overthrows the “bad” genes and elevates the “good” ones)
assemble everything into a coherent system in which robbers can evolve into ideal fighters
to collect and visualize data so that there is something to admire (otherwise it’s interesting!)
evaluate the usefulness of these activities

Here OOP will help us, we will create 4 fundamental classes:

STEP 2 - sharpening the Rogue class for breeding

agree on terms on the shore

In this article I will part with the terms “gene” (in the code - gene ) and “genotype” (in the code - genotype ). There will also be “mutations” (in the code - mutate , mutation ), implying a change in one or more genes of their meaning. Reproduction will occur simply by “budding” the descendant from the parent, so there will be no crossing over and other similar complications. The robber's genotype is a list of 7 numbers , which are his genes:

So, the Rogue class is growing significantly compared to the last time .

1.The robber receives the genes in one of the possible ways (was generated on the very first day or inherited from the “parent” with or without a mutation). The methods generate_random_genes , mutate_genes , mutate_gene are responsible for this :

code gene-forming methods

    #     ():
    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":' + '\n\tgenes generated:\n\t', 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"   :' + '\n\t  \n\told 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" :' + '\n\t : ' + 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" :' + '\n\told 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":' + '\n\tgene_id: ' + str(gene_id) + '\n\told 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) + '\n\ttries: ' + str(tries))

2. Genes (genotype) determine which gear wear robber (immediately at ~~birth~~ initialization object). To do this, the apply_genes method is called :

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":' + '\n\t.')
            print(self)

3. The equipment will determine the final value of the "rating" of the robber. To do this, the calculate_rate method will be called , which calculates the mathematical expectation of damage:

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. The rating of the robber will be the determining factor leading to reproduction or shameful death. For this, the concepts of “victory” ( embody_win method ) and “defeat” ( embody_defeat method ) are introduced :

embody_win and 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 + ' ...')

Well, the class constructor has been redesigned accordingly to make this chain “genes - equipment - rating” work:

Rogue class constructor

    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()

To summarize this class logic with a picture:

STAGE 3 - Population, Stats and Challenge Classes

The Population class is only needed for three things:

creating a population from the specified number of robbers with random genes and biological parameters that will always be unchanged ( wins_to_reproduce - how many victories a robber needs to gain for reproduction, defeats_to_die - how many defeats will make an individual die);
"Reset" of the population, i.e. when the last day of the current Stage ends, all robbers are destroyed and robbers with the best genotypes are created (see the reload method );
storing some population data for statistics.

class population

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)

The Stats class performs two main tasks:

data collection during the simulation (for example, indicators of each day: the number of living robbers, the number of unique genotypes, etc.)
( matplotlib, HTML-, ).

Looking ahead, I show how this report will look:

The HTML template code for the report is available on the github .

The Stats class is also better viewed on the github (otherwise it will hurt a lot of lines here).

The Challenger class is responsible for simulating collisions between randomly selected robbers. Every day, the method is called perform_battles , which forms from living robbers dueling pair and confronts them with a method perform_battle , and eventually for every robber is caused either method embody_win , any method embody_defeat. By the way, if it turns out that a draw has occurred (genotypes, and therefore the ratings of the robbers are the same), then they diverge without consequences:

class challenger

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 !  !')

Well, now we turn to the body of the program, which links together all the mentioned parts of the code. First come the constants that determine the key parameters of the simulation: the number of stages, days in a stage, the initial number of robbers in a population, etc. Then comes the auxiliary constants for debugging. And the challenges themselves:

code to run the simulation

# :
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('\n\n/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__".')

At the end of the simulation, a file with a type name “report 2020-04-25_10-33-54.html” is generated in the program folder. More about it in the next part of the article.

STEP 4 - visualize the data

For further explanations I will use this set of equipment:

evolution_equipment_obvious_strong.py

#       .
#    ,     :
# 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)

Here are the possible combinations of 192 sets (3 * 2 * 2 * 2 * 2 * 2 * 2). Accordingly, there will be 192 possible genotypes .

The main idea of visualization : to represent the entire space of possible genotypes as a rectangular field, where each square represents a separate genotype. A simple algorithm finds two middle divisors of the number 192, these are 16 and 12:

the code for this algorithm from the constructor of the Stats class

        #      - :
        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)

We get a 16x12 area:

A list of possible genotypes is generated by this code:

        #    :
        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)

Therefore, the squares on the field represent the genotypes in this order:

This is an important feature, because, for example, genotypes that contain the “Strong Sword gene” ( blue corner) are in the upper part of the field, and those that also contain the “Strong Dagger gene” ( blue corner) - occupy an even higher region:

Thus, the strongest genotype ( 0-0-0-0-0-0-0-0 ) is in the upper left corner, and the weakest ( 2-1-1-1- 1-1-1 ) - in the opposite. This will help us in observing the dynamics of the situation, because we will know that during the simulation the “dominant gene pool” should shift to the upper left corner of the field:

Now run the simulation with the following parameters:

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

That is, 8 thieves at the start, <div> -containers with fields (hereinafter referred to as slides ) are created for each day, 5 stages of 40 days each. As a result, we get two sets of slides of 200 pieces each: " prevalence of genotypes " (blue-green colors) and " victory of genotypes " (red and green colors). The color saturation of the squares depends on the values.

We open the generated HTML report and see this picture for the 1st and 10th days:

So, on the first day, 8 robbers were generated, their squares will cast a shadow until the end of the simulation. Further, we see that they began to fight, which means that the first victories appear, leading to reproduction. Reproduction with high probability is associated with mutations, so there are more colored squares.

Take a look in the following days. On the 44th day, the genotype " 0-0-0-0-0-0-0-0 " appeared (see behind the blue arrow). On the 59th day, he already pulled ahead on victories (see behind the red arrow).

On the 137th day it can be seen that " 0-0-0-0-0-0-0-0 " was beaten in the lead by the number of appearances in the population (see behind the blue arrow). And on the slide of the last day he had a golden shadow, as he held the first place in terms of the number of victories.

As you can see, indeed, natural selection shifts the “gene pool” of the population to the left and up, that is, towards stronger equipment. The “ lower-right ” genotypes are weaker than the “ upper left ” ones, therefore they disappear as soon as they appear (red indicates no victories).This is more clearly seen on b abouton a larger scale:

Well, the verdict in the report is correct: the winning genotype is 0-0-0-0-0-0-0-0 : The

graphs obtained with matplotlib will help to further evaluate what is happening:

1. the “ live population ” graph shows the dynamics changes in the number of simultaneously living robbers;
2. the graph of " born all " is mostly close to a straight line, if you do not start playing with demographic parameters:

3. the graph of " diversity of genotypes " - usually rapid growth at first, then slows down, gradually approaching the maximum;
4. schedule " draw dynamics"- shows how the number of draws changes over time (these are fights when two identical genotypes clash in a meaningless fight):

It happens that a population" stagnates "when robbers with the same genotypes remain in it (graphs show: a sharp increase in the number of draws, immutability . in terms of population and the number of unique genotypes)

stagnation of the population means that the calculation and drawing slides going in vain to reduce the periods of stagnation, it is necessary to reduce the value MAX_DAYS_AT_STAGE constant, and it will be seen that the congestion has decreased, and in some places completely disappeared.:

STEP 5 - experience large genotype spaces

Now let's try to run the simulation for the evolution_equipment_custom equipment set discussed in the last article with slightly different parameters. Here, the value POSSIBLE_BIRTH_QUANTITIES = [1, 2] means that with the act of reproduction with a 50% probability, either 1 or 2 descendants will be born . This will enhance the dynamics of what is happening:

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

Here the pattern of distribution of genotypes on the slides will be different, because the equipment most significant for the overall result (“Sword of the Master”) is now in “other places”. The visualization of this set of equipment is already characterized by the appearance of a number of “foci of power” in different places where the power of the equipment is higher than in the neighboring “areas”.

By the way, this algorithm unmistakably determined the top set of equipment ( 3-3-0-0-0-0-0-1 ), which matches the one determined by the combinatorial algorithm from the previous article :

And, finally, I ran the test for the extended set , which gives 18432 combinations:

with such parameters

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

In general, you can continue to amuse yourself with this, but the trend remains unchanged: during the simulation, genotypes rather quickly begin to accumulate in these very “centers of power”. And the dominant genotype is in one of the most striking “foci”.

STEP 6 - Does it all make sense?

If we turn now to the practical side of the question, we need to understand whether this genetic algorithm is able to find the right answer at the cost of fewer fights than a simple combinatorial search of all genotypes. Answer: yes, capable . Proof under the cut:

proof of the effectiveness of the genetic algorithm

1728 .

, .. 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% .

.

PS It is possible to get the correct answer even with ROGUES_AT_BEGIN = 2 and POSSIBLE_BIRTH_QUANTITIES = [1] . This seems surprising, because the population never rises above 2 robbers. Because one loses, the other wins, the first dies, and the second gives birth to one descendant. And the parent begins to compete with this descendant. The descendant is either stronger or weaker. And in this way the ruthless selection wheel moves between the parent and his descendant until he comes to a better point (which he can achieve in the allotted time, so this is not always the best).

Summary

The problem is solved using genetic algorithms.
«» .
, , ( calculate_rate Rogue, ).
Of course, on this program you can still experiment and experiment, improving efficiency. For example, at some point, start to “ban” obviously losing genotypes, not allowing their owners to fight or even appear. Thus, the funnel of “leaders” will narrow down, where they must determine exactly who is “strongest” among themselves.

I posted all the project code on the github .

Dear community, I will be glad to receive feedback on this topic.

Choosing the equipment for a game Persian using genetics / evolution in Python