実現可能局面数(1)
ゲーム理論の見地からいうと、将棋というのは先手後手のどちらかに必勝法があるか、両者とも最善を尽くせば引き分けになることは分かっています。このときに、必勝法が見つかるかの指標となるのが、状態空間の複雑さです。
将棋パズル＠将棋パイナップルでも話題に上がっており*1、上界は*2、下界は
程度まで評価できているようです。
上界の評価をする時には、実現不可能な局面も含むが、実現可能な局面は必ず含まれるような評価が必要です。一番大雑把には、40枚の駒を何も考えずに81の升目と駒台に並べることになるでしょう。この評価には、二歩、行き所の無い駒、王手放置、打ち歩詰、などが含まれているためこの場合を排除していく事で小さい値におさえていくことができます。
逆に下界の評価では、実現可能な局面しか含まないような評価が求められます。最も雑な評価では、盤面には玉のみ、残りは全て持駒にする方法があるでしょう。この場合、先手後手の手番が2通り、玉位置の組み合わせが5936通り、持駒の配分はそれぞれ各駒の数+1ですから、
程度となります。この評価に、盤面に駒を置いた場合の数を加えていけば大きい値になっていきます。
