paint-brush
Jouer aux dames avec des algorithmes génétiques : apprentissage évolutif dans les jeux traditionnelspar@vivalaakam
686 lectures
686 lectures

Jouer aux dames avec des algorithmes génétiques : apprentissage évolutif dans les jeux traditionnels

par Andrey Makarov27m2024/03/08
Read on Terminal Reader

Trop long; Pour lire

Dans cet article, nous explorerons l'intersection des jeux de dames et des algorithmes génétiques, démontrant comment des techniques informatiques évolutives peuvent être utilisées pour développer des agents de jeu de dames compétents. Dans mon dernier article, je pense avoir suffisamment abordé le sujet des dames, mais rappelons quand même les règles de base du jeu : Le jeu de dames se joue sur un plateau de 10x10, chaque joueur commençant avec 20 pièces. w
featured image - Jouer aux dames avec des algorithmes génétiques : apprentissage évolutif dans les jeux traditionnels
Andrey Makarov HackerNoon profile picture

Introduction

Les dames, également connues sous le nom de dames, sont un jeu ancien qui est populaire depuis longtemps. Comme d’autres jeux de société classiques, il a suscité l’intérêt des informaticiens et des chercheurs en IA en tant que plateforme pour leurs expériences. Une méthode importante qu'ils utilisent pour entraîner les ordinateurs à jouer aux dames est un algorithme génétique, basé sur le concept de survie du plus fort qui détermine l'évolution.


Dans cet article, nous explorerons l'intersection des jeux de dames et des algorithmes génétiques, démontrant comment des techniques informatiques évolutives peuvent être utilisées pour développer des agents de jeu de dames compétents.


Dans mon dernier article , je pense avoir suffisamment abordé le sujet des dames, mais rappelons quand même les règles de base du jeu : Le jeu de dames se joue sur un plateau de 10x10, chaque joueur commençant avec 20 pièces.


Le but est simple : capturer toutes les pièces de votre adversaire ou les piéger pour qu'elles ne puissent pas bouger. Les principales stratégies tournent autour du positionnement, de la défense, de l’offensive et de la prévision des mouvements de l’adversaire.

Algorithmes génétiques (AG)

Les bases

Les GA sont des algorithmes d’optimisation basés sur le processus de sélection naturelle. Ces algorithmes reflètent la procédure d'évolution observée dans la nature, comprenant la sélection, le croisement (recombinaison) et la mutation.

Composants d'un réseau neuronal

Cet article utilisera un modèle simple avec des couches entièrement connectées. Une couche est un ensemble de neurones qui traitent les entrées et produisent des sorties. Ces sorties sont ensuite utilisées comme prédiction finale dans le cas de la dernière couche (couche de sortie) ou transmises comme entrée à la couche suivante du réseau.


Chaque couche contient :

  • entrées : nombre de paramètres d'entrée


  • sorties : nombre de paramètres de sortie


  • poids : les poids sont les paramètres que le réseau ajuste pendant la formation pour minimiser l'erreur de prédiction.


  • biais : est ajouté à la somme d’entrée avant la fonction d’activation. Le biais aide à ajuster la sortie ainsi que les poids.


  • fonction d'activation : Chaque neurone d'une couche, à l'exception de la couche d'entrée, applique une fonction d'activation à son entrée avant de transmettre la sortie à la couche suivante. Ceci est essentiel pour que le réseau modélise les relations non linéaires dans les données.

Composants d'un algorithme génétique

  • Population : Un ensemble de solutions candidates.


  • Fonction Fitness : Elle évalue la performance ou « fitness » d’une solution individuelle.


  • Sélection : En fonction de l'aptitude, certaines solutions sont sélectionnées pour la reproduction.


  • Crossover : Combiner des parties de deux solutions sélectionnées pour créer une progéniture.


  • Mutation : Introduction de petits changements aléatoires dans la progéniture.

Application d'algorithmes génétiques aux dames

Encodage du problème et évaluation de la condition physique

Tout d’abord, nous devons trouver comment représenter une solution potentielle, comme une stratégie de jeu de dames, d’une manière qui fonctionnera avec un algorithme génétique. Dans notre cas, nous saisirons tous les mouvements possibles pour le joueur actuel, lancerons GA pour chacun d'eux, puis choisirons le mouvement ayant le plus grand poids.


Nous devons également calculer le score du jeu pour choisir les meilleurs éléments de la population. Dans notre cas, ce sera :

  • 250 points pour une victoire
  • 3 points pour chaque pion ordinaire
  • 7 pour le roi Checker
  • -1 pour chaque coup


