유전 알고리즘으로 체커 게임하기: 전통 게임의 진화 학습

소개

드래프트라고도 알려진 체커는 오랫동안 인기를 끌었던 고대 게임입니다. 다른 고전 보드게임과 마찬가지로 이 게임도 실험을 위한 플랫폼으로 컴퓨터 과학자와 AI 연구자들의 관심을 끌었습니다. 체커 게임을 하도록 컴퓨터를 훈련시키는 데 사용하는 대표적인 방법은 진화를 주도하는 적자 생존 개념에 기초한 유전자 알고리즘입니다.

이 기사에서는 체커와 유전자 알고리즘의 교차점을 탐구하고, 체커 게임 에이전트를 능숙하게 개발하기 위해 진화적 컴퓨터 기술을 어떻게 사용할 수 있는지 보여줍니다.

지난 기사 에서 체커에 대한 주제를 충분히 다루었다고 생각합니다. 하지만 여전히 게임의 기본 규칙을 기억해 봅시다. 체커 게임은 10x10 보드에서 진행되며 각 플레이어는 20개의 말을 가지고 시작합니다.

목표는 간단합니다. 상대방의 말을 모두 포획하거나 가두어 움직이지 못하게 하는 것입니다. 기본 전략은 포지셔닝, 수비, 공격 및 상대방의 움직임 예측을 중심으로 이루어집니다.

유전 알고리즘(GA)

기본 사항

GA는 자연 선택 과정을 기반으로 한 최적화 알고리즘입니다. 이러한 알고리즘은 선택, 교차(재조합) 및 돌연변이로 구성되는 자연에서 관찰되는 진화 과정을 반영합니다.

신경망의 구성요소

이 기사에서는 완전 연결된 레이어가 있는 간단한 모델을 사용합니다. 레이어는 입력을 처리하고 출력을 생성하는 뉴런의 모음입니다. 그런 다음 이러한 출력은 마지막 레이어(출력 레이어)의 경우 최종 예측으로 사용되거나 네트워크의 다음 레이어에 입력으로 전달됩니다.

각 레이어에는 다음이 포함됩니다.

• inputs : 입력 매개변수의 수

• 출력 : 출력 매개변수의 수

• 가중치 : 가중치는 예측 오류를 최소화하기 위해 훈련 중에 네트워크가 조정하는 매개변수입니다.

• bias : 활성화 함수 이전의 입력 합계에 추가됩니다. 편향은 가중치와 함께 출력을 조정하는 데 도움이 됩니다.

• 활성화 함수 : 입력 레이어를 제외한 레이어의 각 뉴런은 출력을 다음 레이어로 전달하기 전에 입력에 활성화 함수를 적용합니다. 이는 네트워크가 데이터의 비선형 관계를 모델링하는 데 필수적입니다.

유전 알고리즘의 구성요소

• 인구 : 후보 솔루션 세트입니다.

• 적합성 기능 : 개별 솔루션의 성능 또는 "적합성"을 평가합니다.

• 선택 : 적합도에 따라 재생을 위해 일부 솔루션이 선택됩니다.

• 크로스오버(Crossover) : 선택된 두 솔루션의 일부를 결합하여 자손을 생성합니다.

• 돌연변이 : 자손에게 작은 무작위 변화를 도입합니다.

체커에 유전 알고리즘 적용

문제 인코딩 및 적합성 평가

먼저, 유전자 알고리즘과 함께 작동하는 방식으로 체커 전략과 같은 잠재적인 솔루션을 표현하는 방법을 찾아야 합니다. 우리의 경우 현재 플레이어에 대해 가능한 모든 동작을 파악하고 각 동작에 대해 GA를 누른 다음 가중치가 가장 큰 동작을 선택합니다.

또한 모집단에서 가장 좋은 아이템을 선택하기 위해서는 게임 점수를 계산해야 합니다. 우리의 경우에는 다음과 같습니다:

• 승리 시 250점
• 일반 체커 1개당 3점
• 킹 체커의 경우 7
• - 각 이동마다 -1

각 인구에 대해 토너먼트(스위스 시스템 토너먼트의 단순화된 버전)를 만들 것입니다. 각 토너먼트가 끝나면 향후 선택을 위해 인구의 1/4을 선택합니다.

어떤 에이전트가 1개 이상의 토너먼트에서 상위 플레이어(다음 세대를 위해 선정됨)인 경우, 우리는 그를 상위 플레이어로 선택하고 모든 에포크가 끝난 후 상위 플레이어들 간에 토너먼트를 만들어 최고의 플레이어를 선택합니다. 저장됩니다.

체커의 선택, 교차 및 돌연변이

알고리즘의 핵심은 전략 집단을 발전시키는 데 있습니다.

• 선택 : 게임에서 더 좋은 성과를 내는 전략이 재생산 대상으로 선택될 가능성이 더 높습니다.

• 크로스오버 : 두 가지 "상위" 전략을 결합할 수 있으며, 하나의 시작 동작과 다른 게임의 최종 전술을 사용할 수 있습니다.

• 돌연변이 : 때때로 전략이 무작위로 변경되어 잠재적으로 새롭고 효과적인 전술이 발견될 수 있습니다.

과제와 한계

로컬 최적

알고리즘이 최상의 전략을 찾았다고 생각하지만 솔루션 공간의 작은 영역에서만 최적인 로컬 최적 상태에 걸릴 위험이 있습니다.

계산 강도

GA는 빠를 수 있지만 수천 또는 수백만 개의 게임을 시뮬레이션하려면 상당한 컴퓨팅 리소스가 필요합니다.

과적합

진화된 전략이 훈련 시나리오에 너무 맞춰져 보이지 않는 전략이나 전술에 비해 제대로 수행되지 않을 위험이 있습니다.

코딩

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 및 그 변형과 같은 전통적인 게임 플레이 알고리즘이 효과적인 것으로 입증되었지만 GA의 진화적이고 적응적인 특성은 새로운 관점을 제공합니다.

생물학적 진화와 마찬가지로 이 방법을 통해 개발된 전략이 항상 가장 적합한 것은 아닐 수도 있습니다. 그럼에도 불구하고 충분한 시간과 적절한 조건이 주어지면 그들은 자연에서 영감을 받은 계산의 힘을 보여주는 강력한 적으로 진화할 수 있습니다.

당신이 체커 매니아이든, AI 연구자이든, 아니면 단지 신구의 융합에 매료된 사람이든, 이 오래된 게임과 최첨단 알고리즘의 결합이 인공 지능의 흥미로운 개척지라는 점은 부인할 수 없습니다. .

평소와 같이 GitHub 에서 제공되는 모든 코드