in ,

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

Шашки, также известные как шашечные, – старая и хорошо знакомая игра. Как и другие классические настольные игры, она заинтересовала компьютерщиков и исследователей ИИ

Как и другие классические настольные игры, она заинтересовала компьютерщиков и исследователей искусственного интеллекта и стала платформой для их экспериментов.
Известный метод обучения компьютеров игре в шашки – генетические алгоритмы, основанные на концепции выживания сильнейших, способствующей эволюции.
В этой статье мы исследуем связь между шашками и генетическими алгоритмами и покажем, как методы эволюционных вычислений могут быть использованы для проектирования опытных агентов, играющих в шашки.
Надеюсь, я достаточно упомянул о шашках в предыдущей статье, но все же давайте вспомним основные правила игры: игра в шашки ведется на доске 10×10, и каждый игрок начинает с 20 фигурами.
Цель игры проста: захватить все фигуры противника или заманить их в ловушку, чтобы они не могли двигаться. Базовая стратегия включает в себя позиционирование, защиту, атаку и предвидение ходов соперника.

Генетические алгоритмы (GAs)

Основы

GAs – это алгоритмы оптимизации, основанные на процессе естественного отбора. Эти алгоритмы отражают эволюционные процедуры, наблюдаемые в природе, такие как отбор, кроссинговер (рекомбинация) и мутация.

Компоненты нейронной сети

В данной работе используется простая модель с полностью связанными слоями. Слой – это набор нейронов, которые обрабатывают входные данные и выдают выходные.

Эти выходные данные либо используются в качестве окончательного прогноза в случае последнего слоя (выходного слоя), либо передаются в качестве входных данных в следующий слой сети.

Каждый слой содержит:

  • входные данные: количество входных параметров
  • результаты: количество выходных параметров
  • веса: Веса – это параметры, которые сеть настраивает во время обучения, чтобы минимизировать ошибку прогнозирования.
  • Смещение: добавляется к входной сумме перед активацией функции. Смещение помогает скорректировать выходные данные вместе с весами.
  • функция активации: Каждый нейрон в слое, за исключением входного слоя, применяет функцию активации к своим входным данным, прежде чем передать выходные данные следующему слою. Это важно для сети для моделирования нелинейных взаимосвязей в данных.

Компоненты генетического алгоритма

  • Популяция: набор возможных решений.
  • Функция пригодности: она оценивает производительность или “пригодность” отдельного решения.
  • Выбор: В зависимости от пригодности некоторые решения отбираются для воспроизведения.
  • Кроссовер: объединение частей двух выбранных решений для создания потомства.
  • Мутация: Внесение небольших случайных изменений в потомство.

Применение генетических алгоритмов к шашкам

Кодирование задачи и оценка пригодности

Во-первых, нам нужно найти способ представить потенциальные решения, например стратегии игры в шашки, таким образом, чтобы они работали с генетическими алгоритмами. В нашем случае мы берем все возможные ходы для текущего игрока, обсуждаем каждый из них и выбираем ход с наибольшим весом.

Кроме того, для выбора лучшего элемента в популяции необходимо рассчитать счет игры. В нашем случае это будет:

  • 250 очков за победу
  • 3 балла за каждую обычную шашку
  • 7 для King Checker
  • -1 за каждый ход

Для каждой популяции проводится турнир (упрощенная версия турнира по швейцарскому методу). После каждого турнира отбирается еще 1/4 популяции.

Если агент является лучшим игроком в одном или нескольких турнирах (для отбора в следующее поколение), он выбирается в качестве лучшего игрока, а после завершения всех эпох проводится турнир между лучшими игроками для выбора лучшего игрока.

Отбор, скрещивание и мутации в шашках

Суть алгоритма заключается в развитии совокупности стратегий.

  • Отбор: Стратегии, которые лучше работают в играх, имеют более высокие шансы быть выбранными для воспроизведения.
  • Кроссовер: две “родительские” стратегии могут быть объединены, возможно, взяв несколько начальных ходов от одной, а тактику завершения игры – от другой.
  • Мутация: Иногда стратегия может претерпевать случайные изменения, потенциально открывая новую эффективную тактику.

Проблемы и ограничения

Локальный оптимум

Даже если алгоритм считает, что нашел наилучшую стратегию, есть риск застрять в локальном оптимуме, если он оптимален только в небольшой области пространства решений.

Трудоемкость вычислений

В то время как GAs может быть быстрым, моделирование тысяч или миллионов игр требует значительных вычислительных ресурсов.

Переобучение

Существует риск того, что разработанная стратегия будет слишком адаптирована к сценариям обучения и плохо сработает против невидимых стратегий или тактик.

Кодирование

Я собираюсь использовать 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;
  }
}

Агент

An 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 и его разновидности, доказали свою эффективность, эволюционная и адаптивная природа ГА открывает новые перспективы.

Как и в случае с биологической эволюцией, стратегии, разработанные с помощью этого метода, не всегда оказываются наиболее подходящими. Тем не менее, при наличии достаточного времени и подходящих условий они могут стать грозными противниками, демонстрируя мощь вычислений, созданных природой.

Независимо от того, являетесь ли вы любителем шашек, исследователем искусственного интеллекта или просто тем, кто очарован слиянием старого и нового, нельзя отрицать, что слияние этой древней игры с передовыми алгоритмами – захватывающий рубеж в области искусственного интеллекта.

What do you think?

Добавить комментарий

Ваш адрес email не будет опубликован. Обязательные поля помечены *

GIPHY App Key not set. Please check settings