なんかネタをふられました．
はじめてのにき (2008-08-13) _ 棒けしゲーム
ニコニコ見れない人なので，テキトーに棒消しゲームの仕様を検索．
とりあえず swi-prolog で仕様を書いてみました．ET と Prolog と，確定節で書く限り，問題の表現能力自体に差はありません．そこから先，どういう仕様に対して正しい手続きを議論できるのか，は変わりますが．
% 棒消し(山の大きさ，ゲーム展開，結果)
% ゲーム展開 = 棒消し操作の情報 (X 番目の列の Y 番目から連続 Z 本消した) の列
% 自分は必ず先手
boukeshi(N, Os, R) :- initState(N, S), printState(N, S), !, me(S, N, Os, R).
% 自分とコンピュータで交互にプレイ
me(S, _, [], R) :- dropGame(S), R = lose, !.
me(S, N, [O | Os], R) :- choice(S, N, O), com(S, N, Os, R).
com(S, _, [], R) :- dropGame(S), R = win, !.
com(S, N, [O | Os], R) :- choice(S, N, O), me(S, N, Os, R).
% 行の非決定的な選択(状態, 行番号, [何列目の，何行目を，連続何本倒したか])
choice([S | _], N, [N, Y, Z]) :- kesu(S, 1, Y, Z).
choice([_ | Ss], N, O) :- N1 is N - 1, choice(Ss, N1, O).
% 非決定的印に棒をどこか消す （変数をテキトウに具体化）
kesu([R | Rs], N, N, Z) :- var(R), R = ' ', renzokuKeshi(Rs, 0, Z).
kesu([_ | Rs], N, Y, Z) :- N1 is N + 1, kesu(Rs, N1, Y, Z).
% 連続して非決定的に何本か消す
renzokuKeshi(_, N, N).
renzokuKeshi([R | Rs], N, Z) :- var(R), R = ' ', N1 is N + 1, renzokuKeshi(Rs, N1, Z).
%%%%%%%%%%%%%%%%%%%%%%%%%%%%% misc %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% 最大 N 行の棒山を作る
initState(0, []).
initState(N, [R | Rs]) :- makeRow(N, R), N1 is N - 1, initState(N1, Rs).
makeRow(0, []).
makeRow(N, [_ | R]) :- N1 is N - 1, makeRow(N1, R).
% 棒山の表示
printState(N, S) :- printState1(N, N, S), printRow0(N), print('\n----------\n').
printRow0(0) :- print(' ').
printRow0(N) :- N1 is N - 1, printRow0(N1), print(N).
printState1(_, _, []).
printState1(N, N1, [R | Rs]) :- N2 is N1 -1, printState1(N, N2, Rs), print(N1), printRow(R).
printRow([]) :- !, print('\n').
printRow([X | Xs]) :- var(X), print('|'), printRow(Xs).
printRow([_ | Xs]) :- print(' '), printRow(Xs).
% 終了判定．最後の棒（変数）だったら負け
dropGame(S) :- nvar(S, 0, N), N = 1, !.
% nvar(Term, に含まれる変数の数)
nvar([], N, N).
nvar([R | Rs], A, N) :- nvar1(R, A, A1), nvar(Rs, A1, N).
nvar1([V | Rs], A, N) :- var(V), !, A1 is A + 1, nvar1(Rs, A1, N).
nvar1([_ | Rs], A, N) :- nvar1(Rs, A, N).
nvar1([], N, N).
可能な状態空間を全て表示するだけです．
?- boukeshi(2, Os, R).
1|
2||
12
----------
Os = [[2, 1, 0], [2, 2, 0]],
R = lose ;
Os = [[2, 1, 0], [1, 1, 0]],
R = lose ;
Os = [[2, 1, 1]],
R = win ;
Os = [[2, 2, 0], [2, 1, 0]],
R = lose ;
Os = [[2, 2, 0], [1, 1, 0]],
R = lose ;
Os = [[1, 1, 0], [2, 1, 0]],
R = lose ;
Os = [[1, 1, 0], [2, 2, 0]],
R = lose ;
false.
あとは，どの手が良いかを評価する関数を作って，全通り計算しまくれば解けるはず．対戦ゲームの思考ルーチンとか書いたこと無いので，これ以上はパッと思いつきませんが，たぶん minmax 法とかそういうやつを使って，全ての手数に対して勝った負けたをボトムアップに積み上げて行って，値が最大になる手を常に選択していけば，たぶん必ず先手が勝てるのではないでしょうか ? (そのうち実装してみます．ナイーブに書くと，山の行の数が最大 5 でも状態数が多すぎて解けないかもしれないけど)
|
