Dagaz: Быстрее, Лучше, Умнее…07.03.2018 16:33

Разумеется, возможны коллизии. Например, оба игрока могут одновременно сходить на одно и то же пустое поле или пешка может попытаться съесть фигуру, уходящую тем же ходом от удара. Правила игры хорошо описывают эти нюансы. Пешке разрешается выполнять диагональный ход, при условии того, что она собралась кого-то побить, даже если фигура ушла с этой позиции, а результат конфликта за пустое поле определяется рангом фигур. Всадник всегда убивает пешку, если же фигуры равны — они уничтожаются обе (что, кстати, делает возможными ничейные исходы).

Dagaz.Model.join = function(design, board, a, b) {
  var x = getPiece(design, board, a);
  var y = getPiece(design, board, b);
  if ((x !== null) && (y !== null)) {
      var r = Dagaz.Model.createMove();
      r.protected = [];
      checkPromotion(design, board, a, x, b);
      checkPromotion(design, board, b, y, a);
      var p = a.actions[0][1][0];
      var q = b.actions[0][1][0];
      if ((p == q) && (x.type > y.type)) {
          r.actions.push(b.actions[0]);
          r.actions.push(a.actions[0]);
      } else {
          r.actions.push(a.actions[0]);
          r.actions.push(b.actions[0]);
      }
      if (p == q) {
          if (x.type > y.type) {
              r.actions[0][2] = [ Dagaz.Model.createPiece(2, 2) ];
              r.protected.push(x.player);
              r.captured = p;
          } else {
              if (x.type == y.type) {
                  r.actions[0][2] = [ Dagaz.Model.createPiece(2, 1) ];
                  r.actions[1][2] = [ Dagaz.Model.createPiece(2, 1) ];
                  r.capturePiece(p);
              } else {
                  r.actions[0][2] = [ Dagaz.Model.createPiece(2, 1) ];
                  r.protected.push(y.player);
                  r.captured = p;
              }
          }
      }
      return r;
  } else {
      return a;
  }
}

Есть правда одна тонкость — обычно, постобработка выполняется сразу после генерации, для всех сформированных ходов. В данном случае, так делать нельзя, поскольку это неизбежно приведёт к «комбинаторному взрыву» (игра хоть и небольшая, но всё равно приятного мало). Самое главное, делать этого и не нужно. Есть способ проще. Никто ведь не сказал, что мы не можем переписать контроллер. У модульности есть свои преимущества.

...
var isCovered = function(design, board, pos, player, type) {
  var r = false;
  _.each(Dagaz.Model.GetCover(design, board)[pos], function(pos) {
      var piece = board.getPiece(pos);
      if ((piece !== null) && (piece.player == player)) {
          if (_.isUndefined(type) || (piece.type == type)) {
              r = true;
          }
      }
  });
  return r;
}

