🌃 詰め将棋の暫定結論

2021/10/20

🌃 詰め将棋の暫定結論  最初、何げなく Perl で詰め将棋を解いてみようと思いつきました。 基本的に現局面で可能な全ての手をリストアップし、それが詰みかどうかをチェックするという1手詰めの手法を再帰化すればと思ったのです。 この段階では、5手詰めが30秒以上かかったと思います。

 それから、将棋AIが機械学習、ディープラーニングの方向へ向かっていると知り、Perl から、それらが使える Python に移植しました。 Python2、Python3、その高速版である Pypy と渡り歩き、結局最速は Pypy2 だとわかりました。 バグも取り、現在7手詰め3秒平均、9手詰め20秒平均で解けるまでになりました。 大体のところ、2手進むごとに5〜10倍時間がかかる傾向があるようです。

【まいにち詰将棋の解答速度を比べる】

問題 Perl5 CPython3 Pypy3 Pypy2新版
9/13 3手詰 0秒 0秒 0.1秒 0.1秒
9/17 5手詰 4秒 1秒 1.2秒 1.1秒
9/21 5手詰 2秒 1.8秒 1.2秒 1.0秒
9/8 7手詰 29秒 18.3秒 4.7秒 3.1秒
9/15 7手詰 400秒〜 18.3秒 4.1秒 3.0秒
9/26 9手詰 - 33.8秒 9.0秒 8.7秒
10/13 9手詰 - 242秒 36.9秒 32.1秒
(9/26,10/13はPython3,Pypy3も新版で計時)

 さらに、スピードアップを考え、いろいろな方法にトライしましたが、全て挫折しました。

 まず、詰みのパターンを分類し、現局面をそれに当てはめて詰み・不詰みを判定するというアルゴリズムに変えようと思いつきました。 しかし、これは、金や銀といったコマの詰めパターンは楽ですが、飛や角といった飛コマのパターンの扱いがやっかいです。 そして、詰め将棋にしばしば登場する開き王手の扱いがそれに輪をかけてやっかいです。 そのため、全ての詰みパターンに対応しようとすると、どうしてもアルゴリズムが複雑化し、現在の単純なアルゴリズムの速度には到底太刀打ちできません。

 詰め将棋の速度を速くすることが、現在のDL系の将棋AIの性能アップにつながる、これは確かやねうら王のサイトで読んだのだったと思います。 これを私なりに考えると、現局面をまず詰め将棋エンジンにかけ、詰んでいなければDLで得た局面評価にかける、その結果導かれた最善手を指すのでしょう。 もし、詰め将棋エンジンの段階で詰みが見つかれば、それは DL より何より最優先されなければならないわけですから。

 詰め将棋には完璧が、DL には過去局面分析のレベルが求められるというわけでしょう。

 さて、話題を高速化へもどします。 Python スピードアップの決め手といわれる numpy を取り入れてみましたが、どうやっても時間が数倍かかってしまいました。 これは、numpy が大量のリストの一斉演算に向いているのに対し、将棋ではせいぜい 9x9 の行列の、1コマを動かしたとき、その周辺に及ぶ影響が問題になるだけで、セル1個への入力、しかもその影響をチェックする条件が正だとか負だとかいった簡単なものでなく、複雑怪奇で、影響が影響を生むという種類のものだからです。

 ついで、Cython にトライしました。 確かに Python3 に比べれば劇的に高速化されますが、残念ながら、Pypy にはわずかに及びません。 Python のソースに結構手を入れた結果がこれなので、それ以上やる気が起きません。 それなら、Python のソースを C 言語に全て書き直したほうがマシのような気がしてきます。 ただ、今さら、20年数年ぶりに C をさわってまで高速化を図るのも何だかという気がします。

 numba を試そうとしましたが、現在の Ubuntu を大幅に組み直す必要があることがわかり(つまり使用しているライブラリ等を前バージョンに戻すなど)、ちょっとやる気がしなくなりました。

 最後にディープラーニングで使われる nVidia 配布の CUDA を入れ、CuPy に挑戦しました。 確かに CPU と比べ、私の GPU でも、計算速度は 200 倍くらいアップしていました。 が、これは numpy による計算機能代替手法なので、JS将棋の使う分野ではありません。 それ以外は通常の Python の機能を使うことになると知り、がっかりです。

 ここまでの探索の果てに、結局、私のやり方では、これ以上のスピードアップは不可能との結論に至りました。 あとは、全てを C 言語化すれば数倍速くなるかもしれない、マシン性能をアップすれば数倍以上速くなるだろう、というだけです。 両方やれば13手詰めくらいまでは楽にいくでしょう。 しかし、お金と時間がたっぷり必要です。

 もう一つ別の方向性があります。 それは、特定の読み筋に従って詰みを読んで、だめならあきらめる、解けなくてもいい、その代り解けたら爆速、というやり方です。 例えば、持ち駒に金があるなら、王を一筋に追い詰め最後に金をかぶせようとか、横に効く飛を使うと良さそうだ、その方向で打ってみるかといった感じです。 いくつかそうした作戦をもっていて、それを順次試し、ダメなら終りです。 まあ、趣味のレベルともいえます。 でも、ちょっと面白そうですね。 いくつかの技を持っていて、局面をざっとにらんでそのうちのいくつかを繰り出す。 ひょっとして、局面の認識のところで DL が使えるかもしれず、そうするとここ1ヶ月半の努力も役に立つかもしれません。 でも、当面休息が必要です。 そして、放っておいたファンタジーの方へも戻らねば……。

 Web上のJS将棋もレンタルサーバ上でPython3までは動いているので、3秒以内の制限でも5手詰めまでは全て解けるようになったはずです(Pypyが動き7手詰めまでできるとよかったんですが)。

 とはいえ、pypy も万能でないというのは、Python3は0.4秒足らずで終わる以下のコードも pypy3 では2.8秒かかってしまうことからもわかります。 物事にはやはり向き不向きがあるようです。

from random import random
from time import time
import numpy as np
a = np.random.rand(1000000)
start = time()
ans = 0
for i in a: ans += pow(i, 2)
print('time', time() - start, 'sec')

参考: JS将棋

twitterシェア Facebookシェア
  コメントの注意点