Pour chaque population, nous ferons un tournoi (une version simplifiée du tournoi du système suisse). Après chaque tournoi, nous sélectionnons 1/4 de la population pour une future sélection.


Si un agent est le meilleur joueur (sélectionné pour la génération suivante) dans plus d'un tournoi, nous le choisissons comme meilleur joueur, et une fois toutes les époques terminées, nous organisons un tournoi entre les meilleurs joueurs et choisissons le meilleur. qui sera sauvegardé.

Sélection, croisement et mutation dans les dames

Le nœud de l’algorithme réside dans l’évolution de la population de stratégies.

  • Sélection : Les stratégies qui fonctionnent mieux dans les jeux ont plus de chances d'être sélectionnées pour être reproduites.


  • Crossover : Deux stratégies « parentales » peuvent être combinées, en prenant éventuellement certains mouvements d'ouverture de l'une et les tactiques de fin de partie d'une autre.


  • Mutation : Parfois, une stratégie peut subir des changements aléatoires, découvrant potentiellement de nouvelles tactiques efficaces.

Défis et limites

Local optimal

Il existe un risque que l'algorithme reste coincé dans un optimum local, où il pense avoir trouvé la meilleure stratégie mais n'est optimal que dans une petite région de l'espace des solutions.

Intensité de calcul

Même si les GA peuvent être rapides, la simulation de milliers ou de millions de jeux nécessite des ressources informatiques importantes.

Surapprentissage

Il existe un risque que la stratégie évoluée devienne trop adaptée aux scénarios de formation et ne fonctionne pas bien face à des stratégies ou tactiques invisibles.

Codage

Je vais utiliser node.js.


Pourquoi pas Python ?

Je sais que Python sera plus efficace, mais avec node.js, que je connais mieux, il peut être facilement utilisé côté client et côté serveur.


Pourquoi pas tensorflow.js (ou toute autre bibliothèque si proche de chez vous) ?

Au départ, j'avais prévu d'utiliser cette bibliothèque, mais j'ai ensuite décidé que puisque ce projet est avant tout éducatif, je peux créer moi-même un réseau de neurones minimalement viable et également laisser de la place pour d'autres améliorations (par exemple, utiliser wasm pour les calculs).

Réseau neuronal

Presque tous les réseaux neuronaux sont un ensemble de couches dans lesquelles certaines données sont reçues en entrée, multipliées par un ensemble d'indices, et certaines données sont renvoyées.


Pour plus de clarté, imaginez que vous cherchez la nouvelle maison de vos rêves, et maintenant vous l'avez trouvée, et maintenant vous demandez à vos amis ce qu'ils pensent de cette maison, et ils donnent leur réponse sur une échelle de 10 points, par exemple. .


Vous faites confiance dans une certaine mesure à l'opinion de chacun de vos amis, mais vous devez demander à tout le monde, même à ceux en qui vous n'avez pas particulièrement confiance, pour ne pas offenser. Et ainsi, vous vous asseyez avec vos amis en groupe avec vos boissons préférées et regardez différentes maisons, et tout le monde dit à quel point ils l'ont aimé.


En conséquence, vous savez ce que vos amis pensent de chaque maison et, en fonction du résultat final, vous décidez.


Le réseau neuronal est constitué précisément de ces «amis», mais le nombre de groupes d'amis peut être assez important et chacun se fie à l'opinion du groupe précédent.


Présentation schématique du réseau de neurones :

Présentation de base du fonctionnement du réseau neuronal (original : https://en.wikipedia.org/wiki/Neural_network_(machine_learning)#/media/File:Colored_neural_network.svg)


Couche pour un réseau de neurones :

 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); } }

Réseau neuronal:

 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; } }

Agent

Un agent est une entité qui décide quoi faire ensuite et reçoit des récompenses ou des amendes pour ses activités. En d’autres termes, un agent est une personne ordinaire qui prend des décisions au travail et en reçoit une récompense.


Dans le cadre de notre tâche, l'agent contient un réseau de neurones et sélectionne la meilleure solution du point de vue du réseau de neurones.


