Dame spielen mit genetischen Algorithmen: Evolutionäres Lernen in traditionellen Spielen

Einführung

Dame, auch Dame genannt, ist ein altes Spiel, das seit langem beliebt ist. Wie andere klassische Brettspiele hat es als Plattform für ihre Experimente das Interesse von Informatikern und KI-Forschern geweckt. Eine prominente Methode, mit der sie Computern beibringen, Dame zu spielen, ist ein genetischer Algorithmus, der auf dem Konzept des Überlebens des Stärkeren basiert, das die Evolution vorantreibt.

In diesem Artikel untersuchen wir die Schnittstelle zwischen Dame und genetischen Algorithmen und zeigen, wie evolutionäre Computertechniken eingesetzt werden können, um kompetente Dame-Spielagenten zu entwickeln.

In meinem letzten Artikel habe ich das Thema Dame meiner Meinung nach ausreichend behandelt, aber erinnern wir uns dennoch an die Grundregeln des Spiels: Das Spiel Dame wird auf einem 10x10-Brett gespielt, wobei jeder Spieler mit 20 Spielsteinen beginnt.

Das Ziel ist einfach: Erobern Sie alle Figuren Ihres Gegners oder fangen Sie sie ein, damit sie sich nicht bewegen können. Die Hauptstrategien drehen sich um Positionierung, Verteidigung, Angriff und das Vorhersehen der Bewegungen des Gegners.

Genetische Algorithmen (GAs)

Die Grundlagen

GAs sind Optimierungsalgorithmen, die auf dem Prozess der natürlichen Selektion basieren. Diese Algorithmen spiegeln den in der Natur beobachteten Evolutionsprozess wider, der Selektion, Crossover (Rekombination) und Mutation umfasst.

Komponenten eines neuronalen Netzwerks

In diesem Artikel wird ein einfaches Modell mit vollständig verbundenen Schichten verwendet. Eine Schicht ist eine Ansammlung von Neuronen, die Eingaben verarbeiten und Ausgaben erzeugen. Diese Ausgaben werden dann im Fall der letzten Schicht (Ausgabeschicht) als endgültige Vorhersage verwendet oder als Eingabe an die nächste Schicht im Netzwerk weitergeleitet.

Jede Schicht enthält:

• Eingaben : Anzahl der Eingabeparameter

• Ausgänge : Anzahl der Ausgabeparameter

• Gewichte : Gewichte sind die Parameter, die das Netzwerk während des Trainings anpasst, um den Vorhersagefehler zu minimieren.

• Bias : wird vor der Aktivierungsfunktion zur Eingabesumme addiert. Die Vorspannung hilft bei der Anpassung der Ausgabe zusammen mit den Gewichten.

• Aktivierungsfunktion : Jedes Neuron in einer Schicht, mit Ausnahme der Eingabeschicht, wendet eine Aktivierungsfunktion auf seine Eingabe an, bevor es die Ausgabe an die nächste Schicht weitergibt. Dies ist wichtig, damit das Netzwerk nichtlineare Beziehungen in den Daten modellieren kann.

Komponenten eines genetischen Algorithmus

• Bevölkerung : Eine Reihe von Kandidatenlösungen.

• Fitnessfunktion : Sie bewertet die Leistung oder „Fitness“ einer einzelnen Lösung.

• Auswahl : Basierend auf der Eignung werden einige Lösungen zur Reproduktion ausgewählt.

• Crossover : Kombinieren von Teilen zweier ausgewählter Lösungen, um Nachkommen zu schaffen.

• Mutation : Einführung kleiner zufälliger Veränderungen bei den Nachkommen.

Anwenden genetischer Algorithmen auf Dame

Kodierung der Problem- und Fitnessbewertung

Zuerst müssen wir herausfinden, wie wir eine mögliche Lösung, etwa eine Dame-Strategie, so darstellen können, dass sie mit einem genetischen Algorithmus funktioniert. In unserem Fall greifen wir auf alle möglichen Züge des aktuellen Spielers zu, ermitteln für jeden einzelnen die GA und wählen dann den Zug mit dem größten Gewicht aus.

Außerdem müssen wir den Spielstand berechnen, um die besten Gegenstände in der Bevölkerung auszuwählen. In unserem Fall wird es sein:

• 250 Punkte für einen Sieg
• 3 Punkte für jeden gewöhnlichen Checker
• 7 für King Checker
• -1 für jeden Zug

Für jede Bevölkerung werden wir ein Turnier veranstalten (eine vereinfachte Version des Turniers nach dem Schweizer System). Nach jedem Turnier wählen wir 1/4 der Bevölkerung für die zukünftige Auswahl aus.

Wenn ein Agent in mehr als einem Turnier der Top-Spieler ist (für die nächste Generation ausgewählt), wählen wir ihn zum Top-Spieler, und nachdem alle Epochen abgelaufen sind, veranstalten wir ein Turnier zwischen den Top-Spielern und wählen den Besten aus. was gespeichert wird.

Selektion, Crossover und Mutation im Damespiel

