Nim言語でオセロAI【終盤ソルバーの高速化】

以下の記事の続きです！💭

昨日、終盤ソルバーを"頑張って"作りました。でも、出来上がったものを動かしてみると、ちょっと残念な感じになってました...orz (最終15手読みで、18秒掛かっていました。)

そこで、今日はその「終盤ソルバーを強化しよう！」という回です。

今日行なったことは、以下の通りになります。

終盤ソルバーでは、現在の盤面から一番最後の盤面まで全て読み切ることが求められるので、両者が置けなくなるか、60手目まで再帰探索を行います。 (そして、これらは"葉"と呼ばれます。)

そこで、59手目を置いた時のことを考えます。 59手目を置いた後、もう一度探索関数を呼んでも良いのですが、「残り空きマスは1箇所しか無いので、敢えて関数を呼ばず、その場で処理しちゃおう」という考え方です。

実際、関数を呼び出すことによって、(本当に微々たるものですが)計算コストが生じます。ですが、この終盤探索において、葉の数はとても多いので、結構効果があります。

実際、昨日僕があげた記事によると、MinMax法で最終15手読み切る上で葉に到達した回数は、約2,000万回にもなっていて、これをそのまま当てはめると、0.0000001秒葉の処理を短縮できたら、全体で2秒短縮できるということになります。シビアだね。(適当ですいません🙇)

終盤ソルバーで探索を行う時にも、αβ法のように積極的にノードのカットをしていく方針になりますが、より多くのカットを実現するためには探索する順番がとても大事になってきます。

その順番を決めるために、ソートなどを行っていったりするのですが、「残りn手」となった時は寧ろソートなんかしないで、力💪でねじ伏せた方が良かったりします。 (ソートはソートで計算コスト掛かるんでね！)

このnについては、自分はまだ最適な値を見つけることはできていませんが、n=6とか7辺りが良いんじゃないかなって感覚があります。

手の探索を行う前に、空きマスのみを列挙したリストを作り、探索する時にはその空所リストについてのみループを行います。もし、64マス全てについてループを回していたのだとしたら、ループ回数が少なくなるので、性能改善が見込めます。

ここで注意するべきは、探索関数を再帰呼び出しする毎に空所リストを作らないことです。空所リストを作成するのにもコストが掛かりますので...。(多分、毎回作っていたら逆に遅くなります。)

僕の場合は、空所リストは1手決める毎に1回しか作っていません。

ここまでの時点で、昨日は18秒掛かっていた処理が、8秒弱にまで抑えることができました。

NegaScout法は、単純な処理を上げる訳ではなく、探索するノード数を減らすことが目的です😏

詳細の説明は、眠くなっちゃったのでしません。。。(すみません、許してください)

探索をしていると、例え打った順番が違くても、同じ盤面になることがあります。

なので、探索しておいた結果をメモリ上に保存しておいて、同じような盤面が来た時に保存しておいた内容を再利用することで、省エネ化を図ります。自分は、NegaScout法と合わせて以下のページを参考にしました。

まぁ他にもちょいちょいやったことはあります。(ハッシュとかハッシュとか。。。)

最後に、今日の結果だけ載せますね。赤枠の所を見てください。(終盤読み切りが始まるターンです。)

f:id:g-knk-9410:20180402005737p:plain

やりました！！！🎉🎉🎉

探索ノード数が劇的に減って、探索に掛かる時間が減りました！！！🎉🎉🎉

そして、昨日の時点ではここの秒数が18秒だったのに対し、今日は0.01秒になりました。 1,800倍になりました、ヤッタネ！(昨日やつがポンコツだっただけ)

因みに、終盤ソルバーのベンチマークサイト(ここ)があるみたいなので、もう少し良くなってきたら測ってみようと思います。

以上です。おやすみなさい！💤

たかろぐ