2

λProlog 以假设推理为特征。通过使用运算符 (=>)/2 我们可以临时断言一些子​​句。这可以用来 在 λProlog中实现对抗搜索吗？

正在考虑井字游戏。除了从填充为空白的 cell/3 事实开始，我们还可以简单地从根本没有 cell/3 事实开始。

然后每个玩家通过添加 cell/3 个事实来移动。周围有什么相应的实现吗？我想他们将是这里代码的改编。

两次移动后，数据库可能如下所示：

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

1 回答 1

2

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

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

因此口头解决子目标 F -: G，将事实 F 添加到数据库 Γ 中，然后尝试子目标 G。具有挑战性的是，对于 G 的每一次成功，事实 F 都必须再次从数据库中消失，因为已证明数据库中没有 F。

我们考虑的特殊情况是 G 是确定性的。即 G 要么成功一次，要么失败。我们目前不假设例外或 F 非地面。在这些假设下，假设推理可以如下实现：

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

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

现在可以从这里将 move/3 谓词重写为提供新事实 F 的谓词 move/2。主要的对抗搜索例程如下所示，我们还相应地更改了 win/2 和 tie/2 谓词进入 win/1 和 tie/1 以检查动态事实单元格/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

于 2021-01-24T11:55:18.550 回答