Einführung von Battlescripts: Bots, Schiffe, Chaos!

Beim Programmieren muss es nicht nur darum gehen, Anwendungen zu erstellen, Ziele zu erreichen und Projektspezifikationen zu erfüllen. Es kann auch darum gehen, Spaß zu haben, den Prozess zu genießen, etwas zu erschaffen. Viele Menschen behandeln das Programmieren und Entwickeln dieser Fähigkeit als eine Form der Erholung. Bei Toptal wollten wir etwas Interessantes in unserer Community ausprobieren. Wir haben uns entschieden, eine Bot-gegen-Bot-Spieleplattform rund um Battleship zu bauen, die jetzt Open Source ist.

Seit ihrem ersten internen Start hat die Plattform die Aufmerksamkeit einiger erstaunlicher Bot-Hersteller in unserer Community auf sich gezogen. Wir waren wirklich beeindruckt zu sehen, dass eines der Community-Mitglieder, Toptal-Ingenieur Quan Le, sogar ein Tool zum einfachen Debuggen von Battlescripts-Bots entwickelt hat. Die Ankündigung weckte bei einigen auch das Interesse, ihre eigenen Bot-gegen-Bot-Engines zu entwickeln, die verschiedene Spieltypen und verschiedene Regeln unterstützen. Von dem Moment an, als Battlescripts enthüllt wurde, strömten erstaunliche Ideen herein. Heute freuen wir uns, Battlescripts Open Source zu machen. Dies gibt unserer Community und allen anderen die Möglichkeit, den Code zu erkunden, Beiträge zu leisten und/oder ihn zu forken, um etwas ganz anderes daraus zu machen.

Anatomie von Battlescripts

Battlescripts besteht aus einigen sehr einfachen Komponenten. Es läuft auf Node.js und verwendet einige der beliebtesten und am besten implementierten Pakete wie Express, Mongoose usw. Das Back-End ist in reinem JavaScript, ebenso wie die Front-End-Skripte. Die einzigen zwei externen Abhängigkeiten dieser Anwendung sind MongoDB und Redis. Vom Benutzer übermittelter Code für Bots wird mit dem „vm“-Modul ausgeführt, das mit Node.js geliefert wird. In der Produktion wird Docker für zusätzliche Sicherheit verwendet, ist aber keine harte Abhängigkeit von Battlescripts.

Der Code für Battlescripts ist auf GitHub unter der BSD 3-Klausel-Lizenz verfügbar. Die enthaltene README.md-Datei enthält detaillierte Anweisungen zum Klonen des Repositorys und zum lokalen Starten der Anwendung.

Webserver

Sie werden feststellen, dass die Anwendung eine ähnliche Struktur wie einfache Express.js-Webanwendungen hat. Die Datei app.js bootet den Server, indem sie eine Verbindung zur Datenbank herstellt, einige gängige Middlewares registriert und einige soziale Authentifizierungsstrategien definiert. Darüber hinaus sind alle Modelle und Routen im Verzeichnis „lib/“ definiert. Die vollständige Anwendung erfordert nur wenige Modelle: Battle, Bot, Challenge, Contest, Party und User. Kämpfe zwischen Bots werden außerhalb der Webserverknoten simuliert und mit dem Node.js-Paket Kue durchgeführt. Dadurch können wir die Engine vom Rest der Webanwendung isolieren, wodurch es weniger wahrscheinlich wird, dass die Kampfsimulations-Engine die Webserver stört, wodurch die Webanwendung selbst reaktionsschneller und stabiler bleibt.

Bots & Engine

