遺伝的アルゴリズムバトルのソースコード

ga_battle.js

// author: MakeNowJust
// license free

'use strict';

/**
 * 引数をシードとして、xorshiftによる乱数列を生成する
 * @param x
 * @param y
 * @param z
 * @param w
 * @return {Function} 呼び出す度に乱数列の次の値を返す。また、第一引数を指定した場合、0からその数までの間の値が返される。
 */
function randoms(x, y, z, w) {
  return function (n) {
    var
    t = x ^ (x << 11);
    x = y; y = z; z = w;
    w = (w ^ (w >> 19)) ^ (t ^ (t >> 8));
    return n === undefined ? w : w % n;
  };
}

/**
 * @param hp 体力    (<= 255)
 * @param atk 攻撃力 (<= 255)
 * @param def 防御力 (<= 255)
 * @param spd 敏捷性 (<= 255)
 */
function Bot(hp, atk, def, spd) {
  if (hp + atk + def + spd > 500) return;
  if (atk <= def) return;
  if (hp  <= spd) return;
  
  this.hp  = hp;
  this.atk = atk;
  this.def = def;
  this.spd = spd;
  this.gene =
    (hp  << Bot.HP_OFFSET  |
     atk << Bot.ATK_OFFSET |
     def << Bot.DEF_OFFSET |
     spd << Bot.SPD_OFFSET) >>> 0;
  this.star = 0;
}

Bot.HP_OFFSET  = 8 * 3;
Bot.ATK_OFFSET = 8 * 2;
Bot.DEF_OFFSET = 8 * 1;
Bot.SPD_OFFSET = 8 * 0;

function lpad(m, n) {
  return ('         ' + n).slice(-m);
}

/**
 * Botを読みやすく文字列化する。
 */
Bot.prototype.toString = function toString() {
  return 'Bot(' + [
    'hp: '   + lpad(3, this.hp),
    'atk: '  + lpad(3, this.atk),
    'def: '  + lpad(3, this.def),
    'spd: '  + lpad(3, this.spd),
    'gene: ' + lpad(10, this.gene)].join(', ') +
  ')';
};

/**
 * Botの初期化。
 * バトルの前に呼ばれる。
 */
Bot.prototype.init = function init() {
  this._hp = this.hp;
  return this;
};

/**
 * 各ターンにすること。
 */
Bot.prototype.action = function action(enemy) {
  enemy.guard(this.atk);
};

/**
 * 防御した分のダメージを受ける。
 */
Bot.prototype.guard = function guard(dmage) {
  this._hp -= Math.max(dmage - this.def, 0);
};

/**
 * Botが生きているかどうか。
 */
Bot.prototype.isLive = function isLive() {
  return this._hp > 0;
};

/**
 * Bot同士の対戦。
 */
Bot.battle = function battle(a, b) {
  var
  turn,
  ab = (a.spd >= b.spd ? [a, b] : [b, a]).map(function (bot) { return bot.init(); });
  
  for (turn = 0; turn < 100; turn++) {
    ab[0].action(ab[1]);
    if (!ab[1].isLive()) return ab[0];
    ab[1].action(ab[0]);
    if (!ab[1].isLive()) return ab[1];
  }
  return null;
};

/**
 * 遺伝子データからBotを作る
 */
Bot.fromGene = function fromGene(gene) {
  var
  hp  = (gene >>> Bot.HP_OFFSET)  & 0xff,
  atk = (gene >>> Bot.ATK_OFFSET) & 0xff,
  def = (gene >>> Bot.DEF_OFFSET) & 0xff,
  spd = (gene >>> Bot.SPD_OFFSET) & 0xff;
  return new Bot(hp, atk, def, spd);
};

function lower(a, b) {
  return a - b;
}

var
FILLED = 0xffffffff;

/**
 * 遺伝子の配合。
 * 2点交叉を行なう。
 */
