λProlog гипотетическое рассуждение Крестики-нолики

Question

λProlog использует гипотетические рассуждения . Используя оператор (=>)/2, мы можем временно утвердить некоторое предложение. Можно ли это использовать для реализации состязательного поиска в λProlog?

Думал об игре в крестики-нолики. Вместо того, чтобы начинать с фактов ячейки/3, которые заполнены до нуля, мы могли бы также просто начать вообще без фактов ячейки/3.

Затем каждый игрок делает ход, добавляя факты в клетку/3. Любые соответствующие реализации вокруг? Я предполагаю, что они будут адаптациями этого кода здесь .

После двух перемещений база данных может выглядеть так:

      cell(2, 2, x).
cell(1, 1, o).

Answer 1

Получается, что для поиска игры нам нужен только частный случай гипотетического рассуждения, который можно реализовать на чистом Прологе. Давайте используем оператор (-:)/2 для гипотетических рассуждений, тогда у нас есть это правило вывода:

         Γ, F |- G
 -------------
  Γ |- F -: G

Таким образом, словесно решить подцель F -: G, факт F добавляется в базу данных Γ, а затем проверяется подцель G. Что сложного в том, что для каждого успеха G факт F должен снова исчезнуть из базы данных, потому что то, что доказано, отсутствует в базе данных.

Частный случай, который мы рассматриваем, состоит в том, что G детерминистична. То есть G либо удается один раз, либо терпит неудачу. В настоящее время мы также не принимаем исключения или F без заземления. При этих предположениях гипотетические рассуждения могут быть реализованы следующим образом:

      :- op(1200, xfx, -:).

(F -: G) :-
   assertz(F),
   G, !,
   retract(F).
(F -: _) :-
   retract(F), fail.

Теперь можно переписать отсюда предикат ход/3 в предикат ход/2, который предлагает новый факт F. Основная процедура поиска состязательности читается следующим образом, где мы также соответственно изменили предикат выигрыш/2 и ничья/2. в win/1 и tie/1, чтобы проверить ячейку динамических фактов/3:

      best(P, F) :-
   move(P, F),
   (F -: 
     (  win(P) -> true
     ;  other(P, Q),
        \+ tie(Q),
        \+ best(Q, _))).

Вот некоторые результаты. У первого хода нет выигрышной стратегии:

      ?- best(x, F).
false.

Если доска [[x, -, o], [x, -, -], [o, -, -]]игрок xимеет выигрышную стратегию:

      ?- (cell(1,1,x) -: (cell(3,1,o) -: (cell(1,2,x) -: (cell(1,3,o) -: best(x, F))))).
F = cell(2, 2, x).

Насколько эффективен assertz/retract по сравнению с игровым состоянием термина Prolog? ок. в 3 раза медленнее:

      ?- time(best(x, F)).
% 478,598 inferences, 0.094 CPU in 0.094 seconds (100% CPU, 5105045 Lips)
false.

Открытый исходный код:

Частный случай гипотетического рассуждения
https://gist.github.com/jburse/279b6280ab4311de456e458a7386c1da#file-hypo-pl

Код пролога для игры в крестики-нолики
Поиск мин-макс через отрицание
Игровая доска через факты
пролога