てすと

たかろぐ

自分のログを刻みます。

終盤ソルバーのベンチマークテストしてみた

Nim オセロAI オセロアプリ

ついに、学校が始まってしまった。

そして、新社会人・新学生の方おめでとうございます！🎉🎉

自分もあと1年で社会人の仲間入りなのですが、今から楽しみです。 (自分の実力がまだまだなのが心配ですけどね)

さて、今日は大掛かりな開発はしていないのですが、ここ数日作っていたオセロAIのベンチマークテストとかしてました。

ベンチマークテスト

以下のサイトの終盤ソルバーのベンチマークテストをいくつか試してみました。

The FFO endgame test suite

結果は以下の通りです。 因みに、リンク先にはZebraと呼ばれる有名なオセロソフトでの結果も記述されています。 問題番号#40は20手読み、#41、#42は22手読み、#43、#44は23手読み、#45、#46は24手読みとなります。

問題番号 合計探索数(ノード+葉数) 合計探索時間(s) NPS 盤面ハッシュ衝突回数 勝敗(黒-白)
#40 35,886,095 4.81 7,457,402 71,675 51-13(黒+38)
#41 415,613,233 57.78 7,193,561 6,478,663 32-32(引き分け)
#42 247,232,160 34.62 7,141,248 2,756,625 35-29(黒+6)
#43 363,664,671 58.85 6,179,491 11,983,621 38-26(黒+12)
#44 369,740,509 55.75 6,632,463 9,820,481 39-25(黒+14)
#45 3,506,637,244 492.84 7,115,191 153,288,509 35-29(黒+6)
#46 4,067,407,446 580.51 7,006,586 194,124,962 38-36(白+8)

因みに、Zebraによるテスト結果は以下の通りになっています。

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

これと見比べると、自分のプログラムはまだまだ探索ノード数が多いことが分かりますね。 この探索ノード数は、枝刈りや置換表を上手く利用することで削減できますが、まだまだこの辺改良の余地がありそうです。

でも、取り敢えずは20手を数秒で読み切ることに成功したので、ひとまずAIは一旦置いておこうと思います。

iOSアプリに組み込みたいんじゃ

はい。これの続きです。

takalog.hatenadiary.com

明日からはこの辺ちゃんとやっていこうと思います。 (研究もしなきゃいけないので、まぁ無理の無い程度に。)

その辺が終わったら、ネットワーク通信やりたいですね。(ココ早くやりたい)

さー、明日も頑張りましょー👀

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

Nim オセロAI オセロアプリ

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

takalog.hatenadiary.com

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

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

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

  • 最終1手最適化
  • 終盤n手における全探索
  • 空所リストの導入
  • NegaScout法の導入
  • 置換表の導入

最終1手最適化

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

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

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

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

終盤n手における全探索

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

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

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

空所リストの導入

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

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

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

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

NegaScout法の導入

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

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

置換表の導入

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

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

www.geocities.jp

結果

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

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

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

やりました！！！🎉🎉🎉

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

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

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

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

Nim言語でオセロAI【貧弱な終盤ソルバー】

Nim オセロAI オセロアプリ

以下の記事の続きです！

takalog.hatenadiary.com

オセロは、そのゲームの特性上、最大で60手でゲームが終了するので、ターン数によって終盤判定をします。 (将棋とかになると、ターン数ではなくて「相手を詰ませられるか」になるので、もっと複雑になります！)

そして、終盤になるにつれて、自分・相手の選択肢の幅が狭くなってくるので、(中盤に比べると)ゲーム木が広がりにくくなり、最後まで読み切ることができるようになります。

終盤は、中盤とはまた少し違った性質を持つようになるので、基本的に中盤用のアルゴリズムと終盤用のアルゴリズムはまた違ってきます。 この終盤用の機構のことを、終盤ソルバーと言ったりします。

終盤について

先ほど、終盤になるとゲーム木が広がりにくくなると言いましたが、もしかしたら「簡単そうじゃん♪」と思われたかもしれません。

が、しかし

最近のオセロAIを見ていると、終盤20マス辺りから読み切るそうですね...トッププログラムになると24マスとか...(これは恐ろしいことです)

[補足]あまりピンと来ない人もいると思いますので、簡単な計算をしてみます。 終盤20マスから、取り得るゲーム展開の数は、20!(階乗)になります。

