Давно хотел попробовать Prolog, и вот появился удобный случай. Пришла идея логической игры, смесь шахмат, шашек и нашествия зомби. Prolog - логический язык программирования, говорят, на нём удобно решать комбинаторные задачи, что может пойти не так!
Подготовка
Был опыт работы с функциональными языками, начитался туториалов, но это не помогло. Одно дело читать - другое писать. Код больше похож на уравнение, где значения переменных вычисляются, если для этого достаточно известных данных. А если не достаточно, то Prolog перебирает все возможные значения, пока не найдет подходящее или пока не закончится память.
Без длинного экскурса, покажу интересные примеры кода и как бы это выглядело на Javascript.
Просто, да не просто!
Вся программа состоит из логических предикатов. Предикат всегда возвращает true, если аргументы совпадают с шаблоном и условия в теле выполняются. При несовпадении, возвращается false, а значения переменных сбрасываются в исходные.
Указываем в аргументах переменные или константы, расставляем условия ИЛИ
;И,. Туда-сюда, готово!
% Prolog: предикат с условием, число от 3 до 7 или -1.
is_magic_number(N) :-
( 3 =< N , N =< 7 ) ; N == -1 .
% Предикат без условий, закрывается точкой.
bit_name(0, zero).
% Если первая запись не совпала, управление получает следующая.
bit_name(1, one).
/* Javascript */
function is_magic_number(N) {
return ( 3 <= N && N <= 7 ) || N == -1 ;
}
function bit_name(Bit, Result) {
if (Bit == 0) {
Result.value = 'zero';
return true;
}
if (Bit == 1) {
Result.value = 'one';
return true;
}
return false;
}
Все что начинается с заглавной буквы, считается переменной. Их не требуется заранее декларировать. С маленькой записываются атомы, они похожи на строковые литералы Javascript.
Пример, определение списка фигур:
% Prolog: используем аргументы как словарь
piece_value(pawn, 2).
piece_value(knight, 4).
piece_value(bishop, 4).
piece_value(rook, 5).
piece_value(queen, 9).
piece_value(king, 100).
piece_value(peon, 2).
piece_value(zombie, 3).
piece_value(adviser, 4).
piece_value(cube, 7).
piece_value(dame, 4).
/* Javascript: используем объект как словарь */
const PieceValue = {
pawn: 2,
knight: 4,
bishop: 4,
rook: 5,
queen: 9,
king: 100,
peon: 2,
zombie: 3,
adviser: 4,
cube: 7,
dame: 4
};
Зайдем в интерпретатор и спросим, насколько ценная фигура конь.
-? - приглашение интерпретатора Prolog.
?- piece_value(knight, Val).
Val = 4.
js>> - приглашение интерпретатора Javascript.
js>> PieceValue.knight
4
Теперь наоборот, ищем все фигуры с ценностью 4. Таких больше одной, задействуется поиск решений - backtracking. Чтобы увидеть следующий ответ, нажимаем в консоли ;.
Поиск фигуры:
% Используем backtracking для поиска
?- piece_value(Name, 4).
Name = knight ;
Name = bishop ;
Name = adviser ;
Name = dame.
/* Используем цикл и печать в консоль */
js>> for (Name in PieceValue) { if (PieceValue[Name] == 4) console.log(Name) }
knight
bishop
adviser
dame
Другой пример, проверка координат для доски 8 на 8. Все 64 значения не заполняются, указываем только диапазон.
% Определяем границы доски
coord_pair(X-Y) :- between(1, 8, Y), between(1, 8, X).
% Проверяем условие.
?- coord_pair(7-7).
true.
?- coord_pair(P).
P = 1-1 ;
P = 2-1 ;
P = 3-1 ;
P = 4-1 ;
P = 5-1 ;
P = 6-1 ;
P = 7-1 ;
P = 8-1 ;
P = 1-2 ;
...
const BOARD_START = 1;
const BOARD_END = 8;
function is_coord_pair(Pair) {
return (BOARD_START <= Pair.x && Pair.x <= BOARD_END) &&
(BOARD_START <= Pair.y && Pair.y <= BOARD_END);
}
/* Проверяем */
js>> is_coord_pair({x:7,y:7})
true
/* Перебираем диапазон с запасом, чтобы протестировать граничные значения. */
js>> for (var Y = BOARD_START-1; Y <= BOARD_END+1; ++Y)
for(var X = BOARD_START-1; X <= BOARD_END+1; ++X)
console.log(`P=${X},${Y}`, is_coord_pair({x:X,y:Y}));
P=0,0 false
P=1,0 false
P=1,1 true
P=2,1 true
...
Купи парсер, генератор получишь в подарок!
Когда Prolog ищет решение, ему не важно в какой части выражения находятся переменные. Слева или справа, есть у них значения или нет. Большинство предикатов умеют выводить неизвестные значение.
В следующем примере, encode_layout декодирует список фигур на доске или создает строку по списку фигур. Всё зависит от того, в каком аргументе указать константу, а в каком переменную.
% Разбираем строку, пешка - a2, король - a1, зомби - e3.
?- encode_layout(`w,Pwa2,Kwa1,Zbe3`, Color, List).
Color = w,
List = [1-2-(pawn-w), 1-1-(king-w), 5-3-(zombie-b)].
% Теперь в обратную сторону, создаем строку по списку фигур.
?- encode_layout(Chars, w, [1-2-(pawn-w), 1-1-(king-w), 5-3-(zombie-b)]), string_codes(Str, Chars).
Chars = [119, 44, 80, 119, 97, 50, 44, 75, 119|...],
Str = "w,Pwa2,Kwa1,Zbe3".
% Для парсинга строк и списков, принято использовать модуль DCG.
% Стрелочка --> это правило DCG, похоже на популярный parser combinators
color_name(w) --> "w".
color_name(b) --> "b".
piece_name(pawn) --> "P". piece_name(knight) --> "N".
piece_name(bishop) --> "B". piece_name(rook) --> "R".
piece_name(queen) --> "Q". piece_name(king) --> "K".
piece_name(peon) --> "S". piece_name(dame) --> "D".
piece_name(zombie) --> "Z". piece_name(cube) --> "C".
piece_name(adviser) --> "A".
xcoord_dcg(1) --> "a". xcoord_dcg(2) --> "b".
xcoord_dcg(3) --> "c". xcoord_dcg(4) --> "d".
xcoord_dcg(5) --> "e". xcoord_dcg(6) --> "f".
xcoord_dcg(7) --> "g". xcoord_dcg(8) --> "h".
ycoord_dcg(1) --> "1". ycoord_dcg(2) --> "2".
ycoord_dcg(3) --> "3". ycoord_dcg(4) --> "4".
ycoord_dcg(5) --> "5". ycoord_dcg(6) --> "6".
ycoord_dcg(7) --> "7". ycoord_dcg(8) --> "8".
piece_dcg(Name-Color) --> piece_name(Name), color_name(Color).
coord_dcg(X-Y) --> xcoord_dcg(X), ycoord_dcg(Y).
piece_coord_dcg(Coord-Piece) --> piece_dcg(Piece), coord_dcg(Coord).
layout_dcg(Color, PList) --> color_name(Color), ",", sequence(piece_coord_dcg, ",", PList).
encode_layout(Text, Color, PList) :- phrase(layout_dcg(Color, PList), Text).
Как ходит пешка?
Пешка ходит только вперед, на одну клетку или на две клетки, но только со второй линии.
% Ход на две клетки
pawn_move(X-2, X-4, w).
pawn_move(X-7, X-5, b).
% Ход на одну клетку
pawn_move(X-Y0, X-Y, Color) :-
move_direction(Color, Dir), % определяем направление движения
Y is Y0 + Dir, % вычисляем новую координату Y
coord_pair(X-Y). % проверяем выход за границу доски
move_direction(w, 1). % направление вверх
move_direction(b, -1). % направление вниз
В Javascript потребуется две функции, первая для валидации, вторая для перебора.
function is_pawn_move(A, B, Color) {
if (A.x == B.x) {
if (Color == 'w') {
if (A.y == 2 && B.y == 4)
return true;
if (A.y + 1 == B.y)
return is_coord_pair(B);
}
if (Color == 'b') {
if (A.y == 7 && B.y == 5)
return true;
if (A.y - 1 == B.y)
return is_coord_pair(B);
}
}
return false;
}
/* Перебираем ходы из точки A, возвращаем список. */
function pawn_move(A, Color) {
var Result = [];
for (var Y = 1; Y <= 8; ++Y) {
for(var X = 1; X <= 8; ++X) {
const B = {x:X,y:Y};
if (is_pawn_move(A, B, Color))
Result.push({src:A, dst:B, color:Color});
}
}
return Result;
}
Проверяем, куда можно переместиться из координаты b2.
?- pawn_move(2-2, X-Y, Color).
X = 2, Y = 4, Color = w ;
X = 2, Y = 3, Color = w ;
X = 2, Y = 1, Color = b.
% сразу в дамки
?- pawn_move(2-2, 2-8, 'w').
false
/* Ищем ходы для каждого цвета, соединяем результат */
js>> pawn_move({x:2,y:2},'w').concat(pawn_move({x:2,y:2},'b'))
Array
0: Object { src: { x: 2, y: 2 }, dst: { x: 2, y: 3 }, color: "w" }
1: Object { src: { x: 2, y: 2 }, dst: { x: 2, y: 4 }, color: "w" }
2: Object { src: { x: 2, y: 2 }, dst: { x: 2, y: 1 }, color: "b" }
js>> is_pawn_move({x:2,y:2}, {x:2, y:8 },'w')
false
Бот для одиночной игры
Самый простой ИИ, проходит по всем фигурам на доске и оценивает возможные ходы.
Бьет фигуру соперника, либо ходит на свободную клетку, не задумываясь о последствиях.
cpu_easy_move(game(Color,Board), Result) :-
game_state(game(Color,Board), AllMoves, _),
score_my_moves(AllMoves, MyMoves, Color),
find_best_score(MyMoves, Result).
game_state(game(Color, Board), AllMoves, Claim) :-
find_legal_moves(game(Color, Board), AllMoves),
( nomoves_state(Color, AllMoves, Claim)
; (is_king_check(Color, AllMoves)
-> Claim = check
; Claim = idle)
).
find_best_score(MyMoves, Result) :-
keysort(MyMoves, Sorted),
partition([K-_]>>(K<0), Sorted, BadMoves, OkMoves),
( last(OkMoves, Score-_) ->
include({Score}/[K-_]>>(K = Score), OkMoves, SameScore),
random_member(Result, SameScore)
;
last(BadMoves, Result)
).
Улучшенная версия, просчитывает на ход вперед. Например, если бьем фигуру ценностью 5, а соперник в ответ забирает фигуру ценностью 9, то ход оценивается в -4.
cpu_good_move(Game, Result) :-
game(Color,_) = Game,
game_state(Game, AllMoves, _),
score_my_moves(AllMoves, MyMoves, Color),
score_move_consequence(Game, MyMoves, MyMoves2),
find_best_score(MyMoves2, Result).
score_move_consequence(_, [], []).
score_move_consequence(game(Color,Board), [Score-Rec|T], [Score2-Rec|R]) :-
apply_recording(Rec, Board, BoardTmp),
opposite_color(Color, OpColor),
( cpu_easy_move(game(Color,BoardTmp), 100-_) ->
ThreatScore = 1
; ThreatScore = 0 ),
( cpu_easy_move(game(OpColor,BoardTmp), OpScore-_OpMove)
-> Score2 is Score - OpScore + ThreatScore
; Score2 is 100 ),
score_move_consequence(game(Color,Board), T, R).
Тут нет глубокой стратегии, но такой реализации оказалось достаточно, чтобы заставить попотеть игроков.
Оптимизация
Жизнь без векторов
В языке нет стандартного типа массив, чтобы удобно работать с двумерной матрицей 8 на 8. Самое близкое что похоже на массив, это одномерный compound term. Постоянно конвертировать индекс в координаты показалось неудобно, хотелось максимально простой и понятный формат.
xy_to_index(X-Y, Index) :- Index is (Y - 1) * 8 + X.
index_to_xy(Index, X-Y) :-
Index0 is Index - 1,
divmod(Index0, 8, Y0, X0), Y is Y0 + 1, X is X0 + 1.
get_board(K, V, Board) :-
xy_to_index(K, Index),
arg(Index, Board, V).
put_board(K, V, Board0, Board) :-
% создаем копию, чтобы не повредить другие ветки поиска мутацией
duplicate_term(Board0, Board),
xy_to_index(K, Index),
nb_setarg(Index, Board, V).
Попробовал словарь SWI-Prolog, он удобный, но в нем ограничение на композитные ключи. В итоге использовал обычный список.
% Обычный список как словарь
?- Board1 = [(3-3):(zombie-b)]
Board2 = [(2-2):(pawn-b) | Board1], % добавляем элемент в начало списка
member(3-3:Value, Board2). % поиск совпадения
Board1 = [3-3:zombie-b],
Board2 = [2-2:pawn-b, 3-3:zombie-b],
Value = zombie-b.
% Словарь в ООП стиле, расширение SWI-Prolog
?- Board = board{}.put(33, zombie-b), Piece = Board.get(33).
Board = board{33:zombie-b},
Piece = zombie-b.
% Ругается на композитный ключ
?- Board = board{}.put(3-3, zombie-b),
ERROR: Type error: `dict-key' expected, found `3-3' (a compound)
WASM, скорость x 0.2
Браузер оказался медленнее натива в 5-8 раз. В некоторых случаях, подсчет хода занимал до секунды. Для пошаговой игры сойдет, но хочется побыстрее.
% Тест, cpu_good_move, 48 фигур + ответные ходы, процессор Ryzen 5700X, один поток.
?- time(go()).
% 1,681,082 inferences, 0.109 CPU in 0.107 seconds (103% CPU, 15369893 Lips)
% Chrome 140
js>> Prolog.query("time(go()).").once();
% 1,683,534 inferences, 0.829 CPU in 0.829 seconds (100% CPU, 2030801 Lips)
Проводить алгоритмическую оптимизацию, конечно же, никто не собирался.
В SWI-Prolog есть альтернативный режим перебора Tabled Execution. Предикаты с атрибутом table сохраняют таблицу ответов.
% Выбираем предикаты для ускорения
:- if(current_prolog_flag(generate_debug_info, false)).
:- table pawn_move/3.
:- table pawn_cap/3.
:- table knight_move/2.
:- table diagonal_move/3.
:- table diagonal_move_xys/2.
:- table rook_move/3.
:- table rook_move_xys/2.
:- table peon_jumpover/3.
:- endif.
?- time(go()).
% 1,158,951 inferences, 0.078 CPU in 0.082 seconds (95% CPU, 14834573 Lips)
js>> Prolog.query("time(go()).").once();
% 1,157,819 inferences, 0.577 CPU in 0.577 seconds (100% CPU, 2006618 Lips)
В топе профайлера оказался линейный поиск по списку фигур.
Заменил список на AVL Tree. Результат удовлетворительный.
vacant_cell(K, Board) :- \+ get_assoc(K, Board, _).
del_board(K, Board0, Board) :- del_assoc(K, Board0, _, Board).
get_board(K, V, Board) :- get_assoc(K, Board, V).
put_board(K, V, Board0, Board) :- put_assoc(K, Board0, V, Board).
list_to_board(Pairs, Board) :- list_to_assoc(Pairs, Board).
board_to_list(Board, Pairs) :- assoc_to_list(Board, Pairs).
?- time(go()).
% 359,054 inferences, 0.031 CPU in 0.029 seconds (109% CPU, 11489728 Lips)
js>> Prolog.query("time(go()).").once();
% 357,944 inferences, 0.176 CPU in 0.176 seconds (100% CPU, 2033774 Lips)
Интеграция с браузером
Работать с JavaSсript удобно, примитивные типы передаются без изменений, объекты автоматически конвертируются в словарь, массив в список. Есть доступ к DOM, но я решил не изобретать велик. Подключил графический движок Phaser.
var game;
var options = {
arguments: IS_AI_TEST || IS_AI_BATTLE ? [ "-O", "--debug=false"] : ["-q", "-O", "--debug=false"],
locateFile: (file) => '/' + file,
on_output: print_output,
};
SWIPL(options).then((module) => {
Module = module;
Prolog = Module.prolog;
Prolog.consult("game.qlf").then(() => {
console.log("ready");
game = new Phaser.Game(config);
});
});
Запросы выполняет Prolog.query, возвращает итератор всех доступных ответов.
function queryGameState() {
const q = Prolog.query("pub_game_state(Board,Moves,Claim)");
const r = q.once();
if (r.error)
console.warn(r.message);
q.close();
if (r.success) {
return { color: r.Board.color, board: r.Board, moves: r.Moves, claim: r.Claim };
}
return {};
}
Юнит-тесты
Тесты добавил в конец файла, удобно.
swipl -g run_tests game.pl
[40/40] user:game_cpu_threat ............................................................. passed (0.011 sec)
% All 40 tests passed in 0.147 seconds (0.031 cpu)
:- begin_tests(user).
test(encode_move) :-
encode_move(`a1-b2`, [1-1, 2-2]).
test(pawn_cap1) :-
findall(XY,pawn_cap(1-2,XY,w),Ls),
assertion(Ls == [2-3]),
findall(XY,pawn_cap(2-2,XY,w),Ls2),
assertion(Ls2 == [3-3,1-3]).
test(game_cpu_stallbug1, [nondet]) :-
pub_game_load("b,Pwa2,Kwb2,Sbc3"),
pub_game_cpu_find_move(0, MoveJs),
assertion(MoveJs == [jmp{dst:a1,eat:b2,eat_name:'Kw',src:c3,src_name:'Sb'},pro{src:a1,src_name:'Db'}]).
:- end_tests(user).
Автотесты и балансировка
Другие разработчики: составляют математическую модель игры.
Мой баланс: я так чувствую!
Некоторые игроки жаловались, что миссии слишком сложные. Чтобы это проверить, заставил бота проходить все уровни.
Второй режим был "битва", боты разной сложности соревновались, накапливая статистику.
Статистика особо не помогла. Куб очень сильный, но поскольку у бота отсутствует стратегия, игроки загоняют его в ловушку и разменивают. Сила фигуры, компенсировалась неумелым использованием.
Заключение
Получилось компактно, без эпических фейлов.
Файл | Строк кода |
|---|---|
1406 | |
1064, из них 399 тесты |
VK Play, Шахматы против зомби-шашек
P.S.
Недавно отмечалось 50-ти летие создания языка. На презентации заявили: Мы только в начале пути и делаем первые уверенные шаги!
Ждём персональные квантовые компьютеры, будем считать сколько угодно и ни в чём себе не отказывать.