康威生命游戏最简洁的prolog实现是什么？

Question

我今晚推出了一个版本（如下），但感觉我是从另一种过程语言移植过来的，并且没有利用许多"纯"Prolog功能。

只需运行它，每次按Enter键即可进行下一代操作。

这里有一个版本（迷宫般的比例）

当我用Prolog攻击问题时，我注意到的一件事是，总是（99%的时候）有一个更整洁的实现，这次感觉就是这样。

你能想到什么更好的实现吗？我对我的不满意。它是有效的，并且不是非常低效（？），但仍然。。。

似乎我可以更好地利用统一，也就是说，与其将邻居视为相对于我单独检查的任何给定单元格的X、Y坐标，我本可以让Prolog为我做一些繁重的工作。

% Conway Game of Life (Stack Overflow, 'magus' implementation)
% The life grid, 15x15
grid([
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
     ]
   ).
% Infinite generates sep with keystroke
% -------------------------------------
life(Grid) :-
    dumpgen(Grid),
    onegen(Grid, 0, NewGrid),
    get_single_char(_),
    life(NewGrid).

% Dumps a generation out
% ----------------------
dumpgen([]) :- nl.
dumpgen([H|T]) :-
    write(H), nl,
    dumpgen(T).
% Does one generation
% --------------------------------
onegen(_, 15, []).
onegen(Grid, Row, [NewRow|NewGrid]) :-
    xformrow(Grid, Row, 0, NewRow),
    NRow is Row + 1,
    onegen(Grid, NRow, NewGrid).
% Transforms one row
% --------------------------------
xformrow(_, _, 15, []).
xformrow(Grid, Row, Col, [NewState|NewList]) :-
    xformstate(Grid, Row, Col, NewState),
    NewCol is Col + 1,
    xformrow(Grid, Row, NewCol, NewList).

% Request new state of any cell
% --------------------------------
xformstate(Grid, Row, Col, NS) :-
    cellstate(Grid, Row, Col, CS),
    nextstate(Grid, Row, Col, CS, NS).
% Calculate next state of any cell
% --------------------------------
% Cell is currently dead
nextstate(Grid, Row, Col, 0, NS) :-
    neightotal(Grid, Row, Col, Total),
    (Total =:= 3 -> NS = 1 ; NS = 0).
% Cell is currently alive
nextstate(Grid, Row, Col, 1, NS) :-
    neightotal(Grid, Row, Col, Total),
    ((Total =:= 2; Total =:=3)
    -> NS = 1; NS = 0).
% State of all surrounding neighbours
%-------------------------------------
neightotal(Grid, Row, Col, TotalSum) :-
    % Immediately neighbours X, Y
    XM1 is Col - 1,
    XP1 is Col + 1,
    YM1 is Row - 1,
    YP1 is Row + 1,
    % State at all those compass points
    cellstate(Grid, YM1, Col, N),
    cellstate(Grid, YM1, XP1, NE),
    cellstate(Grid, Row, XP1, E),
    cellstate(Grid, YP1, XP1, SE),
    cellstate(Grid, YP1, Col, S),
    cellstate(Grid, YP1, XM1, SW),
    cellstate(Grid, Row, XM1, W),
    cellstate(Grid, YM1, XM1, NW),
    % Add up the liveness
    TotalSum is N + NE + E + SE + S + SW + W + NW.

% State at any given row/col - 0 or 1
% -----------------------------------
% Valid range, return it's state
cellstate(Grid, Row, Col, State) :-
    between(0, 14, Row),
    between(0, 14, Col),
    nth0(Row, Grid, RL),
    nth0(Col, RL, State).
% Outside range is dead
cellstate(_, _, _, 0).

执行：

