у него есть два больших преимущества…
Во-первых, он дешевле; а во-вторых, на обложке у него большими веселыми буквами напечатан дружеский совет: Don’t panic!
Дуглас Адамс
Из всего многообразия шахматных движков, Garbochess я выбрал по двум причинам: для него есть понятный JavaScript-код и он неплохо играет в Шахматы. Мне совсем не требовался гроссмейстерский уровень! Если бот играет слишком сильно, то обычных людей (вроде меня) это только отпугивает. Требовалась лишь игра достаточно разумная, похожая на игру человека, без глупых раздражающих ошибок и Garbochess мне всё это дал. К сожалению, как и большинство других шахматных движков, он играл только в одну игру — традиционные Шахматы. Именно это мне и предстояло исправить.
В прошлый раз я рассказал о том как подключил шахматного бота к своему DagazServer-у. Разумеется, это было только начало. Моей целью было использование алгоритмов Garbochess в других играх, если не во всех, то по крайней мере, в шахматоподобных. Прежде всего, в моём распоряжении было несколько игр на малых досках, таких как "Шахматы Гарднера".
Здесь всё получилось довольно просто. Прежде всего, изменения касались размеров доски. Текущее её состояние хранится в массиве g_board, размером в 256 байт. Это немного больше чем 8x8 клеток и сделано так для того, чтобы вертикальную и горизонтальную координаты можно было кодировать старшим и младшим полубайтом индекса соответственно. Такое представление ускоряет навигацию по доске, а большая скорость означает большее количество узлов (и соответственно лучшую игру) которое удастся проверить за отведённое время.
Вот как выглядит это преобразование
function MakeSquare(row, column) {
return ((row + 2) << 4) | (column + 4);
}
Обратите внимание на константы, прибавляемые к координатам, позволяющие разместить рабочую область «в центре» массива. В самом начале InitializeFromFen, весь массив g_board заполняется значением 0x80, позволяющим ускорить проверку выхода за границы доски. Рабочая область формируется при разборе FEN-нотации начальной позиции. Поскольку размеры строк и столбцов в передаваемом описании меньше, то и доска получается требуемого размера.
Что касается содержимого массива, фигуры кодируются следующим образом
Таким образом, все проверки на тип фигуры выполняются по маске 0x07. Кодирование цвета фигур выглядит немного избыточным, но это сделано для того, чтобы отличать пустые позиции от занятых. Значение colorWhite используется еще и для кодирования очерёдности хода, хранящейся в g_toMove. Здесь всё просто: 8 кодирует ход белых, 0 — чёрных. Вот так ход переключается:
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;
Таким образом, все проверки на тип фигуры выполняются по маске 0x07. Кодирование цвета фигур выглядит немного избыточным, но это сделано для того, чтобы отличать пустые позиции от занятых. Значение 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);
В конце концов, на маленьких досках и объёмы вычислений, необходимых для хорошей игры, гораздо меньше. Движок сможет просматривать партию глубже, компенсируя тем самым менее качественную оценочную функцию.
Следующим шагом стали игры с изменёнными правилами перемещения фигур. Персидский Шатрандж очень похож на современные шахматы. Это, по всей видимости, первая игра, в которой появились понятия шаха и мата. Основные отличия связаны с тем как ходят слон и ферзь. Кстати, из-за отсутствия дальнобойных диагональных фигур, Шатрандж — очень неторопливая игра. Часто, дебютная фаза пропускалась и игроки начинали игру с оговоренных табий, вроде вот такой:
Прежде всего, в Шатрандже оказался ненужным весь код, связанный с рокировками, прыжками пешек и взятием на проходе. Поскольку пат в Шатрандже также считается победой, проверки на завершение игры также удалось упростить. Изменились правила превращения. В Шатрандже, пешка умеет превращаться лишь в слабого ферзя.
Изменилась оценка позиции
Это касается как стоимости фигур:
так и их мобильности:
-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;
Основные изменения связаны с перемещением фигур
Кстати, g_pieceList — это структура, позволяющая быстро найти на доске фигуру. Про неё ещё поговорим, чуть позже.
// 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 всё что можно оптимизировать оптимизируется?
Вот как это выглядит
Массив g_vectorDelta заполняется следующим образом:
Магия этих приращений становится довольно очевидной при переводе их в шестнадцатеричное представление. Не забывайте, что ферзь в Шатрандже ходит на соседнюю клетку по диагонали. Слон тоже перемещается по диагонали, но через одну клетку.
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, чтобы не мусорить переменными). Сама игра не слишком отличается от Шахмат. Изменены всего две фигуры: слон бьёт вражеские фигуры как конь и наоборот (тихие ходы выполняются по шахматным правилам). Кстати, если придумаете как поставить мат из этой позиции, сообщите мне (меня этот вопрос очень интересует):
Теперь пришло время поговорить о 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 коней. Теперь посмотрите на эту картинку:
С учётом возможного превращения пешек, четырёх битов явно не хватает. В общем, это была самая утомительная правка Garbochess, из тех, что я делал на текущий момент.
Теперь, когда я разобрался с AI для шахматных игр, я нахожусь, некоторым образом, на перепутье. Какими играми заняться дальше? Можно попробовать сделать AI для Сянцы, но там, сходу, доска 9x10 и надо придумывать что-то, чтобы втиснуть её в g_board. Японские Сёги преподносят сюрприз своим правилом сброса (ну и доска тоже 9x9). Можно делать Макрук и Суттуйин, но там не будет чего-то принципиально нового. Наконец, можно заняться "Белорусскими шахматами" — этот вариант для самых смелых, поскольку как делать составные шашечные ходы в GarboChess пока совсем непонятно. В общем, я прикрепил опрос — голосуйте.
valemak
Насчёт Хоппеля-Попеля. Я крутил его и так и сяк, но пока не придумал алгоритма (наподобие метода Делетана) чтобы из почти любой исходной позиции методично загнать короля в угол и там заматовать его.
Единственное что я более-менее точно представляю — как заматовать голого короля, если он уже в углу, а король сильнейшей стороны стоит наискосок через клетку. Где слон и конь при этом не суть важно.
Если (в любом углу) конфигурация королей будет именно такая, а конь и слон находятся где угодно, то у меня есть чёткий алгоритм, как поставить мат.
Если интересно, я могу записать видео с подробностями (тарабанить на клавиатуре много объясняющего текста мне лень). Но тогда уточни, как именно можно в ссылке (на твоего бота, разыгрывающего это окончание) задавать начальное расположение фигур, чтобы в своём объяснении я мог самостоятельно формировать начальную позицию.
GlukKazan Автор
Очень интересно. Потому как у меня вообще никаких мыслей.
GlukKazan Автор
Вот ссылка. В setup передаётся FEN-нотация (на неё движок заточен). В принципе, там всё просто. Строки разделены слешем, Фигуры кодируются буквами (большие у белых). Цифры — последовательности пустых полей.
valemak
Важное уточнение: по всей видимости, мат реалистичен только в случае, если цвет угла (в который загнали голого короля) не совпадает с цветом слона. Если слон ходит по полям того же цвета что и угол, то мат возможен разве что кооперативный (во всяком случае я не увидел гарантии мата если чёрные играют правильно). Если играть не понарошку, то голый король не обязан идти под мат и уйдёт в пат, если подвернётся случай.
Нас интересует, конечно же, вариант, где белые точно мат ставят, как бы чёрные не изощрялись (то есть цвет полей, по которым ходит слон должен быть противоположен цвету угла, в который загнан король).
Если ход белых, то где бы не находился чернопольный слон, они успевают вовремя поставить слона на c5 или d6 (чтобы пресечь поползновения голого короля убежать из угла). Затем подтягивается конь. Этот безотлагательный манёвр слоном нужно сделать не более чем в 2 хода (а не то чёрный король убежит). Это возможно, однако конь не должен стоять на пути слона при этом. Иначе у чёрного короля всё-таки возникает шанс вырваться из плена.
Если в общих чертах, то куда бы чёрный король ни ринулся (в попытке вырваться в данном случае из белопольного угла), то белые, независимо от начального расположения коня и чернопольного слона, успевают выстроить одну из этих четырёх базовых конфигураций, где чёрный король сидит в пределах огороженной области:
В этих конфигурациях голый король не обязательно находится именно в углу a8. Он может быть на любом поле из той небольшой области, где его изолировали (например, на поле b8 или a7). Также можно заметить, что конфигураций на самом деле не 4, а всего 2 (просто тут приведены инвертированные варианты).
Это, так сказать, первичная консолидация белых, чтобы чёрный король никуда не убежал и сидел в «клетке» пока белые перестроят фигуры для финального мата.
Затем белым ещё раз нужно перестроить фигуры, чтобы поставить финальный мат. Если играть аккуратно, то из этих четырёх базовых конфигураций можно прийти, в зависимости от обстоятельств, к одной из двух позиций для финального мата (на самом деле это одна и та же позиция, но так сказать «с разных ракурсов»).
Для примера из этих двух диаграмм возьмём ту, что слева. Если на ней ход белых, то мат ставится элементарно:
1. Kb5-a7+ Крb8-a8 2. Сd6-c7?.
Если ход чёрных, то белым с помощью нехитрого манёвра слона нужно сделать передачу хода, чтобы эта позиция возникла при ходе белых, после чего тем же способом поставить мат:
1.… Крb8-a8 2. Cd6-f8 Крa8-b8 3. Cf8-e7! Крb8-a8 4. Сe7-d6! Крa8-b8 5. Kb5-a7+ Крb8-a8 6. Сd6-c7?
Чей бы ход ни был, последняя картинка будет одна и та же:
Возможно, позже сделаю видосик, где продемонстрирую на примере.
GlukKazan Автор
Спасибо, посмотрю повнимательнее.
valemak
Если что — обнови страницу, потому что я дополнял комментарий с инструкцией.