জেনেটিক অ্যালগরিদম দিয়ে চেকার খেলা: ঐতিহ্যগত গেমে বিবর্তনীয় শিক্ষা

ভূমিকা

চেকার, ড্রাফট নামেও পরিচিত, একটি প্রাচীন খেলা যা দীর্ঘদিন ধরে জনপ্রিয়। অন্যান্য ক্লাসিক বোর্ড গেমগুলির মতো, এটি কম্পিউটার বিজ্ঞানী এবং এআই গবেষকদের তাদের পরীক্ষার জন্য একটি প্ল্যাটফর্ম হিসাবে আগ্রহ আকর্ষণ করেছে। চেকার বাজানোর জন্য কম্পিউটারকে প্রশিক্ষণ দেওয়ার জন্য তারা যে একটি বিশিষ্ট পদ্ধতি ব্যবহার করে তা হল একটি জেনেটিক অ্যালগরিদম, যা যোগ্যতমের বেঁচে থাকার ধারণার উপর ভিত্তি করে যা বিবর্তনকে চালিত করে।

এই প্রবন্ধে, আমরা চেকার এবং জেনেটিক অ্যালগরিদমের ছেদটি অন্বেষণ করব, কীভাবে বিবর্তনীয় গণনামূলক কৌশলগুলি দক্ষ চেকার-প্লেয়িং এজেন্টদের বিকাশের জন্য নিযুক্ত করা যেতে পারে তা প্রদর্শন করব।

আমার শেষ নিবন্ধে , আমি মনে করি আমি চেকারের বিষয়টি যথেষ্ট কভার করেছি, কিন্তু তবুও, আসুন গেমের প্রাথমিক নিয়মগুলি মনে রাখি: চেকারের খেলাটি 10x10 বোর্ডে খেলা হয়, প্রতিটি খেলোয়াড় 20 টুকরা দিয়ে শুরু করে।

লক্ষ্যটি সহজ: আপনার প্রতিপক্ষের সমস্ত টুকরো ক্যাপচার করুন বা তাদের ফাঁদে ফেলুন যাতে তারা নড়াচড়া করতে না পারে। প্রাথমিক কৌশলগুলি পজিশনিং, প্রতিরক্ষা, অপরাধ এবং প্রতিপক্ষের গতিবিধির চারপাশে ঘোরে।

জেনেটিক অ্যালগরিদম (GAs)

অধিকার

GA হল প্রাকৃতিক নির্বাচন প্রক্রিয়ার উপর ভিত্তি করে অপ্টিমাইজেশান অ্যালগরিদম। এই অ্যালগরিদমগুলি প্রকৃতিতে পরিলক্ষিত বিবর্তনের পদ্ধতিকে প্রতিফলিত করে, যার মধ্যে রয়েছে নির্বাচন, ক্রসওভার (পুনঃসংযোজন), এবং মিউটেশন।

নিউরাল নেটওয়ার্কের উপাদান

এই নিবন্ধটি সম্পূর্ণ-সংযুক্ত স্তরগুলির সাথে একটি সাধারণ মডেল ব্যবহার করবে। একটি স্তর হল নিউরনের একটি সংগ্রহ যা ইনপুট প্রক্রিয়া করে এবং আউটপুট তৈরি করে। এই আউটপুটগুলি শেষ স্তরের (আউটপুট স্তর) ক্ষেত্রে চূড়ান্ত পূর্বাভাস হিসাবে ব্যবহৃত হয় বা নেটওয়ার্কের পরবর্তী স্তরে ইনপুট হিসাবে পাস করা হয়।

প্রতিটি স্তর রয়েছে:

• ইনপুট : ইনপুট প্যারামিটারের সংখ্যা

• আউটপুট : আউটপুট প্যারামিটারের সংখ্যা

• ওজন : ভবিষ্যদ্বাণী ত্রুটি কমানোর জন্য প্রশিক্ষণের সময় নেটওয়ার্ক যে প্যারামিটারগুলিকে সামঞ্জস্য করে তা ওজন।

• bias : সক্রিয়করণ ফাংশনের আগে ইনপুট যোগফল যোগ করা হয়। পক্ষপাত ওজন সহ আউটপুট সামঞ্জস্য করতে সাহায্য করে।

