増田は研究者の集まりじゃないんだから何か一言ないと分からんわ。
を考えた時、A、dは将棋のほうが大きいだろうから、kが2倍以上あれば計算量は2乗以上。
さっきも書いたけど、計算量の比較に重要なのは局面数ではなくて各局面の合法着手数じゃないかな。
さて、通常のゲームでの合法着手数は将棋が平均80手、チェスが平均30手らしい。
(legal moves avelageで検索)
完全解析では非通常的な局面も考慮に入れるけど、持ち駒ルールのために①実現可能な局面数が多くて、②打つ場所の自由度が高く、駒が減らないことによって各局面の合法着手数が多いことを考えると計算量の差はもっとあると思う。
ちなみに最大合法着手数は将棋が593手、チェスが218らしい。
調べてみるとなかなか面白いね。
持ち駒が化けようがターンにおける手のパターンは有限なんだから解けないことはねえよ。 計算上精々チェスの倍くらいのオーダーにしかならんはずやろ。
可能な局面数の上界をざっと計算してみる。 すべての駒が異なるとして、盤面+駒台に配置する場合の数を計算すると、 将棋 (81+2)^40 * 2^38 * 2^34 ≒ 10^98 ※二項目は駒の向き、三項目は成...
お、倍も差は無かったな。精々1.5倍くらいのオーダーか。
詳しくないので教えて欲しいんだけど、解析の計算量って総局面数の対数オーダーになるの? 単純に考えると、詰み局面からゲーム木を後退させていくんだろうけど、その場合の計算量...
千日手ルールがあるから持ち駒使えても総手番的に無限になることはないんじゃないのか。 手駒も均衡してるならともかく、均衡が崩れてるなら計算量は減る一方になるはずだし。 指数...
指数部分が2倍という意味ね。 増田は研究者の集まりじゃないんだから何か一言ないと分からんわ。 詰み局面からの後退ゲーム木探索として、 計算量Q=詰み局面数A×探索深さd^合法着手...
10^2と10^4を2倍の差だと思ってそう
逆に聞くけどパターン数みたいなかなりデカ目の数値を扱う場合に「2倍」で実数倍そのものを指すことがどれくらいあると思ってるんだ? こんぴゅーたーは3年で4倍のスピードで進化...