« コンピュータが強くなると、ゲームはどうなるか | トップページ | バグつぶし中 »

2010/12/31

引き続き将棋世界2月号の連載記事「コンピュータは7冠の夢を見るか」より

文化的な面だけでなくアルゴリズム的な面でもバックギャモンの話は面白かった。

山本(東京大学の先生でコンピュータ将棋の開発者でもある人)
<<省略>>構造としては評価関数が重要な位置を占め、探索はチェスや将棋に比べると、 あまり重視されてはいません。 <<中略>> 探索は4手くらいでしょうか。もしくはロールアウトです。 <<中略>> あらゆる出目を想定して探索するとコンピュータでも4手がせいぜいといったところです。

将棋のようなmin-max法をベースに探索して答えを出すゲームは、αβ法という「単純(?)、高速、安全」と三拍子そろった後方枝刈りが強烈に効く。αβが強烈に効くがゆえに、コンピュータ将棋/チェスの世界では、ほかのテクニックもいかにαβを効率的に利用するかを主眼に置いているように思える。たとえば、反復深化法、NULL-MOVE、ヌルウィンドウサーチ、キラームーブなどがまさにそうだ。

しかし、バックギャモンや麻雀のように確率に支配されるゲームの場合、αβ法は使えない。
(余談だけれど、そのため、論文読み解く教養がないのに、麻雀ゲームに生かす目的でインターネットで見つけたチェスや将棋の論文を必死に読み解いていると、論文の主旨を理解できた瞬間に、麻雀では使えないことが分かってがっかりするというケースがとても多い。)

麻雀には、安全に刈れる後方枝刈りの技法がないので、全幅探索で読みを深めると指数関数的爆発の影響をもろに被る結果となる。そのため、麻雀の探索は、将棋やチェスと比較すると、不完全情報ゲームのプログラムをやったことがない人には理解してもらいにくいくらい、探索できる深さが浅くなるのだが、バックギャモンも似たような感じらしい。

計算量の爆発を抑えるために、私は仕方なく人間の経験を生かした前方枝刈りしているけれど、その結果、まったり麻雀はやたらとリーチが早くて愚形が多い、いわゆる棒テン即リータイプの雀風となってしまっている。

バックギャモンの場合は枝刈りに力を入れずに、結果をフィードバックして機械学習する手法など、評価関数に力を入れることで読みの浅さをカバーできているようだ。

麻雀の場合、スタートの局面が一定ではないため定跡が使えず、ゴールの目標も局単位でみると複雑になりがちで、リスクとリターンが表裏一体であるゲームでもあるため、機械学習がやりにくい。さらに、無駄にルールが複雑なこともあり評価関数の数値算出自体が探索処理をともなってしまうこともある。そのため、確率的な局面の推移と親和性がとれ、かつ、演算速度が速い局面評価関数を作るのはとても難しい。

まったり麻雀の評価関数はかなり雑で、ゲームアルゴリズムを専門にやっている人の前で評価関数と呼ぶのも恥ずかしいレベルなのが現実の姿。
麻雀の場合、無駄ツモさえなければ、ゴールまでの距離は短いことと、序盤は19字牌を整理してれば何とかなることが多いので、それでもゲームになるのだけど、改善しないといけない問題であることは間違いない。

いままで、まったり麻雀のAIに生かせるものはないかと将棋や囲碁の思考ルーチンのノウハウを学んできたが、バックギャモンのAIは強化学習のような教師なしの機械学習を使ってるという程度の知識しかなく未知だった。これからはバックギャモンのノウハウも学んだ方が麻雀に生かせるのかもしれない。そのためには、まずはバックギャモンのルールを覚えてゲーム固有の特性をつかむとという、AI以前の部分から始めなければいけないが……

|

« コンピュータが強くなると、ゲームはどうなるか | トップページ | バグつぶし中 »

コメント

コメントを書く



(ウェブ上には掲載しません)




トラックバック

この記事のトラックバックURL:
http://app.cocolog-nifty.com/t/trackback/61182/50453694

この記事へのトラックバック一覧です: 引き続き将棋世界2月号の連載記事「コンピュータは7冠の夢を見るか」より:

« コンピュータが強くなると、ゲームはどうなるか | トップページ | バグつぶし中 »