Tabling in Prolog Game Search for Tic-Tac-Toe

Question

Many Prolog systems meanwhile implement tabling. SWI-Prolog has adopted much of XSB tabling. XSB tabling suggest converting game search:

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

Into this tabling:

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

Is it worth considering tabling for game search in practical game search? What would be the impact on Tic-Tac-Toe?

Answer 1

My point of departure was the Prolog Tic-Tac-Toe tictac.p, link is given at the end of the post. But I wasn't using tnot/1, only the table/1 directive. First we must be careful in adding the right tabling.

So the below first take in adding the table/1 directive is nonsense since the recursive call of best/3 in the negation as failure meta argument has an implicit existential quantifier. The 3rd argument will make best/3 non deterministic and blow up the table:

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

What works better, is only taking the first solution of best/3 into a new predicate best/2. This will not change the result of negation as failure. And then table this new predicate 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)). 

Interesting find, SWI-Prolog negation as failure is much faster than mine, but it is bothered with some overhead, since when switching to tabling it cannot speed up the game search. Was comparing the Prolog texts tictac.p and 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.

On the other hand I get a ca. two fold speed-up:

/* 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

Open source:

Tic-Tac-Toe without tabling
https://github.com/jburse/jekejeke-samples/blob/master/jekrun/benchmark/tests/tictac.p

Tic-Tac-Toe with tabling
https://gist.github.com/jburse/713b6ad2b7e28de89fe51b98be3d0943#file-tictac2-pl