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