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.
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.
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:
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á:
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.
O ponto crucial do algoritmo está na evolução da população de estratégias.
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.
Embora os GAs possam ser rápidos, a simulação de milhares ou milhões de jogos requer recursos computacionais significativos.
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.
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).
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:
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); } }
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; } }
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}`; } }
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; }
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; }
É 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); } }
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.
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.
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.
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
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