31.01.2020 13:06
GlukKazan 17 1700 Источник
          Итак, технологии интересуют меня, так сказать, по необходимости: потому что всякая цивилизация включает и то, к чему общество стремилось, и то, чего никто не замышлял.

          Порой, и довольно часто, путь технологии открывал случай: искали же когда-то философский камень, а нашли фарфор. 
 
Станислав Лем.

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

Если вы посмотрите на исходный код Garbochess-JS (кстати, на КДПВ фотография Греты Гарбо, знаменитой актрисы, в честь которой проект получил своё название), то сможете заметить, что красота исходного кода — это последнее из того, что интересовало его автора. В тексте присутствуют глобальные переменные и прочие милые мелочи, добросовестно портированные из первоначального проекта.

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


Немного о производительности
Этот бот всё ещё слишком требователен к ресурсам. Я работаю над этим, но пока что, он и на компьютерах довольно задумчив, а на телефонах тормозит просто безобразно. Для меня это всё равно большой прогресс, поскольку он играет так, как мог бы играть человек. Все предыдущие мои попытки были весьма далеки от этого.

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

Не стоит устанавливать маленькие значения. Бот будет играть глупо. Я предупредил.

Можно заметить, что хотя эта игра (которую придумал Robert Price в 2001 году) похожа на Шахматы, оригинальный Garbochess с ней вряд ли бы справился. Это хорошая иллюстрация той задачи, что передо мной стояла. Мне следовало отделить алгоритм поиска наилучшего хода, от всего того, что специфично для конкретных игр. Для того, чтобы можно было использовать его в разных играх, разумеется. Для чего же ещё?

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


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

Бот, в этих случаях, бодро продолжал перебор вариантов, несмотря на то, что игра уже закончилась. Я довольно легко победил это, запретив дальнейшую генерацию ходов, после достижения цели игры. Другим отличием явилось то, что отсутствие возможности хода, в этой игре — это всегда поражение. В игре просто нет королей, незачем проверять, под шахом ли они. С этим удалось справиться ещё легче. Следующими на очереди были крупные формы.


Здесь стоит сделать небольшое теоретическое отступление
Я хочу рассказать о том, как работает Garbochess. Всё основано на минимаксном алгоритме с "альфа-бета-отсечением". В связи с этим, есть одна проблема — чтобы всё это работало, мы должны заранее знать, до какого уровня глубины будем опускаться. Предсказать это число, при условии ограничения на продолжительность поиска хода, довольно проблематично.

Либо мы выберем слишком маленькую глубину, неэффективно израсходовав выделенное время, либо опустимся слишком глубоко, потратим много времени и найдём, в результате, скорее всего, далеко не самый лучший ход. Чтобы победить эту проблему, было придумано итеративное углубление. Глубина поиска последовательно инкрементируется, начиная с единички и до тех пор, пока хватает времени.

Это работает, но для того чтобы не повторять одни и те же вычисления (очень дорогостоящие, кстати) снова и снова, необходимо использовать таблицу транспозиций. А поскольку это подразумевает поиск конкретной позиции в памяти по какому-то компактному ключу, без Зобрист-хэша тоже не обойтись! Я к тому, что в Garbochess всё взаимосвязано. Убери что-то одно и остальное просто не будет работать!

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

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

Другая причина зависаний крылась в том, что моя модель оказалась очень медленной
Раз в десять, примерно, медленнее модели шахматной игры, используемой Garbochess. Само собой, за универсальность надо платить, но не такой же ценой! Когда я начинал работу над проектом, я довольно плохо знал JavaScript и принял не очень удачное решение, использовать стековую машину, для генерации разрешённых правилами ходов.

То есть, описание Шахмат выглядит как-то так
Dagaz.Model.BuildDesign = function(design) {
    design.addDirection("w");  // 0
    design.addDirection("e");  // 1
    design.addDirection("s");  // 2
    design.addDirection("ne"); // 3
    design.addDirection("n");  // 4
    design.addDirection("se"); // 5
    design.addDirection("sw"); // 6
    design.addDirection("nw"); // 7

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

    design.addPosition("a8", [0, 1, 8, 0, 0, 9, 0, 0]);
    ...
    design.addPosition("h1", [-1, 0, 0, 0, -8, 0, 0, -9]);
    ...
    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,	1);	// empty?
    design.addCommand(0, ZRF.FUNCTION,	20);	// verify
    design.addCommand(0, ZRF.IN_ZONE,	0);	// last-rank
    design.addCommand(0, ZRF.FUNCTION,	0);	// not
    design.addCommand(0, ZRF.IF,	4);
    design.addCommand(0, ZRF.PROMOTE,	4);	// Queen
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.JUMP,	2);
    design.addCommand(0, ZRF.FUNCTION,	25);	// to
    design.addCommand(0, ZRF.FUNCTION,	28);	// end

    design.addCommand(1, ZRF.FUNCTION,	24);	// from
    design.addCommand(1, ZRF.PARAM,	0);	// $1
    design.addCommand(1, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(1, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.IN_ZONE,	1);	// third-rank
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.PARAM,	1);	// $2
    design.addCommand(1, ZRF.FUNCTION,	22);	// navigate
    design.addCommand(1, ZRF.FUNCTION,	1);	// empty?
    design.addCommand(1, ZRF.FUNCTION,	20);	// verify
    design.addCommand(1, ZRF.FUNCTION,	25);	// to
    design.addCommand(1, ZRF.FUNCTION,	28);	// end
    ...
    design.addPiece("Pawn", 0, 800);
    design.addMove(0, 0, [4], 1);
    design.addMove(0, 1, [4, 4], 1);
    design.addMove(0, 2, [7], 1);
    design.addMove(0, 2, [3], 1);
    design.addMove(0, 3, [1, 4, 4], 1);
    design.addMove(0, 3, [0, 4, 4], 1);
    ...
    design.setup("White", "Pawn", 48);
    ...
    design.setup("Black", "King", 4);
}

