SWI-Prolog深度优先搜索？

Question

我的目标是开发一个简单的程序来运行一个名为'Kayles'的游戏，它与Skittles类似。你有一排瓶子，两名球员轮流击倒他们，而球员击倒最后一瓶胜利。你只能敲下1或2瓶，而且必须彼此相邻。

该计划的第一部分是决定如何表示一个瓶子和一个空的空间。我决定使用一个列表，其中1代表一个瓶子，0代表一个空白空间。

该程序的第二部分是将当前状态打印到终端，其中瓶子由星号*表示，空白空间由间隙表示。

该程序的第三部分是列出并打印从当前状态可达到的所有可能的下一个状态。例如，如果您有3瓶[1,1,1]，则第一个瓶子被撞倒时，下一个可能的状态是[0,1,1]。所以这个谓词应该打印出所有可能的下一个状态的列表，再次用*和空格表示。

我已经成功地做到以上，这是我到目前为止的代码：

printstate([]) :- nl. 
printstate([B|L]) :- (B=0 -> write(' '); write('*')), printstate(L). 

next([1|S], [0|S]). 
next([1,1|S], [0,0|S]). 
next([0|S], [0|T]) :- next(S,T). 
next([1|S], [1|T]) :- next(S,T). 

printnextstates(S,T) :- next(S,T), printstate(T), fail. 

下一位是我坚持的一点！所以我们的目标是要确定一个状态的值是1，如果第一个移动的玩家可以强制取胜，否则为0。我要编写一个谓词值（S，X），它将通过在游戏树中进行深度优先搜索来计算任何游戏状态S的值X.如果可能的话，我应该使用断言来避免搜索多次探索任何位置。

我不知道该怎么做！

到目前为止，这是我能想出：

value(S,X) :- S = 1, ([S,T] = 1); 0. 

但我敢肯定它不是那么简单，但我不知道如何开始这个问题！我已经研究过深度优先搜索，但是我没有足够的理解来写这个......有没有人知道在开始这个问题时可能会怎么样？

任何帮助非常感谢！

Answer 1

由于玩家可以随意挑选任何位置的元素，因此问题的适当数据表示会带来显着的简化：假设我们保留可用瓶子的列表。然后，你可以做到这宣告逻辑：

win(P) :- 
    move(P, P1), 
    \+ win(P1). 
win(P) :- move(P, []). 

move([_|R], R). 
move([_,_|R], R). 

这里一个愚蠢的测试，达到了一些任意长度，没有注意到，一个简单的递推公式给出结果

?- setof(N, L^(between(1,20,N),length(L,N),win(L)), Wins). 
Wins = [1, 2, 4, 5, 7, 8, 10, 11, 13|...].