政策・メディア研究科 修士課程2年 酒井政裕 学籍番号: 80524693
パズルやゲームのロジックおよび定石の帰納論理プログラミングを用いた学習。
将棋や囲碁の強いプログラムを書くことの難しさは良く知られているが、ゲー ムやパズルをブルートフォースで解くと、計算量が非常に大きくなることが多 い。例えば、マインスイーパがNP完全であるとか、倉庫番がPSPACE完全である といった例が良く知られている。計算量の大きさの問題から、これらのゲーム・ パズルをプレイするプログラムの多くはブルートフォースだけでなく、様々な ロジックや定石も用いており、それらは重要な位置を占めている。
一方、人間の学習の支援にプログラムを用いることを考えると、ブルートフォー スによって発見するような解や手ではなく、実際に人間が実行可能な解や手を 使うことが重要になる。
そこで、ゲームやパズルのロジックや定石を機械学習によってプログラムに学 習させることが考えられる。これらのゲームでは盤面やマスの間の相互の関係 など多くの背景知識を必要とするので、学習方法は帰納論理プログラミングが 適当である。
ここでは、有名なパズルである数独(すうどく)を対象に、帰納論理プログラミ ングシステムAlephを用いて学習させることを試みた。
数独については様々な場所で解説されているが、9×9の正方形の枠内に1〜9ま での数字を「縦・横の各列及び、太線で囲まれた3×3 のブロックに同じ数字 が入ってはいけない」という条件を満たすように書き入れるパズルである。問 題は例えば右の図のような形をしている。
学習の対象としては「put(+盤面の状態, +新しく記入する位置, +新しく記入する数字)」という形の述語を選んだ。
また、背景知識として用いる述語に関しては、位置の集合や数字の集合を扱う 述語を中心に用意した。私は SWI-Prolog 上ではなく YAP 上で Aleph を使っ ているので、特に集合演算に関してはordsetsライブラリの述語を幾つか用い た。
% sudoku.b
:- use_module(library(lists)).
:- use_module(library(ordsets)).
allnum([1,2,3,4,5,6,7,8,9]).
allpos(PS) :-
allcord(CS), findall((X,Y), (member(X,CS),member(Y,CS)), L),
list_to_ord_set(L, PS).
allcord([0,1,2,3,4,5,6,7,8]).
:- mode(1, row(+pos, -posset)).
:- mode(1, column(+pos, -posset)).
:- mode(1, block(+pos, -posset)).
row((_,Y), PS) :- allcord(CS), findall((X,Y), member(X,CS), PS).
column((X,_), PS) :- allcord(CS), findall((X,Y), member(Y,CS), PS).
box((X,Y), PS) :-
X0 is (X // 3) * 3, X1 is X0 + 1, X2 is X0 + 2,
Y0 is (Y // 3) * 3, Y1 is Y0 + 1, Y2 is Y0 + 2,
findall((XX,YY), (member(XX,[X0,X1,X2]), member(YY,[Y0,Y1,Y2])), L),
list_to_ord_set(L, PS).
:- mode(1, singleton(-num, +numset)).
:- mode(1, singleton(-pos, +posset)).
singleton(X,[X]).
:- mode(1, ord_intersection(+posset,+posset,-posset)).
:- mode(1, ord_subtract(+posset,+posset,-posset)).
:- mode(1, ord_union(+posset,+posset,-posset)).
:- mode(1, ord_intersection(+numset,+numset,-numset)).
:- mode(1, ord_subtract(+numset,+numset,-numset)).
:- mode(1, ord_union(+numset,+numset,-numset)).
:- mode(1, collectSafePos(+board,+num,-posset)).
collectSafePos(BOARD,N,PS) :-
allpos(AP), findall(P, (member(P,AP), safe(BOARD,N,P)), PS).
:- mode(1, collectSafeNum(+board,+pos,-numset)).
collectSafeNum(BOARD,P,NS) :-
allnum(AN), findall(N, (member(N,AN), safe(BOARD,N,P)), NS).
safe(BOARD,N,P) :- \+( unsafe(BOARD,N,P) ).
unsafe(BOARD, _, (X,Y)) :- member((X,Y,_), BOARD).
unsafe(BOARD, N, (X,_)) :- member((X,_,N), BOARD).
unsafe(BOARD, N, (_,Y)) :- member((_,Y,N), BOARD).
unsafe(BOARD, N, (X,Y)) :- box((X,Y),PS), member((X1,Y1),PS), member((X1,Y1,N),BOARD).
:- mode(1, put(+board, +pos, +num)).
:- determination(put/3, row/2).
:- determination(put/3, column/2).
:- determination(put/3, box/2).
:- determination(put/3, singleton/2).
:- determination(put/3, ord_intersection/3).
:- determination(put/3, ord_subtract/3).
:- determination(put/3, ord_union/3).
:- determination(put/3, collectSafePos/3).
:- determination(put/3, collectSafeNum/3).
:- set(i,5).
:- set(clauselength,5).
:- set(noise,8).
:- set(print,1).
正例としては以下のような形の事実を50個程度与えた。
また、負例としては以下のような形の事実を20個程度与えた。
これらはいずれも別のプログラムで自動生成したものである。
私は例えば以下のようなルールが学習されることを期待していた。これらのルー ルは今回与えた正例を説明し、負例を説明しない。しかし、残念ながらこのよ うなルールは得ることが出来ず、与えた正例全てをそのまま含むようなルール しか得ることが出来なかった。背景知識やパラメータを変更しながら色々と試 してみたが結果は変わらなかった。おそらく何処かに誤りがあるのであろうが、 今回はその原因を特定するには至ることが出来なかった。
put(BOARD, P, N) :-
collectSafePos(BOARD,N,PS1),
column(P,PS2),
ord_intersection(PS1,PS2,PS),
singleton(P,PS).
put(BOARD, P, N) :-
collectSafePos(BOARD,N,PS1),
row(P,PS2),
ord_intersection(PS1,PS2,PS),
singleton(P,PS).
put(BOARD, P, N) :-
collectSafePos(BOARD,N,PS1),
block(P,PS2),
ord_intersection(PS1,PS2,PS),
singleton(P,PS).
put(BOARD,P,N) :-
collectSafeNum(BOARD,P,NS),
singleton(N,NS).