Evoluční algoritmus pro taktickou attack/defense turn hru

Popis problému

Implementace evolučního algoritmu pro trénování obránce v taktické hře. Jeden obránce chrání ovoce před útočníkem. Hra má dvě fáze:

1. Přípravná fáze (100 tahů) - obránce připravuje obranu
2. Útočná fáze (100 tahů) - útočníci sbírají ovoce pomocí BFS

Herní elementy:

• 0 = prázdné pole
• 1 = obránce (trénovaný agent)
• 2 = zeď (lze tlačit obráncem)
• 3 = ovoce (cíl ochrany, lze tlačit obráncem)
• 4 = útočník (BFS)

Reprezentace řešení

Grey code encoding

Každý agent = 400 bitů (100 pohybů × 4 bity)

Každé 4 bity kódují jeden pohyb:

• Bity 0-1: směr (0=N, 1=E, 2=S, 3=W)
• Bity 2-3: akce (0=stát, 1=pohyb/tlačení)

def dekoduj_pohyby_agenta(grey_agent): # fancy bitshifting
    binary_data = prevod_grey_na_binary(grey_agent)
    pohyby = []
    
    for i in range(0, 400, 4):
        bits = binary_data[i:i+4]
        smer = (bits[0] << 1) | bits[1]
        akce = (bits[2] << 1) | bits[3]
        pohyby.append((smer % 4, akce % 4))
    
    return pohyby

Grey to Binary conversion

def prevod_grey_na_binary(grey_kod):
    binary = [grey_kod[0]]
    for i in range(1, len(grey_kod)):
        binary.append(binary[i-1] ^ grey_kod[i])
    return binary

Fitness funkce

fitness = survival_turns + saved_fruits × 50 + exploration × 0.5 + path_length × 0.1

Komponenty:

• survival_turns - suma tahů, které každé ovoce přežilo útočnou fázi
• saved_fruits - počet nesebraného ovoce
• exploration - počet unikátních navštívených polí (přípravná fáze)
• path_length - euklidovská vzdálenost od začátku pohybu do konce

Evoluční algoritmus

Parametry

pop_size = 200          # velikost populace
gens = 1000            # počet generací  
elite_pct = 0.1        # 10% elitismus
crossover_prob = 0.6   # two-point crossover
mut_prob = 0.15 or 0.3    # adaptivní mutace
tournament_size = 3    # tournament selection

Hlavní loop

for gen in range(gens):
    # Evaluace všech jedinců
    for agent in pop:
        agent.fitness.values = eval_agent(agent, sim)
    
    # Řazení podle fitness
    pop = sorted(pop, key=lambda x: x.fitness.values[0], reverse=True)
    
    # Elitismus - zachování nejlepších 10%
    elite_cnt = int(pop_size * elite_pct)
    elite = pop[:elite_cnt]
    
    # Selekce a reprodukce
    offspring = tb.select(pop, pop_size - elite_cnt)
    offspring = list(map(tb.clone, offspring))
    
    # Crossover
    for child1, child2 in zip(offspring[::2], offspring[1::2]):
        if random.random() < 0.6:
            tb.mate(child1, child2)
            del child1.fitness.values
            del child2.fitness.values
    
    # Adaptivní mutace
    div = calc_diversity(pop)
    mut_prob = 0.3 if div < 0.3 else 0.15
    
    for mutant in offspring:
        if random.random() < mut_prob:
            tb.mutate(mutant)
            del mutant.fitness.values
    
    # Fresh blood injection
    if gen % 10 == 0 and div < 0.4:
        fresh_cnt = min(5, len(offspring) // 10)
        fresh = tb.pop(n=fresh_cnt)
        offspring = offspring[:-fresh_cnt] + fresh
    
    # Nová populace
    pop = elite + offspring

Pathfinding útočníka

Útočník používá BFS pro nalezení nejkratší cesty k nejbližšímu ovoci:

def bfs_najdi_cestu(mapa, start, cil):
    queue = deque([(start, [])])
    navstiveno = set([start])
    
    while queue:
        (x, y), cesta = queue.popleft()
        
        if (x, y) == cil:
            return cesta
        
        for smer_idx, (dx, dy) in enumerate(SMERY):
            nx, ny = x + dx, y + dy
            
            if (0 <= nx < cols and 0 <= ny < rows and 
                (nx, ny) not in navstiveno and
                mapa[ny][nx] in [PRAZDNE, OVOCE]):
                
                navstiveno.add((nx, ny))
                nova_cesta = cesta + [smer_idx]
                queue.append(((nx, ny), nova_cesta))
    
    return []

Implementace

Struktura kódu

game_module.py  # GameSim, PathAttacker třídy
learn.py        # evoluční algoritmus
level_editor.py # level editor
maps/          # testovací mapy
snapshots/     # výsledky

Spuštění

python learn.py maps/exp1.json

Výstup

Training...
Gen 0: Best=145.2 (init), Top10=127.3, Div=0.892
Gen 1: Best=156.8 (up), Top10=134.7, Div=0.845
...

Klíčové pozorování

• Exploration bonus nutný proti "líným" strategiím
• Elitismus zabraňuje ztrátě dobrých řešení
• Adaptivní mutace udržuje diverzitu
• Fresh blood pomáhá při předčasné konvergenci

Výsledky evoluce

Typické fáze:

1. Generace 0-20: rychlý růst fitness (~100 → ~600)
2. Generace 20-100: jemné ladění exploration/idle balance
3. Generace 100+: konvergence k lokálnímu optimu

Ukázky řešení

• ŽLUTÁ BARVA "cíl"
• MODRÁ BARVA obránce
• ČERVENÁ BARVA útočník

Experiment 1

Optimální řešení

Experiment 2

Optimální řešení

Experiment 3

Optimální řešení

Experiment 4

Optimální řešení

Experiment 5

Optimální řešení