Игра в шашки с использованием генетических алгоритмов: эволюционное обучение в традиционных играх

вступление Шашки, также известные как шашки, — древняя игра, популярная с давних времен. Как и другие классические настольные игры, она привлекла интерес ученых-компьютерщиков и исследователей искусственного интеллекта как платформа для их экспериментов. Известный метод, который они используют для обучения компьютеров игре в шашки, — это генетический алгоритм, основанный на концепции выживания наиболее приспособленных, которая стимулирует эволюцию. В этой статье мы исследуем пересечение шашек и генетических алгоритмов, демонстрируя, как эволюционные вычислительные методы могут быть использованы для разработки профессиональных агентов, играющих в шашки. В своей прошлой я думаю достаточно раскрыл тему шашек, но все же давайте вспомним основные правила игры: Игра в шашки ведется на доске 10х10, причем каждый игрок начинает с 20 шашками. статье Цель проста: захватить все фигуры противника или поймать их в ловушку, чтобы они не могли двигаться. Основные стратегии вращаются вокруг позиционирования, защиты, нападения и предвидения действий противника. Генетические алгоритмы (ГА) Основы ГА — это алгоритмы оптимизации, основанные на процессе естественного отбора. Эти алгоритмы отражают наблюдаемую в природе процедуру эволюции, включающую отбор, кроссинговер (рекомбинацию) и мутацию. Компоненты нейронной сети В этой статье будет использоваться простая модель с полностью связанными слоями. Слой — это совокупность нейронов, которые обрабатывают входные данные и производят выходные данные. Эти выходные данные затем используются в качестве окончательного прогноза в случае последнего слоя (выходного слоя) или передаются в качестве входных данных на следующий уровень в сети. Каждый слой содержит: : количество входных параметров входы : количество выходных параметров выходы : веса — это параметры, которые сеть корректирует во время обучения, чтобы минимизировать ошибку прогнозирования. веса : добавляется к входной сумме перед функцией активации. Смещение помогает регулировать выходные данные вместе с весами. смещение : каждый нейрон в слое, за исключением входного слоя, применяет функцию активации к своему входу перед передачей вывода на следующий слой. Это важно для того, чтобы сеть могла моделировать нелинейные отношения в данных. Функция активации Компоненты генетического алгоритма : набор возможных решений. Население : оценивает производительность или «пригодность» индивидуального решения. Функция пригодности : в зависимости от приспособленности для воспроизводства отбираются некоторые растворы. Отбор : объединение частей двух выбранных решений для создания потомства. Кроссовер : внесение небольших случайных изменений в потомство. Мутация Применение генетических алгоритмов к шашкам Кодирование проблемы и оценка пригодности Во-первых, нам нужно выяснить, как представить потенциальное решение, например стратегию шашек, таким образом, чтобы оно работало с генетическим алгоритмом. В нашем случае мы берем все возможные ходы текущего игрока, нажимаем GA по каждому из них, а затем выбираем ход с наибольшим весом. Кроме того, нам нужно подсчитать игровой счет, чтобы выбрать лучшие предметы в популяции. В нашем случае это будет: 250 очков за победу 3 очка за каждую обычную шашку 7 для короля шашки -1 за каждый ход Для каждой популяции мы проведем турнир (упрощенная версия турнира по швейцарской системе). После каждого турнира мы отбираем 1/4 населения для дальнейшего отбора. Если какой-то агент является лучшим игроком (выбранным для следующего поколения) более чем в 1 турнире, мы выбираем его лучшим игроком, а после завершения всех эпох мы проводим турнир между лучшими игроками и выбираем лучшего, который будет сохранен. Отбор, кроссовер и мутация в шашках Суть алгоритма заключается в развитии совокупности стратегий. : стратегии, которые лучше работают в играх, имеют больше шансов быть выбранными для воспроизведения. Отбор : можно объединить две «родительские» стратегии, возможно, взяв некоторые начальные ходы из одной и тактику эндшпиля из другой. Кроссовер : иногда стратегия может претерпевать случайные изменения, потенциально открывая новую, эффективную тактику. Мутация Проблемы и ограничения Локальный оптимум Существует риск того, что алгоритм застрянет в локальном оптимуме, когда он думает, что нашел лучшую стратегию, но оптимален только в небольшой области пространства решений. Интенсивность вычислений Хотя ГА могут быть быстрыми, моделирование тысяч или миллионов игр требует значительных вычислительных ресурсов. Переобучение Существует риск того, что разработанная стратегия станет слишком адаптированной к сценариям обучения и будет плохо работать против невидимых стратегий или тактик. Кодирование Я собираюсь использовать node.js. Почему не Питон? Я знаю, что Python будет более эффективным, но с помощью 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 = 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 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 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 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 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); } } Полученные результаты Для получения результатов я использовал самые актуальные модели и вот что получилось: При сравнении двух нейросетевых моделей друг с другом они показывают вполне хорошие результаты, хотя и совершают нелогичные действия. При игре между нейросетью и альфа-бета-поиском с глубиной поиска в 1 шаг нейросеть имеет достаточно хорошие шансы на победу. В игре между нейросетью и альфа-бета-поиском с глубиной поиска в 2 шага у нейросети не было шансов и она проиграла все игры. Я еще не смотрел глубже, потому что это бессмысленно. Может быть, после большего количества игр он сможет выдавать более приемлемые результаты, или если вы научите нейросеть играть не с теми же сетями, а с альфа-бета-поисковым агентом Заключение Применение генетических алгоритмов к игре в шашки иллюстрирует преобразующий потенциал биологических вычислений. Хотя традиционные игровые алгоритмы, такие как Minimax и его варианты, доказали свою эффективность, эволюционный и адаптивный характер ГА открывает новую перспективу. Как и в случае с биологической эволюцией, стратегии, разработанные с помощью этого метода, не всегда сразу могут оказаться наиболее подходящими. Тем не менее, если дать достаточно времени и подходящие условия, они могут превратиться в грозных противников, продемонстрировав мощь вычислений, вдохновленных природой. Являетесь ли вы энтузиастом шашек, исследователем искусственного интеллекта или просто человеком, увлеченным слиянием старого и нового, нельзя отрицать, что объединение этой древней игры с передовыми алгоритмами является захватывающим рубежом в области искусственного интеллекта. . Как обычно, весь код представлен на GitHub.