2016年3月21日月曜日

Prologで作るオセロ盤


最近はAI(Deep Lerning)のプログラムに囲碁のプロが負けちゃう時代のようです。個人的にはAIって超うさんくさいのであります。囲碁の場合も学習でユニークな評価関数が出来たって話なのか？それとも囲碁特有の解き方が見つかったのかでだいぶ違いがあると思うですよね。AIってなんだろう？？難しいテーマですなぁ。

で、AI言語（古い〜）といえばPrologですので、

　　作ってみたよ。Prologでオセロ盤。使っているのはswi-prologです。

初期状態から打ち手を入れて、ゲーム終了になるまで繰り返します。

あくまでもお試しなので、UIその他は最小限の実装。「待った」はできません。
（ん？Prologで待ったかぁ。やりにくそうだな。ま、打ち手と盤を指すごとに残せばいいのか。）

徐々に追記しますが、とりあえず「ザクッ」っとつくったソースだけ晒します。効率や見た目はそこまでちゃんと詰めてないのはご容赦を。あと、一部デバッグ用のwriteln()が残ってます。ま、表示が汚れますけど、今は気にしない（笑）。

基本の考え方だけ

・盤情報の持ち方
　座標は11,21,....,78,88という２桁の数字にします。本当はA1,...H8ですが、処理をサボるためにこうなってます。
　黒い駒が置いてある座標のリストをBlack,白い駒が置いてある場所のリストをWhiteとして、引っ張り回します。

　play :- play(black,white,[44,55],[45,54]).
　→手番black,(次の手番white), 黒の座標リスト、白の座標リスト
　　を食わせた、初期状態からのプレイはこんな感じです。

　普通だと、8X8の配列にしちゃうところですが、Prologと配列はそんなに相性がよいわけでもなし、インデックスで指せないならこの方がいいんじゃないかと思います。あとは、計算結果を残しておくためのデータベースなんてのは今時必須なのですが、高速に実装する方法を考えないといけない。Cとかなら、ハッシュ使ってO(1)に近い検索ができるけど、２分木じゃO(logn)になっちゃうからなぁ。ハッシュは調べないといかんし、これできないなら、しんどいわな。

・駒の反転　checkput()
　direction(方向リスト)に、ある地点から隣へ移動するために加算する数値をいれてあります。８方向に移動するのは、これを使います。
　　direction([-11,-10,-9,-1,1,9,10,11]).
　　→順に、[左上、上、右上、左、右、左下、下、右下]との駒の距離が入ってます。
　　　盤は8X8ですが、数字的には10増減するごとに上下しますので、ここは注意が必要。

