miniMax法の説明がいまいちわからない

質問

こんにちは。
Javaでゲームを制作していてminiMax法というゲームのAIの働きを説明しているサイトを調べているのですが、いまいち説明が理解できません。

ツリー木で最初に自分の手で最大評価値を選択し、相手の番になると最小評価値を選択する
そしてまた自分の手になると最大評価値を選択する。
こうやっていっても５手、６手深く読んでも仕方ないと思うのですがどうなんでしょうか？

サイトに載っているツリー木を見るとただ自分の手だと最大評価値になる手を選択すればいいだけ
なんじゃないでしょうか？３手、４手よむ必要はないんじゃないでしょうか？

回答No.4

Tacosan · ベストアンサー

あ～, こういうことかなぁ....

「ツリーの一番上が6そこから下が順に評価値が4,8,9,10だったとすると」って書いてありますが, この 4 とか 8 とかの評価値を求めるためには一般に「深く読む」ことが必要なんです. つまり, 図2 を例にすると, 「丸の 2番」の局面の評価値を計算するためには (その下の) 「四角の 3番」や「四角の 6番」に対応する局面の評価値を求める必要があります (そしてそれらの評価値の最小値を「丸の 2番」の局面の評価値とする). もちろん, 「四角の 3番」の局面で評価値を求めるためにはさらにその下の「丸の 4番」や「丸の 5番」の局面の評価値が必要です (それらの評価値の最大値が「四角の 3番」の局面の評価値).

こうやって最終局面 (ゲームの木における葉) にたどりついたときに, ようやく「真の評価値」が決まります. ただし, よほど単純なゲームであったりよほど煮詰まった局面でもない限り, あまりにも時間がかかるので「最終局面まで読み進める」ことはできません. 従って, 通常あるところまで読み進めたところで打ち切って「経験に基づく評価値」を割り当てることになります. もちろん, この「経験に基づく評価値」が「真の評価値」と一致するとは保証されないので, 「こっちの方がいいと思ったんだけどそれは間違いだった」ということはあります. あなたの挙げた例で, 評価値 10 の局面に進めたあとで「そこからさらに8, 4, 1,と評価値があるとすると、そこから今度は最小値を選ぶわけだから1を選択します」というのがまさにこれ. 「1手だけ読むと評価値 10 の局面が (自分にとって) もっともうれしいんだけど, 実はそこから相手に絶妙手があって評価値が 1 にまで減ってしまう」ということです. 「ポカ」とか「勝手読み」, あるいは「わなにはまった」というやつですな.

いずれにしても, 「そもそも評価値を計算するためには深く読まなきゃならない」ということです.

お礼

なるほど、理解できました。
ありがとうございます。

上からやるのではなく、下から評価値を求めていくんですね。
下にある評価値を決めてそこからさらに評価値を決めていく・・・
そうすれば最善手が導き出されるということなんですね。

詳しい解説ありがとうございます。

回答No.3

kmee

その図は、「評価値の計算方法」を図示したものです。
実際には、こういう木が選択肢の数だけあるので、それぞれで計算して最高点のものを選択する、という戦略になります。

お礼

回答ありがとうございます。

なんか文が変になってしまいました。
ここのサイトはいまいち文の作成が分かりづらいです。
改行入れても変になるし

補足

すみませんが、
＞実際には、こういう木が選択肢の数だけあるので、それぞれで計算して最高点＞のものを選択する、という戦略になります。
というのがどういうことなのかさっぱり分かりません。
それぞれで計算して最高点のものを選択するということはすべての選択肢を辿り
評価値を比較して最高点を決めるんでしょうか？

回答No.2

LEVELUP100

こんにちは。

＞こうやっていっても５手、６手深く読んでも仕方ないと思うのですがどうなんでしょうか？
　なぜ仕方がないと思うのかわかりませんが、１手先しか読まない手法を「静的評価」といいます。
　相手の次の手を読み、さらに自分の次の手を読むことを繰り返す手法のことを「動的評価」といいます。

　完璧な評価関数があれば確かに静的評価でいけそうにみえても、実際には相手によるので動的評価は必須になります。

ミニマックス法
http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95

参考URL：

http://ja.wikipedia.org/wiki/%E3%83%9F%E3%83%8B%E3%83%9E%E3%83%83%E3%82%AF%E3%82%B9%E6%B3%95

補足

理由はNo.1さんの補足内容に記述されています。

回答No.1

Tacosan

なぜ「５手、６手深く読んでも仕方ない」とか「３手、４手よむ必要はない」と思ったのでしょうか?

お礼

回答ありがとうございます。

補足

まずアドレスを貼っておきます。
http://hp.vector.co.jp/authors/VA015468/platina/algo/2_2.html

　ツリーの一番上が6そこから下が順に評価値が4,8,9,10だったとする
と最大は10ですよね？　そこで6→10になるわけですからそこからさら
に8, 4, 1,と評価値があるとすると、そこから今度は最小値を選ぶわけ
だから1を選択します。　こうやってどんどん深く読んでいくんですが結
局コンピュータ側は一番上の6から最大評価値の10を取るんですよね？
そしたらそれ以上読んでも変わらないと思うんですが、変ですよね。
どういうものか分からないんですよ。

ちょっと複雑な文章になりましたが理解いただけましたでしょうか？