羊の人工知能研究 ~将棋AI開発の日々~

将棋、リバーシのAIプログラミングを中心にその開発過程及び記録を頑張って更新していきます。

スポンサーサイト

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

Minimaxアルゴリズムを使って探索する

 アンケートのご協力ありがとうございましたm(。_。;))m ペコペコ 数々のアンケートよりカナリ元気をもらい、ブックマークもされている方もあるようなので、忙しい中もますます『頑張って更新しないと』と思い本日の更新に至りました(´・ω・汗)ゞなお、アンケートは随時受け付けておりますので、ヨロシクお願いします(人>ω<`◎)


 ってわけで、途中になっていた探索最善手の探索方法について説明したいと思います。最善手とは普通に考えるとなかなか頭が痛く想像がつきにくいものですが、簡単に言うと『自分も相手も最善の手を打ったとき』という一言に尽きます。それをプログラムとして実現する方法として昔々に考えられた方法がMinimaxアルゴリズムなのです。Minimaxアルゴリズムの概要としては、上のノードから返ってきた評価値を探索側では最大値を、敵側では最小値をとることにより最善手が見つけられます。このときの探索側とは、探索をしようとしているプレイヤーのことです。わかりにくいと思いますので下の図25で説明したいと思います。



図25:探索前


 上の図25の木は深さ3のレベルで読んで、末端で評価値を求めたものです。この木において手番は毎回交代するものと考えて、最善のルートを見つけたいと思います。Minimaxにおける探索ルールは極めて簡単です。

①手番が探索側(Max側)ならば候補手の中で最も評価の高いものを選ぶ。
②手番が敵側(Min側)ならば候補手の中で最も評価の低いものを選ぶ。


 このルールに従って最善のルートを探索してみると以下のようになります。←図26参照



図26:探索後


 この結果から、探索側は右の方の手を選ぶと良い事がわかります。ここで、先ほどのルールがなぜ『自分も相手も最善の手を打ったとき』につながるかを説明します。

 ※まず、ここでの評価値は探索側から見た評価値が計算されていることに注意してください。

 ここで、ルール①『手番が探索側(Max側)ならば候補手の中で最も評価の高いものを選ぶ。』というのは簡単にわかると思います。評価値がズラーっと並べられてどれを選ぶ??となると、やはり一番高い(Max)評価値を選ぶでしょう。

 次に、ルール②『手番が敵側(Min側)ならば候補手の中で最も評価の低いものを選ぶ。』は、逆に考えると簡単です。評価値は探索側からみ見た評価で計算されていますので、一番小さいもの(Min)を選ぶと探索側にとって不利(敵側にとって有利)となります。

 これらのことにより、『自分も相手も最善の手を打ったとき』という考え方が出来上がっていることになります。

 最後にMinimaxアルゴリズムをC言語に似た擬似言語で紹介したいと思います。

int mini_max(盤面, int lv)
{
int val, max;

if(lv == 0)return 評価値(盤面);

if(先手)max = -∞;
else max = ∞;

while(打てる手がある){
手を差して次の盤面を作る;
val = mini_max(盤面, lv - 1);
盤面を1手戻す;
if(先手){
if(max < val)max = val;
}
else{
if(max > val)max = val;
}
}
return max;
}

んま~頑張って理解してみてください(´・ω・汗)ゞわからないことがあれば、コメント又はメールでお願いします。。。。



次回予告:未定



↓現在2つのランキングに参加しています↓

スポンサーサイト

あれ?

> val = Minimax(盤面, lv - 1);
これって、val = mini_max(盤面, lv - 1); じゃ・・・

いらん突っ込み、すいません。

おぉ・・

ナイス突っ込みありがとうございます。。。
あっ完全に見逃してました(´・ω・汗)ゞ

あと、アンケートにお答え頂いたPVSや他の探索アルゴリズムも紹介していく予定なのでヨロシクお願いします(m。_。)m

  • 2006年03月09日木
  • URL
  • 羊 #AN1TInro
  • 編集

コメントの投稿

URL
コメント
パスワード
秘密
管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://hitsujiai.blog48.fc2.com/tb.php/21-2a9edf3b
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。