class QuebraDoceGenerator: """ Esta classe é utilizada para manter as informações necessárias pelo Algoritmo Genético e para gerar mapas para o jogo. """ def __init__(self, pop_size=25, n_kids=10, crossover_rate=0.75, mutation_rate=0.01): """ Inicializa o gerador, passando informações necessárias. pop_size -> tamanho da população n_kids -> quantidade de filhos criados crossover_rate -> taxa de cruzamento (depende do método utilizado) mutation_rate -> taxa de mutação As variáveis de n_simulations e n_moves são usadas na simulação de uma fase e *NÃO DEVEM* ser modificadas. O valor de bias e best_distance são usados no interior do processo e não precisa ser modificado. """ self.pop_size = pop_size self.crossover_rate = crossover_rate self.mutation_rate = mutation_rate self.n_simulations = 100 self.n_moves = 1 self.bias = 0.00 self.best_distance = 1.0 self.n_kids = n_kids def _evaluate_content(self, content): """ Avalia um conteúdo gerado, retornando o seu desempenho médio. (calculado por um bot) """ bot = qd_bot.QuebraDoceAI(string=content) resultado = bot.do_playouts(n=self.n_simulations, n_moves=self.n_moves, info=False) return round(resultado, 3) def generate_moves(self): """ Gera uma quantidade de movimentos pro mapa. Este valor varia de 5 até 30. """ if self.fixed_moves is not None: return self.fixed_moves else: return random.randint(5, 30) def generate_types(self): """ Gera a quantidade de peças diferentes estarão no mapa. Este valor varia de 4 até 6. """ if self.fixed_types is not None: return self.fixed_types else: return random.randint(4, 6) def generate_points(self, types): """ Gera a quantidade de pontos necessário para completar a fase. Quanto mais peças diferentes, menor é a pontuação criada. (pois fases com mais peças é mais dificil de fazer combinações) """ if self.fixed_points is not None: return self.fixed_points elif self.points: x = abs(types - 6) return random.randint(0, 100000 + x*20000) else: return 0 def _random_level(self): """ Gera um mapa de forma aleatória. """ # String contendo o mapa string = '' # Quantidade de movimentos moves = self.generate_moves() # Quantidade de tipos types = self.generate_types() # Pontuação necessária points = self.generate_points(types) # Adiciona essa informação na string string += str(moves) + "," string += str(points) + "," string += str(types) + "\n" # Gera o formato do mapa pieces = None for i in range(9): # O mapa é gerado de baixo pra cima, # por isso não pode haver peças de objetivo na ultima linha. # Se não for a ultima linha, pode utilizar todas as peças if i > 0: pieces = self.pieces else: pieces = self.first_pieces # Percorre todas as posições for j in range(9): # Gera a peça p = random.choice(pieces) string += str(p) # Se não for a ultima peça, adiciona a ',' if j != 8: string += "," # Adiciona a nova linha string += "\n" # Retorna o mapa return string def _select(self, pop): """ pop -> população completa Método que seleciona o 2 melhores mapas da população. (avaliando o que tiver a menor distância do objetivo) """ pop.sort(key=lambda data:data['distance']) return pop[:2] def _standard_crossover(self, parents): """ parents -> [p1, p2] Método de cruzamento padrão. caso passe pela taxa de cruzamento, escolhe aleatoriamente uma informação de um dos pais (pra cada posição). Caso contrário, retorna o que tiver a menor distância. """ child = None # Se estiver no crossover_rate, une os dois if random.uniform(0.0, 1.0) <= self.crossover_rate: string = '' p1 = parents[0]['level'] p2 = parents[1]['level'] p1_lines = p1.split("\n") p2_lines = p2.split("\n") line_1 = p1_lines[0].split(",") line_2 = p2_lines[0].split(",") for i in range(len(line_1)): x = int(line_1[i]) y = int(line_2[i]) value = random.choice([x, y]) string += str(value) if i != 2: string += "," string += "\n" for i in range(1, 10): line_1 = p1_lines[i] line_2 = p2_lines[i] for j in range(len(line_1)): if line_1[j] != ",": x, y = int(line_1[j]), int(line_2[j]) value = random.choice([x, y]) string += str(value) else: string += "," string += "\n" child = string # Caso não rolou crossover, retorna o melhor else: child = min(parents, key=lambda x:x['distance']) child = child['level'] # Retorna a lista com a criança return [ { 'level': child, 'evaluate': 0.0, 'distance': 1.0, } ] def _mutate(self, child, distance): """ child -> filho a ser mutado distance -> distância do filho pro objetivo Método de mutação. Aplica mutação ao filho, utilizando a taxa de mutação definida junto da distância. """ string = '' # calcula o mutation rate # Quanto mais longe do resultado esperando, mais mutação mutation_rate = self.mutation_rate + (distance/10) # Divide as linhas lines = child.split("\n") # Divide as informações dos cabeçalhos info = lines[0].split(",") # Pega movimentos moves = 0 if random.uniform(0.0, 1.0) <= mutation_rate: moves = self.generate_moves() else: moves = int(info[0]) # Pega Tipos types = 0 if random.uniform(0.0, 1.0) <= mutation_rate: types = self.generate_types() else: types = int(info[2]) # Pega pontos points = 0 if random.uniform(0.0, 1.0) <= mutation_rate: points = self.generate_points(types) else: points = int(info[1]) # Escreve o cabeçalho string += str(moves) + "," string += str(points) + "," string += str(types) + "\n" # Escreve o mapa ps = None for i in range(1, 10): line = lines[i] pieces = line.split(",") # Se for depois da primeira linha if i > 1: ps = self.pieces else: ps = self.first_pieces # Percorre uma linha for j in range(len(pieces)): p = 0 if random.uniform(0.0, 1.0) <= mutation_rate: p = random.choice(ps) else: p = pieces[j] string += str(p) if j != 8: string += "," string += "\n" # Retorna o mapa return string def _standard_selection(self, pop): """ pop -> população Método de Seleção Padrão. Seleciona uma dupla de indivíduos. """ # Decide o limite dos melhores limit = 10 if self.pop_size < limit: limit = self.pop_size # Pega os melhores pop.sort(key=lambda x: x['distance']) best = pop[:limit] best = copy.deepcopy(best) # Escolhe aleatoriamente os melhores p1 = random.choice(best) p2 = random.choice(best) return [p1,p2] def _create_kids(self, pop): """ pop -> população Cria os filhos desta geração. Utiliza os métodos de Seleção, Crossover e mutação para gerar n_kids filhos. """ # Usado no método de seleção estocastico global valor_segmento valor_segmento = None # Cria os N Filhos kids = [] while len(kids) < self.n_kids: # Escolhe aleatoriamente os melhores parents = self._selection_method(pop) # Crossover dos pais p_kids = self._crossover_method(parents) # Adiciona o valor médio de distância, # para usar na mutação value = 0 for p in parents: value += p['distance'] value /= len(parents) # Faz a mutação nos filhos gerados pelo crossover for p_kid in p_kids: # Muta a criança str_kid = self._mutate(p_kid['level'], value) # Adiciona a lista de filhos data = { 'level': str_kid, 'evaluate': 0.0, 'distance': 1.0 } kids.append(data) # Retorna os filhos return kids def _kill_bad(self, pop, kids, target): """ pop -> população kids -> filhos gerados target -> objetivo a ser alcançado Une a população com os filhos e retorna os pop_size melhores. """ # Avalia todos os filhos criados for k in kids: k['evaluate'] = self._evaluate_content(k['level']) k['distance'] = abs(k['evaluate'] - target) self.save_level(k) pop.append(k) # Retorna apenas os pop_size melhores pop.sort(key=lambda data:data['distance']) pop = pop[:self.pop_size] pop = copy.deepcopy(pop) return pop def save_level(self, data): # Só salva os avaliação maior ou igual a 0.75 if data['evaluate'] < 0.75: return # Verifica se não existe essa fase gerada levels = glob.glob('levels/*.json') for l in levels: with open(l) as f: test = json.load(f) if test['level'] == data['level']: return # informações do nome do arquivo score = int(data['evaluate'] * 100) n = len(levels) # gera o arquivo name = 'levels/{0}_{1}.json'.format(n, score) with open(name, 'w', encoding='utf-8') as f: json.dump(data, f, indent=4) def generate_level(self, target, n_generations=1000, points=True, blocks=True, canes=True, s_method=None, c_method=None, fixed_points=None, fixed_moves=None, fixed_types=None): """ target -> objetivo a ser alcançado n_generations -> número de gerações points -> o mapa terá modo de pontuação? blocks -> o mapa terá modo de bloqueios? canes -> o mapa terá modo de objetivo? s_method -> método de seleção utilizado c_method -> método de crossover utilizado Gera um mapa do jogo com o desempenho médio desejado e com os objetivos inseridos. """ # Inicializa os atributos fixos self.fixed_points = fixed_points self.fixed_moves = fixed_moves self.fixed_types = fixed_types # Usado para verificar se o código é inválido invalid = False start = time.time() # Confere os targets invalidos if target > 1.0: invalid = True elif target < 0.0: invalid = True elif target < self.bias: invalid = True elif (not points) and (not blocks) and (not canes): invalid = True # Não é possivel gerar if invalid: print('deu ruim') return False # Adiciona o método de seleção if s_method is None: self._selection_method = self._standard_selection else: self._selection_method = s_method # Adiciona o método de crossover if c_method is None: self._crossover_method = self._standard_crossover else: self._crossover_method = c_method # Inicializa as peças self.first_pieces = [0, 1] self.pieces = [0, 1] # Inicializa os modos self.points = points self.blocks = blocks self.canes = canes # Se for o modo de bloqueio, adiciona essas # peças possíveis if blocks: self.first_pieces.append(2) self.pieces.append(2) # Se for o modo objetivo, adiciona essa # peça if canes: self.first_pieces.append(3) # Percorre tantas gerações target_level = None found = False # Gera uma população inicial pop = [] for i in range(self.pop_size): l = self._random_level() val = self._evaluate_content(l) d = abs(val - target) data = { 'level': l, 'evaluate': val, 'distance': d} pop.append(data) # Inicializa o bias self.bias = 0.001 # Inicializa a melhor distância self.best_distance = 1.0 # Verifica se encontrou um resultado finished = False # Percorre a geração for gen in range(n_generations): # Recebe a melhor população best_pop = self._select(pop) best_pop = copy.deepcopy(best_pop) # Pega a melhor distância if best_pop[0]['distance'] < self.best_distance: self.best_distance = best_pop[0]['distance'] # Informações da geração print('\r' + ' '*100, end='') print('\rGERAÇÃO [{0}/{1}] -> MELHOR = [{2:.3f}, {3:.3f}] - [{4} mapas gerados]'.format( gen+1, n_generations, best_pop[0]['evaluate'], best_pop[0]['distance'], len(glob.glob('levels/*.json')) ), end='' ) # Se é melhor que o bias target_level = best_pop[0] if best_pop[0]['distance'] <= self.bias: print(" ENCONTRADO!", end='') finished = True break # Cria novos filhos e elimina os piores kids = self._create_kids(pop) pop = self._kill_bad(pop, kids, target) else: print(' NÃO ENCONTRADO!', end='') # Tempo demorado end = time.time() - start # Retorna os resultados return { 'tempo': end, 'gen': gen + 1, 'completo': int(finished), }