Таблица в Prolog Game Search для крестиков-ноликов

Question

Тем временем многие системы Prolog реализуют табличное представление. SWI-Prolog перенял большую часть таблиц XSB. Таблицы XSB предлагают преобразовать поиск игры:

      win(X) :- move(X,Y), \+ win(Y).

В эту таблицу:

      :- table win/1.
win(X) :- move(X,Y), tnot(win(Y))

Стоит ли рассматривать таблицы для поиска игр в практическом поиске игр? Как это повлияет на крестики-нолики?

Answer 1

Моей отправной точкой был Пролог Крестики-нолики tictac.p, ссылка дана в конце поста. Но я не использовал tnot/1, только директиву table/1. Во-первых, мы должны быть осторожны при добавлении правильной таблицы.

Таким образом, приведенный ниже первый взгляд на добавление директивы table/1 является нонсенсом, поскольку рекурсивный вызов best/3 в метааргументе отрицания как отказа имеет неявный квантификатор существования. Третий аргумент сделает best/3 недетерминированным и взорвет таблицу:

      :- table best/3.
best(X, P, Y) :-
   move(X, P, Y),
   (win(Y, P) -> true;
      other(P, Q),
      \+ tie(Y, Q),
      \+ best(Y, Q, _)).

Что работает лучше, так это использование первого решения best/3 в новом предикате best/2. Это не изменит результат отрицания как неудачу. А затем запишите этот новый предикат best/2:

      :- table best/2.
best(X, P) :-
   best(X, P, _), !.

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

Интересная находка, SWI-Prolog отрицание провала гораздо быстрее моего, но надоедает некоторым оверхедом, так как при переходе на таблинг не может ускорить поиск игры. Сравнивал тексты Пролога tictac.p и tictac2.pl:

      /* SWI-Prolog 8.3.19 */
?- time((between(1,50,_), tictac, fail; true)).
% 5,087,251 inferences, 1.034 CPU in 1.044 seconds (99% CPU, 4920224 Lips)
true.

?- time((between(1,50,_), abolish_all_tables, tictac, fail; true)).
% 4,472,251 inferences, 1.343 CPU in 1.426 seconds (94% CPU, 3329897 Lips)
true.

С другой стороны, я получаю ок. двукратное ускорение:

      /* Jekejeke Prolog 1.4.7 */
?- time((between(1,50,_), tictac, fail; true)).
% Up 3,218 ms, GC 10 ms, Threads 3,201 ms (Current 02/14/21 01:04:15)
Yes

?- time((between(1,50,_), retractall_table(_), tictac, fail; true)).
% Up 1,703 ms, GC 11 ms, Threads 1,688 ms (Current 02/14/21 01:06:50)
Yes

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

Крестики-нолики без таблицы
https://github.com/jburse/jekejeke-samples/blob/master/jekrun/benchmark/tests/tictac.p

Крестики-нолики с таблицей
https://gist.github.com/jburse/713b6ad2b7e28de89fe51b98be3d0943#file-tictac2-pl