在 Prolog 中搜索游戏

Question

我想知道是否有人可以帮助我，我在 8 件拼图程序上做了很多工作，现在我想扩展它，但是我很挣扎。

这是板子。

这样做的想法是尝试获取一块当前位于 a1 的 P1 以结束于 b1。棋盘上最多可以有 5 个其他棋子，每个棋子一次只能占据和移动 1 space。

我想要做的是计算需要得到的移动，例如位置 B1 的 P1，到位置 A3 的 P1（或者老实说，任何结束位置）如果它只能移动 1 space一次。任何两颗棋子都不能占据相同的space，如果是t区的棋子，则任何棋子都不能越到另一边。我该如何编码，以便当我输入类似

的内容时

?- pmove([at(a1,p3),at(b1,p1),at(b3,p2)], 
         [at(a1,p1),at(b1,p3),at(b3,p2)],M).

输入所有位置的起始状态以及它们应该结束的位置它将输出如下内容：

M = [move(p3,a1,t),move(p1,b1,b2),move(p3,t,b1), 
     move(p1,b2,t),move(p1,t,a1)]

显示了棋子从开始到结束所需的所有移动，以及其他棋子到达其位置所必须采取的移动。我认为最好为此使用广度优先搜索，但我不太确定从那里去哪里。

Answer 1

这是一个很好的问题，解决这个问题将是提高 Prolog 水平的好方法！所以我赞扬你选择的问题。

这个答案是一个草图，不是一个完整的解决方案，我希望这足以满足您的需求。

您接下来要做的是编写一个谓词来表达从一种状态到另一种状态的单个有效移动，如下所示：

singlemove(StartBoardState, Move, NextBoardState) :- ...

因此我们将 at(Place, Piece) 的列表视为棋盘状态，将 move(Piece,From,To) 等结构视为着法；前者将与 StartBoardState 和 NextBoardState 统一，后者与 Move.

统一

您的游戏规则应编码为 singlemove/3。您可以将其视为给定棋盘状态、每个有效移动和结果状态之间的关系。

我想一旦你有了这个，至少一种解决你问题的低效方法对你来说是显而易见的，那就是使用暴力搜索。一旦你开始工作（慢慢地，可能只适用于两步游戏），你就可以开始了解如何通过使搜索更智能来提高性能。

如何实施`singlemove/3`

从题目来看，这个游戏的规则是：

...it can only move 1 space at a time. No two pieces can occupy the same space, and no pieces can cross over to the other side if their is a piece in the t zone.

首先，让我们陈述一些关于董事会的事实。 space 叫什么？

boardspace(b1).
boardspace(b2).
boardspace(b3).
boardspace(t).
boardspace(a1).
boardspace(a2).
boardspace(a3).

现在我们需要一些位置信息。

:- op(300, xfx, left_of).
:- op(300, xfx, right_of).    

b1 left_of b2.
b2 left_of b3.
a1 left_of a2.
a2 left_of a3.

row(b1, upper).
row(b2, upper).
row(b3, upper).
row(a1, lower).
row(a2, lower).
row(a3, lower).

X right_of Y :- Y left_of X.

adjacent(X, Y) :- X left_of Y.
adjacent(X, Y) :- X right_of Y.
adjacent(t, X) :- boardspace(X), X \= t.
adjacent(X, t) :- boardspace(X), X \= t.

我还不确定我是否需要所有这些，但这似乎是一个合理的开始。现在让我们来谈谈规则。

因此游戏的三个规则是：

每回合只能移动一个。
一个棋子每回合只能移动一个space
没有两块可以占据相同的space。
如果t区有一块就没有一块可以"cross over to the other side"

我觉得 #1 完全可以通过谓词 singlemove/3 得到充分处理。一次调用，一步到位。

对于#2，我们可以根据现在与棋子相邻的东西构建附近 space 的列表。假设 p1 是移动并且我有一个上面定义的板，member(at(StartLocation, p1), Board), adjacent(StartLocation, EndLocation) 将统一 EndLocation 和 p1 可以移动的地方。让我们试试吧：

?- Board = [at(a1,p3),at(b1,p1),at(b3,p2)], 
   member(at(StartLocation, p1), Board), 
   adjacent(StartLocation, EndLocation).
Board = [at(a1, p3), at(b1, p1), at(b3, p2)],
StartLocation = b1,
EndLocation = b2 ;

Board = [at(a1, p3), at(b1, p1), at(b3, p2)],
StartLocation = b1,
EndLocation = t ;
false.

所以这似乎是正确的； b1的相邻位置是b2和t。

现在让我们编纂下一条规则，任何两块都不能占据相同的space。

unoccupied(Board, Location) :-
    \+ member(at(Location, _), Board).

现在我们可以在 singlemove/3:

将这两件事结合起来成为一个好的开始

singlemove(Board,
       move(Piece,StartLocation,EndLocation),
       [at(EndLocation,Piece)|RemainingLocations]) :-
    select(at(StartLocation,Piece), Board, RemainingLocations),
    adjacent(StartLocation, EndLocation),
    unoccupied(Board, EndLocation).

让我们试试看：

?- Board = [at(a1,p3),at(a2,p1),at(a3,p2)], 
   singlemove(Board, Move, NextBoard).
Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p3, a1, t),
NextBoard = [at(t, p3), at(a2, p1), at(a3, p2)] ;

Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p1, a2, t),
NextBoard = [at(t, p1), at(a1, p3), at(a3, p2)] ;

Board = [at(a1, p3), at(a2, p1), at(a3, p2)],
Move = move(p2, a3, t),
NextBoard = [at(t, p2), at(a1, p3), at(a2, p1)] ;

false.

那么这有什么有趣的呢？我正在使用 select/3 将列表分成候选人和余数。我在子句的头部构建结果。但除此之外，我真的只是采用你的规则，将它们翻译成 Prolog，然后列出它们。所以你可以看到你只需要一个谓词来实现你的第四条规则，它会在 unoccupied/2 之后执行，以进一步过滤掉无效的移动。

希望您了解流程的要点。我的数据模型可能太多了，但话又说回来，您可能会发现您需要的数据比最初看起来的要多。而且搜索策略很弱。但这是整体解决方案的基础，即基本案例。归纳案例会很有趣——我再次建议您尝试使用内置的深度优先策略，看看在求助于 BFS 之前它有多可怕。您可能想使用 trace/0 并查看何时陷入陷阱以及如何通过更好的显式推理来规避它。但我认为这是一个好的开始，希望对您有所帮助。

在 Prolog 中搜索游戏

Search Game in Prolog

search

artificial-intelligence

prolog

如何实施`singlemove/3`

在 Prolog 中搜索游戏

Search Game in Prolog

search

artificial-intelligence

prolog

如何实施singlemove/3

如何实施`singlemove/3`