ビットボードの深みにハマる
今日は、前半はNimのお勉強、後半はオセロのビットボード実装をしていました。
Nim
ドキュメントをサーッと見たり、メモしたりしました。
大体の感覚を掴んだ所で、「あとはやってれば覚えるっしょ！」ってノリで勉強を終えて、
ビットボードの勉強へシフト。
勉強してたら、コード書きたくなっちゃうことってありますよね？
ビットボード
まず、オセロは8×8の盤面で構成されています。 そして、その盤面に以下のように番号を割り振っていきます。
すると、盤面の状態が64bit整数2つ(黒用と白用)で表現できるようになります。
例え整数と言えど、内部的には0と1の羅列から成っているので、それを盤面に見立てて利用する訳ですね。
例えば、以下のようなビットボードがあったとします。 (「1」と書かれているマスに対応したビットが立っていて、それ以外のビットは0になっていると考えてください。)
この時、盤面を再現すると以下のようになります。(身体で感じてください。) 因みに、両方0の所は空白扱いになり、両方1になる所は絶対に有りません。
「なんで、わざわざこんな事するの？配列でイイじゃん」と聞こえてきそうですが、このようにする理由がちゃんとあります。 ビットボードで実装すると、とにかく速いんです。 基本的にビット演算を駆使すると、安直に配列をループさせた時の何十倍も速く探索や反転処理が行えます。 (なので、オセロAIを実装しようとしたら、ビットボード化するのは定石です。)
ビットボード化すると、次のような処理が、ビット演算で行えるようになります。
- 石数のカウント
- 着手可能箇所を求める
- 石の反転処理
そして、これらの処理はこの後AIの探索処理を行う際に、何十万・何百万回と使い回されるので、とても重要です。 簡単になりますが、100,000回、上記の処理を行うと仮定した時、その実行に掛かる時間が0.0001秒変わるだけで、全体で10秒もの差が付くということです。 これはヤババ。
ビットボードの大切さが分かった所で、次はビットボード実装は当たり前と考えて、「もっと速く処理するにはどうしたら良いか」という話になってきます。
上述した通り、着手可能箇所を求めたり、反転処理という処理は、AI実装した時にかなりシビアに影響される所で、演算単位での効率が求められるようです。怖っ！
そして、これに関連する記事が最近は結構出てきているので、紹介しておきます。
僕も昔ビットボード実装したことあるんですけど、全然まだまだでした(笑)
特に、反転処理を行う所(flipと言うらしいです)が、以前の僕のコードは結構安直でwhite文とif文を普通に使って実装していました。
上の記事の先には、while文もif文も要らず、本当にビット演算で反転処理を実現しています。すごいです(笑)
最後に
今日は、Nimを少し勉強して、実際にオセロロジックを組んでいました。
基本的に昔書いたプログラムを再利用すれば大丈夫だったのですが、反転処理の所だけ明らかにパフォーマンス悪そうだったので、
先人の知恵を参考にしつつ、より効率の良いアルゴリズムを模索しています。(思い付かなかったら、もうパクるしかない)
ここ、本当に深いなぁ。
あとは、効率良くボードを点回転・軸回転させて状態数を削減したいのと、 学習アルゴリズムを作って辞書作って読み込む形にできたら最高ですね。 まぁ、他の機能との兼ね合いがあるので、どの辺で妥協するかっていう話になりそうですが^^;
探索はNegaScout法とかが良さそうで、評価関数はどうしよう...って感じです。
うわぁ、考えることいっぱいだなこれ全部やれるのか...?
