🍎 Javascriptで詰将棋を解く
2023/03/15
サイトメニューにあるJP詰将棋は以前 Python で作り、
HTML 側から非同期通信で結果を受け取るという実装を選択していました。
しかし、Python は遅く、高速版の Pypy はこのサーバでは使えないことが気がかりでした。
藤井5冠のタイトル戦が TV やネットで放映されるのを見る都度、その気がかりがましたため、
今回、Python のコードを Javascript に移植し、
Pypy を超えるスピードアップを達成し、JP詰将棋を高速版に差し替えました。
Python はご承知のように C 言語などに比べて遅く、高速化のために numpy, pypy, Cython といった方法が試みられてきましたが、 これらはいずれも Web サーバには簡単に置けないもので、効果も限定的です。 Python 版はソースを見直してももうほとんど速度アップできないほどに最適化済みです。 といって Cythonを使わず、自分でC言語へ移植するのはかなり大変で、 レンタルサーバ上でコンパイルし、公開できるかも不明です。
ネットで円周率の計算を Python でやらず Javascript でやったところ、 500倍速くなったという記事を読みました。 Node.js で試してみると本当でした。 これはもう Python を Javascript に移植するしかないと思い立ちました。 Python コードは高速化のため究極の書き方になっていたため作業は手間取りましたが、 昨日何とか終わりました。 その結果が以下です。 残念ながら 500 倍とは行きませんが(10倍程度)、まずまずの結果です。
問題 | Python | Pypy | Node.js | Chrome JS |
---|---|---|---|---|
五手詰 | 0.29秒 | 0.48秒 | 0.13秒 | 0.11秒 |
七手詰 | 32.1秒 | 7.35秒 | 3.94秒 | 3.42秒 |
九手詰 | 81.1秒 | 17.3秒 | 9.27秒 | 7.95秒 |
上の表は同じ問題数題を各エンジンで解いた解答時間を平均したものです。 おわかりのように、五手詰めの段階ではインタープリタの最初の処理のために 大して速くなった感じがしません。 Pypy などはむしろ遅くなっています (Node.js は Javascript のコマンドライン版、 Chrome JS は HTML ファイルに組みこんだ Javascript を Chrome ブラウザで実行したものです)。 七手詰めで、Pypy が Python の 4 倍以上になり、 Javascript はさらにその倍近くのスピードを達成していることになります。
8 秒で 9手詰めが解けますから、もうかなり実用的です。 ちなみに、この後、11手詰めになると Javascript でも 100 秒以上かかり、 選択する手の数が多い詰将棋では 300 秒でも終わりません。 また、合ゴマとその対応を 2手と考えるため、 11手詰でも 13手として解く必要があるものもあり、実際には数百秒どころではなくなります。 7手詰が 9手詰になるように、2手増えると時間が十数倍かかると予想されるからです。
実際、いくら高速化したとしても、確実にあらゆる局面を網羅した詰将棋ソフトを作るなら、 量子コンピュータでも使わなければ 13手詰か 15手詰が限界で、 そうでないなら、画期的な推論規則を見出すか、 過去の膨大な棋譜の蓄積とその類似を高速にスキャンする方法を見出す必要があるでしょう。 ちなみに、全局面を網羅しようと思えば、何千クエタ分かの蓄積が必要になり、 これはテラのテラ倍のそのまたテラ倍くらいの記憶容量が必要になります。 ということで、地上のコンピュータでは永遠に不可能だと思われます。
ひどく悲観的な結論になってしまいましたが、 それだけ将棋というものが奥の深いゲームだということを表しているので、 そう考えると、肯定的な結論だともいえます。
付記: Node.js より Google Chrome の Javascript が速いというのは驚きです。 おまけに Chrome では Javascript のデバッグも簡単にできます。 これは Google の開発スタッフの優秀さを表しているのでしょうか?😅
参考1: JP詰将棋で遊ぼう
参考2: まいにち詰将棋
![]() | ![]() |
🕍 同じジャンルの最新記事(-5件)
![]() | Javascriptで詰将棋を解く(2023/03/15) 今回、詰将棋の Python コードを Javascript に移植し、相当なスピードアップを達成しました... |
![]() | NTT光でVPN(2022/07/27) NTT光接続でつないでいる場合、デフォルトのゲートウェイ機で VPN できちゃいます。その具体的なプロセスです... |
![]() | 動画の広告カット(2022/07/26) 広告をカットしたり、前後の不要部分を削除したりしたい場合、簡単で、安全にできるソフトに kdenlive があります... |
![]() | Python速度アップ考(2022/07/23) Learnig Pythonの中で Pypy の速さに触れていますが、自分でも調べてみようと思い、本では触れられていない、Pypy での結果に加え、numpy, Cython, cupy でも計測して.. |
![]() | Chromebook雑感(2022/07/22) 主に自宅WiFi内、外出時にVPNで自宅LANにつなぐサブ機として購入しました。本当は Ubuntu 搭載タブレットがほしかったんですが、満足できる機種が一向に出ず... |