Pull to refresh

Dagaz: Ищем таланты

Reading time 18 min
Views 3.1K
imageДелай с нами,
делай, как мы,
делай лучше нас!

Телепередача 80-ых


Должен признаться, я не очень хорош в разработке ботов. Уверен, есть люди, умеющие это делать гораздо лучше меня. И я бы очень хотел, чтобы такие люди присоединились к проекту. В плане материального поощрения, предложить я могу немногое. Dagaz был задуман как бесплатная и общедоступная альтернатива Zillions of Games. Сам я не против его коммерческого использования, просто пока не придумал, как это можно сделать.

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

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


Победить у компьютера в такой игре тяжело. И это не потому, что вы не умеете в неё играть! Я знаю человека, который умеет. Так вот, победил он далеко не с первой попытки и с очень небольшим перевесом. И это при том, что в ней используется далеко не самый удачный бот, гораздо более скромно проявляющий себя в других играх. Манкалы словно бы специально созданы для компьютеров! Но дело не только в них.


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


Также, имеются игры, с которыми боты вполне справляются, хотя могли бы играть гораздо лучше. Reversi — отличный тому пример. Уверен, человеку, хорошо играющему в эту игру, справиться с ботом будет не трудно, но для меня, например, это непосильная задача. Увы, с большей частью наиболее популярных игр мои боты не справляются совершенно. Вот список тех из них, для которых эта проблема наиболее актуальна:

  1. Шашки — в первую очередь "Русские", "Международные" и "Фризские". Боты с ними, в принципе, работают, но играют на уровне очень слабого новичка. Также очень интересны "Турецкие шашки", здесь боты играют ещё хуже. Самого пристального внимания заслуживают "Столбовые шашки" и "Ласка". Это действительно сложные и очень интересные игры!
  2. Шахматы и всё что на них похоже. В эти игры, все мои боты играют совершенно отвратительно. То же относится к "Китайским" и, в ещё большей степени, "Японским" шахматам. Здесь, я не говорю о "больших играх", разработка ботов для которых довольно специфична и в которые мало кто играет (я знаю таких людей). В первую очередь, для меня интересны наиболее популярные варианты. Шашматы также в приоритете. Их вообще стоит вынести в отдельную категорию, поскольку они взяли всё самое сложное «из обоих миров». В первую очередь, меня интересуют "Белорусские шахматы" и "Алтайская шатра". Любители совсем уж хардкорной экзотики могут опробовать свои силы на "Платформенных шахматах".
  3. Постановочные игры, прежде всего "Рендзю" и "Го". Это очень свежая тема, в том смысле, что я вот только что к ним приступил. Вообще, игры со сбросом фигур на доску (наравне с манкалами) — тема текущей итерации проекта, так что таких игр совсем скоро будет больше. И уже сейчас понятно, что некоторые из них (Го например) требуют особого подхода при разработке AI. А ведь есть и ещё более замороченные игры.
  4. В эту категорию попадают игры самые разнообразные. Здесь и детские "Джунгли" и французский "Агон" XVIII-го века. Игры большие и поменьше. Игры совершенно безумные. Всех их объединяет одно. Я не имею ни малейшего представления о том, как подступиться к разработке их AI. И, разумеется, я буду просто счастлив, если кто-то поможет довести до ума AI для моего "Спока".

Так каким же образом можно написать своего бота? В качестве самого первого шага, стоит скачать содержимое этого или этого репозитория к себе на компьютер (без чего писать, а тем более отлаживать, что либо будет тяжело). Хотя второй из перечисленных репозиториев является, по сути, релизным, никакой обфускации или минификации он, на текущий момент, не использует. Все приложения устроены предельно просто. Из html-файла последовательно загружаются несколько js-скриптов.

Примерно вот так
<!DOCTYPE html>
<html>
<head>
<META http-equiv="Content-Type" content="text/html; charset=utf-8">
<title>Turkish Dama</title>
</head>
<body>

<img id="Board" style="display:none" src="images/turkish.png">
<img id="WhiteMan" style="display:none" src="images/wman.png">
<img id="BlackMan" style="display:none" src="images/bman.png">
<img id="WhiteKing" style="display:none" src="images/wdamone.png">
<img id="BlackKing" style="display:none" src="images/bdamone.png">