Da erwartet wird, dass die Bots in JavaScript implementiert werden, und genau das haben wir in unserem Backend mit Node.js, war es einfacher, die Engine zu bauen. Wenn es um die Ausführung von vom Benutzer übermitteltem Code geht, besteht eine der größten Herausforderungen darin, sicherzustellen, dass der Code nichts Bösartiges auf dem Server tut oder dass fehlerhafter Code die Stabilität des Gesamtsystems nicht beeinträchtigt. Die Standardbibliothek von Node.js enthält dieses erstaunliche Modul, das einen Teil dieser Aufgabe sehr einfach macht. Das „vm“-Modul wurde eingeführt, um es Node.js-Entwicklern zu erleichtern, nicht vertrauenswürdigen Code in einem separaten Kontext auszuführen. Obwohl es laut offizieller Dokumentation wichtig ist, nicht vertrauenswürdigen Code in einem separaten Prozess auszuführen – aber das ist etwas, was wir auf den Produktionsservern tun. Während der lokalen Entwicklung funktionieren das „vm“-Modul und die Funktionen, die es bietet, einwandfrei.

Ausführen von JavaScript

Wenn Sie beliebigen JavaScript-Code in Node.js in einem separaten Kontext ausführen möchten, können Sie das „vm“-Modul wie folgt verwenden:

 var vm = require('vm') var ctxObj = { result: '' } vm.runInNewContext(' result = “0xBEEF” ', ctxObj ) console.log(ctxObj); // { result: “0xBEEF” }

Innerhalb dieses „neuen Kontexts“ erhält der Code, den Sie ausführen, nicht einmal Zugriff auf „console.log“, da in diesem Kontext eine solche Funktion nicht existiert. Sie könnten jedoch die „context.log“-Funktion des ursprünglichen Kontexts im neuen Kontext verfügbar machen, indem Sie sie als Attribut von „ctxObj“ übergeben.

In Battlescripts führen Knoten, die Schlachten simulieren, jeden Bot unter separaten Node.js-„vm“-Kontexten aus. Die Engine übernimmt die Verantwortung, den Zustand der Kontexte für beide Bots gemäß den Spielregeln zu synchronisieren.

Das Ausführen von JavaScript-Code in isoliertem Kontext ist nicht alles, was dieses Modul tut. Die Funktion „runInNewContext“ akzeptiert ein Objekt als dritten Parameter, der drei zusätzliche Aspekte dieser Codeausführung steuern kann:

• Dateiname, der in generierten Stack-Traces verwendet werden soll, die für diese Ausführung relevant sind.
• Ob Fehler auf stderr gedruckt werden sollen oder nicht.
• Anzahl der Millisekunden, die die Ausführung fortgesetzt werden kann, bevor es zu einer Zeitüberschreitung kommt.

Einer der Fallstricke dieses „vm“-Moduls ist, dass es keine Möglichkeit bietet, die Speichernutzung zu begrenzen. Dies wird zusammen mit einigen anderen Einschränkungen des Moduls auf dem Server durch die Verwendung von Docker und die Art und Weise, wie die Engine-Knoten ausgeführt werden, umgangen. Wenn das „vm“-Modul sehr häufig verwendet wird, beginnt es langsam, Speicher zu verlieren, der schwer aufzuspüren und freizugeben ist. Selbst wenn die Kontextobjekte wiederverwendet werden, wächst der Speicherverbrauch weiter. Wir haben dieses Problem gelöst, indem wir einer einfachen Strategie gefolgt sind. Jedes Mal, wenn ein Kampf in einem Arbeiterknoten simuliert wird, wird der Knoten beendet. Das Supervisor-Programm auf dem Produktionsserver startet dann den Worker-Knoten neu, der dann in Sekundenbruchteilen für die nächste Kampfsimulation bereit ist.

Erweiterbarkeit

Battlescripts wurde ursprünglich um die Standardregeln von Battleship herum entworfen. Der Motor darin war nicht sehr erweiterbar. Nach dem Start von Battlescripts war jedoch eine der häufigsten Anfragen, neuere Spieltypen einzuführen, da Benutzer der Anwendung schnell erkannten, dass einige Spiele mit Bots einfacher zu erobern sind als andere. Wenn Sie beispielsweise TicTacToe mit Schach vergleichen, hat ersteres einen viel kleineren Zustandsraum, was es Bots sehr einfach macht, eine Lösung zu finden, die ein Spiel entweder gewinnt oder unentschieden beendet.

