paint-brush
Jogando Damas com Algoritmos Genéticos: Aprendizagem Evolutiva em Jogos Tradicionaispor@vivalaakam
686 leituras
686 leituras

Jogando Damas com Algoritmos Genéticos: Aprendizagem Evolutiva em Jogos Tradicionais

por Andrey Makarov27m2024/03/08
Read on Terminal Reader

Muito longo; Para ler

Neste artigo, exploraremos a interseção entre damas e algoritmos genéticos, demonstrando como técnicas computacionais evolutivas podem ser empregadas para desenvolver agentes proficientes para jogar damas. No meu último artigo, acho que já abordei o tema das damas o suficiente, mas ainda assim, vamos lembrar as regras básicas do jogo: O jogo de damas é jogado num tabuleiro 10x10, com cada jogador começando com 20 peças. c
featured image - Jogando Damas com Algoritmos Genéticos: Aprendizagem Evolutiva em Jogos Tradicionais
Andrey Makarov HackerNoon profile picture

Introdução

Damas, também conhecidas como damas, é um jogo antigo e popular há muito tempo. Como outros jogos de tabuleiro clássicos, atraiu o interesse de cientistas da computação e pesquisadores de IA como plataforma para seus experimentos. Um método proeminente que usam para treinar computadores para jogar damas é um algoritmo genético, que se baseia no conceito de sobrevivência do mais apto que impulsiona a evolução.


Neste artigo, exploraremos a interseção entre damas e algoritmos genéticos, demonstrando como técnicas computacionais evolutivas podem ser empregadas para desenvolver agentes proficientes para jogar damas.


No meu último artigo , acho que já abordei o tema das damas o suficiente, mas ainda assim, vamos lembrar as regras básicas do jogo: O jogo de damas é jogado em um tabuleiro 10x10, com cada jogador começando com 20 peças.


O objetivo é simples: capturar todas as peças do seu oponente ou prendê-las para que não possam se mover. As estratégias primárias giram em torno de posicionamento, defesa, ataque e previsão dos movimentos do oponente.

Algoritmos Genéticos (AGs)

O básico

AGs são algoritmos de otimização baseados no processo de seleção natural. Esses algoritmos refletem o procedimento de evolução observado na natureza, compreendendo seleção, cruzamento (recombinação) e mutação.

Componentes de uma rede neural

Este artigo usará um modelo simples com camadas totalmente conectadas. Uma camada é uma coleção de neurônios que processam entradas e produzem saídas. Essas saídas são então usadas como previsão final no caso da última camada (camada de saída) ou passadas como entrada para a próxima camada da rede.


Cada camada contém:

  • entradas : número de parâmetros de entrada


  • saídas : número de parâmetros de saída


  • pesos : pesos são os parâmetros que a rede ajusta durante o treinamento para minimizar o erro de previsão.


  • polarização : é adicionado à soma de entrada antes da função de ativação. O viés ajuda a ajustar a saída junto com os pesos.


  • função de ativação : Cada neurônio em uma camada, exceto a camada de entrada, aplica uma função de ativação à sua entrada antes de passar a saída para a próxima camada. Isso é essencial para que a rede modele relacionamentos não lineares nos dados.

Componentes de um algoritmo genético

  • População : Um conjunto de soluções candidatas.


  • Função Fitness : Avalia o desempenho ou “adequação” de uma solução individual.


  • Seleção : Com base na aptidão, algumas soluções são selecionadas para reprodução.


  • Crossover : Combinação de partes de duas soluções selecionadas para criar descendentes.


  • Mutação : introdução de pequenas mudanças aleatórias na prole.

Aplicando Algoritmos Genéticos a Damas

Codificando o problema e avaliação de aptidão

Primeiro, temos que descobrir como representar uma solução potencial, como uma estratégia de damas, de uma forma que funcione com um algoritmo genético. No nosso caso, pegaremos todos os movimentos possíveis para o jogador atual, acessaremos o GA sobre cada um e então escolheremos o movimento com maior peso.