[debug]  ?- grid(X), life(X).
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,1,0,1,0,1,0,0,0,0,0]
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,0,0,1,0,1,0,1,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,1,0,1,0,0,0,0,0,0]
[0,0,0,0,1,1,0,0,0,1,1,0,0,0,0]
[0,0,0,0,1,1,1,0,1,1,1,0,0,0,0]
[0,0,0,0,1,1,0,0,0,1,1,0,0,0,0]
[0,0,0,0,0,0,1,0,1,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0]
[0,0,0,1,0,0,1,0,1,0,0,1,0,0,0]
[0,0,0,0,1,0,0,0,0,0,1,0,0,0,0]
[0,0,0,0,0,1,0,0,0,1,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
[0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
etc.

Answer 1

我认为逻辑的简单性要求最简单的数据结构，这最终与其他语言类似。

但暂时来说，我们可以使用SWI-Prolog提供的无限精度整数和位域运算符：然后一行可以是整数，测试单元的状态可以"一次"将3行移到一起，并屏蔽低位：我们只需要考虑9个位，即512个值，可以预计算。当然，边界检查可能会使算法复杂化：然后一些"带外"填充可能会有所帮助。

这应该很容易做到。

编辑：这是我的努力：

% Conway Game of Life (Stack Overflow, 'chac' implementation)
%
:- module(lifec, [play/0]).
play :-
    grid(G),
    lifec(G).
% The life grid, 15x15
grid([
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,0,0,1,0,0,0,0,0],
      [0,0,0,0,0,1,0,1,0,1,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0],
      [0,0,0,0,0,0,0,0,0,0,0,0,0,0,0]
     ]
   ).
% Infinite generates sep with keystroke
% -------------------------------------
lifec(Grid) :-
    make_ints(Grid, Ints, Size),
    lifei(Ints, Size).
lifei(Ints, Size) :-
    dumpgen(Ints, Size),
    onegen(Ints, Size, NewInts),
    get_single_char(_),
    !, lifei(NewInts, Size).
dumpgen(Ints, Size) :-
    forall(member(I, Ints),
           ( for_next(1, Size, _, show_bit(I)), nl) ).
onegen(Matrix, Size, NewMatrix) :-
    findall(NewBits,
        (three_rows(Matrix, Size, Rows),
         rowstate(Rows, 0, Size, 0, NewBits)), NewMatrix).
three_rows(Matrix, Size, Rows) :-
    nth1(I, Matrix, Row),
    ( I > 1 -> U is I - 1, nth1(U, Matrix, Up) ; Up = 0 ),
    ( I < Size -> D is I + 1, nth1(D, Matrix, Down) ; Down = 0 ),
    % padding: add 0 bit to rightmost position
    maplist(lshift, [Up, Row, Down], Rows).
:- dynamic evopatt/2.
rowstate([_, _, _], Size, Size, NewBits, NewBits) :- !.
rowstate([U, R, D], I, Size, Accum, Result) :-
    Key is (U / 7) / ((R / 7) << 3) / ((D / 7) << 6),
    evopatt(Key, Bit),
    Accum1 is Accum / (Bit << I),
    maplist(rshift, [U,R,D], P),
    J is I + 1,
    rowstate(P, J, Size, Accum1, Result).
%%  initialization
%
make_ints(Grid, Ints, Size) :-
    length(Grid, Size),
    maplist(set_bits(0, 0), Grid, Ints),
    % precompute evolution patterns
    retractall(evopatt(_, _)),
    for_next(0, 511, _, add_evopatt).
add_evopatt(N) :-
    maplist(take_bit(N), [0,1,2], U),
    maplist(take_bit(N), [3,4,5], V),
    maplist(take_bit(N), [6,7,8], Z),
    rule(U, V, Z, Bit),
    assert(evopatt(N, Bit)).
% rules from Rosetta Code
%
rule([A,B,C],[D,0,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3.
rule([_,_,_],[_,0,_],[_,_,_],0).
rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I < 2.
rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 2.
rule([A,B,C],[D,1,F],[G,H,I],1) :- A+B+C+D+F+G+H+I =:= 3.
rule([A,B,C],[D,1,F],[G,H,I],0) :- A+B+C+D+F+G+H+I > 3.
%%  utilities
%
:- meta_predicate for_next(+,+,-,1).
for_next(From, To, N, Pred) :-
    forall(between(From, To, N), call(Pred, N)).
lshift(X, Y) :- Y is X << 1.
rshift(X, Y) :- Y is X >> 1.
show_bit(I, P) :-
    take_bit(I, P - 1, 1) -> put(0'*) ; put(0' ).
take_bit(N, Pos, Bit) :-
    Bit is (N >> Pos) / 1.
set_bits(_Index, Accum, [], Accum).
set_bits(Index, Accum, [ZeroOne|Rest], Number) :-
    Accum1 is Accum / (ZeroOne << Index),
    Index1 is Index + 1,
    set_bits(Index1, Accum1, Rest, Number).