フィジカルを鍛える練習問題
問題:コンピュータ対戦3目並べを作れ。
条件:コンピュータが先行になったとき、コンピュータは負けてはいけない。
とか。
むぎゅう...
そもそもこういうのは苦手な上に,対話形式にするにはどうしたらいいか分からない...
うーみゅ,write
があるなら read
があるのか? あるなぁ.
それを繰り返す... どうやって?
うーみゅ...
なんか,本質と違うところで悩みそうなので,問題を簡略化しちゃいましょう.
まずは盤面を
1 | 2 | 3 |
4 | 5 | 6 |
7 | 8 | 9 |
そして自分と相手の手をリストとして受け取り,次の手を返す述語を考えます.
tick(List1, List2, X)
List1 は Prolog 君,List2 は対戦相手 (人間),X は Prolog 君の次の手の位置.
コンピュータが先手なら最初は
tick([], [], X).
で始まって,
tick([1, 3, 5], [4, 6, 8], X).
なんてなったら
X = 7
となって終了,みたいな.
これなら入出力に悩まされなくてすみます.
まぁ,入出力を扱えるようになるのは将来の課題ということで.
ともあれ (JW),自分や相手の手をリストとして持つことにしたわけですが,このリストは実質 Set (順序無し集合) として扱うのが都合がいいので,写経本から使えそうなものを先取りしてきます.
element(X, [X|_]). element(X, [_|Set]) :- element(X, Set). subset([], _). subset([X|Sub], Set) :- element(X, Set), subset(Sub, Set).
それから,盤上で打てる位置を表す述語と 3 つ点が並んだことを示す述語を定義.
pos(X) :- element(X, [1, 2, 3, 4, 5, 6, 7, 8, 9]). line([1, 2, 3]). line([4, 5, 6]). line([7, 8, 9]). line([1, 4, 7]). line([2, 5, 8]). line([3, 6, 9]). line([1, 5, 9]). line([3, 5, 7]).
次はどうしたものか?
とりあえず,自分なり相手なりの手が揃ったことを判断する述語を考えますか.
これまでに打った手のリスト中に 3 並びが含まれていればいいわけなので,subset/2
を使って
win(List) :- line(Sub), subset(Sub, List).
でいいかなぁ.
それから,次に打つことのできる位置を求める述語を考えます.
next(List1, List2, X) :- pos(X), not(element(X, List1)), not(element(X, List2)).
自分 (List1
) も相手 (List2
) も置いてない位置を X
として返します.バックトラックで次に打てる位置を全部試せるのが Prolog 流.
ここからが本題.
まずはゴールから考えるのがお約束なので,次の一手で勝ち!! ってのを定義します.
tick(List1, List2, X) :- next(List1, List2, X), win([X|List1]).
既に勝負が付いている場合のガードが入っていませんが... 心より恥じる.
あと一手で勝負が付かない場合はどうするか? うーみゅ...
自分 (Prolog 君) が一手打った後,相手が勝つことができなければいいわけですよね.
勝つことができないってことは... どういうことだ?
全ての手について相手の勝ちがないってことだよね.全ての... 全称記号?
困りましたね,ここまで Prolog してきたのって,全称 (∀) じゃなくて存在 (∃) のような気のせいが.
うーみゅ...
全称を存在で表すには... 「全て〜である」を「〜がある」にするんだから「〜じゃないがある」(日本語ヘンなのは気にしない) の否定にすればいいのか?
そんなわけで (どんなわけで?),全ての手について相手が勝てないことを示すにはまず相手が勝つというかこっちが負けることを示してそれを否定すればいいことになるわけなので,って何を書いてるか分かってますか? 分かってませんかそうですか.
ともあれ (JW),負けることを示す述語.例によって次の一手で相手が勝つことを示せばいいので
lose(List1, List2) :- next(List1, List2, X), win([X|List2]), !.
最後のカットは効率のため.相手が勝つかどうかだけ分かれば後はどうでもいいから.
それから相手が一手打ってからこっち (Prolog 君) が打って相手が勝つ場合は... こっちが負けるってことだからさっきの tick/3
を使う... 使っていいのか? いいや,使おう.
lose(List1, List2) :- next(List1, List2, X), not(tick(List1, [X|List2], _)), !.
うーん,だんだん自分が何をやってるか怪しくなってきた (苦笑).
ともあれ (JW),これで元に戻って自分の次の一手を決めることができるような気のせいが.
自分が打った後に相手が勝てる手があったらダメなんだから,
tick(List1, List2, X) :- next(List1, List2, X), not(lose([X|List1], List2)).
本当か? 本当に分かってるのか?>おいら
かなり怪しいけどなんかいいような気もする.
っていうか,メチャクチャ手続き的に考えているのはいかがなものか?
まぁいいや.動けばいいんだよ.とりあえず.
そんなわけで (どんなわけで?),試してみますか.
まずは Prolog 君先手で.
2 ?- tick([], [], X). X = 1
むむぅ? いきなり 1 からとは... ちゃんと考えてますか?
っていうか,最初は中央を取れとか教えてないおいらがダメですかそうですか.
しょうがない,それなら中央を頂きましょう.
○ | ||
× | ||
3 ?- tick([1], [5], X). X = 2
ふーん.工夫がない気もするけど,リーチをかけられたのでこっちは 3 を取るしかありませんね.
○ | ○ | × |
× | ||
4 ?- tick([1, 2], [3, 5], X). X = 7
おぉ!! なんか分かってるじゃん!!
いやその,分かってないのはおいらですけど何か?
そうですか,じゃあおいらは 4 へ入るしかないわけですが.
○ | ○ | × |
× | × | |
○ |
5 ?- tick([1, 2, 7], [3, 4, 5], X). X = 6
ふむ.これでもうどちらにも勝機はなくなったわけですが,そういえば引き分けのことを忘れていたなぁ.心より恥じる.
しょうがないので続けてみますか.とりあえず 8.
○ | ○ | × |
× | × | ○ |
○ | × |
6 ?- tick([1, 2, 6, 7], [3, 4, 5, 8], X). X = 9
ということで Prolog 君は負けることなくゲーム終了.
そういえば,ゲーム終了の判定もないような気のせいが.心より恥じる.
っていうか,Prolog 君,ちゃんと勝てるのか?
最初にリーチかけられたところでわざと墓穴を掘ってみるテスト.
○ | ○ | × |
× | ||
○ | × |
7 ?- tick([1, 2, 7], [3, 5, 9], X). X = 4
おぉ,ちゃんと4を取りましたね.
でもでも,一番小さい数を選んだだけかもしれないから,ちょっと回転して
× | × | |
○ | × | |
○ | ○ |
8 ?- tick([4, 7, 9], [1, 3, 5], X). X = 8
大丈夫みたいです♪
じゃあ,人間先手でやってみましょう.当然中央から攻めるよ.
9 ?- tick([], [5], X). No
ぐはぁっ.(;_;)
うーみゅ,人間先行だとどうやっても答を出してくれない...
考え方が間違っているのか引き分けに持ち込むルールを仕込んでいないことが原因なのか...
ともあれ (JW),きしださんのお題には人間が先手の場合の条件は入ってないからこれでいいや.
...
いいのか? (^^;
まぁ,マジメにやるなら深さ優先だか幅優先だか MiniMax だかって難しいことを駆使しないといけない気がするわけで,おいらのレベルじゃ小手先ではムリポ.
っていうか,そういうのを鍛えるのがフィジカルトレーニング? なんだろうな,やっぱり.
いいのだ.おいらは Prolog のトレーニングがしたかっただけなのだ.
・・・
言い訳です,はい.心より恥じる.