関数型言語ClojureでAI将棋モバイルアプリをつくれないか

# 宣伝

[関ヶ原将棋Online](https://itunes.apple.com/jp/app/関ヶ原将棋online/id491850989?mt=8)
AppStoreで絶賛配信中

![スクリーンショット 2018-11-16 11.38.38.png](https://qiita-image-store.s3.amazonaws.com/0/32152/846b85ea-1ef4-12e0-65f0-a4c61aff5b2b.png)

---

# 背景

- iOS版で出している将棋アプリのAndroid版を作りたい
- Clojureで実装したい
- ReactNative + ClojureScript でそれが実現可能に
- [re-natal](https://github.com/drapanjanas/re-natal)

---

# 将棋AIのアルゴリズム

前段として必要なもの

- 評価値
  - 局面自体を何かしらの基準で測定し評価した値。
  - 例えば駒得（どちらのユニットが多いか）・駒の働き・玉の硬さなど。
- 評価関数
  - 局面に適用して評価値を出す関数。

---

ツリー上のデータを考える
１局面にN通りの指し手があって、その数だけ次局面が存在。

---

- ミニマックス法
- ネガマックス法
- アルファ・ベータ法
- ネガアルファ法

---

* ミニマックス法
  * お互い最前手を指すと言う前提で考える。
* ネガマックス法
  - ミニマックス法の改良版。評価値の判断を逆転することでより簡潔に記述できる。

---

- アルファ・ベータ法
  - ミニマックス法の改良版。絶対に選ばれない局面を考慮してその局面評価処理をカットする（枝刈り）
- ネガアルファ法
  - ネガマックス法の枝刈りバージョン。

---

![nega-max.png](https://qiita-image-store.s3.amazonaws.com/0/32152/3bfcb2e5-0e18-2e6f-9e76-d0dd6633c2fc.png)

---

# ネガマックス(Clojure)

```clojure
(defn deep-score [{:keys [turn] :as db} depth]
  (if (= depth 0)
    (score db)
    (->> db
         next-dbs
         (map #(deep-score % (dec depth)))
         (sort (if turn > <))
         first)))
```

---

![nega-alpha.png](https://qiita-image-store.s3.amazonaws.com/0/32152/f2f322c4-d975-3378-7114-788bb5ae2d3f.png)


---

# ネガアルファ(Swift)

```swift
 func deepScore(_ kifu: String, size: Int, best: (String, Int)?, depth: Int) -> (String, Int) {
        let gameData_ = ShogiLogic.gameData(kifu, size: size)
        if (gameData_["winner"] as? String) != nil { return (kifu, score(kifu, size: size)) }
        let turn = gameData_["turn"] as! String

        var result: (String, Int)?

        // 深さ0ならその局面の評価値
        if depth < 1 { result = (kifu, score(kifu, size: size)) }

        let children = movedKifus(kifu, size: size, stock: depth > 0, capture: depth < 1, safeGyoku: false).sorted {
            turn == "+" ? score($0, size: size) > score($1, size: size) : score($0, size: size) < score($1, size: size)
        }

        if children.count == 0 { return (kifu, score(kifu, size: size)) }

        // 1手先の局面群について
        for child in children {
            // 子供の評価値
            let score_ = deepScore(child, size: size, best: result, depth: depth - 1)

            // resultより高評価ならその値をresultにする（先手か後手かで評価軸を逆にする）
            if result == nil || (turn == "+" ? score_.1 > result!.1 : score_.1 < result!.1) {
                result = score_
            }
            //子供の評価値が同列な層の他局面より良かった場合に終了
            if best != nil && (turn == "+" ? result!.1 >= best!.1 : result!.1 <= best!.1) {
                return result!
            }
        }

        if result == nil { result = (kifu, score(kifu, size: size)) }
        return result!
    }
 }
```

---

# ネガアルファ(Clojure)

```Clojure
(defn deep-score [{:keys [turn] :as db} depth best]
  (if (= depth 0)
    {:score (score db) :db db}
    (reduce (fn [{:keys [end score] :as current} next-db]
              (if end
                current
                (let [{target :score} (deep-score next-db (dec depth) score)]
                  (cond
                    (and ((complement nil?) best) ((if turn >= <=) target best)) {:end true :score target :db next-db}
                    (or (nil? score) ((if turn >= <=) target score)) {:end false :score target :db next-db}
                    :else current))))
            {:end false :score nil :db nil}
            (next-dbs db))))
```

---

# 前回まとめ

* mapで処理する場合は途中の計算結果を次の計算に反映させられない
* reduceで終了フラグ有無を持ち回した
* 遅延評価を使えばもっとスマートに計算省略ができるのでは？
* よくよく考えればreduceで持ち回さずとも再起でできそう（できた）

---

# ネガアルファ(Clojure再起in再起)

``` clojure

(defn deep-score [{:keys [turn] :as db} depth same-layer-best]
  (if (= depth 0)
    {:score (score db) :db db}
    (loop [children (next-dbs db) {:keys [score] :as result} nil]
      (if (= (count children) 0)
        result
        (let [child (first children)
              child-score (:score (deep-score child (dec depth) result))]
          (if (and ((complement nil?) same-layer-best)
                   ((if turn >= <=) child-score same-layer-best))
            {:score child-score :db child}
            (recur
              (rest children)
              (if (or (nil? result)
                      ((if turn > <) child-score score))
                {:score child-score :db child}
                result))))))))

```

---

# COMの指し手の計算中にハング
重い計算をメインスレッドでやってはいけない

ReactNativeはJSの仕組みを踏襲した世界観なので（基本的に）マルチスレッド非対応

---

# NativeModules

自作のネイティブクラスをJSから呼び出して使える
（ネイティブではマルチスレッドでの処理は簡単に書けるので、これを使えばいい感じにできるのでは？）
（結論としてはAndroidでは無理でした）

- [iOS](https://facebook.github.io/react-native/docs/native-modules-ios)
- [Android](https://facebook.github.io/react-native/docs/native-modules-android)

---

流れとしては
ネイティブ側でReactNativeに晒すメソッドを定義
それをClojureScript(JS)側で呼び出す

(ThreadExampleというクラス名・executeというメソッド名でJS側に公開した場合)

``` Clojure


(def thread (.-ThreadExample (.-NativeModules (js/require "react-native"))))

(.execute thread do-somethig-on-sub do-something-on-main)

```

---

# iOSのマルチスレッド

Grand Central Dispatch (GCD) 

``` objective-c   
dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
    // Call long-running code on background thread
    dispatch_async(dispatch_get_main_queue(), ^{
    // Call running code on main thread
    });
});
```

---

NativeModulesにすると

``` objective-c
RCT_EXPORT_METHOD(execute:(RCTResponseSenderBlock)main
                      sub:(RCTResponseSenderBlock)sub)
{
    dispatch_async(dispatch_get_global_queue(DISPATCH_QUEUE_PRIORITY_DEFAULT, 0), ^{
        sub(@[...]);
        dispatch_async(dispatch_get_main_queue(), ^{
            main(@[...]);
        });
    });
}
```

---

# Androidのマルチスレッド

``` java
private class ThreadTask extends AsyncTask<String, Void, String> {
  protected String doInBackground(String... strs) {
    // Do something on Subthread
    return "done";
  }

  protected void onPostExecute(String str) {
    // Do something on MainThread
  }
}

new ThreadTask().execute("arg");
```

---

NativeModulesにすると

``` java
@ReactMethod
public void execute(Callback sub, Callback main) {
  new ThreadTask().execute(sub, main);
}

private class ThreadTask extends AsyncTask<Callback, Void, Callback> {
  protected String doInBackground(Callback... callbacks) {
    callbacks[0].invoke();
    return callbacks[1];
  }

  protected void onPostExecute(Callback main) {
    if (main != null) main.invoke();
  }
}

```

---

### これでうまくいくように思われた。

---

### しかし・・・。

---

# Callbackの制約

ReactNative側からNativeModule側に１メソッドで与えたCallback群はどれか一つしか呼ぶことはできない
（Androidでのみ確認）

---

ので、Callbackを一つだけ受け取るメソッドに変更

``` java
 @ReactMethod
  public void executeSub(Callback callback) {
    new SubThreadTask().execute(callback);
  }

  @ReactMethod
  public void executeMain(Callback callback) {
    new MainThreadTask().execute(callback);
  }

  private class SubThreadTask extends AsyncTask<Callback, Void, String> {
    protected String doInBackground(Callback... callbacks) {
      callbacks[0].invoke();
      return "done";
    }

    protected void onPostExecute(String str) {
      // メインスレッドで何もしない
    }
  }

  private class MainThreadTask extends AsyncTask<Callback, Void, Callback> {
    protected Callback doInBackground(Callback... callbacks) {
      return callbacks[0]; // 実行せずにonPostExecuteにパス
    }

    protected void onPostExecute(Callback callback) {
      callback.invoke();
    }
  }

}
```
---

### これでうまくいくように思われた。

---

### しかし・・・。

---

サブスレッドで呼んでいるはずの処理がメインで実行される。
[AndroidのNativeModulesはサブスレッド非対応っぽい](https://facebook.github.io/react-native/docs/native-modules-android#threading)

---

というわけでAndroidで非同期処理をやるならWebworkers的な記述をしなければいけない。

1. AI部分をClojureScriptからJSにWorkerJSとして別途コンパイル（最適化が入るのでよくわからない・・）
1. 謎の形にコンパイルされたJSにWorkerの機能を実装
1. WorkerJSからClojureScriptで書かれた将棋ロジックのAPIにアクセス

と、どうしていいのかわからない課題が残された

---

# まとめ

ReactNative大変（特にAndroid）