686 讀數

用遗传算法玩西洋跳棋：传统游戏中的进化学习

经过 Andrey Makarov27m2024/03/08

太長; 讀書

在本文中，我们将探索跳棋和遗传算法的交叉点，展示如何利用进化计算技术来开发熟练的跳棋代理。在我的上一篇文章中，我想我已经足够详细地介绍了西洋跳棋的主题，但是，我们仍然要记住游戏的基本规则：西洋跳棋游戏是在 10x10 的棋盘上进行的，每个玩家从 20 颗棋子开始。 w

介绍

跳棋，又称跳棋，是一种古老的游戏，长期以来一直流行。与其他经典棋盘游戏一样，它作为实验平台吸引了计算机科学家和人工智能研究人员的兴趣。他们用来训练计算机下跳棋的一种重要方法是遗传算法，该算法基于驱动进化的适者生存的概念。

在本文中，我们将探索跳棋和遗传算法的交叉点，展示如何利用进化计算技术来开发熟练的跳棋代理。

在我的上一篇文章中，我想我已经足够介绍了西洋跳棋的主题，但是，我们仍然要记住游戏的基本规则：西洋跳棋游戏是在 10x10 的棋盘上进行的，每个玩家从 20 颗棋子开始。

目标很简单：吃掉对手的所有棋子或困住他们，使他们无法移动。主要策略围绕站位、防守、进攻和预测对手的行动。

遗传算法 (GA)

基础

遗传算法是基于自然选择过程的优化算法。这些算法反映了自然界中观察到的进化过程，包括选择、交叉（重组）和突变。

神经网络的组成部分

本文将使用一个具有全连接层的简单模型。层是处理输入并产生输出的神经元的集合。然后，这些输出将用作最后一层（输出层）的最终预测，或作为输入传递到网络中的下一层。

每层包含：

输入：输入参数的数量

输出：输出参数的数量

权重：权重是网络在训练期间调整的参数，以最小化预测误差。

bias ：在激活函数之前添加到输入和中。偏差有助于调整输出和权重。

激活函数：层中的每个神经元（输入层除外）在将输出传递到下一层之前对其输入应用激活函数。这对于网络对数据中的非线性关系进行建模至关重要。

遗传算法的组成部分

总体：一组候选解决方案。

适应度函数：它评估单个解决方案的性能或“适应度”。

选择：根据适应度，选择一些解进行复制。

交叉：结合两个选定解决方案的部分来创建后代。

突变：在后代中引入小的随机变化。

将遗传算法应用于跳棋

问题编码和适应度评估

首先，我们必须弄清楚如何以适用于遗传算法的方式表示潜在的解决方案，例如跳棋策略。在我们的例子中，我们将获取当前玩家的所有可能的动作，对每个动作进行 GA，然后选择权重最大的动作。

此外，我们需要计算游戏得分以选择总体中最好的项目。在我们的例子中，它将是：

获胜可获得 250 分
每个普通检查员 3 分
7 为国王检查者
每次移动-1

我们将为每个人群举办一场锦标赛（瑞士系统锦标赛的简化版本）。每场比赛结束后，我们都会选择 1/4 的人口作为未来的选择。

如果某个智能体是超过 1 场锦标赛中的顶级玩家（为下一代选择），我们选择他作为顶级玩家，并且在所有 epoch 结束后，我们在顶级玩家之间进行锦标赛并选择最好的，这将被保存。

跳棋中的选择、交叉和变异

该算法的关键在于发展策略群体。

选择：在游戏中表现更好的策略有更高的机会被选择进行复制。

交叉：两种“父”策略可以组合起来，可能从一种策略中采取一些开局动作，从另一种策略中采取最终游戏策略。

突变：有时，策略可能会发生随机变化，可能会发现新的有效策略。

挑战和限制

局部最优

算法存在陷入局部最优的风险，即它认为已经找到了最佳策略，但仅在解决方案空间的一小部分区域中是最优的。

计算强度

虽然 GA 速度很快，但模拟数千或数百万个游戏需要大量的计算资源。

过拟合

存在这样的风险：进化后的策略过于适合训练场景，并且对于未见过的策略或战术表现不佳。

编码

我将使用node.js。

为什么不是Python？

我知道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); } }