taralino

Exkurs Quellcode

Ohne im Detail darauf einzugehen und nur für Interessierte:

Nachfolgenden findest du einen Quellcode, der verwendet werden kann, um ein neuronales Netz zu trainieren (wie im Abschnitt zuvor beschrieben).

Du kannst dort das Layout des Netzes anpassen oder aber die Parameter des genetischen Algorithmus verändern. Aber beachte:

Du wirst eine durchaus größere Anzahl an Iterationen bzw. Generationen benötigen, um halbwegs gute Ergebnisse zu erhalten. Dies wird durchaus einige Zeit in Anspruch nehmen.

Zudem sei auf folgendes Problem hingewiesen, das du vielleicht im Abschnitt zuvor bereits beobachtest hast:

Es kann passieren, dass eine Schlange eine Rundtour macht, ohne den Apfel zu futtern. In diesem Falle ist das Spiel nicht endlich und wird nach einer gewissen Anzahl an Simulationsschritten abgebrochen.

Geeigneter wäre die Strategie, dass ein Apfel, der länger nicht gefuttert wird, seine Position ändert. Dies wurde einfachheitshalber aber nicht implementiert.

Quellcode

Trainingsphase unter Verwendung eines genetischen Algorithmus.

<!DOCTYPE html>
<html>
<head>
  <meta charset="utf-8">
  <meta name="viewport" content="width=device-width, initial-scale=1.0">
  <script src="taralino.js"></script>
</head>
<body>
<script>

/***********************
  NeuralNetwork
***********************/

var sensor = [];

var layout = [12,8,4];


function layout_size() {
  var q = 0;
  for (var k = 1; k < layout.length; k++) q = q + (layout[k-1]+1) * layout[k];
  return q;
};

function update_sensor() {
  sensor = [];
  var h = [];

  h = [-1,-1,-1];
  for (var i = y+1; i < n; i++) {
    if ((h[0] == -1) && (T[i][x] == -1)) h[0] = (i-y); // Abstand Norden Wand
    if ((h[1] == -1) && (T[i][x] == -2)) h[1] = (i-y); // Abstand Norden Apfel
    if ((h[2] == -1) && (T[i][x] >=  2)) h[2] = (i-y); // Abstand Norden Schlange
  };
  for (var k = 0; k < 3; k++) sensor.push(h[k] == -1 ? h[k] = 1 : h[k] /= n);

  h = [-1,-1,-1];
  for (var i = y-1; i >= 0; i--) {
    if ((h[0] == -1) && (T[i][x] == -1)) h[0] = (y-i); // Abstand Sueden Wand
    if ((h[1] == -1) && (T[i][x] == -2)) h[1] = (y-i); // Abstand Sueden Apfel
    if ((h[2] == -1) && (T[i][x] >=  2)) h[2] = (y-i); // Abstand Sueden Schlange
  };
  for (var k = 0; k < 3; k++) sensor.push(h[k] == -1 ? h[k] = 1 : h[k] /= n);

  h = [-1,-1,-1];
  for (var i = x+1; i < n; i++) {
    if ((h[0] == -1) && (T[y][i] == -1)) h[0] = (i-x); // Abstand Osten Wand
    if ((h[1] == -1) && (T[y][i] == -2)) h[1] = (i-x); // Abstand Osten Apfel
    if ((h[2] == -1) && (T[y][i] >=  2)) h[2] = (i-x); // Abstand Osten Schlange
  };
  for (var k = 0; k < 3; k++) sensor.push(h[k] == -1 ? h[k] = 1 : h[k] /= n);

  h = [-1,-1,-1];
  for (var i = x-1; i >= 0; i--) {
    if ((h[0] == -1) && (T[y][i] == -1)) h[0] = (x-i); // Abstand Westen Wand
    if ((h[1] == -1) && (T[y][i] == -2)) h[1] = (x-i); // Abstand Westen Apfel
    if ((h[2] == -1) && (T[y][i] >=  2)) h[2] = (x-i); // Abstand Westen Schlange
  };
  for (var k = 0; k < 3; k++) sensor.push(h[k] == -1 ? h[k] = 1 : h[k] /= n);
};



