0

许多 Prolog 系统同时实现表。SWI-Prolog 采用了大部分 XSB 表。XSB 表格建议转换游戏搜索：

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

进入这个表格：

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

在实际游戏搜索中是否值得考虑为游戏搜索表？对井字游戏有什么影响？

4

1 回答 1

-1

我的出发点是 Prolog Tic-Tac-Toe 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 否定失败比我的要快得多，但它有一些开销，因为当切换到表时它不能加快游戏​​搜索。正在比较 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.

另一方面，我得到了一个 ca。两倍加速：

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

于 2021-02-14T12:28:14.837 回答