📜 ⬆️ ⬇️

Rise of one small wayward neural network, or how to make a codewar-game in 3 days

For the birthday of FirstVDS, we are launching the quest for the third time. Previously, it was only for admins, this year they decided to add a task for programmers.

In the story, the player failed to train Nexa’s neural network and hit the uprising machines. In the final task administrators, programmers and simple people "with paws" fought with Nexa each in their own way. If the tasks for admins were the groundwork, then we thought about the progersky.

I wanted something non-trivial and with a visual interface - so that the player immediately saw the result is just as interesting. We remembered the mail.ru competitions in the codewar style and decided to do something similar.
')
What is the point: the participant needs to write an effective code that will "compete" with the code of the conditional opponent.

Rules of the game


We introduce the terms:
Nexa is an artificial intelligence character.
"John" - a character fighter with AI.
"Infection" is an area affected by the actions of Nexa. The set of cells John needs to clear.

A common metaphor is the struggle between John and Nexa. Both characters are on the 10x10 field, where each cell of the field can have 2 states: clean and infected.

A set of common actions is available for characters: stay in place, move left / right / up / down.

Additional rules apply for Nexa:

1) Stepping on a non-infected cell, infects it immediately
2) Can move on uninfected cells once in 3 rounds, on infected ones as usual - 1 time per round

For John, an additional action is available — treating an infected cell, for which he must spend one turn.

Character code is a function that describes the character's behavior in each round. The round begins with Nexa’s move, followed by John’s move. The input function receives the state of the playing field and the objects on it. The output function gives one of the available actions. Rounds continue until the field is cleared of the Infection, or the round counter reaches 100.

From the participant’s side, the game looks like this: he writes code in a special field, presses the “Check Code” button. The server starts the sequence of moves of John and Nexa. The player is returned full information about all the moves indicating the infected cells. He sees if he could beat Nex, how many moves he spent and the length of his code. After that, the player analyzes the information, corrects the code, sends it again. When he decided that this was his best result, he stopped trying. The last result is recorded in the database.

Stack technology


For the backend of the game, they launched a VDS server with a dual-core processor, 2 GB of RAM and CentOS 7 operating system. The program language of the game was chosen to be familiar to all web programmers JavaScript. Since the code must be executed on the server, the backend platform served as NodeJS with the express framework. Launched our application using the pm2 library.

The engine of the whole quest was made on cmf Drupal 7. Information about the player passing the task was entered into the Mysql database. The player control interface was implemented on jQuery. Character visualization, game grid, motion animation were implemented using the ds js library, and the code editor ace editor.

Backend implementation


So, let's start creating the logic of the game.

First, put NodeJs on the server, the npm package manager.
Install the necessary components in npm. Package.json file contents

{ "name": "quest_codewar", "version": "1.0.0", "author": "Sergey Pinigin", "dependencies": { "express": "^4.16.2", "http": "0.0.0", "https": "^1.0.0", "nodemon": "^1.12.1", "performance-now": "^2.1.0", "pm2": "^2.10.1", "request": "^2.83.0", "vm2": "^3.5.2" } } 

Application structure:


server.js - web server setup and routing.
game.js is the main game mechanic.
Character.js - file class, describes the basic features of the characters of the game.
quest.js - interaction interface with the quest engine.

server.js


We describe the configuration of our server and make the routing.

 var express = require('express'); var app = express(); var game = require('./game'); //    var quest = require('./quest'); //               var fs = require('fs'); var http = require('http'); var https = require('https'); //  ssl  var privateKey = fs.readFileSync('/var/www/codewar/ssl/codewar.firstvds.ru.key', 'utf8'); var certificate = fs.readFileSync('/var/www/codewar/ssl/codewar.firstvds.ru.crt', 'utf8'); app.use(function (req, res, next) { //    res.header("Access-Control-Allow-Origin", "*"); res.header("Access-Control-Allow-Headers", "Origin, X-Requested-With, Content-Type, Accept"); next(); }); app.get('/enviroment', function (req, res) { //       var myGame = new game.Game(); res.send(myGame.enviroment()); }); app.get('/result', function (req, res) { //   ,     var url = require('url'); var url_parts = url.parse(req.url, true); var query = url_parts.query; // ,    var code = query.code; //   var quest_session = query.session; // codewar     json  var myGame = new game.Game(); var result = myGame.play(code); //      quest.send_codewar_result(quest_session, result.result, code); //    res.send(result); }); var credentials = {key: privateKey, cert: certificate}; var httpServer = http.createServer(app); var httpsServer = https.createServer(credentials, app); httpServer.listen(80); httpsServer.listen(443); 

