Dagaz: From Easy to Complex

    imageか た つ ぶ り そ ろ そ ろ 登 れ 富士 の 山

    Quietly, quietly crawl, snail, up the Fuji slope,
    up to the heights
     
                            小林 一 茶 (Kobayashi Issa)

    I wrote a lotabout what I want to get as a result. He told how to use it, but left one simple question unanswered. Why am I convinced that all this (allright, almost all of this) works? I have a secret weapon! And today I want to talk about him.

    The project that I am writing is complicated. I am developing a universal model that is potentially suitable for describing anyboard games. Needless to think about how to develop such a project from scratch, start and check if it works. Moreover, there is nothing to run yet. There is no controller nor any overwhelming view under which this model could be launched. But I must now check and debug the written code! Then, when the controller and view appear, debugging it all, in its entirety, will simply be impossible!

    I am not the first to encounter such a problem and a way to solve it has long been invented . To test my code, I use QUnit , but of course, this is not the only such solution in the JavaScript world. I do not adhere to the TDD methodology, in the sense that I do not try to precede code writing with tests, but I try to cover the entire model code with tests as much as possible. This helps me solve the following problems:

    • Search and correction of silly errors and typos in the code
    • Checking compatibility of used solutions with various platforms (browsers)
    • Regression testing (changing something, I must be sure that I did not break anything)
    • Minimal documentation (tests record ways of using model interfaces)

    The approach has already managed to justify itself
    At the very beginning of development, when with JavaScript I was still very much “on you”, I took Jocly code as a basis . Now, I have to get rid of a lot of what was written then, but at that moment, I had to start somewhere. I understood the task well (as time showed, not well enough), but I knew the language very poorly. Here is one of the code samples of those times:

    Search for an item in an array
    if ([].indexOf) {
       Model.find = function(array, value) {
         return array.indexOf(value);
       }
    } else {
       Model.find = function(array, value) {
          for (var i = 0; i < array.length; i++) {
              if (array[i] === value) return i;
          }
          return -1;
       }
    }
    

    Yes, premature optimization. If arrays support " indexOf ", we use it; otherwise, we search manually, in a loop. Since I built the model from the very beginning in such a way as to work only with numerical values, after some time, I decided to optimize something else:

    Arrays of Integer Values
    if (typeof Int32Array !== "undefined") {
       Model.int32Array = function(array) {
          var a = new Int32Array(array.length);
          a.set(array);
          return a;
       }
    } else {
       Model.int32Array = function(array) {
          return array;
       }
    }
    

    The logic is the same. Those who can use numerical arrays, the rest use what they can. For a while, all this worked great. On the browsers that I used. But one fine day, I ran my tests on IE11. And the creation of Microsoft was not slow to strike. The tests did not work. Everything resulted in this correction. I do not want to say that this code is much better (it has now been rewritten), but if I had not run the tests regularly and on different platforms, I would simply not have known about the problem! Unit tests really work.

    By developing tests, I move from simple code to more complex. Before checking the complex logic of the generation of the move (this is the main thing that the model does), I must make sure that all the parts used by it work correctly. All classes used in my model can be ranked by increasing "complexity":

    • ZrfPiece - description of the piece (object on the board)
    • ZrfDesign - Description of the board topology and game rules
    • ZrfMove - description of the move that changes the state of the game
    • ZrfMoveGenerator - generator of possible moves according to the pattern
    • ZrfBoard - game state storage and generator of all valid moves

    The ZrfPiece class is so simple that testing it does not even require a full game design . However, it does have some non-obvious features that need to be verified. For example, the logic of creating a new object when changing the type, owner, or some of the attributes of the figure.

    All this is elementary checked.
    QUnit.test( "Piece", function( assert ) {
      var design = Model.Game.getDesign();
      design.addPlayer("White", []);
      design.addPlayer("Black", []);
      design.addPiece("Man", 0);
      design.addPiece("King", 1);
      var man  = Model.Game.createPiece(0, 1);
      assert.equal( man.toString(), "White Man", "White Man");
      var king = man.promote(1);
      assert.ok( king !== man, "Promoted Man");
      assert.equal( king.toString(), "White King", "White King");
      assert.equal( man.getValue(0), null, "Non existent value");
      var piece = man.setValue(0, true);
      assert.ok( piece !== man, "Non mutable pieces");
      assert.ok( piece.getValue(0) === true, "Existent value");
      piece = piece.setValue(0, false);
      assert.ok( piece.getValue(0) === false, "Reset value");
      var p = piece.setValue(0, false);
      assert.equal( piece, p, "Value not changed");
      Model.Game.design = undefined;
    });
    

    Manually create the most minimal “design” (two players, two types of pieces and no hint at the board) and manually perform all the checks we are interested in. After that, we calmly use ZrfPiece , without expecting any tricks from it. Even if it later turns out that they forgot to check something, just add a few more checks. Next, we test more complex code:

    Game design
    QUnit.test( "Design", function( assert ) {
      var design = Model.Game.getDesign();
      design.addDirection("w");
      design.addDirection("e");
      design.addDirection("s");
      design.addDirection("n");
      assert.equal( design.dirs.length, 4, "Directions");
      design.addPlayer("White", [1, 0, 3, 2]);
      design.addPlayer("Black", [0, 1, 3, 2]);
      assert.equal( design.players[0].length, 4, "Opposite");
      assert.equal( design.players[2].length, 4, "Symmetry");
      design.addPosition("a2", [ 0, 1, 2,  0]);
      design.addPosition("b2", [-1, 0, 2,  0]);
      design.addPosition("a1", [ 0, 1, 0, -2]);
      design.addPosition("b1", [-1, 0, 0, -2]);
      var pos = 2;
      assert.equal( design.positionNames.length,4, "Positions");
      assert.equal( Model.Game.posToString(pos), "a1", "Start position");
      pos = design.navigate(1, pos, 3);
      assert.equal( Model.Game.posToString(pos), "a2", "Player A moving");
      pos = design.navigate(2, pos, 3);
      assert.equal( Model.Game.posToString(pos), "a1", "Player B moving");
      ...
      Model.Game.design = undefined;
    });
    

    ZrfDesign is 99% board navigation. We check it. We create the design again manually (now with a small board), after which we run the most typical test cases. And do not forget, in the end, to clear the created design! So that he does not break other tests.

    By the way, right now it turned out
    I was very wrong when I considered the design of the game a singleton ! Not to mention the server version, which simply needs to be able to work with several different game models at the same time, there is another interesting case. Working on the simplest game bots , I remembered a wonderful game .


    Mines are scattered across the field, but how to lure the enemy on them, provided that he knows about them? After all, there is absolutely no reason for him to simply lose his shape by standing on a “mined” field. The task is solved simply. The bot we play with can get a slightly different game design. The board, the rules for moving the pieces - everything will be the same, with one small exception. He won’t know anything about mines.

    In fact, this is the only adequate way to implement games with incomplete information, such as Kriegspiel or LuzhanqiOf course, if we do not want the computer to see all our figures, but we do not. In any case, I'm working on it now. And unit tests help me again in this! When performing such extensive refactoring, it is vital to know that nothing has fallen apart!

    Further, tests are becoming more and more high-level. Generating a single move according to the template with the ZrfMoveGenerator class , applying the move to the game state and, finally, generating a set of moves by a certain position:

    Fight of several figures by a lady
    QUnit.test( "King's capturing chain", function( assert ) {
      Model.Game.InitGame();
      var design = Model.Game.getDesign();
      var board  = Model.Game.getInitBoard();
      board.clear();
      assert.equal( board.moves.length, 0, "No board moves");
      design.setup("White", "King", Model.Game.stringToPos("d4"));
      design.setup("Black", "Man", Model.Game.stringToPos("c4"));
      design.setup("Black", "Man", Model.Game.stringToPos("a6"));
      design.setup("Black", "Man", Model.Game.stringToPos("f8"));
      board.generate();
      assert.equal( board.moves.length, 2, "2 moves generated");
      assert.equal( board.moves[0].toString(), "d4 - a4 - a8 - g8 x c4 x a6 x f8", "d4 - a4 - a8 - g8 x c4 x a6 x f8");
      assert.equal( board.moves[1].toString(), "d4 - a4 - a8 - h8 x c4 x a6 x f8", "d4 - a4 - a8 - h8 x c4 x a6 x f8");
      Model.Game.design = undefined;
      Model.Game.board = undefined;
    });
    

    For all the brevity of the test, this is almost a full game! In any case, one move from it. Here, compound moves and a move with a "moving" piece and the priority of capture and even a majority rule , implemented as a game extension and requiring the capture of the maximum possible number of enemy pieces, are tested ! This small test covers almost the entire functionality of the model. And when something breaks, we see it, and immediately fix it .

    Another thing unit tests help with is refactoring! At some point, we decided that the project would use Underscore . This great library helps you write functional style code.making it more concise and followed. To make it clearer, I will give one example from the life of the project.

    Functional programming is all the more useful the more difficult the task. If the code is completely simple, rewriting it in a functional style will do little. But if the task is a little more complicated, the advantages of a functional approach become more obvious.


    Remember this game ? She has two funny rules:

    • If moving the stone creates a new row, then the player gains the right to capture any of the opponent’s stones
    • When a player is left with only three stones, his stones turn into "flying". These stones can move (“fly over”) not only to one of the neighboring ones, but generally to any free cell on the board.

    I marked a keyword. What does it mean "a player can capture any enemy stone"? If the opponent has N pieces on the board, then exactly this number of times we are obliged to duplicate each move, leading to the construction of a "row". These moves will differ only in the figure taken! In Zillions of Games, this is exactly what is being done. And this unimaginably complicates the implementation of the game! But there is still a rule of "flying" stones ...

    There is another solution. We can form just one move, listing in it all the positions of potential capture. Of course, this does not mean that we will take everything.stones, not at all! Only one of the listed will be taken. The course becomes non-deterministic. The same with the movements. If a “flying” stone can build a “row”, it turns out the Cartesian product of all resultant moves on the set of positions occupied by enemy figures.

    I came up with a good way by which the user interface can work with such moves, but for AI bots it is not applicable! AI must receive strictly deterministic moves! This means that there must be a mechanism that turns non-deterministic moves into deterministic.

    Here is the first version of what I once wrote
    var getIx = function(x, ix, mx) {
      if (ix > x.length) {
          x = [];
          return null;
      }
      if (ix == x.length) {
          c.push(0);
          return 0;
      }
      var r = x[ix];
      if (r >= mx) {
          if (ix + 1 >= x.length) {
              x = [];
              return null;
          }
          for (var i = 0; i <= ix; i++) {
              x[ix] = 0;
          }
          x[ix + 1]++;
      }
      return r;
    }
    ZrfMove.prototype.determinate = function() {
      var r = [];
      for (var x = [0]; x.length > 0; x[0]++) {
          var m = Model.Game.createMove();
          var ix = 0;
          for (var i in this.actions) {
               var k = 0;
               var fp = this.actions[i][0];
               if (fp !== null) {
                   k = getIx(x, ix++, fp.length);
                   if (k === null) {
                       break;
                   }
                   fp = [ fp[k] ];
               }
               var tp = this.actions[i][1];
               if (tp !== null) {
                   k = getIx(x, ix++, tp.length);
                   if (k === null) {
                       break;
                   }
                   tp = [ tp[k] ];
               }
               var pc = this.actions[i][2];
               if (pc !== null) {
                   k = getIx(x, ix++, pc.length);
                   if (k === null) {
                       break;
                   }
                   pc = [ pc[k] ];
               }
               var pn = this.actions[i][3];
               m.actions.push([fp, tp, pc, pn]);
          }
          r.push(m);      
      }
      return r;
    }
    

    60 lines of completely incomprehensible and absolutely unsupported code! Most likely it doesn't even work! I have not tested it.

    Instead, I rewrote it
    ZrfMove.prototype.getControlList = function() {
      return _.chain(this.actions)
       .map(function (action) {
            return _.chain(_.range(3))
             .map(function (ix) {
                  if (action[ix] === null) {
                      return 0;
                  } else {
                      return action[ix].length;
                  }
              })
             .filter(function (n) { return n > 1; })
             .value();
        })
       .flatten()
       .map(function (n) { return _.range(n); })
       .cartesian()
       .value();
    }
    ZrfMove.prototype.determinate = function() {
      var c = this.getControlList();
      if (c.length > 1) {
          return _.chain(c)
           .map(function (l) {
               var r = new ZrfMove();
               var pos = 0;
               _.each(this.actions, function (action) {
                  var x = [];
                  _.each(_.range(3), function (ix) {
                     pos = pushItem(this, action[ix], l, pos);
                  }, x);
                  x.push(action[3]);
                  if (isValidAction(x)) {
                      this.actions.push(x);
                  }
               }, r);
               return r;
            }, this)
           .filter(isValidMove)
           .value();
      } else {
          return [ this ];
      }
    }
    

    The code has become longer and, at first glance, does not look more understandable. But let's take a closer look at it. To get started, let's try to understand the problem. The description of the course ( ZrfMove ) consists of a set of actions ( actions ), each of which is a tuple of four elements:

    1. Starting position ( from )
    2. End position ( to )
    3. Figure ( piece )
    4. Partial Stroke Number ( num )

    Since there is no transformation of figures in the Mill and composite moves are not used, only the first two of these values ​​are important to us. They are enough to describe any action performed:

    • Adding a piece to the board (reset) - from == null && to! = Null
    • Deleting a shape (capture) - from! = Null && to == null
    • Moving a shape - from! = Null && to! = Null && from! = To

    But this is only half the battle! In fact, both from and to (and even a piece , but it's not about her) are also arrays! If the move is deterministic, each of these arrays contains exactly one element. The presence in any of them of a larger number of values ​​means the possibility of choice (which we must deal with).

    Non-deterministic stroke
    var m = [ [ [0], [1, 2] ], [ [3, 4, 5], null ] ]; // Незначимые элементы опущены
    

    There is a movement of the figure from position 0 to any of two positions ( 1 or 2 ) and capture of one enemy figure from positions 3 , 4 or 5 . To begin with, you can choose the size of all "non-deterministic" positions (containing more than one element):

    The code
    m = _.map(m, function(action) {
            return _.chain(_.range(2))
             .map(function (ix) {
                  if (action[ix] === null) {
                      return 0;
                  } else {
                      return action[ix].length;
                  }
              })
             .filter(function (n) { return n > 1; })
             .value();
    });
    
    Result
    m == [ [2], [3] ] // Только "недетерминированные" позиции
    

    This array is “smoothed", after which we turn each numerical value into range:

    The code

    m = _.chain (m)
    .flatten ()
    .map (function (n) {return _.range (n);})
    .value ();
    Result
    m == [ [0, 1], [0, 1, 2] ]
    

    Now we need an operation that is not provided for in the basic Underscore.js configuration . Something like a Cartesian product . Nothing wrong.

    Write it yourself
    var cartesian = function(r, prefix, arr) {
       if (arr.length > 0) {
           _.each(_.first(arr), function (n) {
              var x = _.clone(prefix);
              x.push(n);
              cartesian(r, x, _.rest(arr));
           });
       } else {
           r.push(prefix);
       }
    }
    
    And embed in Underscore.js
    _.mixin({
      cartesian: function(x) {
         var r = [];
         cartesian(r, [], x);
         return r;
      }
    });
    

    I admit that my decision is not completely "kosher." If anyone knows how to do better, write in the comments. Apply it:

    The code
          _.chain(m)
           .map(function(action) {
            return _.chain(_.range(2))
             .map(function (ix) {
                  if (action[ix] === null) {
                      return 0;
                  } else {
                      return action[ix].length;
                  }
              })
             .filter(function (n) { return n > 1; })
             .value();
            })
           .flatten()
           .map(function (n) { return _.range(n); })
           .cartesian()
           .value();
    
    Result
    [ [0, 0],  [0, 1], [0, 2], [1, 0], [1, 1], [1, 2] ]
    

    The rest of the task is slightly more complicated. It is necessary to select the “non-deterministic” positions from the initial version of the stroke, in accordance with the existing cheat sheet. I will not bother the reader with this, the task is purely technical. The most important thing is that using the functional approach allowed us to divide a rather complex task into parts that can be solved and debugged separately.

    Of course, the use of a functional approach is not always associated with the solution of such puzzles. Usually, everything is somewhat simpler. As a typical example, I can cite the maximal-captures module , which implements the option inherited from Zillions of Games, which ensures that the maximum number of pieces in games of the family of drafts is captured.

    It was
    Model.Game.PostActions = function(board) {
      PostActions(board);
      if (mode !== 0) {
          var moves = [];
          var mx = 0;
          var mk = 0;
          for (var i in board.moves) {
               var vl = 0;
               var kv = 0;
               for (var j in board.moves[i].actions) {
                    var fp = board.moves[i].actions[j][0];
                    var tp = board.moves[i].actions[j][1];
                    if (tp === null) {
                        var piece = board.getPiece(fp[0]);
                        if (piece !== null) {
                            if (piece.type > 0) {
                                kv++;
                            }
                            vl++;
                        }
                    }
               }
               if (vl > mx) {
                   mx = vl;
               }
               if (kv > mk) {
                   mk = kv;
               }
          }
          for (var i in board.moves) {
               var vl = 0;
               var kv = 0;
               for (var j in board.moves[i].actions) {
                    var fp = board.moves[i].actions[j][0];
                    var tp = board.moves[i].actions[j][1];
                    if (tp === null) {
                        var piece = board.getPiece(fp[0]);
                        if (piece !== null) {
                            if (piece.type > 0) {
                                kv++;
                            }
                            vl++;
                        }
                    }
               }
               if ((mode === 2) && (mk > 0)) {
                   if (kv == mk) {
                       moves.push(board.moves[i]);
                   }
               } else {
                   if (vl == mx) {
                       moves.push(board.moves[i]);
                   }
               }
          }
          board.moves = moves;
      }
    }
    
    ... and so it became
    
    Model.Game.PostActions = function(board) {
      PostActions(board);
      var captures = function(move) {
        return _.chain(move.actions)
         .filter(function(action) {
             return (action[0] !== null) && (action[1] === null);
          })
         .map(function(action) {
             return board.getPiece(action[0]);
          })
         .compact()
         .map(function(piece) {
             return piece.type;
          })
         .countBy(function(type) {
             return (type === 0) ? "Mans" : "Kings";
          })
         .defaults({ Mans: 0, Kings: 0 })
         .value();
      };
      if (mode !== 0) {
          var caps = _.map(board.moves, captures);
          var all = _.chain(caps)
           .map(function(captured) {
              return captured.Mans + captured.Kings;
            })
           .max()
           .value();
          var kings = _.chain(caps)
           .map(function(captured) {
              return captured.Kings;
            })
           .max()
           .value();
          board.moves = _.chain(board.moves)
           .filter(function(move) {
               var c = captures(move);
               if ((mode === 2) && (kings > 0)) {
                   return c.Kings >= kings;
               } else {
                   return c.Mans + c.Kings >= all;
               }
            })
           .value();
      }
    }
    

    Both options work quite well (the code was already covered by tests at the time of refactoring), but the functional version is shorter, easier to understand, and assembled from unified blocks. Maintaining it is certainly much easier.

    To conclude this article, I want to voice a few principles that I try to follow in my work. By no means do I want to make dogma out of them, but they help me.

    Not a day without a line
    Work on the project should not be interrupted! In any case, for how long. The longer the break, the harder it is to get back to work. Work takes much less time and effort if you do it every day. At least a little bit! This does not mean that you need to “squeeze” the code “I can’t” through (for a short while, and burn out). If the project is complex and interesting, you can always find work in the mood.
    Morning code, evening tests
    Yes, yes, I know, this goes completely against TDD methodology . But who said that I stick to it? Unit tests are (very) useful, even if you do not put them at the forefront! Any code, both simple and complex, should be covered with tests as much as possible! At the same time, it is desirable to move from simple to complex, testing more complex functionality after there is no doubt about the operability of the one on which it is built. Tests should not be deleted until they have lost their relevance! On the contrary, we must try to run them as often as possible, in various environments. I found some serious and very non-trivial mistakes this way!
    Do no harm
    Any changes should not break the code already covered by tests! No need to commit code with broken tests. Even if you worked on this code all day! Even if you’re very tired to deal with the here and now problem! Non-working code is garbage. This is a bomb that can explode at any moment! If there is no strength to deal with it, it is better to completely remove it, then to rewrite it again.
    Never give up
    Don’t be afraid to rewrite the code again and again! A little refactoring, or even a complete rewrite of the project from scratch - this is not a reason for panic! This is an opportunity to solve the problem better.
    If you can’t win honestly, just win
    Good code solves the problem. Good code is understandable and maintainable. That's all! No need to turn inside out just to “fit” it under the ideology of OOP , FP, or something else! Using some features of the language or its environment, you need to think not about fashion, but only about the usefulness of these "features" for the project. You still can’t keep up with fashion!

    Of course, I still have room to grow. I do not see this as a problem. My understanding of the language is changing (I hope for the better), and with it, the code is changing. And unit tests just help me with that.

    Also popular now: