遺伝的アルゴリズムを使用したチェッカーのプレイ: 従来のゲームにおける進化的学習

イントロ チェッカーはドラフトとしても知られ、長い間人気のある古代のゲームです。他の古典的なボード ゲームと同様に、実験のプラットフォームとしてコンピューター科学者や AI 研究者の関心を集めています。コンピューターをチェッカーとして訓練するために彼らが使用する代表的な方法は、進化を促す適者生存の概念に基づいた遺伝的アルゴリズムです。 この記事では、チェッカーと遺伝的アルゴリズムの接点を探り、進化的な計算技術を利用して熟練したチェッカーを演じるエージェントを開発する方法を実証します。 前回の で、チェッカーのトピックについては十分に説明したと思いますが、それでも、ゲームの基本的なルールを思い出してください。チェッカー ゲームは 10x10 のボードでプレイされ、各プレイヤーは 20 個の駒から開始します。 記事 目標はシンプルです。敵の駒をすべて占領するか、敵が動けないように罠にかけるのです。主な戦略は、ポジショニング、防御、攻撃、そして相手の動きの予測を中心に展開します。 遺伝的アルゴリズム (GA) 基礎 GA は、自然選択のプロセスに基づいた最適化アルゴリズムです。これらのアルゴリズムは、選択、交叉 (組換え)、突然変異など、自然界で観察される進化の手順を反映しています。 ニューラル ネットワークのコンポーネント この記事では、完全に接続されたレイヤーを持つ単純なモデルを使用します。レイヤーは、入力を処理して出力を生成するニューロンの集合です。これらの出力は、最後の層 (出力層) の場合の最終予測として使用されるか、ネットワーク内の次の層に入力として渡されます。 各レイヤーには以下が含まれます。 : 入力パラメータの数 inputs : 出力パラメータの数 出力 : 重みは、予測誤差を最小限に抑えるためにトレーニング中にネットワークが調整するパラメーターです。 Weights : 活性化関数の前に入力合計に加算されます。バイアスは、重みとともに出力を調整するのに役立ちます。 bias : 入力層を除く層内の各ニューロンは、出力を次の層に渡す前にその入力に活性化関数を適用します。これは、ネットワークがデータ内の非線形関係をモデル化するために不可欠です。 活性化関数 遺伝的アルゴリズムのコンポーネント : 候補解のセット。 Population : 個々のソリューションのパフォーマンスまたは「適合性」を評価します。 フィットネス機能 : 適合度に基づいて、再現のためにいくつかのソリューションが選択されます。 選択 : 選択した 2 つのソリューションの一部を組み合わせて子孫を作成します。 クロスオーバー : 子孫に小さなランダムな変化を導入します。 突然変異 遺伝的アルゴリズムをチェッカーに適用する 問題のエンコードと適合性評価 まず、遺伝的アルゴリズムで機能する方法で、チェッカー戦略などの潜在的な解決策を表現する方法を考え出す必要があります。私たちの場合、現在のプレイヤーの可能なすべての手を取得し、それぞれについて GA を実行し、最も大きな重みを持つ手を選択します。 また、母集団内で最良のアイテムを選択するには、ゲーム スコアを計算する必要があります。私たちの場合は次のようになります。 勝利で250ポイント 通常のチェッカーごとに 3 ポイント キングチェッカーの場合は 7 移動ごとに-1 母集団ごとにトーナメント（スイス方式トーナメントの簡易版）を作成します。各トーナメントの後、将来の選択のために人口の 1/4 を選択します。 あるエージェントが複数のトーナメントでトップ プレーヤー (次世代に選ばれる) である場合、そのエージェントをトップ プレーヤーに選び、すべてのエポックが終了した後、トップ プレーヤー間でトーナメントを開催し、最も優れたプレーヤーを選択します。それは保存されます。 チェッカーにおける選択、交叉、突然変異 このアルゴリズムの核心は、戦略の母集団を進化させることにあります。 : ゲームでより優れたパフォーマンスを発揮する戦略は、再現のために選択される可能性が高くなります。 選択 : 2 つの「親」戦略を組み合わせることができ、一方の戦略から序盤の動きを取り、もう一方の戦略から終盤の戦術を取り込むことができます。 クロスオーバー : 場合によっては、戦略がランダムに変更され、新しい効果的な戦術が発見される可能性があります。 突然変異 課題と限界 ローカル最適化 アルゴリズムが局所最適に行き詰まるリスクがあります。つまり、アルゴリズムは最適な戦略を見つけたと考えているものの、解空間の狭い領域でのみ最適であるということです。 計算量 GA は高速ですが、数千または数百万のゲームをシミュレートするには大量の計算リソースが必要です。 過学習 進化した戦略がトレーニング シナリオに合わせすぎて、目に見えない戦略や戦術に対してパフォーマンスが低下するリスクがあります。 コーディング 今回はnode.jsを使ってみます。 なぜPythonではないのでしょうか? Python の方が効率的であることはわかっていますが、私が使い慣れている Node.js を使用すると、クライアント側とサーバー側で簡単に使用できます。 ? なぜ tensorflow.js (またはその他の身近なライブラリ) を使用しないのでしょうか 当初はこのライブラリを使用する予定でしたが、このプロジェクトは主に教育目的であるため、最小限の実行可能なニューロン ネットワークを自分で作成し、さらなる改善の余地も残すことができる (たとえば、計算に wasm を使用するなど) と判断しました。 ニューラルネットワーク ほとんどすべてのニューラル ネットワークは一連の層であり、一部のデータが入力として受信され、一連のインデックスが乗算され、一部のデータが返されます。 わかりやすくするために、あなたが夢の新しい家を探していて、それが見つかったと想像してください。そして友人にこの家についてどう思うか尋ねると、たとえば次のように答えます。 。 あなたは友達それぞれの意見をある程度信頼しますが、気分を害さないように、特に信頼していない人でも、全員に尋ねる必要があります。そこで、友達とグループで好きな飲み物を飲みながら、さまざまな家を見て、みんながどれだけ気に入ったかを言います。 その結果、友達が各家についてどう思っているかがわかり、最終結果に基づいて決定します。 ニューラル ネットワークはまさにそのような「友達」で構成されていますが、友達のグループの数は非常に多くなる可能性があり、誰もが前のグループの意見に依存します。 ニューラル ネットワークの概略図: ニューラルネットワークの層: 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}`; } } エージェント間で試合をプレイします。 作業の結果を得るには、2 つのエージェントが等しい条件になるように比較する必要があります。それぞれが色ごとにプレイされ、最終的な結果が合計されます。 不要な情報でネットワークに過負荷がかからないように、各エージェントはホワイト チェッカーをプレイしているかのようにボードを表示します。 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)); } クロスオーバー: メカニズムは非常に単純です。エージェントから 2 つの遺伝子セット (重み) を取得し、確率に応じて、最初のエージェントまたは 2 番目のエージェントから遺伝子を取得します。これにより、遺伝子が混合され、最初と 2 番目のエージェントからの知識を使用して新しいネットワークが取得されます。エージェント。 これはまさに、現実の自然界ではすべてがどのように機能するかです。私たちはそれぞれ、両親から受け継いだ遺伝子を持っています。 export function crossover(first: Float32Array, second: Float32Array, prob = 0.25): Float32Array { return new Float32Array(first.map((w, i) => Math.random() 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); } } 結果 結果として、最新モデルを使用したところ、次の結果が得られました。 2 つのニューラル ネットワーク モデルを相互に比較すると、非論理的な動作を実行しますが、非常に良好な結果が得られます。 ニューラル ネットワークと検索深さ 1 ステップのアルファ ベータ検索の間で対戦する場合、ニューラル ネットワークが勝つ可能性はかなり高くなります。 検索深さ 2 ステップのニューラル ネットワークとアルファ ベータ検索の間のゲームでは、ニューラル ネットワークには勝ち目がなく、すべてのゲームに負けました。 意味がないのでまだ詳しく調べていません。おそらく、さらにゲームを重ねると、より許容できる結果が得られるようになるでしょう。あるいは、ニューラル ネットワークに同じネットワークではなく、アルファ ベータ検索エージェントを使ってプレイするように教えれば、 結論 遺伝的アルゴリズムをチェッカー ゲームに適用することは、生物学にインスピレーションを得た計算の変革の可能性を実証しています。 Minimax やその亜種のような従来のゲームプレイ アルゴリズムは効果的であることが証明されていますが、GA の進化的かつ適応的な性質は新たな視点を提供します。 生物学的進化と同様、この方法で開発された戦略がすぐに最適であるとは限りません。それでも、十分な時間と適切な条件があれば、彼らは手ごわい敵に進化し、自然からインスピレーションを得た計算の力を実証することができます。 あなたがチェッカーの愛好家でも、AI 研究者でも、あるいは古いものと新しいものの融合に興味を持っているだけの人でも、この古くからあるゲームと最先端のアルゴリズムの融合が人工知能のエキサイティングなフロンティアであることは否定できません。 。 いつものように、すべてのコードは で提供されています GitHub