• অ্যাক্টিভেশন ফাংশন : ইনপুট লেয়ার ব্যতীত একটি স্তরের প্রতিটি নিউরন পরবর্তী স্তরে আউটপুট দেওয়ার আগে তার ইনপুটে একটি অ্যাক্টিভেশন ফাংশন প্রয়োগ করে। ডেটাতে নন-লিনিয়ার সম্পর্ক মডেল করার জন্য নেটওয়ার্কের জন্য এটি অপরিহার্য।

একটি জেনেটিক অ্যালগরিদমের উপাদান

• জনসংখ্যা : প্রার্থী সমাধানের একটি সেট।

• ফিটনেস ফাংশন : এটি একটি পৃথক সমাধানের কর্মক্ষমতা বা "ফিটনেস" মূল্যায়ন করে।

• নির্বাচন : ফিটনেসের উপর ভিত্তি করে, প্রজননের জন্য কিছু সমাধান নির্বাচন করা হয়।

• ক্রসওভার : সন্তানসন্ততি তৈরি করতে দুটি নির্বাচিত সমাধানের অংশগুলিকে একত্রিত করা।

• মিউটেশন : সন্তানসন্ততিতে ছোট ছোট এলোমেলো পরিবর্তনগুলি প্রবর্তন করা।

চেকারগুলিতে জেনেটিক অ্যালগরিদম প্রয়োগ করা

সমস্যা এবং ফিটনেস মূল্যায়ন এনকোডিং

প্রথমত, আমাদের জেনেটিক অ্যালগরিদমের সাথে কাজ করবে এমন একটি উপায়ে চেকার্স কৌশলের মতো একটি সম্ভাব্য সমাধান কীভাবে উপস্থাপন করা যায় তা বের করতে হবে। আমাদের ক্ষেত্রে, আমরা বর্তমান প্লেয়ারের জন্য সমস্ত সম্ভাব্য চালগুলি ধরব, প্রতিটি সম্পর্কে GA হিট করব, এবং তারপরে সবচেয়ে বড় ওজন দিয়ে পদক্ষেপটি বেছে নেব।

এছাড়াও, জনসংখ্যার সেরা আইটেমগুলি বেছে নিতে আমাদের গেমের স্কোর গণনা করতে হবে। আমাদের ক্ষেত্রে, এটি হবে:

• জয়ের জন্য 250 পয়েন্ট
• প্রতিটি সাধারণ পরীক্ষকের জন্য 3 পয়েন্ট
• রাজা চেকারের জন্য 7
• -1 প্রতিটি পদক্ষেপের জন্য

প্রতিটি জনসংখ্যার জন্য, আমরা একটি টুর্নামেন্ট করব (সুইস-সিস্টেম টুর্নামেন্টের একটি সরলীকৃত সংস্করণ)। প্রতিটি টুর্নামেন্টের পর, আমরা ভবিষ্যৎ নির্বাচনের জন্য জনসংখ্যার 1/4 নির্বাচন করি।

যদি কোনো এজেন্ট 1টির বেশি টুর্নামেন্টে শীর্ষ খেলোয়াড় (পরবর্তী প্রজন্মের জন্য নির্বাচিত) হয়, তাহলে আমরা তাকে শীর্ষ খেলোয়াড় হিসেবে বেছে নিই, এবং সমস্ত যুগ শেষ হওয়ার পরে, আমরা শীর্ষ খেলোয়াড়দের মধ্যে একটি টুর্নামেন্ট তৈরি করি এবং সেরাকে বেছে নিই, যা সংরক্ষণ করা হবে।

চেকারে নির্বাচন, ক্রসওভার এবং মিউটেশন

অ্যালগরিদমের মূল ভিত্তি কৌশলগুলির জনসংখ্যার বিকাশের মধ্যে রয়েছে।

• নির্বাচন : গেমগুলিতে আরও ভাল পারফর্ম করে এমন কৌশলগুলি প্রজননের জন্য নির্বাচিত হওয়ার সম্ভাবনা বেশি থাকে।