\displaystyle 20! = 20 \times 19 \times 18 \times ... \times 2 \times 1 = 2.43 \times 10^{18}

また、競プロやってる人は詳しいのですが、コンピュータは107回のループに約1秒掛かると言われています。 なので、単純に全探索しようとすると、なんと2×1011(秒)、つまり約6342年掛かります(ﾆｯｺﾘ)

勿論、置ける場所・置けない場所あるので、実際はもっとゲーム展開数は少なくなりますが、スゴみが分かってきたと思います(僕もビビってます...笑)

じゃあ、どうすれば良いの？

古いページなんですけど、以下のページが読みやすかったです。

キーワードとしては、

  • 速さ優先探索
  • 置換表
  • 最終1手最適化
  • 評価関数は石数の差

とかかな？

まずは作ってみた

とりあえず、作ってみないと様子が分からないのでパパッと作ってみました。 速さ優先探索を意識してNegaScoutチックに書きました。相手の着手可能数が少なくなる順に打っていくイメージです。

動かしたら、以下のような感じになりました。 Turnは今何ターン目か、NodeNは探索したノード数(葉以外)、LeafNは探索した葉の数、Timeは探索に掛かった時間、NPSは1秒に何ノード(+葉)を探索できたかです。

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

あまりにも重いので、終盤15手読み切りです。でも、20秒弱掛かってる...。

ひぃぃぃぃぃぃ⚡️🌀✨💭❄️

でも諦めないよ💪💪 伸び代って考えると頑張れる😏

Nim言語でオセロAI【探索の高速化】

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としては以前と変わっていないのですが、これから強化していきたいと思います。

NimライブラリをReact Nativeから使いたい(全体像の確認)

Nim アーキテクチャ オセロアプリ iOS React Native

React Nativeから呼び出したくて、奮闘してるけど...行けそうで行けないっ。

何が足りないんだっ！？

nimをCにコンパイルしたら、もうnimの問題ではなく「CライブラリをiOSに持って行く」帰着されて、 すると他の記事を参考にしてやればできるはずなんだけど、何故できないか自分が一番分かっていません笑

全体像を振り返る

言葉で説明できる気がしないので、図で描きますね。

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

はい。多分こういうことだと思うんですけど、どうでしょう...()

今自分がやっていたのは、右側の静的ライブラリにまとめるところです。 (アーキテクチャ毎のクロスコンパイルが上手く行かなくてツラミを見てます)

それで、静的ライブラリをインポートした後の話になりますが、それだけですぐにライブラリが使えるようになるかといったら、そうでもないみたいです。

React Nativeサイドの話

先ほどあげた図の左側の話です。

React Nativeは、直接ネイティブコードを呼び出せる訳ではないようで、 それがしたい時は必ずNativeModulesを介して呼び出さなければいけません。

[注意]React Nativeの開発にExpoを利用している場合は、 NativeModulesが使えない制約が掛かっている状態なので、こちらの記事を参考に、 eject(プロジェクトをExpoの管理下から外す作業)を行う必要があります。

NativeModulesが使える状態になったら、以下の記事のようにやれば、React NativeからObjective-C/Swiftのコードが呼べるようになります。 (動作確認しました。)

qiita.com

更に、Objective-C/Swiftから追加クロスコンパイルした静的ライブラリを読み込んで返せばいけるかなーって感じです。

最後に

やるべき全体像を確認しました。

なんか、自ら薔薇の道に進んでる感がしますが、勉強になるはずなのでもう少し頑張ってみたいと思います。

(でも、この辺ができないと通信関係に入れない...。)

NimライブラリをReact Nativeから使いたい(調査編2)

Nim iOS アーキテクチャ オセロアプリ React Native

今日も一日お疲れ様でした〜！

僕は、今日もNimとReact Nativeを連携させる戦いをしてました。

Nimのクロスコンパイル

これ、今すごく苦労しています...orz

昨日載せた記事(これ)を見て、内容を変えていきつつやる方針でやっていたのですが、結構ハマっています。

nimでクロスコンパイルする時、オプションでCPUとOSを指定して実行するのですが、どう指定すれば良いかが分かっていません。(ムズカシイネ！)

勿論ドキュメントを覗きに行ったんですけど、「指定できるリスト」的なものが見つからなくて困っていたりしています。

