Genetik Algoritmalarla Dama Oynamak: Geleneksel Oyunlarda Evrimsel Öğrenme

Giriş

Dama olarak da bilinen dama, uzun süredir popüler olan eski bir oyundur. Diğer klasik masa oyunları gibi, deneyleri için bir platform olarak bilgisayar bilimcilerinin ve yapay zeka araştırmacılarının ilgisini çekmiştir. Bilgisayarları dama oynayacak şekilde eğitmek için kullandıkları öne çıkan yöntemlerden biri, evrimi yönlendiren en uygun olanın hayatta kalması kavramına dayanan genetik algoritmadır.

Bu makalede, dama ile genetik algoritmaların kesişimini inceleyeceğiz ve dama oynayan yetkin aktörler geliştirmek için evrimsel hesaplama tekniklerinin nasıl kullanılabileceğini göstereceğiz.

Son yazımda dama konusuna yeterince değindiğimi düşünüyorum ama yine de oyunun temel kurallarını hatırlayalım: Dama oyunu 10x10'luk bir tahta üzerinde oynanır ve her oyuncu 20 taşla başlar.

Amaç basit: Rakibinizin tüm taşlarını ele geçirin veya hareket edemeyecekleri şekilde tuzağa düşürün. Birincil stratejiler konumlandırma, savunma, hücum ve rakibin hareketlerini öngörme etrafında döner.

