时间戳

首页 > 解决方案 > 如何在 Prolog 中编写特定游戏？

prolog - 如何在 Prolog 中编写特定游戏？

问题描述

我在编写下述程序时遇到问题

考虑下面的游戏。给出了一个带有三颗黑子、三颗白子和一个空白区域的棋盘。游戏的目标是将黑棋子与白棋子交换位置。移动规则定义以下句子： 交替移动白色和黑色块。每个棋子可以垂直或水平移动，占据一个空白空间。每一块都可以垂直或水平地跳过另一块（任何颜色）。在 Prolog 中编写一个程序，找出所有可能的方法来找到一个获胜的序列。例如，如果我们问这个问题：

? - play (w, s (w, w, w, e, b, b, b), s (b, b, b, e, w, w, w), S, R ).

序言应该回答，例如：

S = [s (w, w, w, e, b, b, b), s (w, e, w, w, b, b, b), ..., s (b, b, b, e, w, w, w)] R = [[w, 2,4], [b, 6,2], [w, 4,6], ..., [w, 4,6]]

这里[ w, 2,4]意味着将白兵从位置 2 移动到位置 4。当然 Prolog 应该完整返回字母 S 和 R（不带“...”）。

棋盘上不同棋子设置的最大数量是多少？检查查询：

? - play (_, s (w, w, w, e, b, b, b), s (b, b, e, w, w, b, w), _, _).

Prolog的答案是什么意思？提示：先解决play/4没有 R的问题

还有一个看起来像这样的游戏板：

游戏板

我根本不知道从哪里开始？我怎样才能做到这一点？各位大佬能帮我看看这个吗？

标签： prologstate-space

解决方案

这是标准状态空间搜索，至少从 50 年代中期开始就是 GOFAI 的标准范式。

准系统算法：

search(State,Path,Path) :- is_final(State),!.  % Done, bounce "Path" term
search(State,PathSoFar,PathOut) :- 
   generate_applicable_operators(State,Operators),
   (is_empty(Operators) -> fail ; true),   
   select_operator(Operators,Op,PathSoFar),
   apply_operator(State,Op,NextState), % depth-first / best first 
   search(NextState,[[NextState,Op]|PathSoFar],PathOut).

% Called like this, where Path will contain the reverse Path through
% State Space by which one may reach a final state:

search(InitialState,[[InitialState,nop]],Path).

首先，您需要在这种情况下表示给定状态，即棋盘状态（在某个时间 t）。

我们可以列出棋盘位置及其内容（w白色、黑色、b空令牌）或列出令牌及其位置。让我们列出董事会职位。e

在 Prolog 中，可以轻松进行模式匹配的术语是合适的。这个问题已经提供了一些东西：(w, w, w, e, b, b, b)。这似乎受到 LISP 的启发，并不能很好地适应 Prolog。让我们使用一个列表来代替：[w, w, w, e, b, b, b]

董事会职位与列表职位的映射应为：

       +---+---+
       | 0 | 1 |
   +---+---+---+
   | 2 | 3 | 4 |
   +---+---+---+
   | 5 | 6 |
   +---+---+

我们已经完成了状态描述的设置！

然后您需要表示/定义可以应用于状态的运算符（操作？）：它们将有效状态转换为另一个有效状态。

运算符对应于“移动令牌”，当然并非所有运算符都适用于给定状态（如果那里没有令牌，则不能从字段 1 移动令牌；如果已经有令牌，则不能将令牌移动到字段 1那里）。

因此，您想编写一个谓词，将棋盘状态链接到适用于该状态的运算符：generate_applicable_operators/2

然后您需要选择您要申请的运营商。这可以根据一些启发式（例如A*）随机、详尽地完成，但绝对需要检查到目前为止通过状态空间所采用的路径以避免循环：select_operator/3。

然后应用运算符生成下一个状态：apply_operator/3.

最后递归调用search/3寻找下一步。这一直持续到“最终状态”，在这种情况下[b, b, b, e, w, w, w]已经达到！

如果要执行“广度优先搜索”，也可以使用迭代深化，但必须修改算法结构。

就是这样。

推荐阅读