Além disso, precisamos calcular a pontuação do jogo para escolher os melhores itens da população. No nosso caso, será:

  • 250 pontos por vitória
  • 3 pontos para cada dama comum
  • 7 para Dama Rei
  • -1 para cada movimento


Para cada população faremos um torneio (uma versão simplificada do torneio do sistema suíço). Após cada torneio, selecionamos 1/4 da população para seleção futura.


Se algum agente for o melhor jogador (selecionado para a próxima geração) em mais de 1 torneio, escolhemos ele para ser o melhor jogador, e após todas as épocas terminarem, fazemos um torneio entre os melhores jogadores e escolhemos o melhor, que será salvo.

Seleção, cruzamento e mutação em damas

O ponto crucial do algoritmo está na evolução da população de estratégias.

  • Seleção : Estratégias que apresentam melhor desempenho nos jogos têm maior chance de serem selecionadas para reprodução.


  • Crossover : Duas estratégias "pais" podem ser combinadas, possivelmente tomando alguns movimentos de abertura de uma e táticas de final de jogo de outra.


  • Mutação : Ocasionalmente, uma estratégia pode sofrer alterações aleatórias, potencialmente descobrindo táticas novas e eficazes.

Desafios e Limitações

Ótimo local

Existe o risco de o algoritmo ficar preso num ótimo local, onde pensa ter encontrado a melhor estratégia, mas só é ideal numa pequena região do espaço de soluções.

Intensidade Computacional

Embora os GAs possam ser rápidos, a simulação de milhares ou milhões de jogos requer recursos computacionais significativos.

Sobreajuste

Existe o risco de que a estratégia desenvolvida se torne demasiado adaptada aos cenários de treino e tenha um mau desempenho contra estratégias ou tácticas invisíveis.

Codificação

Vou usar node.js.


Por que não Python?

Eu sei que o Python será mais eficaz, mas com o node.js, com o qual estou mais familiarizado, ele pode ser facilmente usado no lado do cliente e no lado do servidor.


Por que não tensorflow.js (ou qualquer outra biblioteca tão próxima de você) ?

Inicialmente, planejei usar esta biblioteca, mas depois decidi que, como este projeto é principalmente educacional, eu mesmo poderia criar uma rede de neurônios minimamente viável e também deixar espaço para melhorias adicionais (por exemplo, usar wasm para cálculos).

Rede neural

Quase qualquer rede neural é um conjunto de camadas onde alguns dados são recebidos como entrada, multiplicados por um conjunto de índices, e alguns dados são retornados.


Para maior clareza, imagine que você está procurando a nova casa dos seus sonhos, e agora a encontrou, e agora pergunta aos seus amigos o que eles acham desta casa, e eles dão a resposta em uma escala de 10 pontos, por exemplo .


Você confia até certo ponto na opinião de cada um de seus amigos, mas tem que perguntar a todos, mesmo àqueles em quem você não confia particularmente, para não ofender. E aí você senta com seus amigos em grupo com suas bebidas preferidas e olha casas diferentes, e todo mundo fala o quanto gostou.


Com isso, você sabe o que seus amigos pensam de cada casa e, com base no resultado final, você decide.


A rede neural consiste exatamente nesses “amigos”, mas o número de grupos de amigos pode ser bastante grande e todos confiam na opinião do grupo anterior.


Apresentação esquemática da rede neural:

