ぼくの考えたKKPとKPPの実装(2)
テーブルの空間計算量
テーブルの空間計算量の削減には次の2段階があると思う
- テーブルサイズの削減
- テーブル要素a,bのアドレスをテーブル要素aのアドレスで代表することによってテーブル要素b自体を無くする
- 実質データ量の削減
- テーブル要素a,bの値をテーブル要素aの値で代表することによってテーブルを記述するのに要するデータ量を減らする
テーブルサイズの削減はテーブル表現が単一の矩形でなくなって比較的めんどくさいし本番処理が遅くなるのが避けられないので極力避けたいので、さしあたり実質データ量の削減のみを考ゆる
ま、どっちにせよ複数のテーブル要素のアドレスを1つのテーブル要素のアドレスで代表するという操作が基本となるわけだが
いま、添え字集合P,Q,Rがあるとして、写像f:P×Q×R→Eのテーブル化を考えたとき、テーブルサイズ（要素数）は|P|*|Q|*|R|が十分。
ここで都合よく写像g:P×Q×R→P×Q×Rが存在して、任意のa∈P×Q×Rについてf(a)=f(g(a))が成立する（すわなち、アドレス変換gに関してfが対称）なら、実質データ量を(|P|*|Q|*|R| - |Z_g|)/2 + |Z_g|（約半分）にできる
ここでZ_gはgの不動点の集合
これは別にfがgに関して反対称でもいいし、ぶっちゃけ、何も指定せずとも一意に決まる関係か、もしくは最悪でもa∈P×Q×Rを指定したとき一意に決まる関係がf(a)とf(g(a))の間に成立すれば言える（実質データ量を約半分にできる）わけだが、対称と反対称以外は利用しようにも時間計算量的に多分厳しい
まあそれはともかく対称なケースのみ述べればそれ以外のケースも同様の性質の成立が自明なので、以下対称なケースのみ述べる
fが合成写像に分解できる場合は実質データ量を半減よりさらに減らせるケースがある。すわなち
- f:P×Q×R→E
を、適当な中間結果の集合E_1、E_2を導入して
- f_1:Q→E_1
- f_2:R→E_2
- f_3:P×E_1×E_2→E
という3写像に分解（＝f_1とf_2が独立）、もしくは
- f_1:Q→E_1
- f_2:E_1×R→E_2
- f_3:E_2×P→E
（＝f_2がf_1に依存）等としておkな場合でなおかつf_1とf_2の両方に対称性が有する場合とか。こういった場合、約1/4にできり
KKPは盤の駒位置の水平反転（筋5に対する鏡像変換）に関して対象ので実質データ量をテーブルサイズに対して約半減できる
また、KPPは盤の駒位置の水平反転とP要素の交換に対して対称ので実質データ量をテーブルサイズの約1/4にできる
それ以外の対称性（or 反対称性）も探せばあるっていやーあるが、プレイヤーA,Bの手番を超えた対称性（or 反対称性）になるのでコンピュータ将棋には役に立たない*1 *2
最終的な実質データ量
最終的な実質データ量はいくらになるのか計算汁、
KKP:
テーブルサイズ=82*82*82*10
水平反転の不動点の個数=10*10*10*10=10000
∴実質データ量=2751840要素
KPP
テーブルサイズ=82*82*20*82*20
これを
- f_1:{PPos}×{PSpec}→E_1 （テーブルサイズ = 82*20要素）
- f_2:E_1×E_1→E_2 （テーブルサイズ = |E_1|^2要素）
- f_3:{OUPosB}×E_2→E
という合成写像とみなすと、f_1は水平反転に対して対称、f_2はP-P交換に対して対称。
よってf_1は、実質データ量を(82*20 - 10*20)/2 + 10*20 = 920要素にできり
で、f_2はf_1の実質データ量のみについて計算すれば事足りるから、f_2自身の対称性を利用しなければ実質データ量 = 920^2要素、対称性を利用して(920 ^2 - 920*20)/2 + 920*20=432400要素になれり
よって最終的な実質データ量は82*432400=35456800要素。多分、*3
テーブル構成の検討
KPP全体をフラットな矩形テーブルとして実現した場合テーブルサイズが82*82*20*82*20=2.2億要素=210 M要素にもなってしまいメモリを無駄に圧迫しすぐるのでさすがに方針転換汁、
fを上記f_1、f_2、f_3に3分割してそれぞれを矩形テーブルとした場合、1640 + 920^2 + 82*432400 = 36304840ってことでテーブルサイズを何とか3600万台の要素数に抑えられるる
といいなあ、、
