जेनेटिक एल्गोरिदम के साथ चेकर्स खेलना: पारंपरिक खेलों में विकासवादी शिक्षा

पहचान

चेकर्स, जिसे ड्राफ्ट के नाम से भी जाना जाता है, एक प्राचीन खेल है जो लंबे समय से लोकप्रिय रहा है। अन्य क्लासिक बोर्ड गेम्स की तरह, इसने अपने प्रयोगों के लिए एक मंच के रूप में कंप्यूटर वैज्ञानिकों और एआई शोधकर्ताओं की रुचि को आकर्षित किया है। चेकर्स खेलने के लिए कंप्यूटर को प्रशिक्षित करने के लिए वे जिस प्रमुख विधि का उपयोग करते हैं वह आनुवंशिक एल्गोरिदम है, जो विकास को संचालित करने वाले योग्यतम के अस्तित्व की अवधारणा पर आधारित है।

इस लेख में, हम चेकर्स और आनुवंशिक एल्गोरिदम के प्रतिच्छेदन का पता लगाएंगे, यह प्रदर्शित करते हुए कि कुशल चेकर्स-प्लेइंग एजेंटों को विकसित करने के लिए विकासवादी कम्प्यूटेशनल तकनीकों को कैसे नियोजित किया जा सकता है।

मेरे पिछले लेख में, मुझे लगता है कि मैंने चेकर्स के विषय को पर्याप्त रूप से कवर किया है, लेकिन फिर भी, आइए खेल के बुनियादी नियमों को याद रखें: चेकर्स का खेल 10x10 बोर्ड पर खेला जाता है, जिसमें प्रत्येक खिलाड़ी 20 टुकड़ों से शुरू होता है।

लक्ष्य सरल है: अपने प्रतिद्वंद्वी के सभी टुकड़ों पर कब्जा कर लें या उन्हें फँसा लें ताकि वे हिल न सकें। प्राथमिक रणनीतियाँ स्थिति, रक्षा, आक्रमण और प्रतिद्वंद्वी की चाल का पूर्वानुमान लगाने के इर्द-गिर्द घूमती हैं।

आनुवंशिक एल्गोरिदम (GAs)

मूल बातें

जीए प्राकृतिक चयन की प्रक्रिया पर आधारित अनुकूलन एल्गोरिदम हैं। ये एल्गोरिदम प्रकृति में देखी गई विकास की प्रक्रिया को दर्शाते हैं, जिसमें चयन, क्रॉसओवर (पुनर्संयोजन), और उत्परिवर्तन शामिल हैं।

तंत्रिका नेटवर्क के घटक

यह आलेख पूरी तरह से जुड़ी परतों के साथ एक सरल मॉडल का उपयोग करेगा। एक परत न्यूरॉन्स का एक संग्रह है जो इनपुट को संसाधित करता है और आउटपुट उत्पन्न करता है। फिर इन आउटपुट को अंतिम परत (आउटपुट परत) के मामले में अंतिम भविष्यवाणी के रूप में उपयोग किया जाता है या नेटवर्क में अगली परत में इनपुट के रूप में पारित किया जाता है।

प्रत्येक परत में शामिल हैं:

• इनपुट : इनपुट पैरामीटर की संख्या

• आउटपुट : आउटपुट पैरामीटर की संख्या

• वज़न : वज़न वे पैरामीटर हैं जिन्हें नेटवर्क भविष्यवाणी त्रुटि को कम करने के लिए प्रशिक्षण के दौरान समायोजित करता है।

• पूर्वाग्रह : सक्रियण फ़ंक्शन से पहले इनपुट योग में जोड़ा जाता है। पूर्वाग्रह वजन के साथ-साथ आउटपुट को समायोजित करने में मदद करता है।

• सक्रियण फ़ंक्शन : एक परत में प्रत्येक न्यूरॉन, इनपुट परत को छोड़कर, आउटपुट को अगली परत पर भेजने से पहले अपने इनपुट पर एक सक्रियण फ़ंक्शन लागू करता है। नेटवर्क के लिए डेटा में गैर-रेखीय संबंधों को मॉडल करना आवश्यक है।

