Nim言語でリバーシAI
Nim言語触ってました〜。
いいですね！Nim言語！
リバーシAI
リバーシAIは昔作ったことあるので、大体の感覚は掴んでた訳ですが、設計とかビット演算処理とか甘い所はあったので、より良い感じになるように意識して作っています。
Nim言語も初めて触っているので、なかなか刺激的な時間が送れていると思います！
という訳で、一応コマンドライン上で動く形にはしました。リポジトリはこちら。
なるべく見やすくするように...と思っていたんですけど、正直言って見辛いし使いづらいですね、コマンドラインだからしょうがない(苦笑)
まぁ、このプログラムはこのまま使う訳ではなくて、AIのための辞書作りや学習に応用したり、 スマホ端末用にクロスコンパイルしてアプリのオセロロジックとして組み込む予定なので、 とりあえずパソコン上で動かすGUIは作らないで、このままのスタンスでいきたいと思っています。
大枠を簡単に作った所で、今後オセロAI系に関してやることをリマインドとしてまとめておきます。
- 反転処理(Flip処理)の高速化
- 探索アルゴリズムの完成(現在は、まだNegaMax法なので、NegaScout法にする)
- 評価関数の洗練(現在は、石の配置と着手可能数による評価)
- 終盤ソルバーの洗練(というか、今はまだ用意してなかった笑)
- 棋譜から学習させる(同じ負け方は2度しないように学習)
- AI同士で自動で対戦させて棋譜を収集する機構を作る
結構やること多いですね。少なくとも4番まではやっておきたいですね。5番、6番はもう少し後でも問題無さそう。
これと同時平行で、Nim言語をクロスコンパイルしてiOS上で、静的ライブラリとして読み込めるように頑張っていきたいと思います〜。
「Nim言語をiOS上で動かしてみた」っていう記事はあまり無いんですけど、NimはCにも変換しているので、 多分「C言語をiOS上で動かしてみた」と同じような雰囲気でやれば、いけるんじゃないかなとなんとなく思っています〜。
ふー疲れた。明日は早いのでおやすみなさい！
ビットボードの深みにハマる
今日は、前半はNimのお勉強、後半はオセロのビットボード実装をしていました。
Nim
ドキュメントをサーッと見たり、メモしたりしました。
大体の感覚を掴んだ所で、「あとはやってれば覚えるっしょ！」ってノリで勉強を終えて、
ビットボードの勉強へシフト。
勉強してたら、コード書きたくなっちゃうことってありますよね？
ビットボード
まず、オセロは8×8の盤面で構成されています。 そして、その盤面に以下のように番号を割り振っていきます。
すると、盤面の状態が64bit整数2つ(黒用と白用)で表現できるようになります。
例え整数と言えど、内部的には0と1の羅列から成っているので、それを盤面に見立てて利用する訳ですね。
例えば、以下のようなビットボードがあったとします。 (「1」と書かれているマスに対応したビットが立っていて、それ以外のビットは0になっていると考えてください。)
この時、盤面を再現すると以下のようになります。(身体で感じてください。) 因みに、両方0の所は空白扱いになり、両方1になる所は絶対に有りません。
「なんで、わざわざこんな事するの？配列でイイじゃん」と聞こえてきそうですが、このようにする理由がちゃんとあります。 ビットボードで実装すると、とにかく速いんです。 基本的にビット演算を駆使すると、安直に配列をループさせた時の何十倍も速く探索や反転処理が行えます。 (なので、オセロAIを実装しようとしたら、ビットボード化するのは定石です。)
ビットボード化すると、次のような処理が、ビット演算で行えるようになります。
- 石数のカウント
- 着手可能箇所を求める
- 石の反転処理
そして、これらの処理はこの後AIの探索処理を行う際に、何十万・何百万回と使い回されるので、とても重要です。 簡単になりますが、100,000回、上記の処理を行うと仮定した時、その実行に掛かる時間が0.0001秒変わるだけで、全体で10秒もの差が付くということです。 これはヤババ。
ビットボードの大切さが分かった所で、次はビットボード実装は当たり前と考えて、「もっと速く処理するにはどうしたら良いか」という話になってきます。
上述した通り、着手可能箇所を求めたり、反転処理という処理は、AI実装した時にかなりシビアに影響される所で、演算単位での効率が求められるようです。怖っ！
そして、これに関連する記事が最近は結構出てきているので、紹介しておきます。
僕も昔ビットボード実装したことあるんですけど、全然まだまだでした(笑)
特に、反転処理を行う所(flipと言うらしいです)が、以前の僕のコードは結構安直でwhite文とif文を普通に使って実装していました。
上の記事の先には、while文もif文も要らず、本当にビット演算で反転処理を実現しています。すごいです(笑)
最後に
今日は、Nimを少し勉強して、実際にオセロロジックを組んでいました。
基本的に昔書いたプログラムを再利用すれば大丈夫だったのですが、反転処理の所だけ明らかにパフォーマンス悪そうだったので、
先人の知恵を参考にしつつ、より効率の良いアルゴリズムを模索しています。(思い付かなかったら、もうパクるしかない)
ここ、本当に深いなぁ。
あとは、効率良くボードを点回転・軸回転させて状態数を削減したいのと、 学習アルゴリズムを作って辞書作って読み込む形にできたら最高ですね。 まぁ、他の機能との兼ね合いがあるので、どの辺で妥協するかっていう話になりそうですが^^;
探索はNegaScout法とかが良さそうで、評価関数はどうしよう...って感じです。
うわぁ、考えることいっぱいだなこれ全部やれるのか...?
Nimに浮気しました
こんばんは、昨日に引き続き、オセロアプリの開発に関する調査をしています。
Rustで生成した実行ファイルをiOSで読み込む
JavaScriptでいいじゃんという声もあるかもしれませんが、より高速で強いAIを実現するためには、 より効率的で速い実行環境を求めるべきですよね。
そういう意図があったので、実行速度の速いRustで作ったライブラリをiOSで実行できないかどうか調べていました。
すると、以下の記事が見つかりました。(僕が調べた所、日本語資料は見つかりませんでした。)
まさしく、React Native + Rustの構成で、Rustの関数を使って"Hello World"の文字列を画面に表示してみようという内容です。
僕はまだHello Worldを出力しただけでキチンと理解している訳ではないので、詳細を知りたい方は参考サイトを見ていただきたいのですが、 僕の感じ取った事をざっくり述べると、以下のようになります。(iOSの場合のみ)
- 手順
- iOS、Androidの物理アーキテクチャ(CPU、命令セットなど)を再現できるようにインストール
- Rustから実行ファイルを生成するためのMakefileを書き、makeコマンドで実行ファイルを生成
- Rustのビルドシステム兼パッケージマネージャーのCargoの設定ファイルを書く
- 参考サイトでは共通の型としてCのプリミティブ型を使うので、その変換ヘルパーを書く(多分)
- Xcodeを開いて、依存ライブラリにRust実行ファイルを指定して、静的ライブラリとして読み込ませる
- ネイティブモジュール用の「React NativeとRustライブラリの橋渡し」の役割を持つモジュールを定義(これよく分からない)
- React Nativeから、NativeModuleを介してRustライブラリにアクセス
ざっくり書いてみましたが、ちゃんと理解していません、難しいです。(分かる方いましたら、すごく教えて欲しいです...。)
これについては、ちゃんと理解したら記事とか書きたいですね。
Nim言語
iOS上でRustライブラリがちゃんと使えそうなことが分かったので、さて開発に取り掛かるかと思ったその時、次の記事を見つけてしまいました。
この記事は、各言語でフィボナッチ計算を行い、実行速度を比較した記事になります。 この記事の結果を載せておきます。
これを見ると分かると思いますが、最適化したNim言語が速過ぎます。 (実際には、C言語を-O3最適化した時よりほんの少し遅い程度らしいですが。)
これで興味を持って、公式サイトで少し調べました。 特徴としては、
- ガーベジコレクションが高速
- 実行バイナリサイズが小さい(state-of-the-art)
- 読みやすい
- NimからC/JavaScriptにも変換できる
公式ドキュメント見た感じ、結構良さそうだったです。 でも、すごくマイナー言語らしく、日本語の記事は少ないです。
前半のiOSに静的ライブラリを読み込ませる話は、Nimにも応用できるはずなので、今回はより実行速度が速く、
ファイルサイズも小さく、読みやすいNim言語を使って開発していこうかなと思いました。
正直、Rustの所有権周りが嫌いだったです。
最後に
今日、何年か振りに絵書きました。ポリゴンです！
と、ミミッキュです！
以上です。
オセロアプリの制作開始
こんばんは、開発合宿も無事終えることができて、今度は自作アプリを開発することに精を出し始めました。
アプリの題材は、自分が好きで時々やることがあるオセロでいきたいと思います。
調査
どうせ作るなら、既存の有り触れているオセロアプリとは、差別化を図ったものにしたいと思ったので、 片っ端から関連アプリをダウンロードしてみて、どんなものがあるのか調査していました。
- オセロクエスト
数少ないオンライン対戦アプリで、おそらく最もアクティブユーザが多いアプリでもあると思います。 レートがあって、自分の近い実力の人とマッチングするので、初心者〜熟練者まで楽しめるアプリになっていると思います。 リアルタイム観戦機能もあるし、切断時の処理もしっかりしています。 因みに、僕のレートは1950〜2000辺りを行ったり来たりしてます...orz
- リバーシプロジェクト
こちらもオンライン対戦が可能なアプリとなっていますが、レートという概念はありませんありました(2018/3/24追記)。
このアプリの特徴的な所は、少し違ったオセロ対戦ができる所で、いくつかあるキャラクターの中から一つ選択してセットすることができ、
対戦時にはセットしたキャラクター効果(例えば、一度だけ「待った」できる等)が使用できます。
- 入門リバーシ
リバーシ初心者向けのアプリです。 13段階のレベルから選べるコンピュータ対戦があり、対戦が終了した後はどの手が良くて、どの手が悪かったのか振り返ってくれます。 解説も丁寧だし、落ち着きのあるデザインだし人気が出るのは納得ですね。
- リバーシZERO
AIのレベルが100以上あるアプリです。 オフラインで、一人または二人で遊べるようになっています。 オンライン対戦機能はありませんが、UIが綺麗だし、好みの問題かもしれませんが石をひっくり返す時の音も良いです。
他にも、もう10個くらいインストールしてみましたが、書ききれないのでこれくらいにしておきます。
アプリの方針も、何となく頭の中で定まってきたので、楽しみつつ開発頑張っていきたいと思います！
技術構成
技術的な構成としては、アプリ側はReact Native + TypeScript + Redux + (Rust)辺りで考えています。 個人的な目標としては、可読性があって、メンテナンスしやすいコードを作り上げることです！
因みに、RustはAI部分で使いたいと考えています。 C/C++と同程度の速度、メモリ安全なのでクラッシュする心配が薄いのが主な理由です。 また、ビットボード実装する時には64bit整数で盤面を表現するのですが、JavaScriptには32bit整数しか無く不便な点、 Rustを学んでおくと、最近よく聞くWebAssemblyとかにも応用が効きそうだと思った点、後は単純に触ってみたかったからです(笑)
Webで調べていたら、React NativeからでもRustが動かせるみたいなので、明日はその辺やってみたいと思います。
また、オンライン対戦も実装したいと考えているので、AWS + Docker + {何かしらのサーバサイド言語・フレームワーク}とかも使うと思います。 何の言語にするかは、まだ確定ではないのですが、Scala + PlayFramework辺りになるかなぁと思います。
開発合宿！
昨日は開発合宿が終わって、メンバーと話していたらブログを書き忘れてしまいました(笑)
今日は、昨日行ってきた開発合宿についてです。
開発合宿
ブロックチェーンをテーマに、8人体制でフロント、サーバ、ブロックチェーンに分かれて開発を行いました。
僕はサーバ(2人)の所に入り、Docker+Rails+Webpackで開発を行っていたんですけど、 まずDockerを触ったことがなかったり、Railsも触ったの2年振りくらいで、大分つらみがありました...orz
なので、もう一人の人が中心になって、僕が横から調査しつつ茶々入れる感じで開発を行いました。
正直言って、僕自身あまり貢献できなかったと自覚していますが、合宿中にDockerについて教えてもらったり、 その他にも自分の知らないツールなどを教えてもらったりして、技術的な知識も沢山得ることができたと思います。
また、今回チーム開発を行う中で最も手こずってしまったのがそれぞれの機能の連結の部分でした。 その原因としては、それぞれのエンドポイントに対する入力・出力の設計がふわふわしたまま開発に入ってしまったことが考えられました。
次チーム開発する時は、事前に必ずこの辺りの打ち合わせをしっかり行って活かしていきたいですね。 そして、個人としてはDockerは最低限使いこなせるようになりたいです。
2日間の開発を通して、メンバーと話す機会がありましたが、皆それぞれ少しずつ違う方向に強みがあって、 話していてすごく楽しかったですし、全員イイ人でこの合宿行って良かったと思いました！
今回、サーバ開発を主に行いましたが、勿論同時にブロックチェーンも学びましたし、技術的なこと以外でも人から沢山刺激を受けましたし、今すごくテンション上がっています！ 社会人になるまで後1年ですが、悔いの残らないように勉強も遊びも精一杯楽しんでいきたいと思ったイベントでした^ ^
開発合宿なう
今日は開発合宿に来ています。
テーマはブロックチェーンなんですけど、僕はチェーン本体ではなくサーバ組に入っています。
仮想通貨で言うと、CoinCheckとかBitflyer的ポジションでしょうか。 秘密鍵の保持をして、ブロックチェーンとユーザの介入をするポジションです。
Railsを使っての開発で、年単位でブランクがあって忘れているし、Docker使ったことなくて分からないし、 色々大変なことはあるんですけど、逆に言うとこれからの自分の課題は沢山見えてきているので、 なんか逆にテンションあがってます(笑)
明日なんとか形になるように自分のできることをしたいのと、学びのある開発合宿にしたいです^^
明日から開発合宿！
今日もNaivecoinを勉強していました。
なんで最近ブロックチェーンを勉強していたかというと、明日から2日間開発合宿をやることになっていて、 そのテーマがブロックチェーンだったからです！
今日は、上記のページのP2P通信部分で使われているWebSocket通信ライブラリについて、 使い方を完全に理解している訳ではなかったので、調査をしていました。
そして、明日から開発合宿に向けて、鈍行電車に揺られて東京入りを果たしました！
WebSocket通信
WebSocket通信についてはよく知っていましたが、軽くまとめておきます。
普段、僕たちがブラウザから行なっているHTTP通信は、URLからアドレスを検索し、リクエストを行い、レスポンスを貰いそれを表示することで実現されています。
しかし、接続したい場所が決まっている時、毎回毎回接続要求を出すのは、明らかに無駄です。
WebSocket通信は、一度接続要求を送ると、コネクションが確立されて、そのコネクションが存在する間はすぐにメッセージを送ることができます。 高速に、低コストで通信が実現できるので、速度が欲しい場合や、継続的な通信がしたい場合によく導入されます。
...というのが僕の現状の理解なんですけど、メリットはもっと他に沢山あるみたいですね(^_ ^;)
node.jsのWebSocket通信
今回、僕が勉強したサイトでも、ブロックチェーンのP2P通信の部分ではwsというソケット通信ライブラリを使用していたのですが、 これが本当にベストだったのか疑問だったので、少し調べたら以下のようなライブラリが見つかりました。
見てみると、socket.ioはWebSocket通信だけではなく、ポーリングだったりCometにも対応しているみたいですね。
うーん、今回の事だけ考えると、ポーリングとかは要らないから、wsで十分事足りるかな？
最後に
明日からの開発合宿、楽しんで頑張っていきたいと思います！
これが終わったら、ポーリングだったり、Cometの勉強も少ししておきたいです！(どこかで使えるかもしれないので！)
