Tuesday, June 14, 2016

Introducing Battlescripts: Bots, Ships, Mayhem!

Programming doesn’t need to be all about building applications, meeting goals, and satisfying project specifications. It can also be about having fun, about enjoying the process of creating something. Many people do treat programming and development of this skill as a form of recreation. At Toptal, we wanted to try out something interesting within our community. We decided to build a bot-vs-bot game platform around Battleship, that is now open-source.
Introducing Battlescripts: Bots, Ships, Mayhem!
Since its initial launch internally, the platform has grabbed the attention of some amazing bot makers within our community. We were really impressed to see that one of the community members, Toptal engineer Quân Lê, even built a tool to debug Battlescripts Bots easily. The announcement also sparked an interest among a few to create their own bot-vs-bot engines, supporting different games types and different rules. Amazing ideas started to stream in from the moment Battlescripts was unveiled. Today, we are happy to make Battlescripts open-source. This gives our community and everyone else an opportunity to explore the code, make contributions, and/or fork it to make something else entirely of it.

Anatomy of Battlescripts

Battlescripts is built using some very simple components. It runs on Node.js and uses some of the most popular and well implemented packages, such as ExpressMongoose, etc. The back-end is in pure JavaScript, as well as the front-end scripts. The only two external dependencies of this application areMongoDB and Redis. User submitted code for bots are run using the “vm” module that comes with Node.js. In production, Docker is used for added safety, but is not a hard dependency of Battlescripts.
battlescripts
The code for Battlescripts is available on GitHub under the BSD 3-clause license. The included README.mdfile has detailed instructions on how to clone the repository and launch the application locally.

Web Server

You will notice that the application has a structure similar to that of simple Express.js web applications. The app.js file bootstraps the server by establishing a connection to the database, registering some common middlewares, and defining some social authentication strategies. Furthermore, all the models and routes are defined within the “lib/” directory. The entirely application requires only a few models: Battle, Bot, Challenge, Contest, Party, and User. Battles between bots are simulated outside of the web server nodes, and is done using Node.js package Kue. This enables us to isolate the engine from the rest of the web application, making it less likely for the battle simulation engine to interfere with the web servers, keeping the web application itself more responsive and stable.

Bots & Engine

Since the bots are expected to be implemented in JavaScript, and that is exactly what we have on our back-end with Node.js, it was easier to build the engine. When it comes to executing user submitted code, one of the biggest challenges is to make sure that the code doesn’t do something malicious on the server, or that any code that is buggy doesn’t interfere with the stability of the overall system. Node.js’s standard library comes with this amazing module that makes part of the this task a very easy. The “vm” module was introduced in order to make it easier for Node.js developers to run untrusted code in a separate context. Although according to the official documentation, it is important to run untrusted code in a separate process - but that is something we do on the production servers. During local development, the “vm” module and the features that it offers work alright.
Make bots fight each other, while it's still legal!

Executing JavaScript

If you want to run some arbitrary JavaScript code in Node.js under a separate context, you can use the “vm” module as follows:
var vm = require(‘vm’)

var ctxObj = {
    result: ‘’
}
vm.runInNewContext(‘ result = “0xBEEF” ’, ctxObj )
console.log(ctxObj); // { result: “0xBEEF” }
Within this “new context”, the code that you run do not even get access to “console.log”, because in that context such a function does not exist. You could, however, expose the “context.log” function of the original context into the new context by passing it as an attribute of “ctxObj”.
In Battlescripts, nodes that simulate battles run each bot under separate Node.js “vm” contexts. The engine takes on the responsibility of syncing the state of the contexts for both bots according to rules of the game.
Running JavaScript code in isolated context is not all that this module does. The “runInNewContext” function accepts an object as the third parameter which can control three additional aspects of this code execution:
  • Filename to be used in generated stack traces relevant to this execution.
  • Whether or not to print errors to stderr.
  • Number of milliseconds to allow the execution to continue before timing it out.
One of the pitfalls of this “vm” module is that it doesn’t provide any means of limiting memory usage. This, along with a few other limitations of the module is worked-around on the server through the use of Docker, and the way the engine nodes are run. The “vm” module, when used very frequently slowly starts to leak memory that is hard to track down and free. Even if the context objects are reused, the memory usage keeps growing. We solved this problem by following a simple strategy. Every time a battle is simulated in a worker node, the node exits. The supervisor program on the production server then restarts the worker node which then becomes ready to handle the next battle simulation in a fraction of a second.

Extensibility