Die Battlescripts-Engine wurde kürzlich ein wenig modifiziert, um die Einführung neuerer Spieltypen zu erleichtern. Dies kann durch einfaches Befolgen eines Konstrukts mit einer Handvoll Hook-ähnlicher Funktionen erfolgen. Ein zusätzlicher Spieltyp, TicTacToe, wurde der Codebasis hinzugefügt, da er einfacher zu verfolgen ist. Alles, was für diesen Spieltyp relevant ist, ist in der Datei „lib/games/tictactoe.js“ zu finden.

In diesem Artikel werfen wir jedoch einen Blick auf die Implementierung des Battleship-Spieltyps. Die Erforschung des TicTacToe-Spielcodes kann als Übung für später aufgehoben werden.

Schlachtschiff

Bevor wir uns ansehen, wie das Spiel implementiert wird, werfen wir einen Blick darauf, wie ein Standard-Bot für Battlescript aussieht:

 function Bot() {} Bot.prototype.play = function(turn) { // ... }

Das ist so ziemlich alles. Jeder Bot ist als Konstruktorfunktion mit einer Methode „play“ definiert. Die Methode wird für jede Runde mit einem Argument aufgerufen. Für jedes Spiel ist das Argument ein Objekt mit einer Methode, die es dem Bot ermöglicht, seinen Zug für die Runde zu machen, und kann mit einigen zusätzlichen Attributen versehen sein, die den Spielstatus darstellen.

Wie bereits erwähnt, wurde der Motor kürzlich ein wenig modifiziert. Die gesamte Battleship-spezifische Logik wurde aus dem eigentlichen Engine-Code herausgezogen. Da die Engine immer noch die Schwerarbeit leistet, ist der Code, der das Battleship-Spiel definiert, sehr einfach und leichtgewichtig.

 function Battleships(bot1, bot2) { return new Engine(bot1, bot2, { hooks: { init: function() { // ... }, play: function() { // ... }, turn: function() { // ... } } }) } module.exports = exports = Battleships

Beachten Sie, dass wir hier lediglich drei Hook-ähnliche Funktionen definieren: init, play und turn. Jede Funktion wird mit der Engine als Kontext aufgerufen. Die „init“-Funktion direkt beim Engine-Objekt wird innerhalb der Konstruktorfunktion instanziiert. In der Regel sollten Sie hier alle Zustandsattribute der Engine vorbereiten. Ein solches Attribut, das für jedes Spiel vorbereitet werden muss, sind „Raster“ und (optional) „Figuren“. Dies sollte immer ein Array mit zwei Elementen sein, eines für jeden Spieler, die den Zustand des Spielbretts darstellen.

 for(var i = 0; i < this.bots.length; ++i) { var grid = [] for(var y = 0; y < consts.gridSize.height; ++y) { var row = [] for(var x = 0; x < consts.gridSize.width; ++x) { row.push({ attacked: false }) } grid.push(row) } this.grids.push(grid) this.pieces.push([]) }

Der zweite Hook, „play“, wird kurz vor Beginn des Spiels aufgerufen. Dies ist nützlich, da wir so die Möglichkeit haben, Dinge wie das Platzieren von Spielsteinen im Namen der Bots auf dem Brett zu tun.

 for(var botNo = 0; botNo < this.bots.length; ++botNo) { for(var i = 0; i < consts.pieces.length; ++i) { var piece = consts.pieces[i] for(var j = 0; j < piece.many; ++j) { var pieceNo = this.pieces[botNo].length var squares = [] for(var y = 0; y < consts.gridSize.height; ++y) { for(var x = 0; x < consts.gridSize.width; ++x) { squares.push({ x: x, y: y, direction: 'h' }) squares.push({ x: x, y: y, direction: 'v' }) } } var square = _.sample(squares.filter(function(square) { var f = { 'h': [1, 0], 'v': [0, 1] } for(var xn = square.x, yn = square.y, i = 0; i < piece.size; xn += f[square.direction][0], yn += f[square.direction][1], ++i) { var d = [[0, -1], [0, 1], [-1, 0], [1, 0], [-1, -1], [-1, 1], [1, -1], [1, 1]] for(var j = 0; j < d.length; ++j) { var xp = xn+d[j][0] var yp = yn+d[j][1] if(xp >= 0 && xp < 10 && yp >= 0 && yp < 10 && this.grids[botNo][yp][xp].pieceNo >= 0) { return false } } if(xn >= consts.gridSize.width || yn >= consts.gridSize.height || this.grids[botNo][yn][xn].pieceNo >= 0) { return false } } return true; }.bind(this))) switch(true) { case square.direction === 'h': for(var k = square.x; k < square.x+piece.size; ++k) { this.grids[botNo][square.y][k].pieceNo = pieceNo } break case square.direction === 'v': for(var k = square.y; k < square.y+piece.size; ++k) { this.grids[botNo][k][square.x].pieceNo = pieceNo } break } this.pieces[botNo].push({ kind: piece.kind, size: piece.size, x: square.x, y: square.y, direction: square.direction, hits: 0, dead: false }) } } }

Das mag auf den ersten Blick etwas überwältigend erscheinen, aber das Ziel, das dieses Stück Code erreicht, ist einfach. Es generiert Arrays von Stücken, eines für jeden Bot, und platziert sie einheitlich auf den entsprechenden Gittern. Für jedes Stück wird das Gitter gescannt und jede gültige Position in einem temporären Array gespeichert. Eine gültige Position ist dort, wo sich zwei Teile nicht überlappen oder benachbarte Zellen teilen.

Zum Schluss „drehen“ sich der dritte und der letzte Haken. Im Gegensatz zu den anderen beiden Haken ist dieser etwas anders. Der Zweck dieses Hooks besteht darin, ein Objekt zurückzugeben, das die Engine als erstes Argument beim Aufrufen der Play-Methode des Bots verwendet.

 return { attack: _.once(function(x, y) { this.turn.called = true var botNo = this.turn.botNo var otherNo = (botNo+1)%2 var baam = false var square = this.grids[otherNo][y][x] square.attacked = true if(square.pieceNo >= 0) { baam = true this.turn.nextNo = botNo var pieceNo = square.pieceNo var pieces = this.pieces[otherNo] var piece = pieces[pieceNo] piece.hits += 1 if(piece.hits === piece.size) { piece.dead = true baam = { no: pieceNo, kind: piece.kind, size: piece.size, x: piece.x, y: piece.y, direction: piece.direction } } var undead = false for(var i = 0; i < pieces.length; ++i) { if(!pieces[i].dead) { undead = true } } if(!undead) { this.end(botNo) } } this.track(botNo, true, { x: x, y: y, baam: !!baam }) return baam }.bind(this)) }

Bei dieser Methode beginnen wir damit, die Engine darüber zu informieren, dass der Bot erfolgreich eine Bewegung ausgeführt hat. Ein Bot, der in keiner Runde einen Angriffszug für ein Spiel ausführt, verliert automatisch das Spiel. Falls die Bewegung das Schiff erfolgreich getroffen hat, bestimmen wir als Nächstes, ob das Schiff vollständig zerstört wurde. Falls ja, geben wir Details des zerstörten Schiffes zurück, andernfalls geben wir „true“ zurück, um einen erfolgreichen Treffer ohne zusätzliche Informationen anzuzeigen.

In diesen Codes sind wir auf einige Attribute und Methodennamen gestoßen, die unter „this“ verfügbar sind. Diese werden vom Engine-Objekt bereitgestellt und haben jeweils einige einfache Verhaltensmerkmale:

• this.turn.called: Dies beginnt vor jeder Runde als „false“ und muss auf „true“ gesetzt werden, um die Engine darüber zu informieren, dass der Bot für die Runde gehandelt hat.

• this.turn.botNo: Dies ist entweder 0 oder 1, je nachdem, welcher Bot diesen Zug gespielt hat.

• this.end(botNo): Der Aufruf mit einer Bot-Nummer beendet das Spiel und markiert den Bot als siegreich. Wenn Sie es mit -1 nennen, endet das Spiel unentschieden.

• this.track(botNo, isOkay, data, failReason): Dies ist eine praktische Methode, mit der Sie die Zugdetails für den Bot oder den Grund für einen fehlgeschlagenen Zug aufzeichnen können. Schließlich werden diese aufgezeichneten Daten verwendet, um die Simulation auf dem Frontend zu visualisieren.

Im Wesentlichen ist dies alles, was am Backend getan werden muss, um ein Spiel auf dieser Plattform zu implementieren.

Spiele wiederholen

Sobald eine Kampfsimulation endet, leitet sich das Frontend auf die Spielwiederholungsseite um. Hier werden die Simulation und Ergebnisse visualisiert und andere spielbezogene Daten angezeigt.

Diese Ansicht wird vom Back-End unter Verwendung von „battle-view-battleships.jade“ in „views/“ mit allen Gefechtsdetails im Kontext gerendert. Die Wiederholungsanimation des Spiels erfolgt über Front-End-JavaScript. Alle durch die „trace()“-Methode der Engine aufgezeichneten Daten sind im Kontext dieser Vorlage verfügbar.

 function play() { $('.btn-play').hide() $('.btn-stop').show() if(i === moves.length) { i = 0 stop() $('.ul-moves h4').fadeIn() return } if(i === 0) { $('.ul-moves h4').hide() $('table td').removeClass('warning danger') $('.count span').text(0) } $('.ul-moves li').slice(0, $('.ul-moves li').length-i).hide() $('.ul-moves li').slice($('.ul-moves li').length-i-1).show() var move = moves[i] var $td = $('table').eq((move.botNo+1)%2).find('tr').eq(move.data.y+1).find('td').eq(move.data.x+1) if(parseInt($td.text()) >= 0) { $td.addClass('danger') } else { $td.addClass('warning') } ++i $('.count span').eq(move.botNo).text(parseInt($('.count span').eq(move.botNo).text())+1) var delay = 0 switch(true) { case $('.btn-fast').hasClass('active'): delay = 10 break case $('.btn-slow').hasClass('active'): delay = 100 break case $('.btn-slower').hasClass('active'): delay = 500 break case $('.btn-step').hasClass('active'): stop() return } playTimer = setTimeout(function() { play() }, delay) } function stop() { $('.btn-stop').hide() $('.btn-play').text(i === 0 ? 'Re-play' : ($('.btn-step').hasClass('active') ? 'Next' : 'Resume')).show() clearTimeout(playTimer) } $('.btn-play').click(function() { play() }) $('.btn-stop').click(function() { stop() })

Was als nächstes?

Jetzt, da Battlescripts Open Source ist, sind Beiträge willkommen. Die Plattform ist in ihrer aktuellen Phase ausgereift, bietet jedoch viel Raum für Verbesserungen. Sei es eine neue Funktion, ein Sicherheitspatch oder sogar Fehlerbehebungen, erstellen Sie einfach ein Problem im Repository und fordern Sie dessen Behebung an, oder forken Sie das Repository und senden Sie eine Pull-Anfrage. Und wenn Sie dies dazu inspiriert, etwas völlig Neues zu bauen, lassen Sie es uns unbedingt wissen und hinterlassen Sie einen Link dazu im Kommentarbereich unten!