　調べたい座標は、board(座標リスト)から引いてきて、
　　 空いている(Black,Whiteのmemberでない）場所からスタート。上記の[方向リスト]を足しながら、隣の場所を確認
     - 盤からはみ出たらfalseで終了
     - 自分の駒にあたったとき、途中に相手の駒があればtrue.その数と座標リストを返します。
     - 相手の駒に当たった時、ひっくり返す数をインクリメントして、さらに隣をチェックに行きます。
   
割とあっさり出来たような気がします（３時間くらい）。

さて、このプログラムの詳細もありますが、ここから、コンピューターによる打ち手を求めるプログラムを軽く作ってみるのが本題ですねぇ。

　まずは、中間評価関数を作って先読みなしで打つのを実装して、次に先読み。アルファベータ的ななにかを実装できるんか？それと、最後の数マスでは完全読み切りを作ることが重要かな。この辺りは、速度も気にしないといけないんだけど、今回は、このデータ構造でやれるかどうかを確認してみようと思います。

追記１：
・入力のところがなんか気に入らないですよね。こういうのがどうしてもPrologでオセロ作りたくない気分にさせる要因のひとつかなぁ。


＃こういうのってCで書いた方が楽な気がしてたんですけど、思ったよりさっくりかけた。
＃あとは、すくなくとも、自分より強いプログラムをさっくり記述できたら、Prologの勝ちだな（笑）
＃さて、将棋盤とか作れるのかなぁ？より複雑になるので、もっと真面目に考えないといけなさそうです。

実行結果はこんな感じ、コピペしたらフォントの関係かちょっとずれてますね。うひひ。
---8<------8 p="">
16 ?- play.
Game Playing
[teabn,black,[44,55],[45,54]]
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . . . . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
Enter Place:53
[[54]]
Game Playing
[teabn,white,[53,54,44,55],[45]]
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . O . . .
4 . . . O O . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
Enter Place:63
[[54]]
Game Playing
[teabn,black,[53,44,55],[63,54,45]]
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . O X . .
4 . . . O X . . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . .
Enter Place:64
[[54]]
Game Playing
[teabn,white,[64,54,53,44,55],[63,45]]
1 2 3 4 5 6 7 8
1 . . . . . . . .
2 . . . . . . . .
3 . . . . O X . .
4 . . . O O O . .
5 . . . X O . . .
6 . . . . . . . .
7 . . . . . . . .
8 . . . . . . . . 

ここからはソースコード
---8<------8 p="">
board([11,21,31,41,51,61,71,81,12,22,32,42,52,62,72,82,13,23,33,43,53,63,73,83,14,24,34,44,54,64,74,84,
       15,25,35,45,55,65,75,85,16,26,36,46,56,66,76,86,17,27,37,47,57,67,77,87,18,28,38,48,58,68,78,88]).

direction([-11,-10,-9,-1,1,9,10,11]).

member(X,[X|L]).
member(X,[_|L]):-member(X,L).


delete(X,[X|L],L).
delete(X,[Y|L],[Y|L1]):-
    delete(X,L,L1).

deletelist([],L,L).
deletelist([X|Rest],L,L1):-
    delete(X,L,L2),
    deletelist(Rest,L2,L1).

deletelists([],L,L).
deletelists([X|Rest],L,L1):-
    deletelist(X,L,L2),
    deletelists(Rest,L2,L1).

append([],X,X).
append([A|X],Y,[A|Z]):-
    append(X,Y,Z).

appendlists(Move,[],X,[Move|X]).
appendlists(Move,[L|Rest],List,List1):-
    append(L,List,List2),
    appendlists(Move,Rest,List2,List1).

isGameEnd(Black,White):-
    isPut(black,Black,White,_,_),!,fail.
isGameEnd(Black,White):-
    isPut(white,Black,White,_,_),!,fail.
isGameEnd(Black,White).


isPass(Teban,Black,White):-
    isPut(Teban,Black,White,_,_),!,fail.
isPass(Teban,Black,White).


printBoard(Teban,Black,White) :- 
    writeln([teabn,Teban,Black,White]),
    write('  1 2 3 4 5 6 7 8'),
    board(BD),
    printBoard1(BD,Black,White).

printBoard1([],Black,White).
printBoard1([BD|_],_,_):-
    BD // 10 =:= 1,X1 is BD mod 10,nl,write(X1),write(' '),fail.

printBoard1([BD|Rest],Black,White):-
    member(BD,Black),!,
    write("O "),
    printBoard1(Rest,Black,White).

printBoard1([BD|Rest],Black,White):-
    member(BD,White),!,
    write("X "),
    printBoard1(Rest,Black,White).

printBoard1([BD|Rest],Black,White):-
    write(". "),
    printBoard1(Rest,Black,White).

empty(P,Black,White):-
    not(member(P,Black)),
    not(member(P,White)).

checkput1(Teban,Black,White,X,X1,DX,Num,_):- X1 < 1 ,!,fail. 
checkput1(Teban,Black,White,X,X1,DX,Num,_):- X1 > 88,!,fail.
checkput1(Teban,Black,White,X,X1,DX,Num,_):- (X1 mod 10) =:= 0,!,fail.
checkput1(Teban,Black,White,X,X1,DX,Num,_):- (X1 mod 10) =:= 9,!,fail.
checkput1(Teban,Black,White,X,X1,DX,Num,_):- empty(X1,Black,White),!,fail.
checkput1(black,Black,White,X,X1,DX,0,_)  :- member(X1,Black),!,fail.
checkput1(black,Black,White,X,X1,DX,_,[])  :- member(X1,Black),!.
checkput1(white,Black,White,X,X1,DX,0,_)  :- member(X1,White),!,fail.
checkput1(white,Black,White,X,X1,DX,_,[])  :- member(X1,White),!.
checkput1(Teban,Black,White,X,X1,DX,Num,[X1|List])  :- 
    X2 is X1 + DX,
    Num1 is Num + 1,
    checkput1(Teban,Black,White,X1,X2,DX,Num1,List).

checkput(Teban,Black,White,X,List):- 
    direction(DL),
    member(DX,DL),
    X1 is X + DX ,checkput1(Teban,Black,White,X,X1,DX,0,List).

isPut(Teban,Black,White,X,List):-
    board(P),
    member(X,P),
    empty(X,Black,White),
    checkput(Teban,Black,White,X,List).

makePutList(Teban,Black,White,L):-
    findall(X,isPut(Teban,Black,White,X,List),L).

makeRevList(Teban,Move,Black,White,L):-
    findall(List,checkput(Teban,Black,White,Move,List),L).

doMove(black,Move,Black,White,Black1,White1):-
    makeRevList(black,Move,Black,White,List),
    writeln(List),
    deletelists(List,White,White1),
    appendlists(Move,List,Black,Black1).

doMove(white,Move,Black,White,Black1,White1):-
    makeRevList(white,Move,Black,White,List),
    writeln(List),
    deletelists(List,Black,Black1),
    appendlists(Move,List,White,White1).
   
getMove1(Teban,Move,Black,White):-
    makePutList(Teban,Black,White,List),
    member(Move,List).

getMove(Teban,Move,Black,White):-
    write('\nEnter Place:'),
    readln([Move]),
    getMove1(Teban,Move,Black,White).

getMove(Teban,Move,Black,White):-
    getMove(Teban,Move,Black,White).


play(Teban,Teban1,Black,White) :- 
    isGameEnd(Black,White),writeln('Game END'),
    printBoard(Teban,Black,White),nl.

play(Teban,Teban1,Black,White) :- 
    isPass(Teban,Black,White),!,writeln('Game Pass'),
    play(Teban1,Teban,Black,White).

play(Teban,Teban1,Black,White) :- writeln('Game Playing'),
    printBoard(Teban,Black,White),
    getMove(Teban,Move,Black,White),!,
    doMove(Teban,Move,Black,White,Black1,White1),
    play(Teban1,Teban,Black1,White1).


play :- play(black,white,[44,55],[45,54]).
投稿者 時刻:
ラベル:

0 件のコメント:

コメントを投稿

登録: コメントの投稿 (Atom)