Kotlinで再帰関数（AIに丸投げ）

ウォーターソートパズルを題材に

　もう６年以上前の話ですがKotlinが流行り始めた当時、将棋関連アプリのAI部分の高速化を考えていた私はCoffeeScript(Javascript)のソースコードをKotlinに書き換えてみたことがあります。でも文法だけKotlinに書き換えてもわずか３手読みですぐにスタックオーバーフローが発生して、末尾再帰の形になるようにソースコードを書き換えなければならないことが分かって挫折しました。
　でも、前回の記事で作ったプログラムなら、将棋関連アプリに較べればかなり単純な構造の再帰関数なので、これなら出来るんじゃないか？と興味が湧いて、これを題材にして末尾再帰に書き換える作業を体験することにしました。

※Kotlin製の５五将棋プログラムは今でもソースが残ってますが、Null Safetyなんて全く気にしていないCoffeeScriptのソースコードをそのままKotlinに移行して、とにかくコンパイルを通すためにnullableな変数を無理やりnon-nullに強制的に変換する演算子!!（ビックリマーク２つ）だらけの、Kotlin使いに言わせれば汚いコードでした。

Grokに聞いてみる

　プログラミングの際に本やGoogle検索を使うよりもリファレンスとしてGrokは有用だなと思っていたので、まずはKotlinに慣れていない私はRubyのソースコードを貼り付けて「このコードをKotlinに書き換えて！」と丸投げしてみました。コンパイルエラーが出ても実行時エラーが出ても「エラー出てるよ！」と返して、修正されたコードをまたコピペして実行するだけでこちらはあくまでも受け身の姿勢です。
　そしてエラーは無くなったけど期待した結果が返ってこない状態になって、Rubyで配列A == 配列Bの比較をしている部分は「Kotlinでは無理だろうな」と当たりをつけてequalsメソッドを改変したら（ここもGrokに丸投げ）すぐにBFS版は完成しました。Grokが吐き出すコードを碌に確認もせずデバッグ作業も全くしてません。そして肝心のNodeクラス内の再帰関数メソッドに較べて再帰がやや複雑になっているDFS版も「dfs関数も末尾再帰に書き換えて！」とGrokに丸投げしただけで完成しました

ソースコード

　「どうせどこかでトラブってデバッグ作業させられるんだろうなぁ」と期待せずにダラダラと始めた作業なのですが、正味の作業時間は１時間もかかっていません。Grokとのやり取りも数回だけです、公開するのは少し恥ずかしいですが、Grokとのやり取りの一部始終を公開しますので興味ある方は確認してみてください。

生成AIの実力を認めざるを得ない

　この記事は「自作の再帰関数を末尾再帰に書き換えるためにはこんな作業が必要でした」という内容になる予定だったのですが、Grokに丸投げするだけで済んでしまったので書くことが無くなりました。もしそういう内容を期待してた方はGrokの履歴を見てもらえば各再帰関数の変更前と変更後のソースも見れますし、解説もされているのでそちらを見ていただきたいと思います。dfs関数の末尾再帰化された後のコードは自分自身もよく理解できていません。
　生成AIはプログラミング時のリファレンスには使えるぐらいの認識だったのですが、完全に自分が教えて貰ってる状態です。未だにChatGPTもほとんど使ってないしCopilotもよく知りません（何を使っても中身は同じ？）が、積極的に使ったほうが開発効率は上がりそうですね。
　とは言っても今回のケースはRubyの正解がある状態、アルゴリズムに問題が無いことが分かっている状態から始めたので、一からKotlinでプログラミングしていたら例えGrokに手伝ってもらってもこんなに簡単には完成しなかったとは思います。しかしRubyのようなLightweight Languagesでサクッとプロトタイプを作ってから生成AIを使ってC++のようなコンパイラ言語に置き換えるのも一つの使い方としてアリかもしれません。将棋関連アプリのC++（STL使用）への変換も試してみようと思ってます。

ちょっと怪しい…

　vscode上で実行していた時は気づかなかったのですが、コマンドラインでコンパイルするとwarningが出てました