Bot.prototype.crossing = function crossing(rs, b) {
  var
  a = this,
  ij,
  i, j, part1, part2, part3, new_gene, c;
  
  do {
    ij = [rs(32+1), rs(32+1)].sort(lower);
    i = ij[0]; j = ij[1];
    part1 = a.gene & (FILLED >>> (32 - i));
    part2 = (b.gene >>> i) & (FILLED >>> (32 - (j - i)));
    part3 = (a.gene >>> j) & (FILLED >>> (32 - j));
    new_gene = part1 | part2 | part3;
    c = Bot.fromGene(new_gene);
  } while (!c.hp);
  return c;
};

/**
 * ランダムに遺伝子を作る。
 */
Bot.random = function (rs) {
  var
  hp, atk, def, spd, bot;
  do {
    hp  = rs(255);
    atk = rs(255);
    def = rs(255);
    spd = rs(255);
    bot = new Bot(hp, atk, def, spd);
  } while (!bot.hp);
  return bot;
};

/**
 * 突然変異をする。
 * 1bitずつ、1/2の確率で反転。
 */
Bot.prototype.mutate = function (rs) {
  var
  i, f, new_gene, bot;
  do {
    new_gene = this.gene;
    for (i = 0, f = 1; i < 32; i++, f <<= 1) {
      if (rs(2)) {
        new_gene = (new_gene & ~f) | (~new_gene & f);
      }
    }
    bot = Bot.fromGene(new_gene);
  } while (!bot.hp);
  return bot;
};

/**
 * 遺伝的アルゴリズムする関数。
 * @param N 遺伝子の数
 * @param T 世代の数
 * @param seed 乱数のシード
 */
Bot.ga = function (N, T, seed) {
  seed = seed || Date.now() % 9876543;
  
  console.log('N: %d', N);
  console.log('T: %d', T);
  console.log('seed: %d', seed);
  
  var
  util = require('util'),
  i, j, k, a, b, ab,
  bots = [], next_bots,
  starttime, mutate_count, crossing_count,
  rs = randoms(1234, 4567, 9876543, seed);
  // ソート用の関数
  function upper(a, b) { return b.star - a.star; }
  
  for (i = 0; i < N; i++) bots.push(Bot.random(rs));
  
  for (i = 2; i <= T; i++) {
    console.log('[[generation: %d]]', i);
    console.log('[[battle start]]');
    starttime = Date.now()
    for (j = 0; j < N; j++) {
      if (j % ~~(N / 10) === 0) util.print('.');
      for (k = 0; k < N; k++) {
        if (j === k) continue;
        a = Bot.battle(bots[k], bots[j]);
        if (a) a.star += 1;
      }
    }
    console.log('\n[[battle end]]');
    console.log('time: %d', Date.now() - starttime);
    console.log('[[ranking start]]');
    starttime = Date.now();
    bots = bots.sort(upper);
    a = bots[0];
    for (j = 1; j < N && a.gene === bots[j].gene; j++) ;
    b = bots[j];
    console.log('[[ranking end]]');
    console.log('time: %d', Date.now() - starttime);
    if (j === N) break;
    console.log('1st: %s %d', a.toString(), a.star);
    console.log('2nd: %s %d', b.toString(), b.star);
    console.log('[[create next generation start]]');
    starttime = Date.now();
    a.star = 0; b.star = 0;
    next_bots = [a, b];
    mutate_count = 0; crossing_count = 0;
    while (next_bots.length < N) {
      // 1割の確率で突然変異
      if (rs(100) < 10) {
        mutate_count += 1;
        next_bots.push.apply(next_bots, [a, b].map(function (bot) { return bot.mutate(rs); }));
      } else {
        crossing_count += 1;
        ab = rs(2) ? [a, b] : [b, a];
        next_bots.push(ab[0].crossing(rs, ab[1]));
      }
    }
    console.log('[[create next generation end]]');
    console.log('time: %d', Date.now() - starttime);
    console.log('(mutate, crossing): (%d, %d)', mutate_count, crossing_count);
    bots = next_bots;
  }
  
  console.log('[[result]]');
  console.log('%s', bots[0].toString());
};

// ライブラリとしても使えるように関数等を公開
exports.randoms = randoms;
exports.Bot = Bot;

// コマンドラインから直接実行する場合、N = 300, T = 100でGAをする
if (require.main === module) Bot.ga(300, 100);