まぁそれでも、取り敢えず感覚は掴めたらいいなと思って、linux向けにクロスコンパイルを試みました。 設定ファイルに、

# nim.cfg(nimでコンパイルする時の設定ファイル)
arm64.linux.gcc.path = "/usr/bin/"
arm64.linux.gcc.exe = "gcc"
arm64.linux.gcc.linkerexe = "gcc"

って書いて、取り敢えず$ nim c --cpu:arm64 --os:linux --compileOnly src/mainで実行！

すると、 Nim言語で書いたコードがC言語に変換され、以下の内容のシェルファイルも生成されました。

# compile_main.sh

gcc -c  -w  -o main.o main.c
gcc -c  -w  -o stdlib_system.o stdlib_system.c
gcc -c  -w  -o stdlib_os.o stdlib_os.c
gcc -c  -w  -o stdlib_strutils.o stdlib_strutils.c
gcc -c  -w  -o stdlib_parseutils.o stdlib_parseutils.c
gcc -c  -w  -o stdlib_math.o stdlib_math.c
gcc -c  -w  -o stdlib_algorithm.o stdlib_algorithm.c
gcc -c  -w  -o stdlib_times.o stdlib_times.c
gcc -c  -w  -o stdlib_posix.o stdlib_posix.c
gcc -c  -w  -o stdlib_ospaths.o stdlib_ospaths.c
gcc -c  -w  -o stdlib_parseopt2.o stdlib_parseopt2.c
gcc -c  -w  -o game.o game.c
gcc -c  -w  -o core.o core.c
gcc -c  -w  -o command_line.o command_line.c
gcc -c  -w  -o stdlib_strformat.o stdlib_strformat.c
gcc -c  -w  -o stdlib_macros.o stdlib_macros.c
gcc -c  -w  -o stdlib_unicode.o stdlib_unicode.c
gcc -c  -w  -o ai.o ai.c
gcc -c  -w  -o searchResult.o searchResult.c
gcc -c  -w  -o evaluate.o evaluate.c
gcc -c  -w  -o aiConfig.o aiConfig.c
gcc -o main  main.o stdlib_system.o stdlib_os.o stdlib_strutils.o stdlib_parseutils.o stdlib_math.o stdlib_algorithm.o stdlib_times.o stdlib_posix.o stdlib_ospaths.o stdlib_parseopt2.o game.o core.o command_line.o stdlib_strformat.o stdlib_macros.o stdlib_unicode.o ai.o searchResult.o evaluate.o aiConfig.o  -lm -lrt   -ldl

"main.c"、"core.c"、"ai.c"といったファイルは、自分で書いたやつで、"std〜"系はnimの標準ライブラリだと思います。

やっていることは簡単で、それぞれのCファイルをオブジェクトファイルに変換し、 最後にまとめて実行バイナリを作ることをするスクリプトです。

ほほ〜と思って、取り敢えずsh compile_main.sh実行！ そしたら、次のようなエラーが...！

main.c:7:10: fatal error: 'nimbase.h' file not found
#include "nimbase.h"
         ^~~~~~~~~~~
1 error generated.
stdlib_system.c:7:10: fatal error: 'nimbase.h' file not found
#include "nimbase.h"
         ^~~~~~~~~~~
1 error generated.
stdlib_os.c:7:10: fatal error: 'nimbase.h' file not found
#include "nimbase.h"
         ^~~~~~~~~~~
1 error generated.
stdlib_strutils.c:7:10: fatal error: 'nimbase.h' file not found
#include "nimbase.h"

...(もっと続く！)

どうやら、コンパイルするのに"nimbase.h"というファイルが必要みたいですね。 もうこの辺からよく分からなくなってましたが、{nimへのパス}/nim-0.18.0/c_code/nimbase.hというファイルを見つけたので、 これをコピーして持ってきて、もう一度sh compile_main.sh実行！

そしたら、またしてもエラーががが...orz

ld: library not found for -lrt
clang: error: linker command failed with exit code 1 (use -v to see invocation)

今度は、「rtというライブラリが無いので、リンクできません」みたいな内容ですね。 rtって何じゃ！？と思いつつ調べる。 そして、それっぽいのは見つけました。

"compiler-rt" Runtime Library

でも、この辺りで、ちょっと疲れちゃったので、一旦ストップ。 (なんか方針違うことに気が付いたら、そっと教えてくださいますと泣いて喜びます！)