Ai.prototype.getMove = function(ctx) {
  var moves = Dagaz.AI.generate(ctx, ctx.board);
  if (moves.length == 0) {      
      return { done: true, ai: "nothing" };
  }
  timestamp   = Date.now();
  var enemies = 0;
  var friends = 0;
  _.each(ctx.design.allPositions(), function(pos) {
      var piece = ctx.board.getPiece(pos);
      if ((piece !== null) && (piece.type == 1)) {
          if (piece.player == 1) {
              enemies++;
          } else {
              friends++
          }
      }
  });
  var eval = -MAXVALUE;
  var best = null;
  _.each(moves, function(move) {
      var e = _.random(0, NOISE_FACTOR);
      if (move.isSimpleMove()) {
           var pos = move.actions[0][0][0];
           var trg = move.actions[0][1][0];
           var piece = ctx.board.getPiece(pos);
           if (piece !== null) {
               var target = ctx.board.getPiece(trg);
               if (piece.type == 1) {
                   if (isCovered(ctx.design, ctx.board, pos, 1)) e += MAXVALUE;
                   if (target === null) {
                       if (isCovered(ctx.design, ctx.board, trg, 1, 0)) e += LARGE_BONUS;
                       if (isCovered(ctx.design, ctx.board, trg, 1, 1)) {
                           if ((enemies == 1) && (friends == 2)) {
                               e += BONUS;
                           } else {
                               e -= MAXVALUE;
                           }
                       }
                   } else {
                       if (target.type == 1) {
                           e += SMALL_BONUS;
                       } else {
                           e += BONUS;
                       }
                   }
               } else {
                   if (isCovered(ctx.design, ctx.board, pos, 1)) e += SMALL_BONUS;
                   if ((target === null) && isCovered(ctx.design, ctx.board, trg, 1)) e -= MAXVALUE;
                   if (friends == 1) e += BONUS;
                   if (target !== null) e += SMALL_BONUS;
                   if ((move.actions[0][2] !== null) && (move.actions[0][2][0].type != piece.type)) {
                       if (friends == 1) {
                           e += MAXVALUE;
                       } else {
                           e -= MAXVALUE;
                       }
                   }
               }
           }
      }
      if ((best === null) || (eval < e)) {
           console.log("Move: " + move.toString() + ", eval = " + e);
           best = move;
           eval = e;
      }
  });
  return {
      done: true,
      move: best,
      time: Date.now() - timestamp,
      ai:  "aggressive"
  };
}

Для пользователя, сложный составной ход представляет собой последовательность различных действий (перемещений, взятий и, возможно, сбросов новых фигур на доску). Где-то должен быть код, позволяющий по последовательности пользовательских «кликов» выбрать единственный ход из ранее сформированного и возможно большого списка. И такой код в Dagaz, разумеется есть.

MoveList.prototype.isUniqueFrom = function(pos) {
  var c = 0;
  _.each(this.moves, function(move) {
      _.each(this.getActions(move), function(action) {
          if ((action[0] !== null) && (_.indexOf(action[0], pos) >= 0)) c++;
      });
  }, this);
  return c == 1;
}

MoveList.prototype.isUniqueTo = function(pos) {
  var c = 0;
  _.each(this.moves, function(move) {
      _.each(this.getActions(move), function(action) {
          if ((action[1] !== null) && (_.indexOf(action[1], pos) >= 0)) c++;
      });
  }, this);
  return c == 1;
}
...
MoveList.prototype.getStops = function() {
  var result = this.getTargets();
  _.each(this.moves, function(move) {
      var actions = _.filter(this.getActions(move), isMove);
      if ((actions.length > 0) && (actions[0][0].length == 1) && 
          (actions[0][1].length == 1)) {
          if (Dagaz.Model.smartFrom) {
              if (this.isUniqueFrom(actions[0][0][0]) && !this.canPass()) {
                  result.push(actions[0][0][0]);
              }
          }
          if (Dagaz.Model.smartTo) {
              if (this.isUniqueTo(actions[0][1][0])) {
                  result.push(actions[0][1][0]);
              }
          }
      } else {
      ...
      }
  }, this);
  return _.uniq(result);
}

На небольших играх, вроде шашек или шахмат, ошибка никак не проявлялась. Даже в начальной позиции Tenjiku shogi она не была заметна. Понадобились «убийцы производительности», чтобы её выявить. А для локализации ошибки очень пригодился модуль KPI, без которого я попросту не знал бы, где искать проблему. Сейчас ошибка исправлена и, в результате, весь код стал лучше.

eval = A * material-balance + B * mobility; где A >= 0, B >= 0, A + B = 1

При применении «одноходовых» алгоритмов, оценка мобильности творит чудеса. Тупая игра бота становится более «осмысленной». Есть правда один минус — для того чтобы оценить мобильность, необходимо построить (или хотя бы пересчитать) все возможные ходы за каждого из игроков, а это — очень дорогая операция. Поскольку мы, всё равно, вынуждены этим заниматься, хочется «выжать» из генерации ходов всё возможное, а также минимизировать количество таких операций.