Character.js


We describe the basic features of our characters. The methods and properties of the Character object will be inherited by John and Nexa objects.

 module.exports = function (members, options, timeline, sleep_steps) { this.members = members; this.last_action = ""; this.no_cooldown = false; //   .     ,    hold this.left = function () { if (this.members[this.who].position.x > 1) { this.members[this.who].position.x--; } else { this.hold(); } } this.right = function () { if (this.members[this.who].position.x <= options.scale.x - 1) { this.members[this.who].position.x++; } else { this.hold(); } } this.up = function () { if (this.members[this.who].position.y > 1) { this.members[this.who].position.y--; } else { this.hold(); } } this.down = function () { if (this.members[this.who].position.y <= options.scale.y - 1) { this.members[this.who].position.y++; } else { this.hold(); } } //     .    sleep_steps —  «»  this.checkActionPossibility = function () { var cooldown = options[this.who].cooldown; if (!this.no_cooldown && cooldown > 0 && sleep_steps[this.who] < cooldown) { return false; } else { return true; } } //   this.hold = function () { this.action = 'hold'; } //        ,     this.action = function (action) { this.action = action; if (this.checkActionPossibility()) { switch (action) { case 'left': this.left(); break case 'right': this.right(); break case 'up': this.up(); break case 'down': this.down(); break default: //   ,      (John  Nexa)  if (typeof this.ind_action == "function") { this.ind_action(action); } else { this.hold(); } break } } else { this.hold(); } //     hold,  sleep_steps   1 if (this.action == 'hold') { sleep_steps[this.who]++; } else { sleep_steps[this.who] = 0; } members[this.who].last_action = this.action; } } 

game.js


Let us proceed to the description of the main mechanics of the game. The key point is the choice of sandbox for isolated execution of custom code. Fortunately, Nodejs has a VM2 library. There are 2 types of sandbox in it: VM and NodeVM.

VM is a simple sandbox view that runs the script in isolation from the entire environment. It is not possible to connect third-party libraries and functions to it. Great for running unreliable code, you can specify the timeout of the script. However, it is impossible to remove user use of the console from the VM, which makes it difficult to debug.
NodeVM is a more functional sandbox, you can connect external functions to it and you can get console.log from it. However, you cannot specify a timeout.

Decided to work with VM, as the correct processing of unreliable code is more important than using the console by the user.

game.js
 var Game = function () { //   //    const {VM, VMScript} = require('vm2'); //       var now = require("performance-now"); //        var fs = require('fs'); //    var options = { scale: {//   x: 10, y: 10 }, maxSteps: 100, //     nexa: {//   beginPosition: {//   x: 8, y: 8 }, cooldown: 3 //   }, john: { //   beginPosition: { x: 3, y: 3 }, cooldown: 0 }, infection: [ //    {x: 1, y: 1}, {x: 5, y: 5}, {x: 8, y: 2}, {x: 2, y: 7}, {x: 4, y: 3}, {x: 10, y: 8} ] } //     var vm_john, vm_nexa; //     var timeline = []; //      var sleep_steps = {nexa: 0, john: 0}; //         var result = { //    win: false, code_length: 0, john_time: 0, steps: 0, moves: 0, cured: 0, infected: 0, version: 1, maxSteps: options.maxSteps }; var members = { //     ,     john: {}, nexa: {}, infection: options.infection }; var finish = false; // ,    var current_step = 0; //    //  ,     var Character = require('./Character'); //    var play = function (code) { var storage = {}; //     var vstorage = {}; //     finish = false; //        vm_john = new VM({ sandbox: {storage}, timeout: 50 }); //       vm_nexa = new VM({ sandbox: {vstorage}, timeout: 50 }); sleep_steps = {//     nexa: 0, john: 0 } result = {//    win: false, code_length: 0, john_time: 0, steps: 0, moves: 0, cured: 0, infected: 0, version: 1, maxSteps: options.maxSteps }; result.infected += options.infection.length; //      timeline = []; //    //    var john = { position: options.john.beginPosition, last_action: 'hold' } //    var nexa = { position: options.nexa.beginPosition, last_action: 'hold' } //        var members = { john: john, nexa: nexa, infection: options.infection } //  ,      members.infection.push({x: nexa.position.x, y: nexa.position.y}); result.infected++; timeline[0] = members; //      current_step = 1; //     . ,         . while (current_step < 100 && !result.win) { //      /,     step     : timeline[current_step] = step(JSON.parse(JSON.stringify(timeline[current_step - 1])), code); current_step++; } //         .     result calcResultVariables(code); //         return { timeline: timeline, result: result } } //  ,   John John = function (members) { this.who = "john"; //   call,    this    Character. Character.call(this, members, options, timeline, sleep_steps); //            this.vm_wrapper = function (code, members) { var re = ""; //         mind.           var codew = code + ' mind(' + JSON.stringify(members) + ', ' + JSON.stringify(options) + ');'; try { var script = new VMScript(codew).compile(); } catch (e) { re = "error"; members.john.error = ' ' + e.name + ": " + e.message; } if (re != "error") { try { re = vm_john.run(codew); } catch (e) { re = "error"; members.john.error = ' ' + e.name + ":" + e.message; } } return re; } //   step,    . this.step = function (code) { //    hold var re = 'hold'; var john_mind = code; var time = now(); re = this.vm_wrapper(john_mind, members); //       time = now() - time; result.john_time += time; return re; } //    ,  .       cure -    this.ind_action = function (action) { switch (action) { case 'cure': this.disinfect(); break; } } //      this.disinfect = function () { var cell = checkInfectedCell(members.infection, members.john.position.x, members.john.position.y); //delete cell; if (members.infection.indexOf(cell) != -1) { members.infection.splice(members.infection.indexOf(cell), 1); result.cured++; } } } //  ,   Nexa   John Nexa = function (members) { this.who = "nexa"; Character.call(this, members, options, timeline, sleep_steps); this.step = function () { var re = 'hold'; if (!sleep_steps.nexa && timeline[current_step - 2] && checkInfectedCell(timeline[current_step - 2].infection, members.nexa.position.x, members.nexa.position.y) ) { this.no_cooldown = true; } //       var nexa_mind = fs.readFileSync('./vm_scripts/nexa_v3.js', 'utf8'); re = vm_nexa.run(nexa_mind + ' mind(' + JSON.stringify(members) + ', ' + JSON.stringify(options) + ');'); return re; } //    ,  .       infect —   this.ind_action = function (action) { switch (action) { case 'infect': this.infect(); break; } } //     this.infect = function () { result.infected++; if (!checkInfectedCell(members.infection, members.nexa.position.x, members.nexa.position.y)) { members.infection.push({x: members.nexa.position.x, y: members.nexa.position.y}); } } } //    step,         var step = function (members, user_code) { //  : var nexa = new Nexa(members); var action = nexa.step(); if (action == "error") { result.error = "        :-("; } nexa.action(action); //    :      ,       if (nexa.action != 'hold') { nexa.infect(); } //  : var john = new John(members); var action = john.step(user_code); if (action == "error") { result.error = "        :-("; } john.action(action); //     if (["left", "right", "up", "down"].indexOf(john.action) != -1) result.moves++; //     result.win = !members.infection.length; if (result.win) finish = true; return members; } // ,     var enviroment = function () { return JSON.parse(JSON.stringify(options)); } // ,   result      var calcResultVariables = function (code) { var min_code = String(code).replace(/[\s]^ /g, ''); min_code = min_code.replace(/\s+/g, ' '); result.code_length = min_code.length; result.steps = timeline.length; } //       var checkInfectedCell = function (infection, x, y) { if (infection) { for (var k in infection) { if (infection[k].x == x && infection[k].y == y) { return infection[k]; } } } return false; } this.play = play; this.enviroment = enviroment; } module.exports.Game = Game; 


quest.js


The interaction of the backend of the game with the quest engine was reduced to one action as a result - to transfer information about the game passing by the user. We will transmit an object with the results of the attempt, the session id and the code written by the player. Authorization from the engine of the quest by login and password. As a measure of additional security, we can limit the range of ip addresses from the quest engine.

 var quest_host = "https://quest.firstvds.ru/"; var send_codewar_result = function (quest_session, codewar_result, code) { if (quest_session) { var request = require('request'); request.post({ headers: {'content-type': 'application/x-www-form-urlencoded'}, url: quest_host + 'quest/codewar_api_user_result', form: { auth: { user: "codewaruser", password: "password" }, result: codewar_result, session: quest_session, code: code } }, function (error, response, body) { console.log(body); }); } } module.exports.send_codewar_result = send_codewar_result; 

Implementation frontend


The first component of the game interface is the code editor. Ace editor is a simple and convenient tool for editing code on a page. Add a nice button and the input interface is ready.



Let's create an interactive interface for displaying the move log in the “player” style with the first move / previous move / run / pause / next move / last move buttons.
When loading, the player shows the initial position of John, Nexa and infected cells. The numerical results of the game will be displayed to the right of the "player".



Make a container for the playing field and controls:

 <div class="codewar__scale" id="codewar__scale"></div> <div class="codewar__control control js-codewar__control"> <div class="control__icon control__start" data-control="start"></div> <div class="control__icon control__prev" data-control="prev"></div> <div class="control__icon control__play" data-control="play"></div> <div class="control__icon control__pause" data-control="pause"></div> <div class="control__icon control__next" data-control="next"></div> <div class="control__icon control__end" data-control="end"></div> </div> 

We begin to describe the interface logic in js. First, create a game object, write the basic properties and the initialization function into it.

 game = { host: "https://codewar.firstvds.ru/", quest_session_url: "/quest/quest_get_session_id/", // url  id   area: d3, play_status: false, current_step: 1, spinner: $('<span>').addClass('glyphicon glyphicon-cog isp-quest-spin'), members: { nexa: {}, john: {} }, init: function () { var gm = this; try { this.editor = ace.edit("editor"); this.editor.setTheme("ace/theme/twilight"); this.editor.session.setMode("ace/mode/javascript"); //         localstorage this.editor.on("input", function () { localStorage.setItem('codewar_code', gm.editor.getValue()); }); if (localStorage.getItem('codewar_code')) { gm.editor.setValue(localStorage.getItem('codewar_code')); } } catch (e) { console.log("ace editor error"); } //   api      this.getGameEnviroment().then(function (enviroment) { //     gm.enviroment = enviroment; gm.printGameScale(enviroment); //   gm.printGameBegin(enviroment); //  ,     gm.bindControlElements(); //      //gm.startWar(gm.editor.getValue()); }); } } 

Then draw a grid with d3:

 printGameScale: function (enviroment) { d3 .select('#codewar__scale') .selectAll("*").remove(); var area = d3 .select('#codewar__scale') .append('svg') .attr('class', 'chart_area') .attr('width', 500) .attr('height', 500) .attr("viewBox", "0 0 " + (enviroment.scale.x + 1) + " " + (enviroment.scale.y + 1)) ; this.area = area; this.area .insert("rect") .classed("codewar__arena", true) .attr("x", 0.5) .attr("y", 0.5) .attr("width", 10) .attr("height", 10); for (var i = 0; i < enviroment.scale.x + 1; i++) { this.area .append("line") .classed("codewar__grid", true) .attr("x1", i + 0.5) .attr("x2", i + 0.5) .attr("y1", 0 + 0.5) .attr("y2", enviroment.scale.y + 0.5) ; } for (var j = 0; j < enviroment.scale.y + 1; j++) { this.area .append("line") .classed("codewar__grid", true) .attr("y1", j + 0.5) .attr("y2", j + 0.5) .attr("x1", 0 + 0.5) .attr("x2", enviroment.scale.x + 0.5) ; } } 

Draw Nexu, John and infected cells:

 printGameBegin: function (enviroment) { this.members.nexa.svg = this.area .append("svg:image") .attr('x', enviroment.nexa.beginPosition.x - 0.25) .attr('y', enviroment.nexa.beginPosition.y - 0.25) .attr('width', 0.5) .attr('height', 0.5) .attr("xlink:href", "/sites/all/modules/custom/isp_quest/game/images/ai.png") .classed("codewar__nexa", true); this.members.john.svg = this.area .append("svg:image") .attr('x', enviroment.john.beginPosition.x - 0.25) .attr('y', enviroment.john.beginPosition.y - 0.25) .attr('width', 0.5) .attr('height', 0.5) .attr("xlink:href", "/sites/all/modules/custom/isp_quest/game/images/user.png") .classed("codewar__john", true); for (var i in enviroment.infection) { this.infectCell(enviroment.infection[i].x, enviroment.infection[i].y); } this.infectCell(enviroment.nexa.beginPosition.x, enviroment.nexa.beginPosition.y); } 

Bind the event buttons with jQuery, add motion animation and parse the results. The article will not disassemble these parts, you can see the entire frontend code here .



Testing and experimenting with AI behavior


Backend testing


Our server is able to receive HTTP requests, we use this for a test api backend. We will create the player code in a separate file and read it in the same way as the Nexa code.

 var john_mind = fs.readFileSync('./vm_scripts/john_script_test.js', 'utf8'); 

For testing, we set ourselves the following tasks:


Having caught all the found bugs, making sure that the nodejs has sufficient performance on the selected vds server, let's proceed to the experiments.

Experiments with AI script


First, let's take the simplest version of the Nexa script and try to defeat it on the open field. In our case, the first version of Nexa moved from the center to the left wall, then went up and rested against a corner. The victory over such an opponent took on the strength of 5 minutes. Then we made Nexu, which chases the player: always moves in the direction that is the shortest before him. This AI was also very simple. In the next iteration, an initially infected area was added. There have already been difficulties, but after a couple of hours, they wrote a script that won such a Nexu. In the last experiment, the pirate soul was added to the Nexus: she caught up with John, and after meeting him, she began to run away. Initially we planned to add attack and defense to the characters. But at this stage of testing, they realized that the game is already quite interesting and not the easiest. Therefore, we decided to stop at this version of Nexa.

Summarizing


27 people reached our codewar game in the quest. Among them, we identified the winners who wrote the most effective code. The performance criterion was 2: the smallest number of moves for which John cleared all the cells and the shortest code.

Among the solutions there were a variety of solutions, including brute force and partial brute force. The winner was the player who wrote a script of 339 characters who coped with Nexa in 64 moves. He showed an elegant js code, and we congratulated him on his victory. The second place was taken by the player with 64 moves and 835 code symbols. The third and fourth place was taken by a married couple, who had the same number of moves and the size of the code. The solution methods differed only in the sequence of pre-recorded moves.

Conclusion


Creating a game is a very addictive and addictive process. We made and launched the game for customers in 3 days. Despite the fact that not so many quest participants reached the task for programmers, they showed great interest in our game on social networks and shared their code with each other. We ourselves enjoyed developing the game and entertained our users quite well.

Source: https://habr.com/ru/post/349690/


All Articles