気分転換に、React Nativeからネイティブモジュールを呼び出す方法を試していました。(こっちは何とかできました！) が、長くなるので記事にまとめるのは今度にします。

3日後くらいには、nimとReact Nativeの連携が取れるように頑張っていきたいです！ おやすみなさいzzz

NimライブラリをReact Nativeから使いたい(調査編)

Nim アーキテクチャ iOS オセロアプリ React Native

こんばんは、昨日作ったリバーシライブラリをiOSアプリに埋め込みたくて、色々調べていました。

でも、まだちゃんと整理しきれていないので、間違っていたら指摘してください！

やりたい事

まず、やりたい事ですが、以下の図の通りです。

f:id:g-knk-9410:20180327224106p:plain:w600

iOSアプリ(React Native)から、Nimで作ったリバーシライブラリを呼び出したいと思っています。 Nimを採用した理由は、単純に高速に動きそうだと思ったからです。

でも、その為には自分の知識が足りていなかったので、今日は基本的な調査をしていました。 とりあえず、今回はiOSを中心に調べました。

iOS上で外部ライブラリを使うために

これについては、結論だけ言いますが、プロジェクトに静的ライブラリ(.a)をインポートすれば良いようです。

静的ライブラリとは、複数のオブジェクトファイル(.o)をアーカイブしてまとめたもので、 更にオブジェクトファイルとは、機械語命令とデータが記述されたファイルらしいです。

また、機械語はハードウェアを制御する命令のことで、この命令セットは実際に動かすデバイスのアーキテクチャによって違ってくるようです。 つまり、オブジェクトファイルはアーキテクチャに依存したファイルってことですね。

因みに、オブジェクトファイルに対して、「どのアーキテクチャに対応しているか」はfile {オブジェクトファイル名}コマンドで分かります。 f:id:g-knk-9410:20180328000800p:plain:w400

この例だと、x86_64が命令セットのアーキテクチャに当たる感じですかね。

そして、iOSにもこのアーキテクチャの種類がいくつかあるみたいなので、一応まとめておきます。 (こちらの記事の引用です。)

アーキテクチャ名 32 / 64 bit デバイス例
armv6 32bit iPhone、iPhone3G
armv7 32bit iPhone3GS以降
armv7s 32bit iPhone5以降
arm64 64bit iPhone5s以降
armv7k 32bit Apple Watch
i386 32bit Simulator
x86_64 64bit Simulator

なるなる。 ここまでの話を総合すると、色々な種類のデバイスに対応させたいのなら、あらかじめそれぞれのアーキテクチャに対応した形でオブジェクトファイルを作っておいて、 それらを全部静的ライブラリとしてまとめておきなさいってことになるのかなと解釈しました。

そして、この違うアーキテクチャに対応した形に変換することをクロスコンパイルと呼びます。

今回はiPhone、iPhone3G、Apple Watchは対応切っちゃってもいいかなと考えているので、 自分はarmv7、armv7s、arm64、i386、x86_64のオブジェクトファイルを用意することになるかなと思っています。

App Thinning

余談です。少し脱線するかもですが許してください。

先ほど、あらかじめそれぞれのアーキテクチャに対応したオブジェクトファイルを作り、静的ライブラリにまとめると言いました。

これを図にすると、以下のような感じになります。

f:id:g-knk-9410:20180328002925p:plain:w400

これをアプリに組み込むことで、それぞれのデバイス上でこのライブラリが使えるようになる訳ですが、 このライブラリをそのまま配布すると少し無駄が出てきますね。

例えば、arm64ユーザにとってarmv7、armv7s、i386、x86_64用のオブジェクトファイル群は全く要らないですよね。

なので、この無駄を解消する動きがあるみたいですね。詳しくはこちらを参照ください。

キーワードは、Slicingとか、Bitcode辺りです。(疲れたのでまとめるのは今度で...。)

特にBitcodeの話は結構面白かったですよ。画期的です！

Nim言語からクロスコンパイルするには？

Nim言語のクロスコンパイルについては、以下の記事が参考になるかな〜と思います！

qiita.com

最後に

今日は、iOSデバイス上でNimライブラリを呼び出すためにはどうしたら良いか調査していました。

まだまとめきれてない感ありますが、明日は手を動かしつつやっていきたいと思います。

ではおやすみなさいzzz