आनुवंशिक एल्गोरिथम के घटक

• जनसंख्या : उम्मीदवार समाधानों का एक सेट।

• फिटनेस फ़ंक्शन : यह किसी व्यक्तिगत समाधान के प्रदर्शन या "फिटनेस" का मूल्यांकन करता है।

• चयन : फिटनेस के आधार पर, प्रजनन के लिए कुछ समाधान चुने जाते हैं।

• क्रॉसओवर : संतान पैदा करने के लिए दो चयनित समाधानों के भागों का संयोजन।

• उत्परिवर्तन : संतानों में छोटे-छोटे यादृच्छिक परिवर्तन लाना।

चेकर्स पर जेनेटिक एल्गोरिदम लागू करना

समस्या और फिटनेस मूल्यांकन को एन्कोड करना

सबसे पहले, हमें यह पता लगाना होगा कि संभावित समाधान को चेकर्स रणनीति की तरह कैसे प्रस्तुत किया जाए, जो आनुवंशिक एल्गोरिदम के साथ काम करेगा। हमारे मामले में, हम मौजूदा खिलाड़ी के लिए सभी संभावित चालों को पकड़ेंगे, प्रत्येक के बारे में जीए को हिट करेंगे, और फिर सबसे बड़े वजन के साथ चाल को चुनेंगे।

साथ ही, हमें जनसंख्या में सर्वश्रेष्ठ आइटम चुनने के लिए गेम स्कोर की गणना करने की आवश्यकता है। हमारे मामले में, यह होगा:

• एक जीत के लिए 250 अंक
• प्रत्येक साधारण चेकर के लिए 3 अंक
• किंग चेकर के लिए 7
• प्रत्येक चाल के लिए -1

प्रत्येक आबादी के लिए, हम एक टूर्नामेंट (स्विस-सिस्टम टूर्नामेंट का एक सरलीकृत संस्करण) बनाएंगे। प्रत्येक टूर्नामेंट के बाद, हम भविष्य के चयन के लिए 1/4 आबादी का चयन करते हैं।

यदि कोई एजेंट 1 से अधिक टूर्नामेंट में शीर्ष खिलाड़ी (अगली पीढ़ी के लिए चयनित) है, तो हम उसे शीर्ष खिलाड़ी के रूप में चुनते हैं, और सभी युग समाप्त होने के बाद, हम शीर्ष खिलाड़ियों के बीच एक टूर्नामेंट बनाते हैं और सर्वश्रेष्ठ को चुनते हैं, जिसे सहेजा जाएगा.

चेकर्स में चयन, क्रॉसओवर और उत्परिवर्तन

एल्गोरिथम का सार रणनीतियों की जनसंख्या विकसित करने में निहित है।

• चयन : खेलों में बेहतर प्रदर्शन करने वाली रणनीतियों के पुनरुत्पादन के लिए चुने जाने की संभावना अधिक होती है।

• क्रॉसओवर : दो "मूल" रणनीतियों को जोड़ा जा सकता है, संभवतः एक से कुछ शुरुआती चालें और दूसरे से अंतिम-गेम रणनीतियां ली जा सकती हैं।

• उत्परिवर्तन : कभी-कभी, एक रणनीति में यादृच्छिक परिवर्तन हो सकते हैं, संभावित रूप से नई, प्रभावी रणनीति की खोज हो सकती है।

चुनौतियाँ और सीमाएँ

स्थानीय इष्टतम

एल्गोरिथम के स्थानीय इष्टतम में फंसने का जोखिम है, जहां उसे लगता है कि उसे सबसे अच्छी रणनीति मिल गई है लेकिन समाधान स्थान के केवल एक छोटे से क्षेत्र में ही इष्टतम है।

कम्प्यूटेशनल तीव्रता

जबकि जीए तेज़ हो सकते हैं, हजारों या लाखों खेलों के अनुकरण के लिए महत्वपूर्ण कम्प्यूटेशनल संसाधनों की आवश्यकता होती है।

