Материал: Волченков Логическое программирование язык пролог 2015

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

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

Рис. 9.3. Пример И/ИЛИ-графа и решающего подграфа игры Гранди для исходного числа предметов N=7

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

igra(win, P, p(P, m(Q))) :- igrokp(P, p(P, m(Q))), !, assert_new_fact(p(P, m(Q))).

igra(los, P, Sp) :- igrokm(P, Sp), !, assert_new_fact(m(P)).

126

igrokp(P, _) :- nohod(P), !, fail.

igrokp(P, p(P, m(Q))) :- call(p(P, m(Q))), !. igrokp(P, p(P, Tree)) :- hod(P, Q),

igrokm(Q, Tree).

igrokm(P, m(P)) :- nohod(P), !. igrokm(P, m(P)) :- call(m(P)), !.

igrokm(P, m(P, Tree)) :- setof(Q, hod(P, Q), M), ansp(M, Tree).

ansp([], []) :- !.

ansp([P | M], [Tree1 | Tree]) :- igrokp(P, Tree1), ansp(M, Tree).

assert_new_fact(F) :- call(F), !. assert_new_fact(F) :- !, assert(F).

С помощью этой программы в базу данных Пролога вносятся новые факты вида p(P, m(Q)), если позиция P приводит к выигрышу, и факты вида m(P), если позиция P приводит к проигрышу. В первом случае разумно указывать выигрывающий ход P → Q. Во втором случае ходы не указываются, так как ни один из них не уберегает игрока от проигрыша. В первом случае позицию P будем называть «выигрышной», во втором случае – «проигрышной».

Чтобы представленную выше программную структуру применить к конкретной игре, например к описанной выше игре Гранди, к этой программе необходимо добавить определения предикатов hod/2 и nohod/1 для данной игры. Первый из них должен строить все дочерние вершины данной вершины И/ИЛИ-графа, а второй предикат должен доказывать, что данная вершина «висячая».

В качестве примера рассмотрим определения этих предикатов для игры Гранди (код 9.4).

127

Код 9.4

% Ход для игры Гранди (а также отсутствие хода). :- assert(m([])), assert(m([4])).

:- assert(p([3], m([]))).

hod(P, Q) :- setof(Q1, hodizb(P, Q1), L), member(Q, L).

hodizb(P, Q) :- % По возврату будут избыточные решения. memdel(X, P, P1), % Удаление элемента из списка.

nohod([]) :- !.

memdel(X, [X | T], T).

memdel(X, [Y | T], [Y | T1]) :- memdel(X, T, T1).

razb(X, Y, Z) :- V is X // 2, genint(Y, 1, V), Z is X – Y, Z \= Y.

genint(L, L, R).

genint(X, L, R) :- L < R, L1 is L + 1, genint(X, L1, R).

upr([N | P], Q) :- (N = 1; N = 2), !, upr(P, Q). upr([N | P], [N | Q]) :- !, upr(P, Q).

upr([], []) :- !.

mysort([], []) :- !.

mysort([A | L], S) :- mysort(L, S1), insort(A, S1, S). insort(A, [], [A]) :- !.

insort(A, [B | S], [A, B | S]) :- A @=< B, !. insort(A, [B | S1], [B | S]) :- !, insort(A, S1, S).

Взаключение, несколько слов о реализации эксперимента с данной игрой (Гранди).

Всилу того, что представленный выше алгоритм является пере-

борным, даже небольшое увеличение размерности задачи (значения N) резко увеличивает время доказательства выигрыша или

128

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

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

няется в ходе очередного запуска данной программы (код 9.5):

Код 9.5

izvp :- see(ppos), read(T), cys(T), seen.

%Извлечь позиции, приводящие к выигрышу. izvm :- see(mpos), read(T), cys(T), seen.

%Извлечь позиции, приводящие к проигрышу. cys(end_of_file) :- !.

cys(T) :- assert(T), read(TN), cys(TN).

% Создание новых файлов. zapp :- tell(ppos), setof(p(X, Y), p(X, Y), L), cyt(L), told. zapm :- tell(mpos), setof(m(X), m(X), L), cyt(L), told.

cyt([]):-!.

cyt([H|T]):-write(H), write('.'),nl, cyt(T).

Более того, можно существенно сократить время, которое компьютер будет затрачивать на накопление опыта, если для любого заданного числа (например, 21) генерировать все возможные позиции, которые могут возникнуть из этого числа (например, [3, 18], …, [3, 3, 3, 4, 4, 4], …), и выяснять, «выигрышны» или «проигрышны» эти позиции (код 9.6):

129

Код 9.6

%Генерация всех позиций из данного числа.

%(Сумма элементов списка равна данному числу.) genpos(N, L) :- N1 is N + 1, gp(N, N1, [], L).

gp(N, N, L, L) :- !.

gp(I, N, B, L) :- setof(L0, raz(I, L0), L1),

append(B, L1, B1), I1 is I + 1, gp(I1, N, B1, L).

raz(N, L) :- K is N // 3, raz(N, K, L1), reverse(L1, L). raz(N, K, L) :- genint(X, 1, K), raz(N, N, X, 3, [], L). raz(_, 0, 0, _, L, L).

raz(P, N, X, Y, B, L) :- genint(Z, Y, P), N1 is N – Z, N1 >= 0, X1 is X – 1, X1 >= 0, raz(P, N1, X1, Z, [Z | B], L).

% Исследование результатов игры для каждой позиции. igry(N,L) :- genpos(N, L), genigr(L).

genigr([]) :- !.

genigr([P|Ps]) :- igra(R, P, T), write(T), nl, genigr(Ps).

С помощью представленного подхода автору удалось построить решающие подграфы для всех позиций [N], где N < 23. При этом файл mpos содержит 76, а файл ppos – 169 позиций.

Скептики и ниспровергатели Пролога! Попробуйте создать указанные файлы с помощью таких языков как бейсик или паскаль – автор не уверен, что это удастся осуществить такими же «минимальными» средствами, как это сделано на Прологе. Тем же из слушателей или читателей, которые заинтересовались приведенным примером, автор может выслать эти файлы по электронной почте: сыпьте деньги на стол, играйте и выигрывайте, если у Вашего противника таких данных нет…

3. Эвристический поиск на игровых деревьях

Игра Гранди – это тот редкий пример игры двух лиц с полной информацией, когда вручную или на компьютере можно перебрать все возможные варианты ходов за сравнительно небольшое время. Ведь если в исходной кучке N предметов, максимальное число ходов одного игрока не может превысить числа k = (N – 1) / 2. Боль-

130