• ক্রসওভার : দুটি "অভিভাবক" কৌশল একত্রিত করা যেতে পারে, সম্ভবত একটি থেকে শুরুর কিছু চাল এবং অন্যটির থেকে শেষ-খেলার কৌশল নেওয়া।

• মিউটেশন : মাঝে মাঝে, একটি কৌশল এলোমেলো পরিবর্তনের মধ্য দিয়ে যেতে পারে, সম্ভাব্য নতুন, কার্যকর কৌশল আবিষ্কার করতে পারে।

চ্যালেঞ্জ এবং সীমাবদ্ধতা

স্থানীয় সর্বোত্তম

অ্যালগরিদম একটি স্থানীয় সর্বোত্তম মধ্যে আটকে যাওয়ার ঝুঁকি রয়েছে, যেখানে এটি মনে করে যে এটি সর্বোত্তম কৌশল খুঁজে পেয়েছে তবে সমাধান স্থানের একটি ছোট অঞ্চলে এটি সর্বোত্তম।

কম্পিউটেশনাল ইনটেনসিটি

যদিও GAগুলি দ্রুত হতে পারে, হাজার হাজার বা লক্ষ লক্ষ গেমের অনুকরণের জন্য উল্লেখযোগ্য গণনামূলক সংস্থানগুলির প্রয়োজন৷

ওভারফিটিং

একটি ঝুঁকি আছে যে বিকশিত কৌশলটি প্রশিক্ষণের পরিস্থিতির জন্য খুব উপযোগী হয়ে যায় এবং অদেখা কৌশল বা কৌশলগুলির বিরুদ্ধে খারাপভাবে কাজ করে।

কোডিং

আমি node.js ব্যবহার করতে যাচ্ছি.

পাইথন কেন নয়?

আমি জানি যে পাইথন আরও কার্যকর হবে, কিন্তু 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 ধাপের অনুসন্ধান গভীরতা সহ, নিউরাল নেটওয়ার্কের কোন সুযোগ ছিল না এবং সমস্ত গেম হারিয়েছে।

আমি এখনও গভীরভাবে তাকাইনি কারণ এটি অর্থহীন। হয়তো আরও গেমের পরে এটি আরও গ্রহণযোগ্য ফলাফল তৈরি করতে সক্ষম হবে, অথবা আপনি যদি নিউরাল নেটওয়ার্ককে একই নেটওয়ার্কের সাথে নয়, একটি আলফা-বিটা অনুসন্ধান এজেন্টের সাথে খেলতে শেখান।

উপসংহার

চেকারদের খেলায় জেনেটিক অ্যালগরিদম প্রয়োগ করা জৈবিকভাবে-অনুপ্রাণিত গণনার রূপান্তরমূলক সম্ভাবনার উদাহরণ দেয়। যদিও মিনিম্যাক্স এবং এর ভেরিয়েন্টের মতো ঐতিহ্যগত গেম-প্লেয়িং অ্যালগরিদমগুলি কার্যকর প্রমাণিত হয়েছে, GA-এর বিবর্তনীয় এবং অভিযোজিত প্রকৃতি একটি নতুন দৃষ্টিভঙ্গি প্রদান করে।

জৈবিক বিবর্তনের মতো, এই পদ্ধতির মাধ্যমে বিকশিত কৌশলগুলি সবসময়ই উপযুক্ত নাও হতে পারে। তবুও, পর্যাপ্ত সময় এবং সঠিক অবস্থার প্রেক্ষিতে, তারা প্রকৃতি-অনুপ্রাণিত গণনার ক্ষমতা প্রদর্শন করে শক্তিশালী প্রতিপক্ষে পরিণত হতে পারে।

আপনি একজন চেকার উত্সাহী হোন, একজন এআই গবেষক, বা পুরানো এবং নতুনের মিলনে মুগ্ধ যে কেউ, এটা অস্বীকার করার কিছু নেই যে অত্যাধুনিক অ্যালগরিদমগুলির সাথে এই যুগ-পুরনো গেমটি কৃত্রিম বুদ্ধিমত্তার একটি উত্তেজনাপূর্ণ সীমান্ত। .

যথারীতি, সমস্ত কোড গিটহাবে দেওয়া হয়েছে