ओवरफिटिंग

एक जोखिम है कि विकसित रणनीति प्रशिक्षण परिदृश्यों के अनुरूप हो जाती है और अनदेखी रणनीतियों या रणनीति के खिलाफ खराब प्रदर्शन करती है।

कोडन

मैं node.js का उपयोग करने जा रहा हूँ।

पायथन क्यों नहीं?

मुझे पता है कि पायथन अधिक प्रभावी होगा, लेकिन नोड.जेएस के साथ, जिससे मैं अधिक परिचित हूं, इसे क्लाइंट-साइड और सर्वर-साइड पर आसानी से उपयोग किया जा सकता है।

Tensorflow.js (या कोई अन्य लाइब्रेरी जो आपके बहुत करीब है) क्यों नहीं ?

शुरुआत में, मैंने इस लाइब्रेरी का उपयोग करने की योजना बनाई थी, लेकिन फिर मैंने फैसला किया कि चूंकि यह परियोजना मुख्य रूप से शैक्षिक है, इसलिए मैं स्वयं एक न्यूनतम व्यवहार्य न्यूरॉन नेटवर्क बना सकता हूं और आगे के सुधारों के लिए जगह भी छोड़ सकता हूं (उदाहरण के लिए, गणना के लिए wasm का उपयोग करें)।

तंत्रिका नेटवर्क

लगभग कोई भी तंत्रिका नेटवर्क परतों का एक सेट होता है जहां कुछ डेटा इनपुट के रूप में प्राप्त किया जाता है, सूचकांकों के एक सेट से गुणा किया जाता है, और कुछ डेटा वापस किया जाता है।

स्पष्टता के लिए, कल्पना करें कि आप अपने सपनों का एक नया घर ढूंढ रहे हैं, और अब आपको वह मिल गया है, और अब आप अपने दोस्तों से पूछते हैं कि वे इस घर के बारे में क्या सोचते हैं, और वे अपना उत्तर 10-बिंदु पैमाने पर देते हैं, उदाहरण के लिए .

आप अपने प्रत्येक मित्र की राय पर कुछ हद तक भरोसा करते हैं, लेकिन आपको हर किसी से पूछना होगा, यहां तक कि उन लोगों से भी जिन पर आप विशेष रूप से भरोसा नहीं करते हैं, ताकि नाराज न हों। और इसलिए आप अपने दोस्तों के साथ एक समूह में अपने पसंदीदा पेय के साथ बैठते हैं और विभिन्न घरों को देखते हैं, और हर कोई कहता है कि उन्हें यह कितना पसंद आया।

परिणामस्वरूप, आप जानते हैं कि आपके मित्र प्रत्येक घर के बारे में क्या सोचते हैं, और अंतिम परिणाम के आधार पर आप निर्णय लेते हैं।

तंत्रिका नेटवर्क में ऐसे ही "मित्र" होते हैं, लेकिन मित्रों के समूहों की संख्या काफी बड़ी हो सकती है, और हर कोई पिछले समूह की राय पर निर्भर करता है।

तंत्रिका नेटवर्क की योजनाबद्ध प्रस्तुति:

तंत्रिका नेटवर्क के लिए परत:

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

प्रतिनिधि

agent एक ऐसी इकाई है जो यह तय करती है कि आगे क्या करना है और अपनी गतिविधियों के लिए पुरस्कार या जुर्माना प्राप्त करती है। दूसरे शब्दों में, एक एजेंट एक सामान्य व्यक्ति होता है जो काम पर निर्णय लेता है और इसके लिए पुरस्कार प्राप्त करता है।

हमारे कार्य के भाग के रूप में, एजेंट में एक तंत्रिका नेटवर्क होता है और तंत्रिका नेटवर्क के दृष्टिकोण से सर्वोत्तम समाधान का चयन करता है।

