Путеводитель разработчика по Garbo-боту25.06.2021 11:17

cwgy1lbpqtsguk8c-m0q8tjkx9e.pngу него есть два больших преимущества
…
Во-первых, он дешевле;, а во-вторых, на обложке у него большими веселыми буквами напечатан дружеский совет: Don«t panic!

Дуглас Адамс

Из всего многообразия шахматных движков, Garbochess я выбрал по двум причинам: для него есть понятный JavaScript-код и он неплохо играет в Шахматы. Мне совсем не требовался гроссмейстерский уровень! Если бот играет слишком сильно, то обычных людей (вроде меня) это только отпугивает. Требовалась лишь игра достаточно разумная, похожая на игру человека, без глупых раздражающих ошибок и Garbochess мне всё это дал. К сожалению, как и большинство других шахматных движков, он играл только в одну игру — традиционные Шахматы. Именно это мне и предстояло исправить.
В прошлый раз я рассказал о том как подключил шахматного бота к своему DagazServer-у. Разумеется, это было только начало. Моей целью было использование алгоритмов Garbochess в других играх, если не во всех, то по крайней мере, в шахматоподобных. Прежде всего, в моём распоряжении было несколько игр на малых досках, таких как «Шахматы Гарднера».

45rcgxwjkp1qm5kpprmwxsuwv_u.png

Здесь всё получилось довольно просто. Прежде всего, изменения касались размеров доски. Текущее её состояние хранится в массиве g_board, размером в 256 байт. Это немного больше чем 8×8 клеток и сделано так для того, чтобы вертикальную и горизонтальную координаты можно было кодировать старшим и младшим полубайтом индекса соответственно. Такое представление ускоряет навигацию по доске, а большая скорость означает большее количество узлов (и соответственно лучшую игру) которое удастся проверить за отведённое время.
Вот как выглядит это преобразование 
function MakeSquare(row, column) {
    return ((row + 2) << 4) | (column + 4);
}

Обратите внимание на константы, прибавляемые к координатам, позволяющие разместить рабочую область «в центре» массива. В самом начале InitializeFromFen, весь массив g_board заполняется значением 0×80, позволяющим ускорить проверку выхода за границы доски. Рабочая область формируется при разборе FEN-нотации начальной позиции. Поскольку размеры строк и столбцов в передаваемом описании меньше, то и доска получается требуемого размера.
Что касается содержимого массива, фигуры кодируются следующим образом 
var colorBlack  = 0x10;
var colorWhite  = 0x08;

var pieceEmpty  = 0x00;
var piecePawn   = 0x01;
var pieceKnight = 0x02;
var pieceBishop = 0x03;
var pieceRook   = 0x04;
var pieceQueen  = 0x05;
var pieceKing   = 0x06;

Таким образом, все проверки на тип фигуры выполняются по маске 0×07. Кодирование цвета фигур выглядит немного избыточным, но это сделано для того, чтобы отличать пустые позиции от занятых. Значение colorWhite используется еще и для кодирования очерёдности хода, хранящейся в g_toMove. Здесь всё просто: 8 кодирует ход белых, 0 — чёрных. Вот так ход переключается: 
var otherColor = 8 - g_toMove;
...
g_toMove = otherColor;

Далее, следовало позаботиться о том, чтобы пешка превращалась на правильной горизонтали. Кстати, набор фигур, доступных для превращения, пришлось ограничить флагами, поскольку, часто, на малых досках используются не все фигуры.
Аналогичные флаги используются для ряда других действий 
var moveflagEPC = 0x2 << 16;
var moveflagCastleKing = 0x4 << 16;
var moveflagCastleQueen = 0x8 << 16;
var moveflagPromotion = 0x10 << 16;
var moveflagPromoteKnight = 0x20 << 16;
var moveflagPromoteQueen = 0x40 << 16;
var moveflagPromoteBishop = 0x80 << 16;

+var g_flags = moveflagPromoteKnight | moveflagPromoteQueen | moveflagPromoteBishop | moveflagCastleKing | moveflagCastleQueen | moveflagEPC;