/***********************
  Snake Game
***********************/

var n = 16;
var T = matrix(n, n);
var x = 0;
var y = 0;
var size = 0;
var view = "";
var gameover = 0;

function neuer_apfel() {
  do {
    var i = Math.floor(random(0,n));
    var j = Math.floor(random(0,n));
    if (T[i][j] == 0) T[i][j] = -2;
  } while (T[i][j] != -2);
};

function spielfeld_start() {
  x = Math.round(n/2);
  y = Math.round(n/2);
  size = 3;
  view = "";
  gameover = 0;
  for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) T[i][j] = 0;
  for (var i = 0; i < n; i++) {
    T[0][i] = -1;
    T[n-1][i] = -1;
    T[i][0] = -1;
    T[i][n-1] = -1;
  }
  T[y][x] = size;
  neuer_apfel();
};

function schlange_bewegen() {
  if (view == "O") x = x + 1;
  if (x == n) x = 0;
  if (view == "W") x = x - 1;
  if (x < 0) x = n-1;
  if (view == "N") y = y + 1;
  if (y == n) y = 0;
  if (view == "S") y = y - 1;
  if (y < 0) y = n-1;
};

function spielfeld_updaten() {
  for (var i = 0; i < n; i++) for (var j = 0; j < n; j++) {
    if (T[i][j] > 0) T[i][j]--;
  }
  if ((T[y][x] == -1) || (T[y][x] > 0)) {
    gameover = 1;
  }
  if (T[y][x] == -2) {
    size = size + 1;
    T[y][x] = size;
    neuer_apfel();
  } else {
    T[y][x] = size;
  }
};

function simulate_key() {
  update_sensor();
  var k = NeuralNetwork.evaluate(sensor, {output:"index"});
  if (k == 0) view = "N";
  if (k == 1) view = "O";
  if (k == 2) view = "S";
  if (k == 3) view = "W";
};

function snake_run() {
  var c = 0;
  spielfeld_start();
  while ((c < 2000) && (gameover == 0)) {
    simulate_key();
    schlange_bewegen();
    spielfeld_updaten();
    c++;
  };
  return size-3;
};





/***********************
  GeneticAlgorithm
***********************/

function zero_vector(n) {
  var x = new Array(n);
  for (var j = 0; j < n; j++) x[j] = 0;
  return x;
};

function zero_matrix(m, n) {
  var A = new Array(m);
  for (var i = 0; i < m; i++) A[i] = new Array(n);
  for (var i = 0; i < m; i++) for (var j = 0; j < n; j++) A[i][j] = 0;
  return A;
};

function flatten(T) {
  var w = T.weights;
  var b = T.biases;
  var u = [];
  for (var k = 0; k < w.length; k++) for (var i = 0; i < w[k].length; i++) for (var j = 0; j < w[k][i].length; j++) {
    u.push(w[k][i][j]);
  };
  for (var k = 0; k < b.length; k++) for (var i = 0; i < b[k].length; i++) {
    u.push(b[k][i]);
  };
  return u;
};

function unflatten(u, L) {
  var w = [];
  var q = 0;
  for (var k = 0; k < L.length-1; k++) {
    w.push(zero_matrix(L[k+1], L[k]));
    for (var i = 0; i < w[k].length; i++) for (var j = 0; j < w[k][i].length; j++) {
      w[k][i][j] = u[q];
      q++;
    };
  };
  var b = [];
  for (var k = 0; k < L.length-1; k++) {
    b.push(zero_vector(L[k+1]));
    for (var i = 0; i < b[k].length; i++) {
      b[k][i] = u[q];
      q++;
    };
  };
  return {layout:L, weights:w, biases:b};
};

function f(x) {
  var b = unflatten(x, layout);
  NeuralNetwork.set_data(b);
  var h = snake_run();
  return -h;
};


var q = layout_size(); // Anzahl der Gewichte und Schwellwerte

var s = GeneticAlgorithm.vector(f, q, {iterations:10, population:100, children:40});


Console.print("Bestes Individuum:");
Console.print(s);
Console.print("Fitness:");
Console.print(f(s));


</script>
</body>
</html>

Vorschau Download Kopie speichern