Battlescripts was originally designed around the standard rules of Battleship. The engine within was not very extensible. However, after Battlescripts was launched, one of the most common requests was to introduce newer game types, as users of the application quickly realized that some games are easier to conquer with bots than others. For example, if you compare TicTacToe with Chess, the former has a much smaller state space, making it very easy for bots to come up with a solution that will either win or end a game in draw.
The Battlescripts engine has been recently modified a little to make it easier to introduce newer game types. This can be done by simply following a construct with a handful of hook-like functions. An additional game type, TicTacToe, was added to the codebase since it is easier to follow. Everything relevant to this game type can be found inside the “lib/games/tictactoe.js” file.
However, in this article, we will take a look at the implementation of Battleship game type. Exploration of TicTacToe game code can be left as an exercise for later.

Battleship

Before taking a look at how the game is implemented, let us take a peek at what a standard bot for Battlescript looks like:
function Bot() {}
Bot.prototype.play = function(turn) {
    // ...
}
That is pretty much it. Every bot is defined as a constructor function with one method “play”. The method is invoked for every turn with one argument. For any game, the argument is an object with one method that allows the bot to make its move for the turn, and can come with some additional attributes representing the game state.
As mentioned earlier, the engine has been modified a little recently. All Battleship specific logic has been pulled out of the actual engine code. As the engine still does the heavy lifting, the code that defines the Battleship game is very simple, and lightweight.
function Battleships(bot1, bot2) {
 return new Engine(bot1, bot2, {
  hooks: {
   init: function() {
    // ...
   },
   play: function() {
    // ...
   },
   turn: function() {
    // ...
   }
  }
 })
}

module.exports = exports = Battleships
Notice how we are merely defining three hook-like functions here: init, play, and turn. Each function is invoked with the engine as its context. The “init” function right as the engine object is instantiated, from within the constructor function. Typically this is where you should prepare all the state attributes of the engine. One such attribute that must be prepared for every game is “grids” and (optionally) “pieces”. This should always be an array with two elements, one for each player, representing the state of the game board.
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([])
}
The second hook, “play”, is invoked right before the game begins. This is useful, as this gives us the opportunity to do things like place game pieces on the board on behalf of the bots.
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
   })
  }
 }
}
This may look a bit overwhelming at first, but the goal that this piece of code achieves is simple. It generates arrays of pieces, one for each bot, and places them on the corresponding grids in a uniform fashion. For every piece, the grid is scanned and every valid position is stored in a temporary array. A valid position is where two pieces do not overlap or share adjacent cells.
Finally, the third and the last hook “turn”. Unlike the other two hooks, this one is a little different. The purpose of this hook is to return an object, which the engine uses as the first argument in invoking the bot’s play method.
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))
}
Within this method, we begin by informing the engine that the bot has successfully made a move. A bot that fails to make an attacking move for any game in any turn automatically forfeits the game. Next, in case the move has successfully hit the ship, we determine if the ship has been destroyed completely. In case it was, we return details of the ship that was destroyed, otherwise we return “true” to indicate a successful hit without any additional information.
Throughout these codes, we have encountered some attributes and method names that are available at “this”. These are provided by the Engine object and each have some simple behavioral characteristics:
  • this.turn.called: This begins as false before every turn, and must be set to true to inform the engine that the bot has acted for the turn.
  • this.turn.botNo: This will either be 0 or 1, depending on which bot has played this turn.
  • this.end(botNo): Calling this with a bot number ends the game, and marks the bot as victorious. Calling it with -1 ends the game in a draw.
  • this.track(botNo, isOkay, data, failReason): This is a convenience method that lets you record the move details for the bot, or reason for a failed move. Eventually, these recorded data are used to visualize the simulation on the front-end.
Essentially, this is all that needs to be done on the back-end to implement a game on this platform.

Replaying Games

As soon as a battle simulation ends, the front-end redirects itself to the game replay page. This is where the simulation and results are visualized, and other game related data is displayed.
This view is rendered by the back-end using the “battle-view-battleships.jade” in “views/” with all battle details in context. Re-play animation of the game is done through front-end JavaScript. All the data recorded through the “trace()” method of the engine is available in the context of this template.
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()
})

What Next?

Now that Battlescripts is open source, contributions are welcome. The platform at its current stage is mature, but has a lot of room for improvements. Be it a new feature, a security patch, or even bug fixes, feel free create an issue in the repository requesting it to be addressed, or fork the repository and submit a pull request. And if this inspires you to build something entirely new, be sure to let us know and leave a link to it in the comments section below!
This article was written by Mahmud Ridwan, a Toptal Python developer.

1 comment:

  1. Superb. I really enjoyed this article here.
    Really it is an amazing article I had ever read. I hope it will help a lot for all.
    Thank you so much for these amazing posts and please keep updating this excellent article.
    Thank you for sharing such a great blog with us. expecting for yours.

    ReplyDelete