Dagaz.AI.eval = function(design, params, board, player) {
  var r = 0;
  var cover = board.getCover(design);
  _.each(design.allPositions(), function(pos) {
      var defended = _.filter(cover[pos], function(p) {
          var piece = board.getPiece(p);
          if (piece === null) return false;
          return piece.player == player;
      });
      if (defended.length > 0) r++;
  });
  return r;
}

Разумеется, универсальный алгоритм построения «покрытия» пригоден далеко не для всех игр. Для Шахмат и Шашек он работает, а вот для Спока уже нет (поскольку, в этой игре фигуры могут беспрепятственно проходить через другие фигуры своего цвета). Это не должно смущать. Также как оценочную функцию и эвристики, алгоритм построения «покрытия» можно переопределять, используя имя Dagaz.Model.GetCover. Более того, даже в тех случаях, когда универсальный алгоритм работает, бывает полезно подумать о его кастомизации. Специализированные алгоритмы, как правило, более производительны.

Как только мы доходим до очередной цели, загружается следующий уровень, но расстановка фигур, при этом, берётся из предыдущего! Мы просто продолжаем с того места где остановились. Модуль, используемый для передачи позиции между уровнями, ценен сам по себе. Теперь, если включить лог браузера вовремя, можно вернуться к любой ранее пройденной позиции, практически в каждой из игр. Достаточно скопировать в URL строку, следующую в логе за надписью «Setup:». Это здорово помогает в отладке!

Кастомный «progressive levels» применим в играх со сложным жизненным циклом, таких как Kamisado. Эта игра не заканчивается при достижении одной из фигур последней линии! По правилам, фигура вошедшая в лагерь противника получает ранг «сумоиста» и дополнительные возможности, после чего, фигуры расставляются по оговоренному алгоритму и начинается следующий раунд. Теперь, Dagaz умеет это! Не сомневаюсь, возможность будет полезной при реализации многих традиционных манкал. А при очень большом желании, на его основе, вполне можно сделать какой нибудь простенький рогалик.

Dagaz.AI.eval = function(design, params, board, player) {
  var r = 0;
  var white = null;
  var black = [];
  for (var pos = 0; pos < design.positions.length - 3; pos++) {
      var piece = board.getPiece(pos);
      if (piece !== null) {
          if (piece.player == 1) {
              if (white === null) {
                  black.push(pos);
              } else {
                  r += MAXVAL / 2;
              }
          } else {
              white = pos;
          }
      }
  }
  if (white !== null) {
      r += white;
  }
  if (black.length == 2) {
      if ((black[0] + 1 == black[1]) && (black[1] + 1 == white)) {
          if (board.player == 1) {
              r = MAXVAL;
          } else {
              r = -MAXVAL;
          }
          if (player == 1) {
              r = -r;
          }
      }
  }
  return r;
}

Dagaz.AI.heuristic = function(ai, design, board, move) {
  var b = board.apply(move);
  return design.positions.length +
         Dagaz.AI.eval(design, ai.params, b, board.player) -
         Dagaz.AI.eval(design, ai.params, board, board.player);
}
...
AbAi.prototype.ab = function(ctx, node, a, b, deep) {
  node.loss = 0;
  this.expand(ctx, node);
  if (node.goal !== null) {
      return -node.goal * MAXVALUE;
  }
  if (deep <= 0) {
      return -this.eval(ctx, node);
  }
  node.ix = 0;
  node.m  = a;
  while ((node.ix < node.cache.length) && (node.m <= b) && 
         (Date.now() - ctx.timestamp < this.params.AI_FRAME)) {
      var n = node.cache[node.ix];
        if (_.isUndefined(n.win)) {
          var t = -this.ab(ctx, n, -b, -node.m, deep - 1);
          if ((t !== null) && (t > node.m)) {
              node.m = t;
              node.best = node.ix;
          }
        } else {
            node.loss++;
        }
      node.ix++;
  }
  return node.m;
}

