宣伝
関ヶ原将棋Online
AppStoreで絶賛配信中
背景
- iOS版で出している将棋アプリのAndroid版を作りたい
- Clojureで実装したい
- ReactNative + ClojureScript でそれが実現可能に
- re-natal
将棋AIのアルゴリズム
前段として必要なもの
- 評価値
- 局面自体を何かしらの基準で測定し評価した値。
- 例えば駒得（どちらのユニットが多いか）・駒の働き・玉の硬さなど。
- 評価関数
- 局面に適用して評価値を出す関数。
ツリー上のデータを考える
１局面にN通りの指し手があって、その数だけ次局面が存在。
- ミニマックス法
- ネガマックス法
- アルファ・ベータ法
- ネガアルファ法
- ミニマックス法
- お互い最前手を指すと言う前提で考える。
- ネガマックス法
- ミニマックス法の改良版。評価値の判断を逆転することでより簡潔に記述できる。
- アルファ・ベータ法
- ミニマックス法の改良版。絶対に選ばれない局面を考慮してその局面評価処理をカットする（枝刈り）
- ネガアルファ法
- ネガマックス法の枝刈りバージョン。
ネガマックス(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)))
ネガアルファ(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)
(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再起)
(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では無理でした）
流れとしては
ネイティブ側でReactNativeに晒すメソッドを定義
それをClojureScript(JS)側で呼び出す
(ThreadExampleというクラス名・executeというメソッド名でJS側に公開した場合)
(def thread (.-ThreadExample (.-NativeModules (js/require "react-native"))))
(.execute thread do-somethig-on-sub do-something-on-main)
iOSのマルチスレッド
Grand Central Dispatch (GCD)
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にすると
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のマルチスレッド
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にすると
@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を一つだけ受け取るメソッドに変更
@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はサブスレッド非対応っぽい
というわけでAndroidで非同期処理をやるならWebworkers的な記述をしなければいけない。
- AI部分をClojureScriptからJSにWorkerJSとして別途コンパイル（最適化が入るのでよくわからない・・）
- 謎の形にコンパイルされたJSにWorkerの機能を実装
- WorkerJSからClojureScriptで書かれた将棋ロジックのAPIにアクセス
と、どうしていいのかわからない課題が残された
まとめ
ReactNative大変（特にAndroid）