2019-11-27

anond:20191127163029

指数部分が2倍という意味ね。

増田研究者の集まりじゃないんだから何か一言ないと分からんわ。

詰み局面からの後退ゲーム木探索として、

計算量Q=詰み局面数A×探索深さd^合法着手数k

を考えた時、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倍のスピードで進化...

記事への反応(ブックマークコメント)

ログイン ユーザー登録
ようこそ ゲスト さん