Der Kern des Algorithmus liegt in der Weiterentwicklung der Strategiepopulation.

• Auswahl : Strategien, die in Spielen besser abschneiden, haben eine höhere Chance, zur Reproduktion ausgewählt zu werden.

• Crossover : Zwei „übergeordnete“ Strategien können kombiniert werden, wobei möglicherweise einige Eröffnungszüge von einer und Endspieltaktiken von einer anderen übernommen werden.

• Mutation : Gelegentlich kann eine Strategie zufälligen Änderungen unterliegen und möglicherweise neue, wirksame Taktiken entdecken.

Herausforderungen und Einschränkungen

Lokales Optimum

Es besteht die Gefahr, dass der Algorithmus in einem lokalen Optimum stecken bleibt, wo er glaubt, die beste Strategie gefunden zu haben, aber nur in einem kleinen Bereich des Lösungsraums optimal ist.

Rechenintensität

Während GAs schnell sein können, erfordert die Simulation von Tausenden oder Millionen Spielen erhebliche Rechenressourcen.

Überanpassung

Es besteht das Risiko, dass die entwickelte Strategie zu sehr auf die Trainingsszenarien zugeschnitten ist und im Vergleich zu unbekannten Strategien oder Taktiken schlecht abschneidet.

Codierung

Ich werde node.js verwenden.

Warum nicht Python?

Ich weiß, dass Python effektiver sein wird, aber mit node.js, mit dem ich besser vertraut bin, kann es problemlos auf der Client- und Serverseite verwendet werden.

Warum nicht tensorflow.js (oder eine andere Bibliothek, die Ihnen so nahe steht) ?

Ursprünglich hatte ich geplant, diese Bibliothek zu verwenden, aber dann entschied ich, dass ich, da dieses Projekt in erster Linie pädagogischer Natur ist, selbst ein minimal lebensfähiges Neuronennetzwerk erstellen und auch Raum für weitere Verbesserungen lassen kann (z. B. wasm für Berechnungen verwenden).

Neurales Netzwerk

Fast jedes neuronale Netzwerk besteht aus einer Reihe von Schichten, in denen einige Daten als Eingabe empfangen, mit einer Reihe von Indizes multipliziert und einige Daten zurückgegeben werden.

Stellen Sie sich zur Verdeutlichung vor, Sie sind auf der Suche nach dem neuen Zuhause Ihrer Träume und haben es nun gefunden. Nun fragen Sie Ihre Freunde, was sie von diesem Haus halten, und sie geben ihre Antwort beispielsweise auf einer 10-Punkte-Skala .

Du vertraust der Meinung jedes einzelnen deiner Freunde bis zu einem gewissen Grad, aber du musst jeden fragen, auch diejenigen, denen du nicht besonders vertraust, um nicht zu beleidigen. Und so setzt man sich mit seinen Freunden in einer Gruppe bei seinen Lieblingsgetränken zusammen und schaut sich verschiedene Häuser an, und jeder sagt, wie gut es ihm geschmeckt hat.

Dadurch wissen Sie, was Ihre Freunde über jedes Haus denken, und entscheiden auf der Grundlage des Endergebnisses.

Das neuronale Netzwerk besteht aus genau solchen „Freunden“, aber die Anzahl der Freundesgruppen kann recht groß sein und jeder verlässt sich auf die Meinung der vorherigen Gruppe.

Schematische Darstellung des neuronalen Netzwerks:

Schicht für ein neuronales Netzwerk:

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

Neurales Netzwerk:

 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

Ein agent ist eine Entität, die entscheidet, was als nächstes zu tun ist und für ihre Aktivitäten Belohnungen oder Geldstrafen erhält. Mit anderen Worten: Ein Agent ist ein gewöhnlicher Mensch, der bei der Arbeit Entscheidungen trifft und dafür eine Belohnung erhält.

Im Rahmen unserer Aufgabe enthält der Agent ein neuronales Netzwerk und wählt die aus Sicht des neuronalen Netzwerks beste Lösung aus.

Außerdem merkt sich unser Agent, wie jeder gute Mitarbeiter, die Ergebnisse seiner Arbeit und berichtet seinen Vorgesetzten (genetischer Algorithmus) über den Durchschnittswert, auf dessen Grundlage die endgültige Entscheidung über diesen Mitarbeiter getroffen wird.

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

Spielen Sie ein Match zwischen Agenten.

Um das Ergebnis der Arbeit zu erhalten, müssen wir zwei Agenten vergleichen, damit sie sich in gleichen Bedingungen befinden; Jeder von ihnen spielt für jede der Farben und das Endergebnis wird zusammengefasst.

Um das Netzwerk nicht mit unnötigen Informationen zu überlasten, sieht jeder Agent das Spielbrett so, als würde er weiße Dame spielen.

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

Turnier spielen

In jeder Phase des Trainings (Testens der Arbeit) von Agenten verfügen wir über eine Reihe experimenteller Agenten, die wir gegeneinander antreten lassen. Da die Überprüfung der einzelnen Agenten untereinander jedoch sehr langwierig und ineffektiv sein wird, verwenden wir einen vereinfachten Schachturnier-Algorithmus.