var eval = Dagaz.AI.eval;

Dagaz.AI.eval = function(design, params, board, player) {
  var r = eval(design, params, board, board.player);
  var cover = board.getCover(design);
  var cnt = null;
  _.each(cover, function(list) {
      var cn = 0;
      _.each(list, function(pos) {
          var piece = board.getPiece(pos);
          if (piece !== null) {
              if (piece.player == board.player) {
                  r--;
              } else {
                  cn++;
              }
          }
      });
      if ((cnt === null) || (cnt < cn)) {
           cnt = cn;
      }
  });
  r += cnt * 3;
  if (board.player != player) {
      return -r;
  } else {
      return r;
  }
}

var done = function(design, board, player, pos, dir, trace, captured) {
  var p = design.navigate(player, pos, dir);
  if (p !== null) {
      var piece = board.getPiece(p);
      if (piece !== null) {
          if (piece.player == player) {
              _.each(trace, function(pos) {
                  if (_.indexOf(captured, pos) < 0) {
                      captured.push(pos);
                  }
              });
          } else {
              trace.push(p);
              done(design, board, player, p, dir, trace, captured);
              trace.pop();
          }
      }
  }
}

var capture = function(design, board, player, pos, dir, dirs, trace, captured) {
  var p = design.navigate(player, pos, dir);
  if (p !== null) {
      var piece = board.getPiece(p);
      if (piece !== null) {
          if (piece.player == player) {
              _.each(trace, function(pos) {
                  if (_.indexOf(captured, pos) < 0) {
                      captured.push(pos);
                  }
              });
          } else {
              trace.push(p);
              capture(design, board, player, p, dir, dirs, trace, captured);
              if (trace.length > 1) {
                  _.each(dirs, function(dir) {
                      var pos = design.navigate(player, p, dir);
                      if (pos !== null) {
                          var piece = board.getPiece(pos);
                          if ((piece !== null) && (piece.player != player)) {
                              trace.push(pos);
                              done(design, board, player, pos, dir, trace, captured);
                              trace.pop();
                          }
                      }
                  });
              }
              trace.pop();
          }
      }
  }
}

var checkCapturing = function(design, board, pos, player, captured) {
  var trace = [];
  capture(design, board, player, pos, 3, [0, 1], trace, captured);
  capture(design, board, player, pos, 1, [3, 2], trace, captured);
  capture(design, board, player, pos, 2, [0, 1], trace, captured);
  capture(design, board, player, pos, 0, [3, 2], trace, captured);
}

Dagaz.Model.GetCover = function(design, board) {
  if (_.isUndefined(board.cover)) {
      board.cover = [];
      _.each(design.allPositions(), function(pos) {
           board.cover[pos] = [];
           if (board.getPiece(pos) === null) {
               var neighbors = [];
               var attackers = [];
               _.each(design.allDirections(), function(dir) {
                   var p = design.navigate(1, pos, dir);
                   if (p !== null) {
                       var piece = board.getPiece(p);
                       if (piece !== null) {
                           neighbors.push(piece.player);
                           attackers.push(piece.player);
                       } else {
                           while (p !== null) {
                               piece = board.getPiece(p);
                               if (piece !== null) {
                                   attackers.push(piece.player);
                                   break;
                               }
                               p = design.navigate(1, p, dir);
                           }
                       }
                   }
               });
               if (neighbors.length > 1) {
                   var captured = [];
                   if ((_.indexOf(attackers, 1) >= 0) && 
                       (_.indexOf(neighbors, 2) >= 0)) {
                       checkCapturing(design, board, pos, 1, captured);
                   }
                   if ((_.indexOf(attackers, 2) >= 0) && 
                       (_.indexOf(neighbors, 1) >= 0)) {
                       checkCapturing(design, board, pos, 2, captured);
                   }
                   if (captured.length > 0) {
                       board.cover[pos] = _.uniq(captured);
                   }
               }
           }
      });
  }
  return board.cover;
}