オセロまとめ

 オセロ大会も終わったので今回の成果のまとめ。

 今回2回目のオセロプログラム作成ということで「スピードup」を目標にして色々むちゃなこと(データ構造変えたり)をしてきた。その結果を書いておく。


石数保持変数の追加(成功)

 今までボードをCELL構造体(中身は石の色を保持する変数と開放度を保持する変数)の二次元配列によって表現していたが、GBOARD構造体を追加しその中にCELL構造体の二次元配列と白、黒、空の石数を保持する変数を追加した。


 理由はプロファイラによって各関数ごとに処理の割合を見たところ、終盤探索時に石差を計算する評価関数の部分が全体の28%に達していたからである。このときはボードを左端から右下まで一つずつ調べて石の個数を調べることをしていたので、そこがボトルネックになっていたようだった。


 新しく石数を保存する変数を作った結果、その部分のボトルネックが消えて全体として高速化した。またゲームの終了判定部分や中盤から終盤への判断にいちいち空きマスの個数を調べる必要もなくなったので、非常にコードがシンプルになった。

開放度保持変数の追加(成功?)

 石数保持変数を追加した後、再びプロファイラで処理割合を見たところ評価関数で開放度を計算している部分が全体の6%ほどを占めていた(評価関数で使われているほかの関数は全て1%かそれ未満)。そのため、この開放度を上記の方法と同じように変数に保持させておくデータ構造に変えた。


 思いのほか開放度の計算の部分の書き換えに苦労したが、なんとか成功。プロファイラで確認したところ1%未満の割合に減っていた。しかし、元々割合が6%と低かったこと、条件分岐が増えたこともあり、あまり高速化はなされなかった。

インデックスによる着手可能手列挙の高速化(失敗)

 上記のように全体の中で大部分の処理時間を使っているところを中心に高速化を図っていたが、一番処理時間を使っているのは着手可能手をリストアップするところだった。処理時間全体の約65%ほどを占めていた。


 この部分をどうにか高速化したいと思い、パターンを使って着手可能手を簡単に取得する方法を用いることにした。詳しくは説明しないが、Thellの作者のHPにあるアルゴリズム解説に書かれていることと同じようなことをした。


 このデータ構造の改変はかなりきつかった。現在盤面のインデックス値を保持するための変数を追加する、石が返ったときに影響のあるインデックスの値を再計算する、もちろんアンドゥ処理の部分にも。そんなことをしていたら多くのバグが......。


 そんな困難にも負けず見事にデータ構造改変を成功させいざ実行してみると。
 ……遅くなっている。2倍ほど遅くなっている。何故だ、と思いプロファイラで関数の処理の割合を見てみると、着手可能手列挙部分の割合が1%未満になっていて、実行時間もかなり早くなっているという結果が。


 いや、遅くなってるから。
 原因を色々考えてみた。今回インデックスを用いて着手可能手取得の高速化を行おうとしたため、そのインデックス値の場合に着手できる方角と個数を入れたテーブルを作り、そこにアクセスすることで着手可能かどうかを判断していた。
 このテーブルだが3^8=6561行ほどあり、さらにどこに置いたときどの方角に石を返せるかを保持するために長さ16の配列になっている。さらに黒の場合と白の場合の2種類テーブルが存在する。そしてこのテーブルにインデックス値を用いてアクセスしているわけだ。


 もしかすると、アクセスの際にデータをロードしてくる部分にかなりの時間をとられているのではあるまいか。なにしろ6561行もあるし、保持しているインデックス値はバラバラであり、石が一つ置かれたり返されたりしただけで値が大きく変わる。
 これではデータの空間的局所性だとか時間的局所性だとかがまるで有効活用されないだろう。このせいでキャッシュへのヒットミスが多発して処理が遅くなってしまったのではないのだろうか。あくまで推測にすぎないが。


 しかしながら、Thellなどはきちんとこの方法論で高速化されているらしいので、自分の実装に何らかの問題点がある可能性も大いにある。


 ともかく、この改造は失敗だった。

