前からチョコチョコやっていたオセロの終盤読み切りの話です。動機は、ただ高速化やってみたいなと思ったらそこにオセロがあったというだけです。やりつくされたネタではあるので、ここに書かれているようなことはググればすぐにヒットします。今回僕が目指したのは、現在の盤面から勝ちor引き分けに持っていけるかを判定し、もし勝てるのならば勝つための次の手、引き分けが最善ならば引き分けるための次の手を出力することです。負けているのならそれを伝えるだけなので実際に対戦で使うときはその時の処理も考える必要があります。やったことを時系列順に列挙しておきます。long型の変数二つで現在の盤面を保持するという一般的なテクです。することで多くの処理がビット演算で書くことができるようになり、処理が高速になります。ハッシュ化はその名の通り盤面をハッシュ化してメモしておき、同じ盤面が現れたらその結果を使うというものです。盤面はゾブリストハッシュを用いてハッシュ化し、unordered_mapに突っ込むようにしました。ここでゾブリストハッシュの乱数の生成範囲を64bitにしないと衝突しまくって死にます。探索した盤面をすべてunordered_mapに突っ込んでしまうとメモリが溢れてしまうので、ある程度の深さまでだけメモ化するようにしました。深さをいくつかに分割してそれぞれハッシュ化するなどの手法も試してみたのですが、速くなりませんでした。flipとは盤面の反転処理のことです。各方向での処理をループ展開したり、細々と高速化したりとなかなかに時間をかけたのですが、やはり時間がかかってしまったのでここは諦めてprimenumber.hatenadiary.jpの記事のコードを借りました。並列化うんぬんは環境が整ってないので、全方向についてゴリゴリと書いています。-mtune=nativeこのような感じにしました。こんなにいらないと書いてある記事もありましたが、書けば書くほど速くなったので書いておきました。一つ一つ言っていたらキリがないですが、細々と高速化しました。着手可能位置については強い人たちはビット演算でオラっとやっているのですが、僕は空きマスの情報を伝播させていき、その全ての空きマスについてflipした後盤面が変化しているかどうかを見ています。ここはまだあまり触れていませんが、改善の余地がありそうです。最新の更新では速さ優先探索を組み込みました。これはもっと前にやっていたつもりだったのですが、すっかり忘れていました。今回の僕のプログラムでは、各盤面の探索において勝つ手が一つでも見つかればよいのでできるだけその先の候補が少ない手から試したほうが速く終わるんじゃないかというアイディアを実装した探索です。実際、これでかなり速くなりました。気が向いたら開発しているものなので、まだまだ改善すべき場所もありますが、そこそこ速くなった気がしたので公開しておきます。TSGの部員から与えられた22マス空きの盤面に、開発始めのころは3000sほどかかっていましたが今では20sほどまで高速化されました*1。検索はてなブログをはじめよう!gasinさんは、はてなブログを使っています。ブログを報告するスターをつけました引用をストックしましたストック一覧を見る閉じる引用するにはまずログインしてくださいログイン閉じる引用をストックできませんでした。再度お試しください閉じる限定公開記事のため引用できません。