Genetik Algoritmalar (GA'lar)

Temeller

GA'lar doğal seçilim sürecine dayalı optimizasyon algoritmalarıdır. Bu algoritmalar doğada gözlemlenen seçilim, çaprazlama (rekombinasyon) ve mutasyondan oluşan evrim prosedürünü yansıtır.

Sinir Ağının Bileşenleri

Bu makalede, tamamen bağlantılı katmanlara sahip basit bir model kullanılacaktır. Katman, girdileri işleyen ve çıktılar üreten bir nöron topluluğudur. Bu çıktılar daha sonra son katman (çıkış katmanı) durumunda nihai tahmin olarak kullanılır veya ağdaki bir sonraki katmana girdi olarak aktarılır.

Her katman şunları içerir:

• girişler : giriş parametrelerinin sayısı

• çıkışlar : çıkış parametrelerinin sayısı

• ağırlıklar : Ağırlıklar, tahmin hatasını en aza indirmek için ağın eğitim sırasında ayarladığı parametrelerdir.

• önyargı : aktivasyon fonksiyonundan önce giriş toplamına eklenir. Önyargı, çıktının ağırlıklarla birlikte ayarlanmasına yardımcı olur.

• Aktivasyon Fonksiyonu : Giriş katmanı dışındaki katmandaki her nöron, çıkışı bir sonraki katmana geçirmeden önce girişine bir aktivasyon fonksiyonu uygular. Bu, ağın verilerdeki doğrusal olmayan ilişkileri modellemesi için gereklidir.

Genetik Algoritmanın Bileşenleri

• Popülasyon : Bir dizi aday çözüm.

• Uygunluk Fonksiyonu : Bireysel bir çözümün performansını veya "uygunluğunu" değerlendirir.

• Seçim : Uygunluğa bağlı olarak bazı çözümler çoğaltılmak üzere seçilir.

• Çaprazlama : Seçilen iki çözümün parçalarını birleştirerek yeni nesiller oluşturma.

• Mutasyon : Yavrularda rastgele küçük değişiklikler yapılması.

Damalara Genetik Algoritmaların Uygulanması

Problemin Kodlanması ve Uygunluk Değerlendirmesi

İlk olarak, dama stratejisi gibi potansiyel bir çözümü genetik algoritmayla çalışacak şekilde nasıl temsil edeceğimizi bulmamız gerekiyor. Bizim durumumuzda, mevcut oyuncu için mümkün olan tüm hamleleri alacağız, her biri için GA'ya ulaşacağız ve ardından en büyük ağırlığa sahip hamleyi seçeceğiz.

Ayrıca popülasyondaki en iyi eşyaları seçmek için oyun puanını hesaplamamız gerekiyor. Bizim durumumuzda şöyle olacak:

• Galibiyete 250 puan
• Her sıradan pul için 3 puan
• Kral Checker için 7
• Her hamle için -1

Her nüfus için bir turnuva yapacağız (İsviçre sistemindeki turnuvanın basitleştirilmiş bir versiyonu). Her turnuvadan sonra gelecekteki seçim için nüfusun 1/4'ünü seçiyoruz.

Eğer bir temsilci 1'den fazla turnuvada en iyi oyuncuysa (yeni nesil için seçilmişse), onu en iyi oyuncu olarak seçeriz ve tüm dönemler bittikten sonra en iyi oyuncular arasında bir turnuva düzenler ve en iyisini seçeriz, hangisi kurtarılacak.

Damada Seçme, Çaprazlama ve Mutasyon

Algoritmanın özü, strateji popülasyonunun geliştirilmesinde yatmaktadır.

• Seçim : Oyunlarda daha iyi performans gösteren stratejilerin yeniden üretim için seçilme şansı daha yüksektir.

• Çaprazlama : İki "ana" strateji birleştirilebilir, muhtemelen birinden bazı açılış hamleleri ve diğerinden oyun sonu taktikleri alınabilir.

• Mutasyon : Bazen bir strateji rastgele değişikliklere uğrayabilir ve potansiyel olarak yeni, etkili taktikler keşfedilebilir.

Zorluklar ve Sınırlamalar

Yerel Optimum

Algoritmanın, en iyi stratejiyi bulduğunu ancak çözüm uzayının yalnızca küçük bir bölgesinde optimal olduğunu düşündüğü yerel bir optimumda takılıp kalma riski vardır.

Hesaplama Yoğunluğu

GA'lar hızlı olabilse de binlerce veya milyonlarca oyunun simüle edilmesi önemli hesaplama kaynakları gerektirir.

Aşırı uyum gösterme

Geliştirilen stratejinin eğitim senaryolarına çok fazla uyarlanması ve görünmeyen strateji veya taktiklere karşı düşük performans göstermesi riski vardır.

Kodlama

Node.js'yi kullanacağım.

Neden Python olmasın?

Python'un daha etkili olacağını biliyorum ama daha aşina olduğum node.js ile istemci tarafında ve sunucu tarafında rahatlıkla kullanılabiliyor.

Neden tensorflow.js (veya size bu kadar yakın olan başka bir kütüphane) olmasın ?

Başlangıçta bu kütüphaneyi kullanmayı planladım, ancak daha sonra bu projenin öncelikle eğitim amaçlı olması nedeniyle, minimum düzeyde uygulanabilir bir nöron ağı oluşturabileceğime ve ayrıca daha fazla iyileştirme için alan bırakabileceğime (örneğin, hesaplamalar için wasm'i kullanma) karar verdim.

Sinir ağı

Hemen hemen her sinir ağı, bazı verilerin girdi olarak alındığı, bir dizi endeksle çarpıldığı ve bazı verilerin geri döndürüldüğü bir katmanlar kümesidir.

Anlaşılır olması açısından, hayallerinizdeki yeni evi aradığınızı ve onu bulduğunuzu ve şimdi arkadaşlarınıza bu ev hakkında ne düşündüklerini sorduğunuzu ve cevaplarını 10 puanlık bir ölçekte verdiklerini hayal edin. .

Her arkadaşlarınızın fikrine bir dereceye kadar güveniyorsunuz, ancak rencide etmemek için herkese, özellikle güvenmediklerinize bile sormalısınız. Ve böylece arkadaşlarınızla bir grup halinde oturup en sevdiğiniz içecekleri içiyorsunuz ve farklı evlere bakıyorsunuz ve herkes bunu ne kadar beğendiğini söylüyor.

Sonuç olarak, arkadaşlarınızın her ev hakkında ne düşündüğünü bilirsiniz ve nihai sonuca göre karar verirsiniz.

Sinir ağı tam da bu tür "arkadaşlardan" oluşur, ancak arkadaş gruplarının sayısı oldukça fazla olabilir ve herkes bir önceki grubun görüşüne güvenir.

Sinir ağının şematik sunumu:

Sinir Ağı Katmanı:

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

Sinir ağı:

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

Ajan

agent , bundan sonra ne yapılacağına karar veren ve faaliyetleri karşılığında ödül veya para cezası alan bir varlıktır. Başka bir deyişle temsilci, işyerinde kararlar veren ve bunun karşılığında ödül alan sıradan bir kişidir.

Görevimizin bir parçası olarak, etmen bir sinir ağı içerir ve sinir ağı açısından en iyi çözümü seçer.

Ayrıca temsilcimiz, herhangi bir iyi çalışan gibi, işinin sonuçlarını hatırlar ve bu çalışan hakkında nihai kararın verildiği ortalama değer hakkında üstlerine (genetik algoritma) rapor verir.

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

Temsilciler Arasında Bir Maç Oynayın.

Çalışmanın sonucunu elde etmek için iki ajanı eşit koşullarda olacak şekilde karşılaştırmamız gerekir; her biri her renk için oynayacak ve nihai sonuç özetlenecek.

Ağı gereksiz bilgilerle aşırı yüklememek için her temsilci tahtayı sanki beyaz dama oynuyormuş gibi görüyor.

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

Turnuva Oyna

Ajanların eğitiminin (işin test edilmesi) her aşamasında, birbirimize karşı koyacağımız bir dizi deneysel ajanımız var. Ancak her bir temsilciyi birbiriyle kontrol etmek çok uzun ve etkisiz olacağından, basitleştirilmiş bir satranç turnuvası algoritması kullanacağız.

Her aşamada, puanlara göre sıralanmış bir oyuncu listemiz var ve bunları şu şekilde dağıtıyoruz: İlki, sayfanın ortasından ilk rakiple oynuyor. Eğer onunla zaten oynadıysa bir sonrakini seçiyoruz.

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

Turnuvalar

Genetik algoritmanın tüm büyüsü burada gerçekleşir. Mevcut modeller yüklenir ve yenileri oluşturulur.

Bu modellerden oyunumuzda kullanılacak ajanların bulunduğu bir genom elde ediyoruz. Eğitim ilerledikçe bu genom değişecek, en düşük puana sahip ajanlar atılacak, en yüksek puana sahip ajanlar genlerini yeni nesillere aktaracak ve onlarla karşılaştırılacak.

Yeni bir genom oluşturun:

Belirli bir sayısal aralıkta, kalıtsal sorunlar ve benzeri olmadan yeni bir gen dizisi yaratılır ve her şey burada başlayacaktır.

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

Karşıdan karşıya geçmek:

Mekanizması oldukça basittir; ajanlardan iki set gen (ağırlık) alıyoruz ve olasılığa bağlı olarak birinci veya ikinci ajandan bir gen alıyoruz, böylece genler karıştırılıyor ve birinci ve ikinciden bir miktar bilgi ile yeni bir ağ elde ediliyor ajan.

Gerçek doğada her şey tam olarak böyle işler; her birimiz ebeveynlerimizin her birinden genlere sahibiz.

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

Mutasyon:

Mutasyon işlevi şu şekilde çalışır: Bir dizi gen alırız ve bir dereceye kadar olasılıkla ona biraz kaos ekleriz. Yine gerçek hayatta her şey tamamen aynı şekilde çalışır ve her birimizin ebeveynimizde olmayan genleri vardır, aksi takdirde vücudumuzda hiçbir hastalık ve diğer anlaşılmaz süreçler olmazdı.

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

Her turnuva sonucunda diğerlerinden biraz daha şanslı olan belirli sayıda ajanımız olur (Genetik algoritmalarda her şey bizim hayatımız üzerine kuruludur ve bazıları daha şanslı, bazıları daha az).

Ve sonunda bu çok şanslı olanların listesini alıyoruz ve oyunumuz için en iyi genomu bulmak için bunları birbirleriyle karşılaştırıyoruz ve verilerin kaybolmaması için bu genomu kaydetmeyi unutmamalıyız.

Yeterli sayıda bu tür genomlara sahip olduğumuzda, bunlara dayanarak ajan popülasyonları oluşturabiliriz. Yine de, genomların her biri zaten ne yapması gerektiğine dair bir anlayışa sahip.

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

Sonuçlar

Sonuçlar için en güncel modelleri kullandım ve ortaya şu çıktı:

2 sinir ağı modeli birbiriyle karşılaştırıldığında mantıksız eylemler gerçekleştirmesine rağmen oldukça iyi sonuçlar veriyor.

Bir sinir ağı ile 1 adımlık arama derinliğine sahip bir alfa beta araması arasında oynarken, sinir ağının kazanma şansı oldukça yüksektir.

Sinir ağı ile alfa beta aramaları arasında 2 adımlık arama derinliğine sahip bir oyunda sinir ağının hiç şansı yoktu ve tüm oyunları kaybetti.

Henüz daha derine bakmadım çünkü anlamsız. Belki daha fazla oyundan sonra daha kabul edilebilir sonuçlar üretebilir veya sinir ağına aynı ağlarla değil, bir alfa-beta arama aracısıyla oynamayı öğretirseniz

Çözüm

Dama oyununa genetik algoritmaların uygulanması, biyolojik olarak ilham alan hesaplamanın dönüştürücü potansiyelini örneklendiriyor. Minimax ve çeşitleri gibi geleneksel oyun oynama algoritmalarının etkili olduğu kanıtlanmış olsa da, GA'ların evrimsel ve uyarlanabilir doğası yeni bir bakış açısı sunuyor.

Biyolojik evrimde olduğu gibi, bu yöntemle geliştirilen stratejiler her zaman en uygun stratejiler olmayabilir. Yine de yeterli zaman ve doğru koşullar sağlandığında, doğadan ilham alan hesaplamanın gücünü gösteren zorlu rakiplere dönüşebilirler.

İster dama meraklısı olun, ister yapay zeka araştırmacısı olun, ister sadece eski ile yeninin birleşiminden büyülenmiş biri olun, bu asırlık oyunun son teknoloji algoritmalarla birleştirilmesinin yapay zekada heyecan verici bir sınır olduğu inkar edilemez. .

Her zamanki gibi tüm kodlar GitHub'da sağlandı