In jeder Phase erstellen wir eine nach Punkten sortierte Spielerliste und verteilen diese wie folgt: Der Erste spielt mit dem ersten Gegner aus der Mitte des Blattes. Wenn er bereits mit ihm gespielt hat, wählen wir den nächsten aus.

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

Turniere

Hier geschieht die ganze Magie des genetischen Algorithmus. Bestehende Modelle werden geladen und neue erstellt.

Aus diesen Modellen erhalten wir ein Genom mit Wirkstoffen, die in unserem Spiel verwendet werden. Dieses Genom wird sich mit fortschreitendem Training verändern, Agenten mit der niedrigsten Punktzahl werden verworfen und Agenten mit der höchsten Punktzahl werden ihre Gene an neue Generationen weitergeben und mit ihnen verglichen.

Erstellen Sie ein neues Genom:

In einem bestimmten numerischen Intervall wird ein neuer Satz von Genen erstellt, ohne erbliche Probleme und dergleichen, und hier beginnt alles.

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

Crossover:

Der Mechanismus ist recht einfach; Wir nehmen zwei Sätze von Genen (Gewichten) von Agenten und nehmen je nach Wahrscheinlichkeit ein Gen vom ersten oder vom zweiten Agenten. Auf diese Weise werden die Gene gemischt und ein neues Netzwerk mit etwas Wissen vom ersten und zweiten erhalten Agent.

Genau so funktioniert alles in der realen Natur; Jeder von uns hat Gene von jedem unserer Eltern.

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

Mutieren:

Die Mutationsfunktion funktioniert wie folgt: Wir nehmen eine Reihe von Genen und fügen mit einer gewissen Wahrscheinlichkeit ein wenig Chaos hinzu. Auch im wirklichen Leben funktioniert alles genauso und jeder von uns hat Gene, die nicht in unseren Eltern vorhanden sind, sonst gäbe es keine Krankheiten und andere unverständliche Prozesse in unserem Körper.

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

Als Ergebnis jedes Turniers haben wir eine bestimmte Anzahl von Agenten, die etwas mehr Glück haben als andere (In genetischen Algorithmen basiert alles auf unserem Leben, und einige haben mehr Glück, andere weniger).

Und am Ende nehmen wir die Liste dieser sehr Glücklichen und vergleichen sie miteinander, um das beste Genom für unser Spiel zu finden, und damit die Daten nicht verschwinden, müssen wir daran denken, dieses Genom zu speichern.

Wenn wir über eine ausreichende Anzahl solcher Genome verfügen, können wir darauf basierende Wirkstoffpopulationen aufbauen. Dennoch hat jedes der Genome bereits ein gewisses Verständnis dafür, was es tun muss.

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

Ergebnisse

Für die Ergebnisse habe ich die aktuellsten Modelle verwendet, und das Ergebnis ist:

Beim Vergleich zweier neuronaler Netzwerkmodelle miteinander zeigen sie recht gute Ergebnisse, obwohl sie unlogische Aktionen ausführen.

Beim Spiel zwischen einem neuronalen Netzwerk und einer Alpha-Beta-Suche mit einer Suchtiefe von 1 Schritt hat das neuronale Netzwerk recht gute Gewinnchancen.

In einem Spiel zwischen neuronalem Netz und Alpha-Beta-Suchen mit einer Suchtiefe von 2 Schritten hatte das neuronale Netz keine Chance und verlor alle Spiele.

Ich habe noch nicht tiefer geschaut, weil es sinnlos ist. Vielleicht können nach mehr Spielen akzeptablere Ergebnisse erzielt werden, oder wenn Sie dem neuronalen Netzwerk beibringen, nicht mit denselben Netzwerken, sondern mit einem Alpha-Beta-Suchagenten zu spielen

Abschluss

Die Anwendung genetischer Algorithmen auf das Damespiel veranschaulicht das transformative Potenzial biologisch inspirierter Berechnungen. Während sich traditionelle Spielalgorithmen wie Minimax und seine Varianten als effektiv erwiesen haben, bietet der evolutionäre und adaptive Charakter von GAs eine neue Perspektive.

Wie bei der biologischen Evolution sind die mit dieser Methode entwickelten Strategien möglicherweise nicht immer sofort die besten. Dennoch können sie sich mit genügend Zeit und den richtigen Bedingungen zu beeindruckenden Gegnern entwickeln und die Leistungsfähigkeit der von der Natur inspirierten Berechnung unter Beweis stellen.

Egal, ob Sie ein Dame-Enthusiast, ein KI-Forscher oder einfach nur jemand sind, der von der Konvergenz von Altem und Neuem fasziniert ist, es lässt sich nicht leugnen, dass die Verschmelzung dieses uralten Spiels mit modernsten Algorithmen eine spannende Grenze in der künstlichen Intelligenz darstellt .

Wie üblich wird der gesamte Code auf GitHub bereitgestellt