$ kotlinc -include-runtime -d ./game.jar waterBottles
waterBottles/game.kt:72:21: warning: recursive call is not a tail call.
    val subResult = dfs(node, temp, depth - 1, 0, 0, false, newResult)
                    ^^^
waterBottles/node.kt:52:22: warning: recursive call is not a tail call.
        } else if (c.add(nd, target, 0)) {
                     ^^^
waterBottles/node.kt:77:22: warning: recursive call is not a tail call.
        } else if (c.replace(nd, target, 0)) {
                     ^^^^^^^
waterBottles/node.kt:94:22: warning: recursive call is not a tail call.
        } else if (c.search(target, 0)) {
                     ^^^^^^

　コンパイラは「末尾再帰になってませんよ」と言ってます
どうやら末尾再帰化が中途半端になっているようですが、dfs関数に関してはGrokによる末尾再帰化を施さないと期待通り動かなかったので、間違った変更を加えたわけではないようですし、内部の処理がRubyとどのような違いがあるのかは分かりません。それより驚いたのは、完成したKotlinのプログラムでRubyのプログラムと同じ問題を解かせてみるとDFS版もBFS版もKotlin版の方がRuby版よりもかなり遅かったことです。Rubyに合わせて敢えて不要な部分で可変長の配列を使ってるところとか、確かに実行速度を上げることを目指したコードではないですが、まさか同じデータ構造とアルゴリズムでインタプリタ言語のRubyより大幅に実行速度が遅くなるとは思いませんでした。

`Kotlin(Java)`って再帰関数が苦手なの？

　前回の記事の冒頭の問題を解かせて見たところDFS版で0.151秒、BFS版で5530.022秒（約１時間半！！）でした、Rubyでは前回の記事でも書いた通り0.016248494秒と279.599430481秒（約４分半）です。再帰関数ではないはずのBFS版の遅さが目立ちますが、BFS版でも内部では再帰関数であるNodeクラスのaddメソッドを頻繁に呼び出すので、念の為Node.addメソッドを末尾再帰ではない元々のコードに戻して試してみましたが実行時間に違いはありませんし、スタックオーバーフローも発生しません。末尾再帰化はスタックオーバーフローを避けるためのものなので、実行速度は変わらない（あるいは若干遅くなる）はずで、まぁこうなるところでしょう。それよりなによりRubyより遅いのならそもそもKotlinに書き換える意味がありません。Javaは昔に較べて速くなってると聞いていたし、原因はいろいろあると思いますが、もしかしてKotlin(Java)は末尾再帰化されているかどうかに関わらす再帰関数を使うと遅くなるのでしょうか？とにかくモチベーションが一気に下がりました。
　結局、末尾再帰化は中途半端になりましたが、速度アップには繋がらないし、スタックオーバーフローが発生しているわけでもないのでここで止めておきます。昔、GOTO文も駆使しながらスタックの消費を抑えているC言語のソースを見たことがありますが、そこまでする必要はないでしょう、というかそこまでやる人に敬意を表しますが私には出来そうにないです。
　もうこのKotlin版の高速化に時間を掛けようとは思いませんが、その昔将棋関連アプリをKotlinに書き換えることを早々に諦めたことは私にとって良かったのかもしれません。生成AIが存在しなかった当時、スタックオーバーフローを避けるために苦労して末尾再帰に書き換えても実行速度が遅くなったのではさぞ虚しかったことでしょう。

やはり高速化なら`C++`

　将棋関連アプリの高速化のために将棋AI部分をC++で書き直したとしても、GUIを何で作るかという問題が残りますのでこれについては今後も模索中です。Kotlinで高速なものが作れれば、AndroidアプリのGUIもKotlinで作れるのでよかったのですが、残念です。
　現在販売中の３三将棋アプリは評価値でソートして候補手を絞る関数と局面を先読みする関数の２つの関数を再帰呼出ししている面白い処理（「反復深化？を工夫してより深く読む」参照）をしているので、GUI付きのアプリとして販売するかどうかに関わらず一度C++で実装してみたいとは思っています。