function MovePawnTo(moveStack, start, square) {
    var row = square & 0xF0;
+    var delta = (8 - g_height) << 4;
-    if ((row == 0x90 || (row == 0x20))) {
+    if ((row == (0x90 - delta) || (row == 0x20))) {
+        if (g_flags & moveflagPromoteQueen) {
            moveStack[moveStack.length] = GenerateMove(start, square, 
            moveflagPromotion | moveflagPromoteQueen);
+        }
+        if (g_flags & moveflagPromoteKnight) {
            moveStack[moveStack.length] = GenerateMove(start, square, 
            moveflagPromotion | moveflagPromoteKnight);
+        }
+        if (g_flags & moveflagPromoteBishop) {
            moveStack[moveStack.length] = GenerateMove(start, square, 
            moveflagPromotion | moveflagPromoteBishop);
+        }
        moveStack[moveStack.length] = GenerateMove(start, square, 
        moveflagPromotion);
    }
    else {
        moveStack[moveStack.length] = GenerateMove(start, square, 0);
    }
}

Как можно заметить, для ладьи флаг не предусмотрен: 
if (move & moveflagPromotion) {
    if (move & moveflagPromoteBishop) result += "=B";
    else if (move & moveflagPromoteKnight) result += "=N";
    else if (move & moveflagPromoteQueen) result += "=Q";
    else result += "=R";
}

Осталась самая малость. Сила фигуры зависит от её расположения на доске. В Garbochess это кодируется специальными таблицами:
Я не стал с этим заморачиваться 
var pawnAdj =
[
    0,  0,    0,   0,   0,   0,   0,     0,
  -25, 105, 135, 270, 270, 135, 105,   -25,
  -80,   0,  30, 176, 176,  30,   0,   -80,
  -85,  -5,  25, 175, 175,  25,  -5,   -85,
  -90, -10,  20, 125, 125,  20,  -10,  -90,
  -95, -15,  15,  75,  75,  15,  -15,  -95, 
 -100, -20,  10,  70,  70,  10,  -20, -100, 
    0,   0,   0,   0,   0,   0,    0,    0
];

var knightAdj =
    [-200, -100, -50, -50, -50, -50, -100, -200,
     -100,    0,   0,   0,   0,   0,    0, -100,
      -50,    0,  60,  60,  60,  60,    0,  -50,
      -50,    0,  30,  60,  60,  30,    0,  -50,
      -50,    0,  30,  60,  60,  30,    0,  -50,
      -50,    0,  30,  30,  30,  30,    0,  -50,
     -100,    0,   0,   0,   0,   0,    0, -100,
     -200,  -50, -25, -25, -25, -25,  -50, -200
     ];

var bishopAdj =
    [ -50,-50,-25,-10,-10,-25,-50,-50,
      -50,-25,-10,  0,  0,-10,-25,-50,
      -25,-10,  0, 25, 25,  0,-10,-25,
      -10,  0, 25, 40, 40, 25,  0,-10,
      -10,  0, 25, 40, 40, 25,  0,-10,
      -25,-10,  0, 25, 25,  0,-10,-25,
      -50,-25,-10,  0,  0,-10,-25,-50,
      -50,-50,-25,-10,-10,-25,-50,-50
     ];

var rookAdj =
    [ -60, -30, -10, 20, 20, -10, -30, -60,
       40,  70,  90,120,120,  90,  70,  40,
      -60, -30, -10, 20, 20, -10, -30, -60,
      -60, -30, -10, 20, 20, -10, -30, -60,
      -60, -30, -10, 20, 20, -10, -30, -60,
      -60, -30, -10, 20, 20, -10, -30, -60,
      -60, -30, -10, 20, 20, -10, -30, -60,
      -60, -30, -10, 20, 20, -10, -30, -60
     ];

var kingAdj =
    [  50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
       50, 150, -25, -125, -125, -25, 150, 50,
      150, 250, 75,   -25,   -25,  75, 250, 150
     ];

var emptyAdj =
    [0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     0, 0, 0, 0, 0, 0, 0, 0, 
     ];

pieceSquareAdj[piecePawn] = MakeTable(
((g_width == 8) && (g_height == 8)) ? pawnAdj : emptyAdj);
pieceSquareAdj[pieceKnight] = MakeTable(
((g_width == 8) && (g_height == 8)) ? knightAdj : emptyAdj);
pieceSquareAdj[pieceBishop] = MakeTable(
((g_width == 8) && (g_height == 8)) ? bishopAdj: emptyAdj);
pieceSquareAdj[pieceRook] = MakeTable(
((g_width == 8) && (g_height == 8)) ? rookAdj : emptyAdj);
pieceSquareAdj[pieceQueen] = MakeTable(emptyAdj);
pieceSquareAdj[pieceKing] = MakeTable(
((g_width == 8) && (g_height == 8)) ? kingAdj: emptyAdj);

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

Следующим шагом стали игры с изменёнными правилами перемещения фигур. Персидский Шатрандж очень похож на современные шахматы. Это, по всей видимости, первая игра, в которой появились понятия шаха и мата. Основные отличия связаны с тем как ходят слон и ферзь. Кстати, из-за отсутствия дальнобойных диагональных фигур, Шатрандж — очень неторопливая игра. Часто, дебютная фаза пропускалась и игроки начинали игру с оговоренных табий, вроде вот такой:
a9jnq0wxdfvhw0_hb-8nexbeilu.png

Прежде всего, в Шатрандже оказался ненужным весь код, связанный с рокировками, прыжками пешек и взятием на проходе. Поскольку пат в Шатрандже также считается победой, проверки на завершение игры также удалось упростить. Изменились правила превращения. В Шатрандже, пешка умеет превращаться лишь в слабого ферзя.
Изменилась оценка позиции
Это касается как стоимости фигур: 
-var materialTable = [0, 800, 3350, 3450, 5000, 9750, 600000];
+var materialTable = [0, 800, 3350, 1500, 5000, 2500, 600000];

так и их мобильности: 
// Bishop mobility
mob = -4;
pieceIdx = (color | 3) << 4;
from = g_pieceList[pieceIdx++];
while (from != 0) {
    mob += mobUnit[g_board[from + 30]];
    mob += mobUnit[g_board[from + 34]];
    mob += mobUnit[g_board[from - 30]];
    mob += mobUnit[g_board[from - 34]];
    from = g_pieceList[pieceIdx++];
}
result += 44 * mob;
...
// Queen mobility
mob = -2;
pieceIdx = (color | 5) << 4;
from = g_pieceList[pieceIdx++];
while (from != 0) {
    mob += mobUnit[g_board[from + 15]];
    mob += mobUnit[g_board[from + 17]];
    mob += mobUnit[g_board[from - 15]];
    mob += mobUnit[g_board[from - 17]];
    from = g_pieceList[pieceIdx++];
}
result += 22 * mob;

Основные изменения связаны с перемещением фигур 
// Bishop quiet moves
pieceIdx = (g_toMove | 3) << 4;
from = g_pieceList[pieceIdx++];
while (from != 0) {
    to = from + 30; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from + 34; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from - 30; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from - 34; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    from = g_pieceList[pieceIdx++];
}
...
// Queen quiet moves
pieceIdx = (g_toMove | 5) << 4;
from = g_pieceList[pieceIdx++];
while (from != 0) {
    to = from + 15; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from + 17; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from - 15; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    to = from - 17; 
    if (g_board[to] == 0) 
        moveStack[moveStack.length] = GenerateMove(from, to);
    from = g_pieceList[pieceIdx++];
}

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

Но одно дело перемещения, а совсем другое — проверка на бой фигур (и шах, соответственно)! Вы же помните, что в Garbochess всё что можно оптимизировать оптимизируется?
Вот как это выглядит 
function IsSquareAttackableFrom(target, from){
    var index = from - target + 128;
    var piece = g_board[from];
    if (g_vectorDelta[index].pieceMask[(piece >> 3) & 1] & 
        (1 << (piece & 0x7))) {
        // Yes, this square is pseudo-attackable.  
        // Now, check for real attack
	var inc = g_vectorDelta[index].delta;
        do {
		from += inc;
		if (from == target)
			return true;
	} while (g_board[from] == 0);
    }
    return false;
}

Массив g_vectorDelta заполняется следующим образом: 
var g_vectorDelta = new Array(256);

var g_bishopDeltas = [-30, -34, 30, 34];
var g_knightDeltas = [31, 33, 14, -14, -31, -33, 18, -18];
var g_rookDeltas   = [-1, +1, -16, +16];
var g_queenDeltas  = [-15, -17, 15, 17];
var g_kingDeltas   = [-1, +1, -15, +15, -17, +17, -16, +16];
...
var pieceDeltas = [[], [], g_knightDeltas, g_bishopDeltas, g_rookDeltas, 
    g_queenDeltas, g_kingDeltas];

for (var i = 0; i < 256; i++) {
    g_vectorDelta[i] = new Object();
    g_vectorDelta[i].delta = 0;
    g_vectorDelta[i].pieceMask = new Array(2);
    g_vectorDelta[i].pieceMask[0] = 0;
    g_vectorDelta[i].pieceMask[1] = 0;
}
    
// Initialize the vector delta table    
for (var row = 0; row < 0x80; row += 0x10) 
    for (var col = 0; col < 0x8; col++) {
        var square = row | col;
         
        // Pawn moves
        var index = square - (square - 17) + 128;
        g_vectorDelta[index].pieceMask[colorWhite >> 3] |=
             (1 << pieceSarbaz);
        index = square - (square - 15) + 128;
        g_vectorDelta[index].pieceMask[colorWhite >> 3] |= 
            (1 << pieceSarbaz);
            
        index = square - (square + 17) + 128;
        g_vectorDelta[index].pieceMask[0] |= (1 << pieceSarbaz);
        index = square - (square + 15) + 128;
        g_vectorDelta[index].pieceMask[0] |= (1 << pieceSarbaz);
            
        for (var i = pieceAsb; i <= pieceShah; i++) {
            for (var dir = 0; dir < pieceDeltas[i].length; dir++) {
                var target = square + pieceDeltas[i][dir];
                while (!(target & 0x88)) {
                    index = square - target + 128;
                    
                    g_vectorDelta[index].pieceMask[colorWhite >> 3] |= 
                        (1 << i);
                    g_vectorDelta[index].pieceMask[0] |= (1 << i);
                        
                    var flip = -1;
                    if (square < target) 
                        flip = 1;
                     
                    if ((square & 0xF0) == (target & 0xF0)) {
                        // On the same row
                        g_vectorDelta[index].delta = flip * 1;
                    } else if ((square & 0x0F) == (target & 0x0F)) {
                        // On the same column
                        g_vectorDelta[index].delta = flip * 16;
                    } else if ((square % 15) == (target % 15)) {
                        g_vectorDelta[index].delta = flip * 15;
                    } else if ((square % 17) == (target % 17)) {
                        g_vectorDelta[index].delta = flip * 17;
                    }

                    if ((i == pieceAsb) || (i == pieceAlfil) || 
                        (i == pieceFers)) {
                        g_vectorDelta[index].delta = pieceDeltas[i][dir];
                        break;
                    }

                    if (i == pieceShah)
                        break;

                    target += pieceDeltas[i][dir];
                }
            }
        }
    }

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

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

Чтобы двигаться дальше, требовалось научиться запускать Garbochess непосредственно в браузере. Для «Hoppel-Poppel» я так и сделал (попутно обернув всё в IIFE, чтобы не мусорить переменными). Сама игра не слишком отличается от Шахмат. Изменены всего две фигуры: слон бьёт вражеские фигуры как конь и наоборот (тихие ходы выполняются по шахматным правилам). Кстати, если придумаете как поставить мат из этой позиции, сообщите мне (меня этот вопрос очень интересует):

79y68ttdjlumj2bn5ti7pvlsggs.png

Теперь пришло время поговорить о g_pieceList. Как я уже говорил, эта структура предназначена для быстрого поиска позиций, на которых стоят фигуры заданного типа. Быстрый поиск очень важен, поскольку такая операция выполняется очень часто и сканирование по всей доске полностью убило бы всю производительность.
Работает это вот так 
var g_pieceIndex = new Array(256);
var g_pieceList = new Array(2 * 8 * 16);
var g_pieceCount = new Array(2 * 8);

function InitializePieceList() {
    for (var i = 0; i < 16; i++) {
        g_pieceCount[i] = 0;
        for (var j = 0; j < 16; j++) {
            // 0 is used as the terminator for piece lists
            g_pieceList[(i << 4) | j] = 0;
        }
    }
    for (var i = 0; i < 256; i++) {
        g_pieceIndex[i] = 0;
        if (g_board[i] & (colorWhite | colorBlack)) {
            var piece = g_board[i] & 0xF;
            g_pieceList[(piece << 4) | g_pieceCount[piece]] = i;
            g_pieceIndex[i] = g_pieceCount[piece];
            g_pieceCount[piece]++;
        }
    }
}


В качестве ключа используется побитовая сумма цвета и типа фигуры, а поскольку фигур одного типа может быть несколько, 4 бита резервируем под счётчик. Почему так много? Для кодирования 8-ми пешек действительно хватило бы трёхбитного счётчика, но потенциально мы можем превратить все эти пешки в другие фигуры и получить на доске, например, 10 коней. Теперь посмотрите на эту картинку:
zhqyzmonzoioe9e1ho6dclevnie.png

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

Теперь, когда я разобрался с AI для шахматных игр, я нахожусь, некоторым образом, на перепутье. Какими играми заняться дальше? Можно попробовать сделать AI для Сянцы, но там, сходу, доска 9×10 и надо придумывать что-то, чтобы втиснуть её в g_board. Японские Сёги преподносят сюрприз своим правилом сброса (ну и доска тоже 9×9). Можно делать Макрук и Суттуйин, но там не будет чего-то принципиально нового. Наконец, можно заняться «Белорусскими шахматами» — этот вариант для самых смелых, поскольку как делать составные шашечные ходы в GarboChess пока совсем непонятно. В общем, я прикрепил опрос — голосуйте.

© Habrahabr.ru