かたつぶりそろそろ登れ富士の山Тихо-тихо ползи, улитка, по склону Фудзи,
вверх, до самых высот
小林一茶 (Кобаяси Исса)
Я много писал о том, что хочу получить в итоге. Рассказал, как этим можно пользоваться, но оставил без ответа один простой вопрос. Почему я убеждён в том, что всё это (ладно-ладно, почти всё это) работает? У меня есть секретное оружие! И сегодня я хочу о нём рассказать.
Проект, который я пишу сложен. Я разрабатываю универсальную модель, потенциально пригодную для описания любых настольных игр. Нечего и думать о том, чтобы разработать такой проект «с нуля», запустить и проверить, работает ли он. Тем более, что и запускать-то пока нечего. Нет ни контроллера ни сколь нибудь завалящего представления, под которыми эту модель можно было бы запустить. Но я должен уже сейчас проверять и отлаживать написанный код! Потом, когда контроллер и представление появятся, отладить его весь, целиком, будет попросту невозможно!
Я не первый, кто сталкивается с такой проблемой и способ её решения давно придуман. Для тестирования своего кода, я использую QUnit, но конечно же, это не единственное подобное решение в мире JavaScript. Я не придерживаюсь методологии TDD, в том отношении, что не стараюсь предварять написание кода тестами, но стараюсь максимально покрыть тестами весь код модели. Это помогает мне решить следующие задачи:
- Поиск и исправление глупых ошибок и опечаток в коде
- Проверка совместимости используемых решений с различными платформами (браузерами)
- Регрессионное тестирование (изменяя что-то, я должен быть уверен, что ничего не сломал)
- Минимальное документирование (тесты фиксируют способы использования интерфейсов модели)
Подход уже успел себя оправдать
В самом начале разработки, когда с JavaScript-ом я был ещё очень сильно «на Вы», я брал за основу код Jocly. Сейчас, мне приходится избавляться от много из того, что было написано тогда, но на тот момент, надо было с чего-то начинать. Я хорошо (как показало время, недостаточно хорошо) понимал задачу, но очень плохо знал язык. Вот один из образчиков кода тех времён:
Да-да, преждевременная оптимизация. Если массивы поддерживают "indexOf", пользуемся им, в противном случае, ищем вручную, в цикле. Поскольку я с самого начала строил модель таким образом, чтобы работать только с числовыми значениями, по прошествии некоторого времени, я решил соптимизировать кое что ещё:
Логика та же. Те кто могут — пользуются числовыми массивами, остальные пользуются тем чем могут. Некоторое время всё это прекрасно работало. На тех браузерах, которыми я пользовался. Но в один прекрасный момент, я запустил свои тесты на IE11. И творение Microsoft-а не замедлило нанести свой удар. Тесты не отработали. Всё вылилось в это исправление. Я не хочу сказать, что этот код сильно лучше (сейчас он уже переписан), но если бы я не запускал тесты регулярно и на разных платформах, то попросту не узнал бы о проблеме! Unit-тесты действительно работают.
Поиск элемента в массиве
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;
}
}
Да-да, преждевременная оптимизация. Если массивы поддерживают "indexOf", пользуемся им, в противном случае, ищем вручную, в цикле. Поскольку я с самого начала строил модель таким образом, чтобы работать только с числовыми значениями, по прошествии некоторого времени, я решил соптимизировать кое что ещё:
Массивы целочисленных значений
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;
}
}
Логика та же. Те кто могут — пользуются числовыми массивами, остальные пользуются тем чем могут. Некоторое время всё это прекрасно работало. На тех браузерах, которыми я пользовался. Но в один прекрасный момент, я запустил свои тесты на IE11. И творение Microsoft-а не замедлило нанести свой удар. Тесты не отработали. Всё вылилось в это исправление. Я не хочу сказать, что этот код сильно лучше (сейчас он уже переписан), но если бы я не запускал тесты регулярно и на разных платформах, то попросту не узнал бы о проблеме! Unit-тесты действительно работают.
Разрабатывая тесты, я двигаюсь от простого кода к более сложному. Перед тем как проверять сложную логику генерации хода (это главное из того чем занимается модель), я должен убедиться в правильности работы всех используемых ей частей. Все классы, используемые в моей модели, можно ранжировать по нарастанию «сложности»:
- ZrfPiece — описание фигуры (объекта на доске)
- ZrfDesign — описание топологии доски и игровых правил
- ZrfMove — описание хода, изменяющего состояние игры
- ZrfMoveGenerator — генератор возможных ходов «по шаблону»
- ZrfBoard — хранилище игрового состояния и генератор всех допустимых ходов
Класс ZrfPiece настолько прост, что его тестирование даже не требует наличия полноценного игрового дизайна. Тем не менее, у него имеются некоторые не очевидные особенности, которые необходимо проверить. Например, логика создания нового объекта при изменении типа, владельца либо какого-то из атрибутов фигуры.
Всё это элементарно проверяется
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;
});
Создаём вручную самый минимальный «дизайн» (два игрока, два типа фигур и никакого намёка на доску) и вручную же выполняем все интересующие нас проверки. После этого спокойно пользуемся ZrfPiece, не ожидая от него никаких подвохов. Даже если впоследствии выяснится, что что-то проверить забыли, просто добавим ещё несколько проверок. Далее тестируем более сложный код:
Дизайн игры
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 — это на 99% навигация по игровой доске. Её и проверяем. Дизайн снова создаём вручную (теперь уже с небольшой доской), после чего прогоняем наиболее типичные тест-кейсы. И не забываем, в конце, очистить созданный дизайн! Чтобы он не ломал другие тесты.
Кстати, вот прямо сейчас выяснилось
Я был сильно не прав, когда посчитал дизайн игры синглтоном! Не говоря уже о серверной версии, которой попросту необходимо уметь работать с несколькими различными моделями игр одновременно, существует ещё один любопытный кейс. Работая над простейшими игровыми ботами, я вспомнил о замечательной игре.
По полю разбросаны мины, но как заманить на них противника, при условии, что он про них знает? Ему ведь нет абсолютно никакого резона просто терять фигуру, встав на «заминированное» поле. Задача решается просто. Бот, с которым мы играем, может получить слегка отличающийся дизайн игры. Доска, правила хода фигур — всё будет тем же, за одним маленьким исключением. О минах он не будет знать ничего.
Фактически, это единственный адекватный способ реализации игр с неполной информацией, таких как Kriegspiel или Luzhanqi, конечно, если мы не хотим, чтобы компьютер видел все наши фигуры, а мы его нет. В любом случае, сейчас я над этим работаю. И в этом мне вновь помогают unit-тесты! При выполнении столь обширного рефакторинга, жизненно необходимо знать, что у тебя ничего не развалилось!
По полю разбросаны мины, но как заманить на них противника, при условии, что он про них знает? Ему ведь нет абсолютно никакого резона просто терять фигуру, встав на «заминированное» поле. Задача решается просто. Бот, с которым мы играем, может получить слегка отличающийся дизайн игры. Доска, правила хода фигур — всё будет тем же, за одним маленьким исключением. О минах он не будет знать ничего.
Фактически, это единственный адекватный способ реализации игр с неполной информацией, таких как Kriegspiel или Luzhanqi, конечно, если мы не хотим, чтобы компьютер видел все наши фигуры, а мы его нет. В любом случае, сейчас я над этим работаю. И в этом мне вновь помогают unit-тесты! При выполнении столь обширного рефакторинга, жизненно необходимо знать, что у тебя ничего не развалилось!
Далее, тесты становятся всё более и более высокоуровневыми. Генерация отдельного хода по шаблону классом ZrfMoveGenerator, применение хода к игровому состоянию и, наконец, генерация набора ходов определённой позицией:
Бой нескольких фигур дамкой
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;
});
При всей лаконичности теста, это уже, практически, полноценная игра! Во всяком случае, один ход из неё. Здесь тестируются и составные ходы и ход «скользящей» фигурой и приоритет взятия и даже правило большинства, реализованное как игровое расширение и предписывающее взятие максимально-возможного количества вражеских фигур! Этот небольшой тест покрывает практически всю функциональность модели. И когда что-то ломается, мы это видим, и сразу же исправляем.
Ещё одна вещь, в которой помогают unit-тесты — это рефакторинг! В какой-то момент, мы решили, что в проекте будет использоваться Underscore. Эта замечательная библиотека помогает писать код в функциональном стиле, делая его более лаконичным и сопровождаемым. Чтобы было понятнее, приведу один пример «из жизни» проекта.
Функциональное программирование тем полезнее, чем сложнее задача. Если код совсем простой, переписывание его в функциональном стиле мало что даст. Но если задачка чуть посложнее, преимущества функционального подхода становятся более очевидными.
Помните эту игру? У неё есть два забавных правила:
- Если перемещение камня создает новый ряд, то игрок получает право захватить любой из камней противника
- Когда игрок остается всего с тремя камнями, его камни превращаются в «летающие». Эти камни могут перемещаться («перелетать») не только в одну из соседних, но вообще в любую свободную клетку на доске.
Я отметил ключевое слово. Что значит «игрок может захватить любой камень противника»? Если у противника N фигур на доске, то ровно такое количество раз мы обязаны продублировать каждый ход, приводящий к построению «ряда». Эти ходы будут отличаться лишь взятой фигурой! В Zillions of Games всё именно так и делается. И это невообразимо усложняет реализацию игры! А ведь есть ещё правило «летающих» камней…
Есть другое решение. Мы можем сформировать всего один ход, перечислив в нём все позиции потенциального взятия. Разумеется, это не означает, что мы возьмём все камни, вовсе нет! Взят будет лишь один из перечисленных. Ход станет недетерминированным. То же с перемещениями. Если «летающий» камень может построить «ряд», получается декартово произведение всех результативных ходов на множество позиций занятых вражескими фигурами.
Я придумал хороший способ, при помощи которого пользовательский интерфейс может работать с такими ходами, но для AI-ботов он неприменим! AI должен получать на вход строго детерминированные ходы! Это означает, что должен быть механизм, превращающий недетерминированные ходы в детерминированные.
Вот первый вариант того, что я когда-то написал
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 строк совершенно непонятного и абсолютно неподдерживаемого кода! Скорее всего, он даже не работает! Я так и не протестировал его.
Вместо этого, я его переписал
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 ];
}
}
Код стал длиннее и, на первый взгляд, не выглядит более понятным. Но давайте присмотримся к нему повнимательнее. Для начала, попробуем разобраться в задаче. Описание хода (ZrfMove) состоит из набора действий (actions), каждое из которых представляет собой кортеж из четырёх элементов:
- Начальная позиция (from)
- Конечная позиция (to)
- Фигура (piece)
- Номер частичного хода (num)
Поскольку превращение фигур в «Мельнице» отсутствует и составные ходы не используются, для нас важны только первые два из этих значений. Их достаточно, чтобы описать любое выполняемое действие:
- Добавление фигуры на доску (сброс) — from == null && to != null
- Удаление фигуры (захват) — from != null && to == null
- Перемещение фигуры — from != null && to != null && from != to
Но это только половина дела! На самом деле и from и to (и даже piece, но речь не о ней) — тоже массивы! В случае, если ход детерминированный, каждый из таких массивов содержит ровно по одному элементу. Наличие в любом из них большего количества значений означает возможность выбора (с которой мы и должны разобраться).
Недетерминированный ход
var m = [ [ [0], [1, 2] ], [ [3, 4, 5], null ] ]; // Незначимые элементы опущены
Имеется перемещение фигуры с позиции 0 на любую из двух позиций (1 или 2) и захват одной фигуры противника с позиций 3, 4 или 5. Для начала, можно выбрать размер всех «недетерминированных» позиций (содержащих более одного элемента):
Код
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();
});
Результат
m == [ [2], [3] ] // Только "недетерминированные" позиции
Этот массив «сглаживаем», после чего, превращаем каждое числовое значение в range:
Код
m = _.chain(m)
.flatten()
.map(function (n) { return _.range(n); })
.value();
m = _.chain(m)
.flatten()
.map(function (n) { return _.range(n); })
.value();
Результат
m == [ [0, 1], [0, 1, 2] ]
Теперь нам понадобится операция, в базовой комплектации Underscore.js не предусмотренная. Что-то вроде декартова произведения. Ничего страшного.
Напишем его сами
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);
}
}
И встроим в Underscore.js
_.mixin({
cartesian: function(x) {
var r = [];
cartesian(r, [], x);
return r;
}
});
Допускаю, что моё решение не вполне «кошерно». Если кто нибудь знает, как сделать лучше, пишите в комментарии. Применим его:
Код
_.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();
Результат
[ [0, 0], [0, 1], [0, 2], [1, 0], [1, 1], [1, 2] ]
Оставшаяся часть задачи немногим сложнее. Необходимо выбрать из исходного варианта хода «недетерминированные» позиции, в соответствии с имеющейся шпаргалкой. Не стану утруждать этим читателя, задача чисто техническая. Самое главное то, что использование функционального подхода позволило разделить довольно сложную задачу на части, которые можно решать и отлаживать по отдельности.
Разумеется, использование функционального подхода не всегда связано с решением подобных головоломок. Обычно, всё несколько проще. В качестве характерного примера могу привести модуль maximal-captures, реализующий унаследованную от Zillions of Games опцию, обеспечивающую взятие максимального количества фигур в играх семейства шашек.
Так было
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;
}
}
... и так стало
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();
}
}
И тот и другой вариант вполне работающие (на момент рефакторинга код был уже покрыт тестами), но функциональный вариант короче, легче понимается и собран из унифицированных блоков. Поддерживать его, безусловно, гораздо проще.
В заключение статьи, я хочу озвучить несколько принципов, которыми я стараюсь руководствоваться в работе. Я, ни в коем случае, не хочу делать из них догму, но мне они помогают.
Ни дня без строчки
Работа над проектом не должна прерываться! Во всяком случае, на сколь нибудь продолжительное время. Чем дольше перерыв — тем сложнее вернуться к работе. Работа отнимает гораздо меньше времени и сил, если заниматься ей каждый день. Хотя бы понемногу! Это не означает, что нужно «выдавливать» из себя код «через не могу» (так недолго и перегореть). Если проект сложен и интересен, всегда можно найти работу под настроение.
Утром код, вечером тесты
Да-да, знаю, это идёт в полный разрез с методологией TDD. Но кто сказал, что я её придерживаюсь? Unit-test-ы (очень) полезны, даже если не ставить их во главу угла! Любой код, и простой и сложный, должен быть покрыт тестами, насколько это возможно! При этом, желательно двигаться от простого к сложному, тестируя более сложную функциональность после того как не остаётся сомнений в работоспособности той, на которой она построена. Не следует удалять тесты, пока они не потеряли свою актуальность! Напротив, надо стараться запускать их как можно чаще, в различных окружениях. Я нашёл несколько серьёзных и очень нетривиальных ошибок таким образом!
Не навреди
Любые изменения не должны ломать код уже покрытый тестами! Не надо commit-ить код со сломанными тестами. Даже если занимался этим кодом весь день! Даже если очень устал, чтобы разобраться с проблемой «здесь и сейчас»! Не работающий код — это мусор. Это бомба, которая может взорваться в любой момент! Если нет сил с ним разобраться, лучше полностью его удалить, чтобы потом переписать заново.
Никогда не сдавайся
Не надо бояться переписывать код снова и снова! Небольшой рефакторинг, или даже полное переписывание проекта с нуля — это не повод для паники! Это возможность решить задачу лучше.
Если не можешь победить честно - просто победи
Хороший код решает задачу. Хороший код — понятен и сопровождаем. На этом, всё! Не надо выворачиваться наизнанку просто для того, чтобы «подогнать» его под идеологию ООП, ФП или чего-то там ещё! Используя какие-то возможности языка или его окружения, надо думать не о моде, а лишь о полезности этих «фич» для проекта. За модой всё равно не угонишься!
Безусловно, мне ещё есть куда расти. Я не вижу в этом проблемы. Меняется (надеюсь, что в лучшую сторону) моё понимание языка, а вместе с ним, меняется и код. А unit-тесты просто помогают мне в этом.
