「Winbomb」におけるCPUの動きの考察

招悠<yuuki_y@anet.ne.jp>

０．はじめに

　この話は私の作ったソフト、「Winbomb」における、コンピュータの動き方について考えたものである。なお私は専門家ではないので、用語等おかしいところがあるかもしれないですが、ご了承いただきたい。

１．学習とは

　「専門家ではない」といっておきながらこれですが。　まず、Winbombってのは、爆弾を置いて敵を倒すゲームである。まあアレと言えばいいであろう。ただここでは、ゲームを作ることというよりも、次のことに重点を置いてみる。
「コンピュータの学習機能」

　まず、このゲームでの学習はどういうものかを考えてみる。このゲームだと、行動の結果を点数化して、次に「似たような状態」になったときにどの行動が一番いいかを、点数で判断するというのが考えられる。例えば、『「今の状態」では、「上に移動」の行動が一番いいから、上に移動しよう。そして、上に移動した結果やられたりしたら、「上に移動」を3ポイント引こう』とか。

２．状態判別

　ところで、「似たような状態」というのは、どのように判断されるだろう？私は二つほど考えてみた。
　
　

・条件による判別

　　例えば、人間がプレイする場合、近くにアイテムがあれば取りに行きたくなるし、近くに爆弾置かれたら逃げたくなるだろう。そういった条件によって、点数を増減させて、すべての条件における点数の和で行動を決めたりする。このときの「似たような状態」は、つまり「似たような条件」。って、よくわからない記述なぁ。

　

・場所による判別

　　条件による判別は、学習機能を実装しにくいと言った点が見られる。そこで、周りのマスがどのような状態になってるかを考えてみる。例えば、以下のような、自キャラから２マス四方の地形を考えてみる。
　　　□＋＋＋＋　
　　　＋■□■＋　○：自分
　　　□＋○＋＋　□：破壊できる壁
　　　＋■＋■＋　＋：移動できるマス
　　　＋＋＋＋＋　■：破壊できない壁

　　ここで、二通りの表現方法を考えてみる。
　　まず、一つ目はすべての位置を記憶しておく方法だ。この場合、５＊５マス分の、データが必要になる。さらに、そのときにおける行動の値をすべて記憶しておかなければならない。これのデータ量はどれだけになるだろう？
自分のまわり2マス四方を判定する場合、まず判定条件の数値で、5*5マス分、そして、その結果が行動数分。Cの構造体で表すとこんな感じか。KOUDOU_MAXは行動の数だ。
　　 struct A{
　　　　char block[5][5];
　　　　char koudouchi[KOUDOU_MAX];
　　　}
　　　これが位置をすべて記憶する場合の、一個分のchar型一個が1バイトとすると、大体(25+KOUDOU_MAX)バイトになる。ところで、5*5マスの中では、どれだけ条件があるだろう？マスのタイプが、破壊できる壁と破壊できない壁と移動できるマスの三つを考えただけでも、２の５＊５乗とおりはある(実際には破壊できない壁の位置が決まっていたりするんで、少なくなるのですが)。2の25乗。まあ、これに25+KOUDOU_MAXのサイズを掛けても、今のPCのメモリの量なら扱えるサイズであろう。だが、これが4マス四方ならどうか。2の81乗。もう、見てらんなくなる話である。では、どうすれば要素数を減らせるだろうか？
　　

・記憶数に限界を作って、似たものをパターンマッチングみたいなもので類推させる

　　　例えば、100000通り位は覚えておいて、あとは、『似たもの』を検索して、それに当てはめる。無論、正確さは掛けるが、そのほうが人間に近いのではないだろうか。残念ながらまだ実装まではいたっていない。

　　

３．行動とは

　そして、行動はどういう状態かを考えてみる。何も行動は、「右へ行く」「左へ行く」だけではない。
「逃げる」「近づいて、爆弾を置いて、去る」とか、「尾行する」とかでもいいのだ。むしろ後者のほうが、あいまいさが出て、先ほどの『似たような状態』で、方向による違いがなくなるのがいい。

４．実装

　残念ながら、まだ条件による判別しか実装されていない。しかも、正確に動くものでもなく、よく自爆を起こす。今後多く改良が必要である。

10月24日
　　