【論理】Prolog【初心者】

**デフォルトの名無しさん** · 2010/11/06(土) 13:00:56

Prolog初心者のスレ

これは良い言語だ…

**デフォルトの名無しさん** · 2013/03/20(水) 14:52:27.58

prologのバックトラックを使って
深さ優先探索のミニマックス戦略のプログラムを作れますか。
やむをえなければassert,retractを使ってもかまいません。
幅優先探索ならできるのですが。

**デフォルトの名無しさん** · 2013/03/20(水) 17:44:36.54

>>646
こんな定義になると思う。未定義の部分が多いけれどそのうちに書く。

n手先を評価する(_n,_局面1,_着手ならび,_評価点,_局面) :-
　　　　length(Ln,_n),
　　　　手を読む(Ln,自分,_局面,[],[],_着手ならび,_評価点,_局面).

手を読む([],_,_局面,_着手ならび,_評価ならび,_着手ならび,_評価点,_局面) :-
　　　　sum(_評価ならび,_評価点),!.
手を読む([_|Ln],自分,_局面1,_着手ならび1,_評価ならび1,_着手ならび,_評価点,_局面) :-
　　　　findmax([_評価,_着手,_局面2],(
　　　　　　　　　　着手(_局面1,_局面2,_着手,評価)),
　　　　　　　　[_評価,_着手,_局面2]),
　　　　手を読む(Ln,相手,_局面2,[_着手|_着手ならび1],[_評価|_評価ならび1],_着手ならび,_評価点,_局面).
手を読む([_|Ln],相手,_局面1,_着手ならび1,_評価ならび1,_着手ならび,_評価点,_局面) :-
　　　　findmin([_評価,_着手,_局面2],(
　　　　　　　　　　着手(_局面1,_局面2,_着手,評価)),
　　　　　　　　[_評価,_着手,_局面2]),
　　　　手を読む(Ln,自分,_局面2,[_着手|_着手ならび1],[_評価|_評価ならび1],_着手ならび,_評価点,_局面).

着手(_局面1,_局面2,_着手,_評価) :-
　　　　着手の選択(_局面1,_局面2,_着手),
　　　　局面の評価(_局面2,_評価).

**647** · 2013/03/20(水) 18:04:57.94

そうか。
これだと、最善手をn手続けてみただけか。
一手目を非決定性に着手してn手先まで最善手で読ませて、すべての着手を
評価して、評価点がもっとも高い着手を選ぶようにしないといけないか。

**デフォルトの名無しさん** · 2013/03/20(水) 18:25:18.12

>>647,648
深さ優先ですから、とりあえずある道筋で、最終局面まで行き、
そこで評価点を決め、それをひとつ下のレベルに下ろしておいて、
また別の最終局面に行って評価点を求め、其れを先ほどの値と比較し、
最終局面がなくなったら更に一つ下のレベルと比較．．．．．．
のようなことを繰り返し、次第にレベルを下げていくことになるはずですが、
バックトラックをうまく制御できません。

**647** · 2013/03/20(水) 18:45:14.17

>>649
深さ優先といっても株は全部評価しないとどれが最高評価点かが
分かりません。それで最高点-最低点-最高点...と降りていって、
葉までたどり着いたら(つまりn手先)一つ候補が決まる。次善候補を
葉のレベルの次の評価点の候補着手とするという意味ですか？

**デフォルトの名無しさん** · 2013/03/20(水) 19:12:35.16

>>650
理屈からいうと、N手目の局面で評価するとすると、
あるN-1手目から派生するN手目の評価点を全て比較して、
其れをN-1手目の評価点とし、同様にあるN-2手目から派生する
全てのN-1手目について評価点を決めて其れを比較して
N-2手目の評価点として．．．．．．．．というように、
だんだん一手目まで戻っていきます。
（もちろんmini とmax交互に)
これを、同じレベルの評価をfindall等を使っていっぺんに行うと
幅優先になり、行ったりきたりして評価すると深さ優先になります。
1->N->N-1->N->N-1->N->N-1->N-2->N-1->N->N-1->N->N-1->N-2........
というような感じだと思います。.

**デフォルトの名無しさん** · 2013/03/20(水) 21:31:55.30

着手の選択/4と局面評価/2が未定義ですが、

http://nojiriko.asia/prolog/mini_max_senryaku.html

のようなコードでしょうか。

**デフォルトの名無しさん** · 2013/03/20(水) 23:01:45.80

>>652
初心者ですので、他人のコードを読むのは難しいのですが、
これは基本的に幅優先のコードではないでしょうか。

**デフォルトの名無しさん** · 2013/03/21(木) 00:23:36.01

>>653
何か間違っていますね。 ! を削りましょう。そうすると、

着手候補の取り出し(_枝切り,_評価_着手_局面ならび_2,_評価,_着手,_局面2) :-
　　　　length(L0,_枝切り),
　　　　append(L0,_,_評価_着手_局面ならび_2),
　　　　member([_評価,_着手,_局面2],L0).

の最後memberが働いて、全解を取り出せると思います。

3手先読みの最善手は -> 次の可能な全ての手を評価して整列 ->
探索範囲を狭めるため枝切り -> 最も評価の高い手を選択 ->
相手の立場から最も評価高い手を選択 ->
その局面で全ての可能な着手を評価し -> 整列して枝切り　->
これで第一解が得られる
バックトラックすると、
3手先読みの整列枝切り後も member/2 の次の候補が取り出されて第二解。

findmax で次々呼び出されて、最高評価点を探す。

**デフォルトの名無しさん** · 2013/03/21(木) 00:55:51.96

>>654
これ深さ優先でしょうか。
幅優先のような気がしてなりません。

**デフォルトの名無しさん** · 2013/03/21(木) 01:29:24.35

その人、悪い人じゃないんだけど、ちょっとおかしいところあるから、あまり関わらないほうがいいよ。

**デフォルトの名無しさん** · 2013/03/21(木) 06:29:01.79

>>655
Wikipedia の幅優先の項のグラフを借用して説明します。
http://ja.wikipedia.org/wiki/%E5%B9%85%E5%84%AA%E5%85%88%E6%8E%A2%E7%B4%A2

　　　　　　1

　　　2　　3　　4

　5　　6　　7　　　8

9 10　　　　　　　11 12

プログラムでは、着手評価が唯一の実効のある作用なので、着手評価によって
横方向の優先順位を決めることが幅優先に見えることは仕方ない。
[2,3,4],[5,6],[7,8],[11,12]の順序は実は動的に決められます。

しかし、実際の手の読む順序は
1 - 2 - 5 - 9 　が第一解
1 - 2 - 5 - 10　が第二解
1 - 2 - 6 　　　が第三解

のように、このノードが先に優先して評価されていきます。2-5-9,10を評価して
いる時には7,8,11,12などは置いてきぼりの状態にあります。
これは幅優先ではありません。

**657** · 2013/03/21(木) 06:31:38.99

実際の手の読まれる順序ですね。

**デフォルトの名無しさん** · 2013/03/21(木) 10:44:06.29

>>657
私の求めていたアルゴリズムとは違うようですが、
これはこれで興味深いですので、何とか解読してみたいと思います。
ありがとうございました。