着手可能手列挙部分をアセンブラで記述する(失敗)

 データ構造の改良が無理ならアルゴリズムアルゴリズムの改良が無理ならインラインアセンブラ。ということでアセンブラを使ってボトルネックとなっている着手可能手列挙部分を高速化しようと考えた。


 このオセロプログラム(以下開発名『そよぎ』と表す)はGCCで作っているのだが、GCCにもインラインアセンブラ機能が付いている。情報処理技術者試験で使われているCASLⅡとはかなり印象が違うのだが、まあほとんど同じといえば同じなので理解するのにそれほど苦労はしなかった。


 一応参考のために今の着手可能手列挙部分のコードをGCCアセンブラ出力してみた。
 ……どう高速化すればいいのか分からん。もっと無駄な部分があるのかと思ったがそんなことはなかったぜ。俺が書いてもこのアセンブラと変わらないか、より悪いものしか書けない気がした。むしろ最適化オプション有効にしたほうがよほど最適化されるような……。


 というわけでこの案は実装する前に没。

ボードの大きさを10x10から8x8へ(成功?)

 今まで『そよぎ』のボード実装は10x10のCELL型配列で表していた。知ってのとおりオセロの盤面は8x8の64マスで表されている。では何故10x10の配列を使っていたかというと、そのほうが着手可能手列挙や石を返す処理の記述が簡潔になるからである。外周を壁として特別な値を入れておけば配列の大きさを越えたときの処理を書く必要がなくなるから。


 ところが、前節で着手可能手部分をアセンブラ出力したときに俺は気づいたのだ。盤面が10x10の場合の欠点に。出力されたアセンブラコードの配列アクセス部分は次のようになっていた。

movl  -16(%ebp), %edx      # y の値を %edxに
movl  %edx, %eax           # y の値を%eaxに
sall  $2, %eax             # yの値を左に2bit算術シフトつまり4*y
addl  %edx, %eax           # 4*y+yを%eaxにつまり5*y
addl  %eax, %eax           # 5*y+5*yを%eaxにつまり10*y
addl  -12(%ebp), %eax      # x+10*yを%eaxに、この時点でインデックスが決まる

 二次元配列の列数が10なので、このようにシフト演算と足し算を組み合わせてアクセスするインデックスを決めている。


 そこで俺は思った「ボードの実装を8x8にすれば、3bit左にシフトするだけで何行目にアクセスするかが決められるので、早くなるのでは?」と。
 そしてデータ構造の改変を決行した。


 案の定、配列の大きさを越えたときの条件文をかなり追加しなければならなかった。ボトルネックになっている部分に条件分岐を追加することにかなり抵抗を覚えたが、実際に動かしてみると体感的な早さは以前とあまり変わっていなかった。むしろ、プロファイラを通した結果だと以前より早くなっているようだ。


 しかし、それほど劇的なスピードアップにもなっていないので、『そよぎ』のボード実装は10x10のままである。

一つの変数にデータを詰め込む(失敗)

 以前インデックスを用いた着手可能手列挙の高速化を試みたときに、(たぶん)データのロード時間が思いのほか大きくなり失敗した。


 もしかすると、今の『そよぎ』もそのデータのロード時間がどこかでネックとなっているのではあるまいか。
 そう考えた俺は『そよぎ』のボード実装を見直した。


 まずCELL構造体である。これは石の色を表す変数と開放度を表す変数の二つを持っている。両方ともint型である。こいつを改良できないだろうか。
 石の色を表す変数は白、黒、空き、壁の四つの状態を表すことができればいい。開放度も回りが全て開いている状態から全て石で埋まっている状態までの9つの状態を表すことができれば事足りる。


 つまり、実質色を表すのには2bit、開放度を表すのは4bitあれば十分なのだ。そして同じマスの色と開放度を取得したい場合は、主に石を返す処理の部分で多くある。


 そこで俺はCELL構造体を廃止し、int型の10x10配列の中に色の情報と開放度の情報を保持させることにした。それぞれの値を取得したい場合にはビット演算を駆使することになる。


 思いのほかデータ構造の改変はスムーズに終わった。
 しかし、なにやら妙なバグが……ある地点から開放度の計算結果を間違えているのである。さらに悪いことにどこが間違っているのか分からない。途中まで計算が合っているのに突然間違え始めるのである。


 このバグを解決したかったのだが、大会までの期限も迫っており断念。残念ながら『そよぎ』には実装されていない。






 なんだか、最初以外はほとんど失敗していた気もするが、気にしない。
 今回はデータ構造の改変で色々やったことを書いた。それ以外に、オセロプログラムを作っていて学んだことも多々あるので、そのことを次回書こうと思う。