0

一方、多くの Prolog システムはテーブルを実装しています。SWI-Prolog は、XSB テーブルの多くを採用しています。XSB テーブルは、ゲーム検索の変換を提案しています:

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

この表に:

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

実際のゲーム検索でゲーム検索のテーブル化を検討する価値はありますか? Tic-Tac-Toe にどのような影響がありますか?

4

1 に答える 1

-1

私の出発点は Prolog Tic-Tac-Toe tictac.p でした。リンクは投稿の最後にあります。しかし、私は tnot/1 を使用しておらず、table/1 ディレクティブのみを使用していました。まず、適切なテーブルを追加する際に注意する必要があります。

したがって、table/1 ディレクティブを追加する以下の最初の例はナンセンスです。なぜなら、失敗のメタ引数としての否定での best/3 の再帰呼び出しには暗黙の存在量指定子があるからです。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を取得します。2 倍のスピードアップ:

/* 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 に答える