De plus, notre agent, comme tout bon employé, se souvient des résultats de son travail et rend compte à ses supérieurs (algorithme génétique) de la valeur moyenne, sur la base de laquelle la décision finale concernant cet employé est prise.

 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}`; } }

Jouez un match entre agents.

Pour obtenir le résultat du travail, il faut comparer deux agents afin qu'ils soient dans des conditions égales ; chacun d'eux jouera pour chacune des couleurs, et le résultat final est résumé.


Afin de ne pas surcharger le réseau d'informations inutiles, chaque agent voit le plateau comme s'il jouait aux dames blanches.

 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; }

Jouer au tournoi

A chaque époque de formation (test du travail) des agents, nous disposons d'un ensemble d'agents expérimentaux que nous opposerons les uns aux autres. Mais comme vérifier chaque agent entre eux sera très long et inefficace, nous utiliserons un algorithme de tournoi d'échecs simplifié.


A chaque étape, nous disposons d'une liste de joueurs triés par points et les répartissons comme suit : le premier joue avec le premier adversaire du milieu de la feuille. S'il a déjà joué avec lui, on sélectionne le suivant.

 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; }

Tournois

C’est là que se produit toute la magie de l’algorithme génétique. Les modèles existants sont chargés et de nouveaux sont créés.


A partir de ces modèles, nous obtenons un génome avec des agents qui seront utilisés dans notre jeu. Ce génome changera au fur et à mesure de la formation, les agents ayant le score le plus bas seront écartés et les agents ayant le score le plus élevé transmettront leurs gènes aux nouvelles générations et seront comparés à eux.


Créez un nouveau génome :

Un nouvel ensemble de gènes est créé dans un intervalle numérique donné, sans problèmes héréditaires ni autres, et c'est là que tout va commencer.

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


Croisement :

Le mécanisme est assez simple ; nous prenons deux ensembles de gènes (poids) d'agents et, selon la probabilité, nous prenons un gène du premier agent ou du second, ainsi, les gènes sont mélangés et un nouveau réseau est obtenu avec une certaine connaissance du premier et du deuxième agent.


C’est exactement ainsi que tout fonctionne dans la vraie nature ; chacun de nous possède des gènes de chacun de nos parents.

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


Subir une mutation:

La fonction de mutation fonctionne comme suit : nous prenons un ensemble de gènes et, avec un certain degré de probabilité, y ajoutons un peu de chaos. Encore une fois, dans la vraie vie, tout fonctionne exactement de la même manière, et chacun de nous a des gènes qui ne sont pas chez nos parents, sinon il n'y aurait pas de maladies ni d'autres processus incompréhensibles dans notre corps.

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


A la suite de chaque tournoi, nous avons un certain nombre d'agents qui ont un peu plus de chance que d'autres (Dans les algorithmes génétiques, tout se construit sur nos vies, et certains ont plus de chance, d'autres moins).


Et au final, on prend la liste de ces très chanceux et on les compare entre eux pour trouver le meilleur génome pour notre jeu, et pour que les données ne disparaissent pas, il faut penser à sauvegarder ce génome.


Lorsque nous disposons d’un nombre suffisant de ces génomes, nous pouvons construire des populations d’agents basées sur eux. Pourtant, chacun des génomes comprend déjà dans une certaine mesure ce qu’il doit faire.

 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); } }

Résultats

Pour les résultats, j'ai utilisé les modèles les plus récents, et voici ce qui en est ressorti :

Lorsque l'on compare 2 modèles de réseaux neuronaux entre eux, ils montrent d'assez bons résultats, bien qu'ils effectuent des actions illogiques.

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

En jouant entre un réseau de neurones et une recherche alpha bêta avec une profondeur de recherche de 1 pas, le réseau de neurones a de assez bonnes chances de gagner.

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

Dans un jeu entre recherche sur réseau neuronal et recherche alpha bêta avec une profondeur de recherche de 2 étapes, le réseau neuronal n'avait aucune chance et a perdu toutes les parties.

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

Je n'ai pas encore approfondi car c'est inutile. Peut-être qu'après plus de jeux, il pourra produire des résultats plus acceptables, ou si vous apprenez au réseau neuronal à jouer non pas avec les mêmes réseaux, mais avec un agent de recherche alpha-bêta.

Conclusion

L’application d’algorithmes génétiques au jeu de dames illustre le potentiel transformateur du calcul d’inspiration biologique. Alors que les algorithmes de jeu traditionnels comme Minimax et ses variantes se sont révélés efficaces, la nature évolutive et adaptative des GA offre une nouvelle perspective.


Comme pour l’évolution biologique, les stratégies développées grâce à cette méthode ne sont pas toujours les plus adaptées dans l’immédiat. Pourtant, avec suffisamment de temps et de bonnes conditions, ils peuvent devenir de redoutables adversaires, démontrant ainsi la puissance du calcul inspiré par la nature.


Que vous soyez un passionné de dames, un chercheur en IA ou simplement quelqu'un fasciné par la convergence de l'ancien et du nouveau, il est indéniable que la fusion de ce jeu séculaire avec des algorithmes de pointe constitue une frontière passionnante en matière d'intelligence artificielle. .


Comme d'habitude, tout le code fourni sur GitHub