साथ ही, हमारा एजेंट, किसी भी अच्छे कर्मचारी की तरह, अपने काम के परिणामों को याद रखता है और अपने वरिष्ठों (आनुवंशिक एल्गोरिदम) को औसत मूल्य के बारे में रिपोर्ट करता है, जिसके आधार पर इस कर्मचारी के बारे में अंतिम निर्णय किया जाता है।

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

एजेंटों के बीच मैच खेलें।

कार्य का परिणाम प्राप्त करने के लिए, हमें दो एजेंटों की तुलना करने की आवश्यकता है ताकि वे समान स्थिति में हों; उनमें से प्रत्येक प्रत्येक रंग के लिए खेलेगा, और अंतिम परिणाम संक्षेप में प्रस्तुत किया जाएगा।

अनावश्यक जानकारी के साथ नेटवर्क को ओवरलोड न करने के लिए, प्रत्येक एजेंट बोर्ड को ऐसे देखता है जैसे वह सफेद चेकर्स खेल रहा हो।

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

टूर्नामेंट खेलें

एजेंटों के प्रशिक्षण (कार्य का परीक्षण) के प्रत्येक युग में, हमारे पास प्रयोगात्मक एजेंटों का एक सेट होता है जिन्हें हम एक-दूसरे के खिलाफ खड़ा करेंगे। लेकिन चूँकि प्रत्येक एजेंट की एक-दूसरे से जाँच करना बहुत लंबा और अप्रभावी होगा, इसलिए हम एक सरलीकृत शतरंज टूर्नामेंट एल्गोरिदम का उपयोग करेंगे।

प्रत्येक चरण में, हमारे पास अंकों के आधार पर क्रमबद्ध खिलाड़ियों की एक सूची होती है और उन्हें निम्नानुसार वितरित किया जाता है: पहला खिलाड़ी शीट के मध्य से पहले प्रतिद्वंद्वी के साथ खेलता है। यदि वह पहले ही उसके साथ खेल चुका है, तो हम अगले का चयन करते हैं।

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

प्रतियोगिता

यहीं पर आनुवंशिक एल्गोरिदम का सारा जादू घटित होता है। मौजूदा मॉडल लोड किए जाते हैं, और नए बनाए जाते हैं।

इन मॉडलों से, हमें एजेंटों के साथ एक जीनोम मिलता है जिसका उपयोग हमारे खेल में किया जाएगा। जैसे-जैसे प्रशिक्षण आगे बढ़ेगा, यह जीनोम बदल जाएगा, सबसे कम स्कोर वाले एजेंटों को हटा दिया जाएगा, और उच्चतम स्कोर वाले एजेंट अपने जीन को नई पीढ़ियों तक पहुंचाएंगे और उनके साथ तुलना की जाएगी।

एक नया जीनोम बनाएं:

वंशानुगत समस्याओं आदि के बिना, किसी दिए गए संख्यात्मक अंतराल में जीन का एक नया सेट बनाया जाता है, और यहीं से सब कुछ शुरू होगा।

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

क्रॉसओवर:

तंत्र काफी सरल है; हम एजेंटों से जीन (वजन) के दो सेट लेते हैं और, संभावना के आधार पर, हम पहले एजेंट या दूसरे से एक जीन लेते हैं, इस प्रकार, जीन मिश्रित होते हैं और पहले और दूसरे से कुछ ज्ञान के साथ एक नया नेटवर्क प्राप्त होता है प्रतिनिधि।

वास्तविक प्रकृति में सब कुछ ठीक इसी प्रकार काम करता है; हममें से प्रत्येक के पास अपने माता-पिता में से प्रत्येक से जीन हैं।

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

उत्परिवर्तित करें:

उत्परिवर्तन फ़ंक्शन इस प्रकार काम करता है: हम जीन का एक सेट लेते हैं और, कुछ हद तक संभावना के साथ, इसमें थोड़ी गड़बड़ी जोड़ते हैं। फिर, वास्तविक जीवन में, सब कुछ बिल्कुल उसी तरह से काम करता है, और हम में से प्रत्येक के पास ऐसे जीन होते हैं जो हमारे माता-पिता में नहीं होते हैं, अन्यथा, हमारे शरीर में कोई बीमारी और अन्य समझ से बाहर होने वाली प्रक्रियाएं नहीं होतीं।

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

