TIM Labs

2015年7月アーカイブ

今回のあらすじ

SICP3.5.2 Infinite Streams をサクサク読んで、Execise 3.55 まで解きます。

問題

前回はオセロの対戦AIを原始モンテカルロ法で作成しました。実際に対戦してみると「角は優先して取るべき」等といったオセロのノウハウを全く知らない乱択ベースとは思えないそれなりの強さでした。

試行回数が200回/手とはいえそれなりの強さだったのですから、試行回数を増やせばもっと強くなるはずです。 しかし単純に試行回数を400回/手、800回/手......等と増やしていくと問題が出てきます。

  • 序盤や終盤は着手可能な場所が限られているものの、中盤になると数が膨大になります。試行回数をn回/手にしてるとAIの思考(試行)完了待ち時間が長くなってストレスフルです。
  • 試行方法を「全体でN回試行する」「各手についてNを等分して試行する」ことにすれば中盤のストレスは減りますが、これは中盤の各手の試行回数を減らしている為、中盤の手筋は質が下がって弱くなります。

そもそも、 着手可能な手を平等に試行する必要はあるのでしょうか? ある程度試行すれば各手の大雑把な勝率が得られますから、 勝率(大雑把)が悪そうな手について試行するよりも 勝率(大雑把)が良さそうな手について試行回数を重点的に割り振った方が効率が良いですよね。

しかし、これは少々の試行回数で割り出した勝率(大雑把)なので、 勝率(真)とはかけ離れている可能性はあります。 勝率(大雑把)が悪いからといって早々に切り捨ててしまうと、それが本当に良い手だった時に困ります。

つまり、

  • 勝率の良さそうな手を重点的に試行する
  • 実はもっと勝率の良さそうな手があるかも知れないので他の手も調べる

という2点を上手いことバランスを取って試行を行えば、 原始モンテカルロ法よりも少ない試行回数で効率良く精度の高い勝率を叩き出せそうですね。 でもこの2点、どう考えても矛盾してます。どうやって最適なバランスを取ればいいのでしょう?

このアーカイブについて

このページには、2015年7月に書かれたブログ記事が新しい順に公開されています。

前のアーカイブは2015年6月です。

次のアーカイブは2015年9月です。

最近のコンテンツはインデックスページで見られます。過去に書かれたものはアーカイブのページで見られます。