Nim言語でオセロAI【探索の高速化】
以下の記事の続きです。今回は、反転処理(Flip処理)の効率を上げて、自分の悪い実装を直してゲーム木探索の速度を上げました。 takalog.hatenadiary.com
反転処理
以下2つの記事を参考に、実装しました。 primenumber.hatenadiary.jp qiita.com
詳しくは記事に書かれておりますので、割愛させていただきます。
そして、修正する前と後でどれくらい変わったのかを、簡単に比較しました。
- コンピュータ同士の対戦をそれぞれ10回ずつ行いました
- それぞれの手を探索によって求める時、1秒間に探索できるノード数NPS(Nodes Per Second)を計算し、比較指標とします
- 反転処理の計算方法以外は全て同じ条件下で行いました
- 現段階では、コンピュータの手にランダム性は無いので、10回とも同じ展開になります
- 最終的な評価は、中盤(全60手中10手目〜50手目までとする)のNPSの平均値で行いました
実験した結果、修正前が平均3,291,344NPS、修正後が平均3,411,607NPSになりました。
NPSの性能としては、約3.5%強ほど向上しました。 多分、まだまだ余分なことしていると思うので、もしかしたらもう少し上がるかもしれません。
ゲーム木探索速度の向上
以前まで、探索を行う際、可読性を上げる為にある程度まとめたデータをインスタンスに詰めてやり取りしていました。 正直、「少しくらいインスタンス作っても誤差の範囲内っしょ!」と思っていました。
甘かったです(笑)
コードは少し長くなるけど、インスタンスを生成している部分を取り除いて先ほどと同じように実験しました。
すると、平均4,648,397NPSにまで跳ね上がりましたたたた...orz
結果として、一番最初のものと比べて、約1.4倍強の処理性能になりました。 正直、インスタンス作ってデータのやり取りをするか否かで、ここまで性能が変わってくるとは思いませんでした...(反省)
この辺りで満足し始めたので、この話はこれで終わりにします。 まだ評価関数をちゃんと書いていないので、AIとしては以前と変わっていないのですが、これから強化していきたいと思います。