प्रत्येक टूर्नामेंट के परिणामस्वरूप, हमारे पास कुछ निश्चित संख्या में एजेंट होते हैं जो दूसरों की तुलना में थोड़े भाग्यशाली होते हैं (आनुवंशिक एल्गोरिदम में, सब कुछ हमारे जीवन पर आधारित होता है, और कुछ अधिक भाग्यशाली होते हैं, कुछ कम)।

और अंत में, हम इन बहुत भाग्यशाली लोगों की सूची लेते हैं और अपने खेल के लिए सर्वश्रेष्ठ जीनोम खोजने के लिए उनकी एक-दूसरे से तुलना करते हैं, और ताकि डेटा गायब न हो जाए, हमें इस जीनोम को सहेजना याद रखना चाहिए।

जब हमारे पास पर्याप्त संख्या में ऐसे जीनोम होंगे, तो हम उनके आधार पर एजेंटों की आबादी बना सकते हैं। फिर भी, प्रत्येक जीनोम को पहले से ही कुछ समझ है कि उसे क्या करने की आवश्यकता है।

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

परिणाम

परिणामों के लिए, मैंने सबसे मौजूदा मॉडलों का उपयोग किया, और यही परिणाम निकला:

जब 2 तंत्रिका नेटवर्क मॉडल की एक दूसरे से तुलना की जाती है, तो वे काफी अच्छे परिणाम दिखाते हैं, हालांकि वे अतार्किक कार्य करते हैं।

1 चरण की खोज गहराई के साथ तंत्रिका नेटवर्क और अल्फा बीटा खोज के बीच खेलते समय, तंत्रिका नेटवर्क के जीतने की काफी अच्छी संभावना होती है।

2 चरणों की खोज गहराई के साथ तंत्रिका नेटवर्क और अल्फा बीटा खोजों के बीच एक गेम में, तंत्रिका नेटवर्क के पास कोई मौका नहीं था और सभी गेम हार गए।

मैंने अभी तक गहराई से नहीं देखा है क्योंकि यह व्यर्थ है। हो सकता है कि अधिक गेम के बाद यह अधिक स्वीकार्य परिणाम देने में सक्षम हो, या यदि आप तंत्रिका नेटवर्क को समान नेटवर्क के साथ नहीं, बल्कि अल्फा-बीटा खोज एजेंट के साथ खेलना सिखाते हैं

निष्कर्ष

चेकर्स के खेल में आनुवंशिक एल्गोरिदम लागू करना जैविक रूप से प्रेरित गणना की परिवर्तनकारी क्षमता का उदाहरण है। जबकि मिनिमैक्स और इसके वेरिएंट जैसे पारंपरिक गेम-प्लेइंग एल्गोरिदम प्रभावी साबित हुए हैं, जीए की विकासवादी और अनुकूली प्रकृति एक नया परिप्रेक्ष्य प्रदान करती है।

जैविक विकास की तरह, इस पद्धति के माध्यम से विकसित की गई रणनीतियाँ हमेशा तुरंत सबसे उपयुक्त नहीं हो सकती हैं। फिर भी, पर्याप्त समय और सही परिस्थितियाँ मिलने पर, वे प्रकृति-प्रेरित गणना की शक्ति का प्रदर्शन करते हुए, दुर्जेय विरोधियों के रूप में विकसित हो सकते हैं।

चाहे आप चेकर्स के प्रति उत्साही हों, एआई शोधकर्ता हों, या पुराने और नए के अभिसरण से रोमांचित हों, इस बात से इनकार नहीं किया जा सकता है कि अत्याधुनिक एल्गोरिदम के साथ इस सदियों पुराने गेम का मिश्रण कृत्रिम बुद्धिमत्ता में एक रोमांचक सीमा है। .

हमेशा की तरह, सभी कोड GitHub पर उपलब्ध कराए गए हैं