もんしょの巣穴blog

モンテカルロ木探索

1000円で『レッドクリフ』を見てきたのですが、面白くなかったです。
三国志ファンからするとキャラクタ設定がおかしいというか、孔明がシュウユを友人とかいうのにすげぇ違和感が。
三国志を知らないとキャラクタがよくわからない。あんまり特徴がない。
初めて関羽が出てきた時は、名前が出るまで関羽だと気づかなかったくらい。
アクションも白々しくてしょっぱい。ジョン・ウーも戦争映画で多対多を表現するのは苦手か?
しかもこれが3時間。これならもう1回『ダークナイト』を見た方が良かった。やってないけど。

先週金曜日はDiGRAの公開講座に行ってきました。囲碁AIにおけるモンテカルロ木探索についてです。
実はあまり期待してなかったのですが、これがかなり大当たり。
モンテカルロ木探索はここ数年に出てきた技術ではなく、結構昔に考えられた技術。
しかし、当時はそのAIは強くはなく、むしろ弱い部類だったようです。
これに注目が集まったのはほんの2年半前。突然現れてそれまでの様々なAIを過去のものにしてしまいました。
理由としては、CPUの並列化と速度が上がったこと。アルゴリズムに対する若干の改良もありますが、これらが非常に大きい。
そもそもどんな技術なのかというと、これがまたきわめて単純。
モンテカルロ木探索においては、ランダムに終局までゲームを実行することをプレイアウトと言います。
このプレイアウトをとにかく何回も行い、その勝率がいい次の一手を選択するというものです。
囲碁は他のゲームと違って評価関数が作りにくいゲームです。
将棋やチェスは駒によって価値が違ってきますが、囲碁は白黒の石だけです。
オセロの場合、駒には価値がありませんが、目の位置には価値があります。4角や端の辺がいい場所となるわけです。
囲碁は他の石との連携になりますし、短期的な良い手が長期的にも良い手になるわけでもありません。
しかし、将棋などと違って打てる場所にランダムで打っていくだけで終局までいけます。将棋の場合、いつまでたっても王将が取られないということもあるでしょう。
大量に行ったプレイアウトから成績の良いものを選び出せばよいのですが、プレイアウトの質を高めることも重要です。やるだけ無駄なプレイアウトをやらないとか。
この技術はとにかく単純。故に実装しやすいし、アイデア次第でいろいろな場面に利用できます。
某氏と話していて考えた使い道としては、FPSの敵AIの連携した位置取りとか。
黒板モデルで黒板が考えたような感じで、プレイヤーに対する包囲網を敷こうとするわけです。
NPCもPCも次のウェイポイントへ移動する、待機する、銃を撃つ(撃った方向のウェイポイントにいるキャラクタはダメージを受ける)の3つの行動しかできないと仮定します。
この条件で、今のNPC、PCの位置を設定し、プレイアウトを行います。ここで、PCを仕留めることができたら勝ち、だめなら負けということにします。
こうすれば、PCを包囲できる一手を打てるようになる…かもしれません。
ついでに、プレイアウトの回数を増減させてみたり、プレイアウトを最後までやらずに途中で切り上げるなどで難易度の調整も可能です。
プレイアウトの結果から勝率ではなく他の要素を評価することで(囲碁なら目数差とか)ギャンブル性の高いAIを作成することも可能です。
これらは囲碁のAIの世界では追求されません。エンタテインメント的な使用方法については我々の方が研究すべき問題でしょう。
評価関数は基本的に必要ないのですが、プレイアウトの質を高めるためにある程度の評価関数は必要になります。
ですが、そんなに正確でなくてもいいので、やっぱり適切な評価関数がなければ困る他の手法よりは実装しやすいでしょう。
考えてみると結構面白いことができる技術だと思いますが、リアルタイムでやる場合はAIの更新期間が長めのやつじゃないと厳しいかもしれませんね。

スポンサーサイト
  1. 2008/12/02(火) 01:49:56|
  2. プログラミング
  3. | トラックバック:0
  4. | コメント:0
<<パーバーテクスライティングは時代遅れ? | ホーム | デュアルクオータニオン>>

コメント

コメントの投稿


管理者にだけ表示を許可する

トラックバック

トラックバックURLはこちら
http://monsho.blog63.fc2.com/tb.php/90-3cdacf3d
この記事にトラックバックする(FC2ブログユーザー)

プロフィール

monsho

Author:monsho
ゲームプログラマ?

最近の記事

最近のコメント

最近のトラックバック

月別アーカイブ

カテゴリー

ブロとも申請フォーム

この人とブロともになる

ブログ内検索

RSSフィード

リンク

このブログをリンクに追加する