<table id="Table" style="margin:auto; font-family:sans-serif; font-size:14px">
<tr><td>Traditional - Turkish <a href="turkish-dama-board.htm">no AI</a></td></tr>
	<tr style="height:548px; vertical-align:top">
		<td id="CanvasCell" style="width:548px">
			<canvas id="Canvas" width="548" height="548" style="cursor:default">Broken canvas...</canvas>
		</td>
		<td style="width:300px;">
			<div id="ScrollDiv" style="height:510px; overflow:auto">
				<img id="GlyphImage" />
				<p id="HelpText"></p>
				<p id="GameSession"></p>
			</div>
		</td>
	</tr>
	<tr>
		<td>
			<div style="height:100px; width:500px; margin-left:auto; margin-right:auto">
				<table>
					<tr id="PieceInfo" style="display:none">
						<td>
							<img id="PieceInfoImage" />
						</td>
						<td id="PieceInfoText"></td>
					</tr>
				</table>
			</div>
		</td>
	</tr>
</table>

<script src="https://cdnjs.cloudflare.com/ajax/libs/underscore.js/1.8.3/underscore-min.js"></script>
<script src="../common-scripts/dagaz.js"></script>
<script src="../common-scripts/zrf-model.js"></script>
<script src="../common-scripts/zobrist.js"></script>
<script src="../common-scripts/common-setup.js"></script>
<script src="../common-scripts/2d-view-v2.js"></script>
<script src="../common-scripts/move-list-v2.js"></script>
<script src="../common-scripts/maxmin-ai-v2.js"></script>
<script src="../common-scripts/sgf-parser.js"></script>
<script src="data/turkish.js"></script>
<script src="../common-scripts/sgf-ai.js"></script>
<script src="scripts/maximal-captures.js"></script>
<script src="scripts/turkish-dama.js"></script>
<script src="../common-scripts/app-v2.js"></script>

<script src="../common-scripts/analytics.js"></script>

</body>
</html>

Можно заметить, что из числа сторонних библиотек, я использую только очень для меня удобную Underscore (я не настаиваю на её использовании). Все скрипты ботов содержат в своём имени "-ai". Именно они нам сейчас и интересны. Но прежде чем двигаться дальше, стоит немного рассказать о том:

Что такое дизайн игры?
Прежде всего, Dagaz отделяет дизайн игры (ZrfDesign) от её состояния (ZrfBoard). Дизайн определяет топологию доски и правила перемещения фигур, а состояние — то какие фигуры и где находятся, в данный конкретный момент. Объект ZrfDesign создаётся один раз на всю игру, объектов ZrfBoard может создаваться (в том числе, для нужд ботов) неограниченное количество. В начале игры, дизайн инициализируется вызовом функции Dagaz.Model.BuildDesign:

turkish-dama.js
Dagaz.Model.BuildDesign = function(design) {
    design.checkVersion("z2j", "2");
    design.checkVersion("zrf", "2.0");
    design.checkVersion("animate-captures", "false");
    design.checkVersion("smart-moves", "true");
    design.checkVersion("maximal-captures", "true");

    design.addDirection("w");
    design.addDirection("e");
    design.addDirection("s");
    design.addDirection("n");

    design.addPlayer("White", [1, 0, 3, 2]);
    design.addPlayer("Black", [0, 1, 3, 2]);

    design.addPosition("a8", [0, 1, 8, 0]);
    design.addPosition("b8", [-1, 1, 8, 0]);
    ...
    design.addPosition("h1", [-1, 0, 0, -8]);

    design.addZone("promotion", 1, [0, 1, 2, 3, 4, 5, 6, 7]);
    design.addZone("promotion", 2, [56, 57, 58, 59, 60, 61, 62, 63]);

    design.addCommand(0, ZRF.FUNCTION,	24);	// from
    design.addCommand(0, ZRF.PARAM,	0);	// $1
    design.addCommand(0, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(0, ZRF.FUNCTION,	2);	// enemy?
    design.addCommand(0, ZRF.FUNCTION,	20);	// verify
    design.addCommand(0, ZRF.FUNCTION,	26);	// capture
    design.addCommand(0, ZRF.PARAM,	1);	// $2
    design.addCommand(0, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(0, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(0, ZRF.FUNCTION,	20);	// verify
    design.addCommand(0, ZRF.IN_ZONE,	0);	// promotion
    design.addCommand(0, ZRF.IF,	4);
    design.addCommand(0, ZRF.MODE,	0);	// jump-type
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.JUMP,	3);
    design.addCommand(0, ZRF.PROMOTE,	1);	// King
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.FUNCTION,	28);	// end

    ...
    design.addPriority(0);			// jump-type
    design.addPriority(1);			// normal-type

    design.addPiece("Man", 0, 1);
    design.addMove(0, 0, [3, 3], 0);
    design.addMove(0, 0, [0, 0], 0);
    design.addMove(0, 0, [1, 1], 0);
    design.addMove(0, 1, [3], 1);
    design.addMove(0, 1, [0], 1);
    design.addMove(0, 1, [1], 1);

    ...
    design.setup("White", "Man", 48);
    design.setup("White", "Man", 49);
    ...
}

Весь этот код генерируется из zrf-файла автоматически и трогать его не надо. На что здесь стоит обратить внимание? Вызовы addPlayer определяют игроков и, в простейшем случае, очерёдность их ходов (на второй аргумент функции пока отвлекаться не будем). Функция addPosition определяет единичную позицию на доске, а addDirection — направление. В самом конце, вызовами setup задаётся начальная расстановка фигур.

Позиции и направления — это просто два линейных массива, индексируемых с нуля. Таким образом, положение фигуры на доске всегда определяется целым не отрицательным числом. Такое числовое значение, в любой момент, можно превратить в имя позиции, используя функцию Dagaz.Model.posToString. Обратное преобразование выполняет Dagaz.Model.stringToPos.

С направлениями немного сложнее. Также как и позиции, они кодируются целыми не отрицательными числами (в соответствии с порядком вызова addDirection при конфигурировании дизайна игры). Получить код направления из имени можно использовав метод getDirection объекта design. Метод allDirections позволяет получить массив всех доступных направлений (для получения списка всех позиций имеется аналогичный метод allPositions). Но что такое само направление?

Помните второй аргумент addPosition? Фактически, это массив смещений внутри линейного списка всех позиций, по одному для каждого направления. Если соответствующее значение равно нулю, двигаться в указанном направлении из этой позиции запрещено (нет такого направления). Сама навигация осуществляется следующим методом:

ZrfDesign.prototype.navigate = function(player, pos, dir) {
  if (!_.isUndefined(this.players[player])) {
      dir = this.players[player][dir];
  }
  if (this.positions[pos][dir] != 0) {
      return + pos + this.positions[pos][dir];
  } else {
      return null;
  }
}

Как видите, достаточно просто прибавить смещение к индексу позиции или вернуть null, если такое перемещение запрещено. Все перемещения должны формулироваться в «системе координат» первого игрока. Это означает, что например в Шахматах, чёрные пешки, также как и белые движутся «на север». За правильную перекодировку направлений отвечает второй аргумент метода addPlayer.

Осталось рассказать об игровых зонах. Это просто списки «особых» позиций на доске, определяемые методом addZone. Зоны индивидуальны для каждого игрока. Это означает, что одна и та же (по имени) зона, для разных игроков, может содержать различные позиции. Для проверки нахождения позиции в заданной зоне используется метод inZone. Все определения перечисленных функций можно найти в исходном тексте модуля zrf-model.js

Таким образом, у нас есть дизайн, не изменяемый в процессе игры, и набор игровых состояний, кодирующих расстановку фигур, на момент начала каждого хода, но возникает законный вопрос:

Как изменять игровое состояние?
Вообще говоря, никак, потому что изменять его непосредственно вы никогда не должны! Конечно, в zrf-model имеется метод setPiece, позволяющий поместить фигуру на доску, но вызывать его напрямую не надо! Игровое состояние иммутабельно. Новое состояние создаётся из старого применением к нему хода (объекта типа ZrfMove), методом apply.

Откуда берутся эти самые ходы? Они генерируются самим игровым состоянием при вызове метода generate. При этом, дизайн и расширения игры следят за тем, чтобы в список сформированных ходов попали только ходы, допустимые правилами игры! Также как и игровое состояние, ходы не должны изменяться разработчиком бота непосредственно, но можно в любой момент, выполнить генерацию допустимых ходов, получить новое состояние игры, применив ход и, разумеется, читать любую информацию, содержащуюся в этих объектах.

Итак, чем нас может порадовать ZrfBoard? Прежде всего, мы всегда можем узнать, чей сейчас ход, обратившись к члену player (в отличии от позиций и направлений, игроки в Dagaz индексируются начиная с единицы). Целочисленный член zSign содержит значение zobrist-хэша идентифицирующее расстановку фигур. Метод getPiece позволяет получить фигуру, находящуюся по указанной позиции (принимается числовой индекс). Если метод возвращает null, значит опрашиваемая позиция пуста.

Сама фигура (ZrfPiece) содержит два члена: type — тип фигуры (числовое значение индексируемое с нуля) и владельца — player. Кроме того, объекты ZrfPiece могут содержать значения атрибутов (индексируемые числовыми ключами). Метод getValue позволяет получить такое значение, указав индекс. Как обычно, null означает отсутствие искомого значения. Допускается хранение значений как строкового, так и числового типов.

Осталось разобраться с ходами (ZrfMove). Это самая сложная часть. Во многих играх, таких как Шахматы и Шашки, допускаются «сложные» ходы, включающие в себя одновременное перемещение нескольких фигур, последовательное взятие фигур, одну за другой и т.п. Поскольку ход переводит игру из одного непротиворечивого состояние в другое, все эти действия кодируются в рамках одного хода и применяются атомарно (всё или ничего).

Последовательность всех выполняемых действий содержится в массиве actions. Каждое элементарное действие представляет собой четырёхэлементный массив, содержащий следующие элементы:

0 — Массив начальных позиций перемещения
1 — Массив конечных позиций перемещения
2 — Массив фигур (объектов типа ZrfPiece) помещаемых на доску
3 — Целое число, содержащее номер частичного хода, в рамках составного

Каждый из перечисленных массивов, обычно состоит из одного элемента. Массивы большего размера используются редко, для недетерминированных ходов, применяемых в некоторых играх. Номер частичного хода определяет очерёдность выполнения действий. Если для двух действий это значение одинаково, они выполняются одновременно. В противном случае, первым выполняется действие с меньшим номером частичного хода. Используются три разновидности действий:

  1. Взятие фигуры — нулевой элемент заполнен, первый элемент содержит null
  2. Сброс (добавление фигуры на доску) — нулевой элемент равен null, заполнены первый и второй элементы
  3. Перемещение — заполнены нулевой и первый элементы, также может быть заполнен второй элемент (если фигура превращается в процессе выполнения хода)

Метод toString позволяет получить текстовое описание (нотацию) хода. Иногда это здорово помогает в процессе отладки.

Вся игра представляет собой, по сути, повторяющийся цикл, состоящий из генерации допустимых ходов и последующего применения их к игровому состоянию. Итерации повторяются (с чередованием ходов игроков, заданным правилами игры) до тех пор, пока не произойдёт одно из следующих событий.

  1. Список ходов, сгенерированных одним из игроков, оказывается пуст (в зависимости от игры, это может расцениваться как поражение, ничья или даже победа игрока)
  2. Функция Dagaz.Model.checkGoals возвращает значение, отличное от null

Второй пункт позволяет запрограммировать корректное завершение для практически любой игры.

Вот, например, как это выглядит для Reversi
var isValid = function(design, board, player, pos) {
  for (var dir = 0; dir < design.dirs.length; dir++) {
       var p = design.navigate(player, pos, dir);
       if (p === null) continue;
       var piece = board.getPiece(p);
       if ((piece === null) || (piece.player == player)) continue;
       while (p !== null) {
           p = design.navigate(player, p, dir);
           if (p !== null) {
               piece = board.getPiece(p);
               if (piece === null) break;
               if (piece.player == player) return true;
           }
       }
  }
  return false;
}

var checkGoals = Dagaz.Model.checkGoals;

Dagaz.Model.checkGoals = function(design, board, player) {
  var fc = 0; var ec = 0;
  var positions = [];
  _.each(design.allPositions(), function(pos) {
      var piece = board.getPiece(pos);
      if (piece === null) {
          positions.push(pos);
      } else {
          if (piece.player == player) {
              fc++;
          } else {
              ec++;
          }
      }
  });
  var f = true;
  _.each(positions, function(pos) {
      if (f) {
          if (isValid(design, board, player, pos)) f = false;
          if (isValid(design, board, design.nextPlayer(player), pos)) f = false;
      }
  });
  if (f) {
      if (fc == ec) return 0;
      if (fc > ec) {
          return 1;
      } else {
          return -1;
      }
  }
  return checkGoals(design, board, player);
}

Обратите внимание на функцию isValid. При помощи неё, определяется наличие разрешённых правилами игры ходов и только в том случае, если ни один из игроков не может сделать такой ход, определяется победитель (просто тот игрок, у которого больше фигур на доске).

Функция checkGoals — неотъемлемая часть дизайна игры. На момент разработки бота, она уже определена и вполне достаточно просто уметь её вызывать, для корректного определения позиций, завершающих игру. Функция может быть вызвана для любого игрового состояния и принимает три аргумента: дизайн игры, текущее состояние игры и идентификатор игрока, с точки зрения которого оценивается позиция. Результат вызова интерпретируется следующим образом:

1 — победа игрока player
-1 — поражение игрока player
0 — ничья
null — не терминальная позиция (игра может быть продолжена)

Ещё одна важная вещь, о которой необходимо знать, до того как приступать к разработке каких либо ботов — это оценочная функция. Я уже довольно подробно писал об этом раньше, но ещё раз повторюсь. Задачей оценочной функции является числовая оценка позиции, с точки зрения одного из игроков (чем больше значение — тем лучше позиция).

Вот как она может выглядеть
Dagaz.AI.eval = function(design, params, board, player) {
  var r = 0;
  _.each(design.allPositions(), function(pos) {
      var piece = board.getPiece(pos);
      if (piece !== null) {
          var v = design.price[piece.type];
          if (piece.player != player) {
              v = -v;
          }
          r += v;
      }
  });
  return r;
}

Обычно (но не обязательно) оценка позиции, с точки зрения одного из игроков, совпадает с оценкой той же позиции его противником, взятой с противоположным знаком. Без соблюдения этого условия не будут работать, например, минимаксные алгоритмы. Существуют игры (например те, в которых участвует более двух игроков), в которых соблюсти это условие не представляется возможным. Также, есть игры, в которых использование минимакса затруднительно, по другим причинам (например, сложная очерёдность передачи хода).


В этих случаях, на первый план выходят эвристики (при использовании минимакса они тоже очень полезны, поскольку позволяют предварительно отсортировать возможные ходы по их потенциальной «силе»). В отличии от оценочной функции, эвристика оценивает сам ход, а не позицию на доске после его выполнения. Эвристика может быть как очень сложной, так и максимально простой.

Такой, например
Dagaz.AI.heuristic = function(ai, design, board, move) {
  return move.actions.length;
}

В тибетской игре "Минг-Манг", чем больше мы берём фигур противника за ход, тем лучше. Поскольку ход в «Минг-Манг» состоит из перемещения своей фигуры и произвольного количества взятий, для того, чтобы получить хорошую эвристику, достаточно просто оценить количество элементов в массиве move.actions (о структуре хода в Dagaz я рассказывал выше).

Далеко не для всех игр построить качественную оценочную функцию бывает легко. В особенно сложных случаях хорошо помогают «маленькие хитрости». Про «покрытие», очень полезное в играх шахматного типа, я уже писал ранее. Другой возможностью является хранение вспомогательных значений в атрибутах фигур.


В "Рендзю" наиболее важным аспектом является наличие на доске «троек» и «четвёрок», ориентированных по четырём различным направлениям. Эта информация используется не только AI, но и для выявления ситуаций всевозможных «фолов» (длинных рядов и «вилок»), запрещённых для первого игрока, а также для определения завершения игры (5 камней «в ряд»). Между тем, поиск таких конфигураций на доске — задача довольно таки ресурсоёмкая.

С другой стороны, если мы уже храним счётчики с длинами рядов, для всех ранее поставленных на доску камней, задача обновления этих счётчиков, при добавлении нового камня, становится тривиальной. Чуть более сложен (но вполне реализуем) подсчёт количества "дамэ" для групп камней, в играх семейства "Го". В любом случае, гораздо проще хранить эти значения, чем вычислять снова и снова, каждый раз, когда они понадобятся. Конечно, эти мелочи, сами по себе, не превратят бота в AlphaGo, но могут сделать его разработку гораздо более комфортной.

Вот мы и подошли к разговору о ботах. Задача бота, в Dagaz — выбор наилучшего (в каком-то смысле) хода из списка всех допустимых ходов, сгенерированных игровым состоянием. Вот как выглядит самый простой бот:

random-ai.js
(function() {

function RandomAi(params) {
  this.params = params;
  if (_.isUndefined(this.params.rand)) {
      this.params.rand = _.random;
  }
}

var findBot = Dagaz.AI.findBot;

Dagaz.AI.findBot = function(type, params, parent) {
  if ((type == "random") || (type == "solver")) {
      return new RandomAi(params);
  } else {
      return findBot(type, params, parent);
  }
}

RandomAi.prototype.setContext = function(ctx, board) {
  ctx.board  = board;
}

RandomAi.prototype.getMove = function(ctx) {
  var moves = Dagaz.AI.generate(ctx, ctx.board);
  if (moves.length == 0) {      
      return { done: true, ai: "nothing" };
  }
  if (moves.length == 1) {
      return { done: true, move: moves[0], ai: "once" };
  }
  var ix = this.params.rand(0, moves.length - 1);
  return {
      done: true,
      move: moves[ix],
      ai:   "random"
  };
}

})();

Да-да, просто выбор случайного хода из всех доступных. Кстати, не надо думать, что это совершенно бесполезный бот. У него есть свои, очень важные, применения.

Уже по этому листингу можно понять следующее:

  1. Любой бот должен «встроиться» в цепочку вызовов Dagaz.AI.findBot (для того, чтобы контроллер смог его найти. Поиск бота осуществляется по его типу. Основных типов три: «opening», «common» и «random». Найденные боты также выстраиваются «в цепочку». Это делается для того, чтобы первым наилучший ход искал бот, предназначенный для дебютов (sgf-ai, например), вслед за ним отрабатывал главный бот (maxmin-ai, в большинстве случаев), а уж если он ничего не нашёл (счёл все ходы слишком плохими), в игру включался random-ai, просто чтобы сходить хотя бы как нибудь. Для решения головоломок используется специальный тип бота "solver".
  2. Для каждого игрока, с которым работает бот, создаётся свой «контекст» (это делается для того, чтобы один бот мог обслуживать одновременно несколько различных игроков). Внутри контекста можно хранить любые данные, разделяемые между последовательными обращениями к боту (например, дерево состояний игры). Перед запросом у бота «наилучшего» хода, контроллер передаёт боту текущее состояние игры (вызовом метода setContext).
  3. Ход у бота запрашивается методом getMove. Метод возвращает хэш, содержащий поле move (искомый ход). Также, если бот завершил поиск хода, он должен передать true в поле done возвращаемого хэша. В настоящее время эта функциональность не используется, но подразумевается, что контроллер может запросить у бота ход несколько раз подряд. В случае, если бот не успел найти наилучший ход за отведённое время, он может вернуть лучший ход из уже рассмотренных, но не устанавливать поле done, чтобы контроллер продолжил опрос.

Посмотрим на чуть более сложный бот:

heuristic-ai.js
(function() {

Dagaz.AI.NOISE_FACTOR = 10;

function Ai(params, parent) {
  this.params = params;
  this.parent = parent;
  if (_.isUndefined(this.params.NOISE_FACTOR)) {
      this.params.NOISE_FACTOR = Dagaz.AI.NOISE_FACTOR;
  }
}

var findBot = Dagaz.AI.findBot;

Dagaz.AI.findBot = function(type, params, parent) {
  if ((type == "heuristic") || (type == "common") || (type == "1") || (type == "2")) {
      return new Ai(params, parent);
  } else {
      return findBot(type, params, parent);
  }
}

Ai.prototype.setContext = function(ctx, board) {
  if (this.parent) {
      this.parent.setContext(ctx, board);
  }
  ctx.board     = board;
  ctx.timestamp = Date.now();
}

Ai.prototype.getMove = function(ctx) {
  ctx.board.moves = Dagaz.AI.generate(ctx, ctx.board);
  if (ctx.board.moves.length == 0) {
      return { done: true, ai: "nothing" };
  }
  var nodes = _.chain(ctx.board.moves)
     .map(function(m) {
          return {
             move:   m,
             weight: Dagaz.AI.heuristic(this, ctx.design, ctx.board, m)
          };
      }, this)
     .filter(function(n) {
          return n.weight >= 0;
      }).value();
  if (this.params.NOISE_FACTOR > 1) {
      _.each(nodes, function(n) {
         n.weight *= this.params.NOISE_FACTOR;
         n.weight += _.random(0, this.params.NOISE_FACTOR - 1);
      }, this);
  }
  if (nodes.length > 0) {
      nodes = _.sortBy(nodes, function(n) {
           return -n.weight;
      });
      return {
           done: true,
           move: nodes[0].move,
           time: Date.now() - ctx.timestamp,
           ai:  "heuristic"
      };
  }
  if (this.parent) {
      return this.parent.getMove(ctx);
  }
}

})();

Это не столько «искусственный интеллект», сколько «искусственные инстинкты». Просто выбор хода с максимальной эвристикой, без какого бы ты ни было использования оценочной функции. Этот бот быстр и прозрачен в отладке, но на этом его достоинства заканчиваются. Глубину его интеллекта вы можете оценить по текущему уровню игры "Рендзю", "Войны вирусов" и особенно "Атари Го". В идеале, хотелось бы добиться нормальной работы чего нибудь вроде этого (моя реализация минимакса с альфа-бета отсечением пока что, увы, не работающая).

Говоря об отладке ботов, стоит отметить, что дело это кропотливое, нудное и к особому веселью не располагающее. Любой инструмент облегчающий этот процесс безусловно стоит использовать. В первую очередь это касается модуля common-setup. Достаточно добавить его в список загружаемых скриптов и в логе (как включить лог в браузере, думаю объяснять не надо), после выполнения каждого хода, начнут появляться записи примерно такого вида:

Setup: ?setup=+19;0:1=4;+2;0:1=4;+5;0:2=3;+7;0:1=2;0:2=5;+7;0:2=5;+29; 

Добавив эту запись к адресной строки браузера (вот так) можно воссоздать соответствующую позицию немедленно, без нудного воспроизведения предшествующих ходов. А при некоторой сноровке, можно навостриться читать эту нотацию и даже редактировать её непосредственно в адресной строке.

Другая полезная возможность предоставляется контроллером. Если в htm-файле заменить app-v2 на app-auto, можно заставить ботов сражаться друг с другом, не отвлекаясь на кликанье по доске мышью. Помните странные числовые типы ботов в heuristic-ai.js?

...
Dagaz.AI.findBot = function(type, params, parent) {
  if ((type == "heuristic") || (type == "common") || 
      (type == "1") || (type == "2")) {
      return new Ai(params, parent);
  } else {
      return findBot(type, params, parent);
  }
}
...

Бот с типом "1" будет загружаться для первого игрока, а с типом "2" для второго. Это конечно не autoplay из Axiom, но тоже штука весьма полезная. Кроме того, в отличии от autoplay, только двумя игроками app-auto не ограничивается.

Модуль debug-ai ещё один полезный инструмент, который стоит взять на вооружение. Иногда, при отладке логики игры, бывает недостаточно просто воспроизвести позицию. В таких случаях, бывает необходимо, чтобы бот воспроизводил ходы по заданному списку и debug-ai умеет это делать. Именно с его помощью я отлаживал "Апокалипсис".

Ну вот, в общем-то и вся премудрость. Как я уже сказал, дело нудное, но не сверхъестественное. И я буду рад, если в этом деле ко мне кто нибудь присоединиться. Кстати, буквально два дня назад на почту проекта пришло первое письмо. Garrick Wells здорово помог мне с дебютами для Micro Shogi. Попутно, я обнаружил и исправил серьёзный баг, затронувший эту и несколько других игр. Это именно та форма сотрудничества, к которой я стремлюсь.
Tags:
Hubs:
+9
Comments 12
Comments Comments 12

Articles