Apresentação básica de como funciona a rede neural (original: https://en.wikipedia.org/wiki/Neural_network_(machine_learning)#/media/File:Colored_neural_network.svg)


Camada para uma rede neural:

 import {createEmpty, createNew} from "./genetic"; export enum Activation { Sigmoid, Relu, } class Layer { weights: Float32Array; biases: Float32Array; inputCount: number; outputCount: number; size: number; activation: Activation; /** * Create a new layer * @param inputCount * @param outputCount * @param activation */ constructor( inputCount: number, outputCount: number, activation: Activation = Activation.Relu ) { this.inputCount = inputCount; this.outputCount = outputCount; this.weights = createNew(inputCount * outputCount, 2); this.biases = createNew(outputCount, 2); this.activation = activation; this.size = inputCount * outputCount + outputCount; switch (activation) { case Activation.Sigmoid: this.activate = this.activateSigmoid.bind(this); break; case Activation.Relu: this.activate = this.activationRelu.bind(this); break; } } /** * Activation function (identity) * @param val */ activate(val: Float32Array) { return val; } /** * Activation function (sigmoid) * @param val */ activateSigmoid(val: Float32Array) { return val.map((v) => 1 / (1 + Math.exp(-v))); } /** * Activation function (relu) * @param val */ activationRelu(val: Float32Array) { return val.map((v) => Math.max(0, v)); } /** * Predict an output * @param inputs */ predict(inputs: Float32Array) { let result = createEmpty(this.outputCount); for (let i = 0; i < this.outputCount; i++) { for (let j = 0; j < this.inputCount; j++) { result[i] += inputs[j] * this.weights[i * this.inputCount + j]; } result[i] += this.biases[i]; } return this.activate(result); } /** * Get the weights of the layer */ getWeights() { return Float32Array.from([...this.weights, ...this.biases]); } /** * Gst current layer topology */ getTopology() { return new Float32Array([ this.inputCount, this.activation, this.outputCount, ]); } /** * Set the weights of the layer * @param weights */ setWeights(weights: Float32Array) { this.weights = weights.slice(0, this.weights.length); this.biases = weights.slice(this.weights.length); } }

Rede neural:

 export class Network { network: Layer[] = []; inputs: any; outputs: any; /** * Create a new network * @param inputs * @param outputs * @param layer */ constructor(inputs: number, outputs: number, layer: (number[] | Layer)[]) { this.inputs = inputs; this.outputs = outputs; for (const layerSize of layer) { const l = layerSize instanceof Layer ? layerSize : new Layer(layerSize[0], layerSize[2], layerSize[1]); this.network.push(l); } } /** * Predict an output * @param input */ predict(input: Float32Array) { return this.network.reduce((acc, layer) => layer.predict(acc), input); } /** * Get topology for whole network */ getTopology() { return new Float32Array( [ this.inputs, this.outputs, this.network.length, ...this.network.map((layer) => [...layer.getTopology()]), ].flat() ); } /** * Get the weights of the network */ getWeights() { return this.network.reduce((acc, layer) => { return new Float32Array([...acc, ...layer.getWeights()]); }, new Float32Array([])); } /** * Set the weights of the network * @param weights */ setWeights(weights: Float32Array) { let offset = 0; for (const layer of this.network) { layer.setWeights(weights.slice(offset, offset + layer.size)); offset += layer.size; } } /** * Get the size of the network */ size() { return this.network.reduce((acc, layer) => acc + layer.size, 0); } /** * Serialize the network */ toBinary() { const topology = this.getTopology(); const weights = new Float32Array(topology.length + this.size()); weights.set(this.getTopology()); weights.set(this.getWeights(), topology.length); return Buffer.from(weights.buffer); } /** * Create a network from a binary * @param json * @param weights */ static fromBinary(buffer: Float32Array) { const inputs = buffer[0]; const outputs = buffer[1]; const length = buffer[2]; const layers = Array.from({ length }).map((_, i) => { const start = 3 + i * 3; const end = start + 3; const topology = buffer.subarray(start, end); return new Layer(topology[0], topology[2], topology[1]); }); const network = new Network(inputs, outputs, layers); network.setWeights(buffer.subarray(3 + length * 3)); return network; } }

Agente

Um agent é alguma entidade que decide o que fazer a seguir e recebe recompensas ou multas por suas atividades. Em outras palavras, um agente é uma pessoa comum que toma decisões no trabalho e recebe uma recompensa por isso.


Como parte de nossa tarefa, o agente contém uma rede neural e seleciona a melhor solução do ponto de vista da rede neural.


Além disso, nosso agente, como qualquer bom funcionário, lembra o resultado de seu trabalho e reporta aos seus superiores (algoritmo genético) o valor médio, com base no qual é tomada a decisão final sobre esse funcionário.

 import { Keccak } from "sha3"; import { Network, Agent, createEmpty, getMoves, FEN } from "shared"; export class AgentTrainer implements Agent { historySize: number; history: Float32Array; id: string; private _games: Set<string> = new Set(); games: number = 0; wins: number = 0; score: number = 0; minScore = +Infinity; maxScore = -Infinity; age: number = 0; network: Network; taken: boolean = false; _player: "B" | "W" = "W"; /** * Create a new agent * @param historySize * @param modelPath * @param weights */ constructor(historySize: number, buf: Float32Array) { this.historySize = historySize; this.network = Network.fromBinary(buf); this.id = new Keccak(256).update(Buffer.from(buf.buffer)).digest("hex"); this.history = createEmpty(this.historySize); } /** * Create a new epoch */ onNewEpoch() { this.age += 1; this.score = 0; this.games = 0; this._games = new Set(); this.maxScore = -Infinity; this.minScore = +Infinity; this.wins = 0; this.reset(); } /** * Check if the player has played against the opponent * @param player */ hasPlayedBefore(player: AgentTrainer) { if (this.id === player.id) { return false; } return this._games.has(player.id); } /** * Set the result of a match * @param score * @param opponent */ setResult(score: number, opponent: AgentTrainer) { this._games.add(opponent.id); this.games += 1; this.score += score; this.minScore = Math.min(this.minScore, score); this.maxScore = Math.max(this.maxScore, score); if (score > 0) { this.wins += 1; } } /** * Calculate the average score * @returns number */ getAverageScore() { return this.score / this.games; } /** * Get the weights of the network */ getWeights() { return this.network.getWeights(); } getTopology() { return this.network.getTopology(); } /** * Serialize the weights of the network */ serialize() { return this.network.toBinary(); } /** * Reset history */ reset() { this.history = new Float32Array(this.historySize); this.taken = false; } toString() { return `${this.id} with ${String(this.score).padStart( 6, " " )} points min: ${String(this.minScore).padStart(6, " ")} max: ${String( this.maxScore ).padStart(6, " ")} avg: ${String( this.getAverageScore().toFixed(2) ).padStart(9, " ")} ${((this.wins / this.games) * 100) .toFixed(2) .padStart(6, " ")}%`; } setPlayer(player: "B" | "W") { this._player = player; } /** * Calculate moves and return the best one * @param gameState * @returns */ getMove(gameState: FEN): string { const board = new Float32Array(50); const wMul = this._player === "W" ? 1 : -1; for (let i = 0; i < gameState.white.length; i++) { let isKing = gameState.white[i].startsWith("K"); let pos = isKing ? parseInt(gameState.white[i].slice(1), 10) : parseInt(gameState.white[i], 10); board[pos] = wMul * (isKing ? 2 : 1); } for (let i = 0; i < gameState.black.length; i++) { let isKing = gameState.black[i].startsWith("K"); let pos = isKing ? parseInt(gameState.black[i].slice(1), 10) : parseInt(gameState.black[i], 10); board[pos] = -1 * wMul * (isKing ? 2 : 1); } this.history = new Float32Array([...board, ...this.history.slice(50)]); const value = new Float32Array(this.network.inputs); value.set(new Float32Array(50)); value.set(this.history, 50); let pos = 0; let posVal = -Infinity; const moves = getMoves(gameState); for (let i = 0; i < moves.length; i += 1) { /** * Create a new value for move */ const move = moves[i]; const val = value.slice(); val[move.from - 1] = -1; val[move.to - 1] = 1; const result = this.network.predict(val); /** * If the result is better than the previous one, save it */ if (result[0] > posVal) { pos = moves.indexOf(move); posVal = result[0]; } } /** * Return the best move in the format from-to */ return `${moves[pos].from}-${moves[pos].to}`; } }

Jogue uma partida entre agentes.

Para obter o resultado do trabalho, precisamos comparar dois agentes para que fiquem em igualdade de condições; cada um deles jogará para cada uma das cores, e o resultado final será resumido.


Para não sobrecarregar a rede com informações desnecessárias, cada agente vê o tabuleiro como se estivesse jogando damas brancas.

 import { Draughts } from "@jortvl/draughts"; import { Player, Position, getFen } from "shared"; import { AgentTrainer } from "./agent"; export function playMatch(white: AgentTrainer, black: AgentTrainer) { const draughts = new Draughts(); white.setPlayer(Player.White); black.setPlayer(Player.Black); while (!draughts.gameOver()) { /** * Get current player */ const player = draughts.turn() === Player.White ? white : black; /** * Get the move from the player */ const move = player.getMove(getFen(draughts.fen())); draughts.move(move); } /** * Calculate the score */ const [winner, ...left] = draughts.position().split(""); const score = 250 + left.reduce((acc: number, val: string) => { switch (val) { case Position.Black: case Position.White: return acc + 3; case Position.BlackKing: case Position.WhiteKing: return acc + 7; default: return acc; } }, 0) - draughts.history().length; /** * Set the result, if white won, the score is positive; if black won, the score is negative */ return winner === Player.White ? score : score * -1; }

Jogar torneio

A cada época de treinamento (teste do trabalho) de agentes, temos um conjunto de agentes experimentais que colocaremos uns contra os outros. Mas como a verificação de cada agente será muito longa e ineficaz, usaremos um algoritmo simplificado de torneio de xadrez.


Em cada etapa temos uma lista de jogadores ordenados por pontos e os distribuímos da seguinte forma: o primeiro joga com o primeiro adversário do meio da ficha. Se ele já jogou com ele, selecionamos o próximo.

 import {Agent} from "./agent"; import {playMatch} from "./play-match"; export function playTournament(playerList: Agent[]) { let d = Math.floor(playerList.length / 2); /** * Count rounds */ let rounds = Math.ceil(Math.log2(playerList.length)) + 2; for (let i = 0; i < rounds; i += 1) { for (let j = 0; j < d; j += 1) { let dj = d; /** * Find the next opponent */ let found = false; while (dj < playerList.length && !found) { if (playerList[dj].hasPlayedBefore(playerList[j]) || playerList[dj].games > i) { dj += 1; } else { found = true; } } if (found) { let score = 0; /** * Play the match */ score += playMatch(playerList[j], playerList[dj]); /** * Play the reverse match */ score += playMatch(playerList[dj], playerList[j]) * -1; playerList[j].setResult(score, playerList[dj]); playerList[dj].setResult(-1 * score, playerList[j]); } } playerList.sort((player1, player2) => player2.score - player1.score); console.log('round', i, playerList[0].id, playerList[0].score.toFixed(1).padStart(6, ' ')); } return playerList; }

Torneios

É aqui que toda a magia do algoritmo genético acontece. Os modelos existentes são carregados e novos são criados.


A partir desses modelos, obtemos um genoma com os agentes que serão utilizados em nosso jogo. Este genoma mudará à medida que o treinamento avança, os agentes com pontuação mais baixa serão descartados e os agentes com pontuação mais alta transmitirão seus genes às novas gerações e serão comparados com elas.


Crie um novo genoma:

Um novo conjunto de genes é criado em um determinado intervalo numérico, sem problemas hereditários e afins, e é aí que tudo começará.

 export function createNew(size: number, delta = 4): Float32Array { return new Float32Array(size).map(() => Math.random() * delta - (delta / 2)); }


Cruzamento:

O mecanismo é bastante simples; pegamos dois conjuntos de genes (pesos) dos agentes e, dependendo da probabilidade, pegamos um gene do primeiro agente ou do segundo, assim, os genes se misturam e uma nova rede é obtida com algum conhecimento do primeiro e do segundo agente.


É exatamente assim que tudo funciona na natureza real; cada um de nós tem genes de cada um de nossos pais.

 export function crossover(first: Float32Array, second: Float32Array, prob = 0.25): Float32Array { return new Float32Array(first.map((w, i) => Math.random() < prob ? second[i] : w)) }


Mutar:

A função de mutação funciona da seguinte forma: pegamos um conjunto de genes e, com algum grau de probabilidade, adicionamos um pouco de caos a ele. Novamente, na vida real tudo funciona exatamente da mesma maneira, e cada um de nós possui genes que não estão em nossos pais, caso contrário não haveria doenças e outros processos incompreensíveis em nosso corpo.

 export function mutate(master: Float32Array, prob = 0.25, delta = 0.5): Float32Array { return new Float32Array(master.map(w => Math.random() < prob ? w + (Math.random() * delta - (delta / 2)) : w)) }


Como resultado de cada torneio, temos um certo número de agentes que têm um pouco mais de sorte que outros (nos algoritmos genéticos, tudo é construído em nossas vidas, e alguns têm mais sorte, outros menos).


E no final pegamos a lista desses sortudos e comparamos entre si para encontrar o melhor genoma para o nosso jogo, e para que os dados não desapareçam, devemos lembrar de salvar esse genoma.


Quando tivermos um número suficiente desses genomas, poderemos construir populações de agentes baseados neles. Ainda assim, cada um dos genomas já tem alguma compreensão do que precisa fazer.

 import * as fs from "fs"; import { playTournament } from "./play-tournament"; import { Network, createNew, crossover, mutate } from "shared"; import { playBattle } from "./play-battle"; import { AgentTrainer } from "./agent"; export async function tournaments( historySize: number, layers: number[] = [], epoch = 64, population = 32, best = false ) { const modelName = `${(historySize + 1) * 50}_${layers.join("_")}`; const modelPath = `../models/${modelName}`; /** * Create the model if it does not exist */ if (!fs.existsSync(modelPath)) { fs.mkdirSync(modelPath, { recursive: true }); } let topPlayerList = []; const topPlayerIds = new Set(); const bestModels = new Set(); let playerList: AgentTrainer[] = []; const baseLayers = []; let inp = historySize * 50 + 50; for (let i = 0; i < layers.length; i++) { baseLayers.push([inp, 1, layers[i]]); inp = layers[i]; } const baseNet = new Network(historySize * 50 + 50, 1, baseLayers); const topologySize = baseNet.getTopology().length; const size = baseNet.size() + topologySize; /** * Load the best models */ if (best) { const weights = fs .readdirSync(modelPath) .filter((file) => file.endsWith(".bin")); for (const weight of weights) { const buf = fs.readFileSync(`${modelPath}/${weight}`); const weights = new Float32Array(buf.buffer); const agent = new AgentTrainer(historySize * 50, weights); agent.age = 1; bestModels.add(agent.id); playerList.push(agent); topPlayerList.push(agent); topPlayerIds.add(agent.id); } const d = playerList.length; let ind = 0; /** * Create new players by crossover and mutation from the best models. * For the zero population, we need to ensure the greatest genetic diversity, than next populations. * This way we will get a larger number of potentially viable models, from which subsequent generations will be built in the future */ if (d > 1) { while (playerList.length < Math.max(population, d * 2)) { const playerA = playerList[ind]; const playerB = playerList[Math.floor(Math.random() * d)]; if (playerA && playerB && playerA.id !== playerB.id) { const newWeights = mutate( crossover(playerA.getWeights(), playerB.getWeights()) ); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(newWeights, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); ind += 1; ind = ind % d; } } } } /** * Create the initial population */ while (playerList.length < population) { const w = createNew(baseNet.size(), 2); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(w, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); } /** * Run the initial championship */ playerList = await playTournament(playerList); console.log( `0 ${playerList[0].id} (${playerList[0].age}) with ${playerList[0].score} points` ); let currentEpoch = 0; while (currentEpoch <= epoch) { /** * Keep the best 25% of the population */ playerList = playerList.slice(0, Math.floor(population / 4)); for (const player of playerList) { player.onNewEpoch(); /** * if the player is in the top 25% and has played at least one tournament, add it to the top players */ if (player.age > 1 && !topPlayerIds.has(player.id)) { topPlayerIds.add(player.id); topPlayerList.push(player); console.log("add top player", player.id, topPlayerList.length); } } const d = playerList.length; /** * Create new players by crossover and mutation */ let ind = 0; while (playerList.length < population) { const playerA = playerList[ind]; const playerB = playerList[Math.floor(Math.random() * d)]; if (playerA && playerB && playerA.id !== playerB.id) { const newWeights = mutate( crossover(playerA.getWeights(), playerB.getWeights()) ); const weights = new Float32Array(size); weights.set(baseNet.getTopology()); weights.set(newWeights, topologySize); const agent = new AgentTrainer(historySize * 50, weights); playerList.push(agent); ind += 1; ind = ind % d; } } /** * Run the championship */ playerList = await playTournament(playerList); currentEpoch += 1; console.log( `${currentEpoch} ${playerList[0].id} (${playerList[0].age}) with ${playerList[0].score} points` ); } /** * Add the top players to the list from championship */ for (const player of playerList) { if (player.age > 1 && !topPlayerIds.has(player.id)) { topPlayerIds.add(player.id); topPlayerList.push(player); console.log("add top player", player.id, topPlayerList.length); } } console.log("-----"); console.log(topPlayerList.length); console.log("-----"); /** * Reset agents */ for (const player of topPlayerList) { player.onNewEpoch(); } /** * Run the final championship */ topPlayerList = await playBattle(topPlayerList); let index = 1; for (const player of topPlayerList) { const code = bestModels.has(player.id) ? "\x1b[32m" : "\x1b[36m"; const reset = "\x1b[m"; console.log( `${code}${String(index).padStart(4, " ")} ${player.toString()}${reset}` ); index += 1; } /** * Save the best player */ while (topPlayerList[0] && bestModels.has(topPlayerList[0].id)) { /** * Remove the best player if it is already in the best models */ console.log("remove", topPlayerList[0].id); topPlayerList.shift(); } if (topPlayerList[0]) { let player = topPlayerList[0]; console.log(`${player.score} ${player.id}`); const weights = player.serialize(); console.log(weights.length, weights.length / 4); fs.writeFileSync(`${modelPath}/${player.id}.bin`, weights); } }

Resultados

Para os resultados utilizei os modelos mais atuais, e foi o que saiu:

Ao comparar 2 modelos de redes neurais entre si, eles apresentam resultados bastante bons, embora executem ações ilógicas.

https://github.com/vivalaakam/checkers/blob/main/images/nn_nn.gif

Ao jogar entre uma rede neural e uma pesquisa alfa beta com profundidade de pesquisa de 1 passo, a rede neural tem uma boa chance de vencer.

https://github.com/vivalaakam/checkers/blob/main/images/nn_profundidade_1.gif

Em um jogo entre pesquisas de rede neural e alfa beta com profundidade de pesquisa de 2 etapas, a rede neural não teve chance e perdeu todos os jogos.

https://github.com/vivalaakam/checkers/blob/main/images/nn_profundidade_1.gif

Ainda não olhei mais fundo porque é inútil. Talvez depois de mais jogos ele consiga produzir resultados mais aceitáveis, ou se você ensinar a rede neural a jogar não com as mesmas redes, mas com um agente de busca alfa-beta

Conclusão

A aplicação de algoritmos genéticos ao jogo de damas exemplifica o potencial transformador da computação de inspiração biológica. Embora os algoritmos tradicionais de jogos, como o Minimax e suas variantes, tenham se mostrado eficazes, a natureza evolutiva e adaptativa dos AGs oferece uma nova perspectiva.


Tal como acontece com a evolução biológica, as estratégias desenvolvidas através deste método podem nem sempre ser as mais adequadas de imediato. Ainda assim, com tempo suficiente e condições adequadas, podem evoluir para adversários formidáveis, demonstrando o poder da computação inspirada na natureza.


Quer você seja um entusiasta de damas, um pesquisador de IA ou apenas alguém fascinado pela convergência do antigo e do novo, não há como negar que a fusão deste jogo antigo com algoritmos de ponta é uma fronteira emocionante na inteligência artificial. .


Como de costume, todo o código fornecido no GitHub