А должно бы выглядеть следующим образом
var step = function(ctx, params) {
    if (ctx.go(params, 0) && !ctx.isFriend()) {
        ctx.end();
    }
}

var pawnShift = function(ctx, params) {
    if (ctx.go(params, 0) && ctx.isEmpty()) {
        if (ctx.inZone(0)) {
            ctx.promote(4);
        }    
        ctx.end();
    }
}

var pawnLeap = function(ctx, params) {
    if (ctx.go(params, 0) && ctx.isEnemy()) {
        if (ctx.inZone(0)) {
            ctx.promote(4);
        }    
        ctx.end();
    }
}

var pawnJump = function(ctx, params) {
    if (ctx.go(params, 0) && 
        ctx.isEmpty() && 
        ctx.inZone(1) && 
        ctx.go(params, 0) && 
        ctx.isEmpty()) {
        ctx.end();
    }
}

var enPassant = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEnemy() &&
        ctx.isPiece(0)) {
        ctx.capture();
        if (ctx.go(params, 1)) {
            ctx.put();
            if (ctx.go(params, 1) &&
                ctx.isLastFrom()) {
                ctx.end();
            }
        }
    }
}

var jump = function(ctx, params) {
    if (ctx.go(params, 0) && 
        ctx.go(params, 1) && 
       !ctx.isFriend()) {
        ctx.end();
    }
}

var slide = function(ctx, params) {
    while (ctx.go(params, 0)) {
        if (ctx.isFriend()) break;
        ctx.end();
        if (!ctx.isEmpty()) break;
    }
}

var O_O = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEmpty() &&
        ctx.go(params, 0) &&
        ctx.isEmpty()) {
        ctx.put();
        if (ctx.go(params, 0) &&
            ctx.isFriend() &&
            ctx.isPiece(1)) {
            ctx.take();
            if (ctx.go(params, 1) &&
                ctx.go(params, 1)) {
                ctx.end();
            }
        }
    }
}

var O_O_O = function(ctx, params) {
    if (ctx.go(params, 0) &&
        ctx.isEmpty() &&
        ctx.go(params, 0) &&
        ctx.isEmpty()) {
        ctx.put();
        if (ctx.go(params, 0) &&
            ctx.isEmpty() &&
            ctx.go(params, 0) &&
            ctx.isFriend() &&
            ctx.isPiece(1)) {
            ctx.take();
            if (ctx.go(params, 1) &&
                ctx.go(params, 1) &&
                ctx.go(params, 1)) {
                ctx.end();
            }
        }
    }
}

games.model.BuildDesign = function(design) {
    design.addDirection("w");  // 0
    design.addDirection("e");  // 1
    design.addDirection("s");  // 2
    design.addDirection("ne"); // 3
    design.addDirection("n");  // 4
    design.addDirection("se"); // 5
    design.addDirection("sw"); // 6
    design.addDirection("nw"); // 7

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

    design.addPosition("a8", [0, 1, 8, 0, 0, 9, 0, 0]);
    ...
    design.addPosition("h1", [-1, 0, 0, 0, -8, 0, 0, -9]);
    ...
    design.addPiece("Pawn", 0, 2);
    design.addMove(0, pawnShift, [4], 0);
    design.addMove(0, pawnJump, [4], 0);
    design.addMove(0, pawnLeap, [7], 0);
    design.addMove(0, pawnLeap, [3], 0);
    design.addMove(0, enPassant, [1, 4], 0);
    design.addMove(0, enPassant, [0, 4], 0);
    ...
    design.setup("White", "Pawn", ["a2", "b2", "c2", "d2", "e2", "f2", "g2", "h2"]);
    design.setup("White", "Rook", ["a1", "h1"]);
    design.setup("White", "Knight", ["b1", "g1"]);
    design.setup("White", "Bishop", ["c1", "f1"]);
    design.setup("White", "Queen", ["d1"]);
    design.setup("White", "King", ["e1"]);
    design.setup("Black", "Pawn", ["a7", "b7", "c7", "d7", "e7", "f7", "g7", "h7"]);
    design.setup("Black", "Rook", ["a8", "h8"]);
    design.setup("Black", "Knight", ["b8", "g8"]);
    design.setup("Black", "Bishop", ["c8", "f8"]);
    design.setup("Black", "Queen", ["d8"]);
    design.setup("Black", "King", ["e8"]);
}

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

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

Стоит отметить, что далеко не всегда вопрос производительности стоит остро. Есть игры, играть в которые людям объективно сложно. Использование в таких играх алгоритмов не упускающих ни единой возможности приводит к совершенно убойным результатам:


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


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

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

Кстати, порядок просмотра узлов очень важен! Альфа-бета-отсечение работает гораздо лучше, если просматривать ходы в порядке от лучших к худшим. Сложность заключается в том, что по самому ходу бывает трудно судить о том, насколько он хорош. Разумеется, на эту тему была придумана куча эвристик.

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

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