bitboardを用いたライフゲーム
この前ライフゲームをJavaでプログラムする機会に恵まれた。
折角の機会なのでビットボードを用いて作ってみることにした。
ライフゲームを知らないのであれば以下の動画を見るといいと思う。
bitboardの理解には以下のサイトを参考にさせて頂いた。
ビット演算（ビットボード）によるライフゲーム高速化
Bitboard版ライフゲームの拡張 - Tosikの雑記
Game of Life(LifeGame)
ライフゲームは，1970年にフランスの数学者コンウェイが提案した二次元セル・オートマトンである．ライフゲームは生命のプロセスを簡易的なモデルで再現したシミュレーションゲームである．隣接8マスのセルが次世代の生死に影響する．
Bitboard
BitBoardとは，ビット配列を論理演算等で調理して各ビットを並列的に高速処理してしまおうという手法で，オセロやチェスといったボードゲームの処理を得意としている．
つまるところ、例えばbool型の変数をセルの数だけ用意し1セル毎に次世代の生死を判断するのではなく、1bit毎にセルの生死を管理し論理演算することによって次世代のいくつかのセルを同時に求めてしまおうという手法だ。とてつもなく速い。
unsigned long long int が使えなかった。
Cではuint64を用いることができるが、Javaにはunsigedがなく0xfefefefefefefe00Lが範囲外といわれてしまったため8*8ではなく、4*4を一単位(チップ)として作成することにした。
次世代のセルを計算する
8方向それぞれを更新したいセルの方向にずらして比較するという考え方を用いるとチップを更新することができる。下図は注目チップの隣接8チップが表示されている図であるが、黒塗りのセルの塊を左上、上、左、自分の4つのチップから再構築する。
注目チップ自体はTとして、左上から順にa,b,c...とつけていくと再構築されたa'は以下のように表すことができる。
a'=((T&0xeee0)>>5)|((a&0x0001)<<15)|((b&0x000e)<<11)|((d&0x1110)>>1)
以上の処理をb'～h'すべてに対して行ったものを用意しておく。
これらを論理演算して次世代のセルの生死を求める。(この演算はいまいち何をやっているのかわからなかった。)
完成品
出来上がったものがこちらだ。
ついでに世界を有限ではなく無限にしたのでグライダー銃などを作った際には永遠に広がる世界を垣間見ることができた。
中々高速でP690 60P5H2V0 gunなどを設置しても観測に耐えうる速度を発揮することができた。
