エンジニアのソフトウェア的愛情

または私は如何にして心配するのを止めてプログラムを・愛する・ようになったか

PrologでTick-Tack-Toeをどう書く

Prologのトレーニング中。今日も「どう書く」の過去問から。


今回は、条件分岐を使ってみたのですが、見事にハマりました。


gameの3番目の定義ですが、最初は次のように書いていました。

game([H|Hs], Player, Board, Result) :-
    subst(H, Player, Board, NextBoard),
    succeed(NextBoard) ->
        format_to_chars("~a won.", Player, Result);
        switch_player(Player, NextPlayer), game(Hs, NextPlayer, NextBoard, Result).


cond -> p1; p2というのが条件分岐で、condが真ならp1が、偽ならp2が評価されます。
どう見てもこれで問題なさそうなんですが、思い通りに動きません。動作をひとつひとつトレースしたところ、末尾のgame(Hs, NextPlayer, NextBoard, Result)内のNextBoardが自由変数(値が決定されていない変数)になっていました。subst(H, Player, Board, NextBoard)NextBoardの値は決定されているはずなのになんで? と思ったら。


上の式は実は次のような意味なのでした。

game([H|Hs], Player, Board, Result) :-
    (subst(H, Player, Board, NextBoard), succeed(NextBoard)) ->
        format_to_chars("~a won.", Player, Result);
        switch_player(Player, NextPlayer), game(Hs, NextPlayer, NextBoard, Result).


つまり、succeed(NextBoard)が偽になると、subst(H, Player, Board, NextBoard), succeed(NextBoard)全体が偽になってしまい、NextBoardの値も破棄されてしまいます。その上で値が偽ということでswitch_player(Player, NextPlayer), game(Hs, NextPlayer, NextBoard, Result)が評価されるので、上記のような理由からNextBoardが決定されていない、という事態になっているのでした。


Prolog道は、なかなか厳しいです。


以下、最終的なコード。

chr2int(C, N) :- N is  C - 48.
str2int(S, L) :- maplist(chr2int, S, L).

init_board( [ blank, blank, blank,
              blank, blank, blank,
              blank, blank, blank ] ).

succeed([X,X,X,_,_,_,_,_,_]) :- X \== blank, !.
succeed([_,_,_,X,X,X,_,_,_]) :- X \== blank, !.
succeed([_,_,_,_,_,_,X,X,X]) :- X \== blank, !.
succeed([X,_,_,X,_,_,X,_,_]) :- X \== blank, !.
succeed([_,X,_,_,X,_,_,X,_]) :- X \== blank, !.
succeed([_,_,X,_,_,X,_,_,X]) :- X \== blank, !.
succeed([X,_,_,_,X,_,_,_,X]) :- X \== blank, !.
succeed([_,_,X,_,X,_,X,_,_]) :- X \== blank, !.

switch_player(o, x).
switch_player(x, o).

subst(1, X, [_|Xs], [X|Xs]).
subst(N, X, [Y|Xs], [Y|Ys]) :- N > 1, N1 is N - 1, subst(N1, X, Xs, Ys).

game(_, _, Board, "Draw game.") :-
    not(member(blank, Board)).

game([H|_], Player, Board, Result) :-
    nth1(H, Board, C),
    C \== blank,
    switch_player(Player, Opposition),
    format_to_chars("Foul: ~a won.", Opposition, Result).

game([H|Hs], Player, Board, Result) :-
    subst(H, Player, Board, NextBoard),
    ( succeed(NextBoard) ->
        format_to_chars("~a won.", Player, Result);
        switch_player(Player, NextPlayer), game(Hs, NextPlayer, NextBoard, Result) ).

ord1(S, R) :- str2int(S, S0), init_board(B), game(S0, o, B, R).

test(S) :- ord1(S, R), format("~s~n", [R]).

tests :-
    test("79538246"),
    test("35497162193"),
    test("61978543"),
    test("254961323121"),
    test("6134278187"),
    test("4319581"),
    test("9625663381"),
    test("7975662"),
    test("2368799597"),
    test("18652368566"),
    test("965715"),
    test("38745796"),
    test("371929"),
    test("758698769"),
    test("42683953"),
    test("618843927"),
    test("36535224"),
    test("882973"),
    test("653675681"),
    test("9729934662"),
    test("972651483927"),
    test("5439126787"),
    test("142583697"),
    test("42198637563"),
    test("657391482").


実行結果。

$ swipl -s ord1.pl -g tests -t halt
x won.
x won.
x won.
x won.
x won.
Foul: x won.
Foul: x won.
Foul: x won.
Foul: x won.
Foul: x won.
o won.
o won.
o won.
o won.
o won.
Foul: o won.
Foul: o won.
Foul: o won.
Foul: o won.
Foul: o won.
Draw game.
Draw game.
Draw game.
Draw game.
Draw game.