prolog - λProlog 假设推理井字游戏

Question

λProlog 特性 hypothetical reasoning .通过使用运算符 (=>)/2
我们可以暂时断言一些条款。这个可以用来实现吗
adversarial search在λProlog？
正在考虑井字游戏。而不是开始
填充为空白的 cell/3 事实，我们也可以简单地
从根本没有单元格/3 个事实开始。
然后每个玩家通过添加 cell/3 个事实来移动。任何
相应的实现？我猜他们会
此代码的改编 here .
两次移动后，数据库可能如下所示:

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

Answer 1

事实证明，对于博弈搜索，我们只需要一个可以在纯 Prolog 中实现的假设推理的特例。让我们使用运算符 (-:)/2 进行假设推理，然后我们有这个推理规则:

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

所以口头上解决子目标F-:G，事实F被添加到数据库Γ然后尝试子目标G。挑战 G 的每一次成功，事实 F 都必须再次从数据库中消失，因为事实证明数据库中没有 F。
我们考虑的特殊情况是 G 是确定性的。即 G 要么成功一次，要么失败。我们目前也不假设异常(exception)或 F 非接地。在这些假设下，假设推理可以实现如下:

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

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

现在可以将 here 中的 move/3 谓词重写为提供新事实 F 的谓词 move/2。然后，主要的对抗搜索例程如下所示，其中我们也相应地更改了 win/2 和 tie/2 谓词进入 win/1 和 tie/1 以检查动态事实 cell/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).

与 Prolog 术语游戏状态相比，assertz/retract 的性能如何？约慢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
井字游戏的 Prolog 代码
通过否定的最小-最大搜索
通过 Prolog 事实的游戏板
https://gist.github.com/jburse/279b6280ab4311de456e458a7386c1da#file-tictac2-pl