キャーこの人置換表です

ハッシュ関数のバリデーション

いま何か適当な分布（一様とは限らない）に従い生起する事象sがあったとして、ハッシュ関数fでもってハッシュキーhをh=f(s)として作ったとする
このとき（sの分布は一様とは限らないにもかかわらず）hの剰余h % Nは有限の区間[0, N)の範囲内で一様に分布して欲しい
かような虫の良い思惑が外れなかったことを調べ鯛、
のだが
ネットに情報が無いのでここに書く、

その(1): 置換表が埋まる速度をバリデート

いまエントリ[0..N-1]からなる置換表がu_i個のエントリまで埋まっているとする、
エントリの確保はh=f(s)の剰余h % Nが指すエントリを割り当てるものとすると、直近に確保するエントリ[h % N]が既存エントリの上書きにならない確率は、
　1 - u_i/N
であり、この確率で、確保後のu_iが+1される、すわなち
　u_(i+1) = u_i + (1 - u_i/N) * 1 + (u_i/N) * 0 = 1 + *1

その(2): 置換エントリ毎の衝突回数をバリデート

いわずと知れた話で、エントリの確保1回につき、既存エントリが上書きされる確率は1/N。これを確認する、
すわなち、順当に行けば全エントリの上書き回数は1/Nづつ増加する。実際には当たるときと外れるときがあり、hの一様性から時間平均は長時間見たらどっちも同じ頻度で生起するから、c_i = (1/N)*iを中心とするランダムウォーク的な振る舞いとなる
c_iから外れるエントリがあったらNG

理想的なハッシュ関数とは、

置換表サイズNを素数として、ハッシュ関数hは最小完全ハッシュとして、h(s)の結果をNで剰余すれば良い
上のテストにはよゆーでパスする*2

*1:N-1)/N) * u_i という漸化式を得るが、これは 　u_1 = 1 　u_i = (1 - α^i) / (1 - α) に他ならぬ ここでα=((N-1)/N)である。Excelで1兆項ぐらい計算するとﾜｶﾙが、u_iはNに収束する。 これのiの増加に対する曲線と、実際の置換表の埋まる曲線を比較すればおk 下回り続けるようなら一様性に問題がある((上回り続けても一様でないと言えるが、他の基準に抵触しなければひとまずおk（多分有り得ないが

*2:筆者の想像だが

All about 配列表現

例の聖なる書物には配列表現で実現することしか書いていないので、配列以外の表現は禁忌に抵触する
故に配列表現の高速化を試みた

特に飛び駒の利きとOUのPINについては、ﾌﾂｰに作ると駒のmake moveの度に、駒の除去に際して一旦消して、駒を置いた直後に書き直されるというマスが複数発生する

これを徹底的に無くすには…

やり方はあって本気で作りこんだがあんま速くならんかった、orz*1
よって説明略

*1:多分条件分岐が増えたため

All about 2駒間の相対関係のインデックス化

例えば将棋とかは9×9マスなので、ﾌﾂｰに作ると9×9ぐらいの2次元配列になるが、盤面を配列方式で表す技法を記した例の聖なる書物には2次元配列では遅いから1次元配列にしなさいと書いてあった
例えば、筋s、段dの駒をboard[(s << 4) + d]に入れる約束にすれば、シフト1回と加算1回で、筋s、段dに対応する格納先の絶対位置が求まる
この(s << 4) + d形式のindexの差分で2駒間の相対関係を表せるとﾌﾂｰ思うじゃん？
ところがやってみると例えば
　2一に対応するindex = (2 << 4) + 1 = 33
　1九に対応するindex = (1 << 4) + 9 = 25
　1一に対応するindex = (1 << 4) + 1 = 17
であり、
　33 - 25 = 25 - 17 = 8
となるため、全く幾何学的意味合いが異なる相対位置関係2一 〜 1九と、相対位置関係1九〜1一が同じに見えてしまい計画は破綻する

かような事態を避けるには、シフト量は4ではダメで、4より大きい値にすることが必要十分だる、*1

■ 証明

 *	kをサンプル(sta, dst)の識別のための添え字として、通常のオフセットは次式で表される。
 *		ofs(k) = p_dst(k) - p_sta(k)
 *			= (W * s_dst(k)) + d_dst(k) - (W * s_sta(k) + d_sta(k))
 *			= W * (s_dst(k) - s_sta(k)) + (d_dst(k) - d_sta(k))		-- (1)
 *	ここで、WはIv2DanMaxであり、かつ
 *		1≦s_dst(k)≦SujiMax,
 *		1≦s_sta(k)≦SujiMax,
 *		1≦d_dst(k)≦DanMax,
 *		1≦d_sta(k)≦DanMax		-- (2)
 *	いま、
 *		a = s_sta(i), b = d_sta(i), c = s_dst(i), d = d_dst(i),
 *		e = s_sta(j), f = d_sta(j), g = s_dst(j), h = d_dst(j)
 *	と置いた上で2つのオフセットofs(i), ofs(j)が等しくなる条件を考えると、
 *		ofs(i) - ofs(j)
 *			=	  (W * (s_dst(i) - s_sta(i)) + (d_dst(i) - d_sta(i)))
 *				- (W * (s_dst(j) - s_sta(j)) + (d_dst(j) - d_sta(j)))
 *			=	  (W * (c - a) + (d - b))
 *				- (W * (g - e) + (h - f))
 *			= - W * (a - e) - (b - f) + W * (c - g) + (d - h)
 *			= - W * { (a - e) - (c - g) } - { (b - f) - (d - h) }
 *			= 0
 *		∴ - W * { (a - e) - (c - g) } = { (b - f) - (d - h) }		-- (3)
 *	一方、(2)より
 *		-(DanMax-1) ≦(b - f)≦(DanMax-1),
 *		-(DanMax-1) ≦(d - h)≦(DanMax-1)			-- (2')
 *	よって、(3)の右辺は下記範囲の値しかとらない。
 *		- 2 * (DanMax-1) ≦ { (b - f) - (d - h) } ≦ 2 * (DanMax-1)		--(4)
 *	一方、(3)の左辺はステップ幅Wで動き得るから、
 *		α := (a - e) - (c - g)						-- (5)
 *	とおくと、
 *		((3)の左辺) ≦ -W		(α≧ 1)
 *		((3)の左辺) ＝  0		(α=  0)
 *		((3)の左辺) ≧  W		(α≦-1)			-- (6)
 *	が成立するため、
 *		W ＞ 2*(DanMax-1)							-- (7)
 *	ならばα=0のみで(4)が成立、
 *		DanMax ＜ W ≦ 2*(DanMax-1)					-- (8)
 *	ならばα=0のとき(4)が成立する他、α=±1でも(4)が成立し得る。

（ここまでいまいち地上界の言葉になっていないのはご容赦されたい、）
故に式(8)は成立してはならず、W＞2*(DanMax-1)=16である必要がある、
よってシフト量はlog(16)/log(2) = 4より大きい値にしないとNG、
一方4より大きい値にしたらば、式(6)によって安寧がもたらされる

*1: 実用的には整数のシフト量ということで(s << 5) + dとか、

All about 三角化

いま二次元配列x[i][j]が任意のi, jについてx[i][j] = x[j][i]を満たすとする*1
ﾌﾂｰに作ると(iの上限+1)×(jの上限+1)語ぐらいの記憶域が要るが、常に
　高次側のindex ＜ 低次側のindex
とする約束とせば、
　k = S(i, j) = (i * (i - 1)) / 2 + j
というindex kを設けることで、記憶域を1語も無駄にせずに約半分のサイズに1次元化できる

■ 1語も無駄にならないことの証明
S(i, j) := (i * (i - 1)) / 2 + jとおくと、j = S(i, j) - (i * (i - 1)) / 2。
一方、仮定より0 ≦ j ＜ i。よって、
0 ≦ S(i, j) - (i * (i - 1)) / 2 ＜ i
∴(i * (i - 1)) / 2 ≦ S(i, j) ＜ i + (i * (i - 1)) / 2
∴S(i, 0) ≦ S(i, j) ＜ S(i+1, 0)

もし
　高次側のindex ≦ 低次側のindex
とする約束（＝が有り得る）ならば、
　k = S(i, j) = (i * (i + 1)) / 2 + j
でおk

証明は上と同様、

*1:Indexは0始まりの整数とする

エイプリルフール

ひょっとしたら今年はキャンセルせずに済むかもしれない…
かもしれない運転、

All about テーブル化

スパースなデータのテーブル化

いまS, Tを適当な（離散的な）順序集合として、写像d:S→Tをテーブルで実現するというのはよくある話で、y=d(x)のx∈Sを添え字とする配列aに、y∈Dを代入しとけばおk
しかしこれ一本槍ではSがスパースな集合だったりするとﾋｼﾞｮｰに苦しいことになる
すわなち、aのサイズはmax{ S } - min{ S } + 1が必要だがそのうちの0.1 %ぐらいの値しか実際には取り得ない値とかだったりするとメモリのﾁｮｰ無駄づかいだる、
こういうときは、適当な全単射写像f:S→Dを用意して、ただしDは稠密となるようにして、
　d = (d・f^(-1))・f　・・・(1)
と分解し（ここでf^(-1)はfの逆写像）、g := d・f^(-1)に対しy=g(z)をテーブル化しておいて、dの計算にあたってはz=f(x)を都度毎回計算してzでy=g(z)のテーブルを引くようにする、
ここで注目すべきは、テーブル構成時に∀x∈Sでループを回す限り、合成写像d・f^(-1)のテーブル化は、
　y=d(x)
　z=f(x)
の2つを計算し、テーブル実体となる配列b[]の添え字をz、値をyとすることで、f^(-1)を陽には計算しなくて全く良い、*1

入力段におけるちょっとした追加の演算もついでにテーブル化

(1)によりめでたく最高の記憶密度とそこそこの処理速度で写像dを計算できるようになったところで、全く同じコードでもって*2、合成写像
　d・r
を計算したくなったと汁、
ただしrはr:S→Sな全単射写像で、定義域と値域がどっちもSというのがポイント、
これをテーブルの差し替えだけで実現するには…
こう考える、
　d・r = ( (d・r)・f^(-1) )・f ・・・(2)
(1)と(2)を比較してわかるのは、今度は( (d・r)・f^(-1) )をテーブル化すれば良いのだということ
より具体的には、
　foreach (x in S) {
　　x' = r(x)
　　y = d(x')
　　z = f(x)
　　b[z] = y
　}
でおk
これで(1)を計算するのと全く同じコードで*3、(2)によりめでたく最高の記憶密度とそこそこの処理速度で写像d・rを計算できるようになた、*4
このようにしてfの計算前に適用するr:S→S的かつ全単射な写像であれば、いくつあってもテーブル構成時に事前計算しとける
、

*1:BonaPieceの作り方とかはまさにこれ

*2:つまり後付けのif文とか無しに

*3:つまり後付けのif文とか無しに

*4:BonaPieceの手番反転とかまさにこれ

探索のシュマ

これはもう単純な話で、深く読めば読むほどよろしい
ていうか終局まで読み切る以外に真実の解を知る術が無いという問題だというのに、探索しない選択肢などあろうもののかは、
NPSも高ければ高いほど良い、まあオーダリングの精度である程度代替が利くが*1、
評価関数のに仮にバイアスがあったとしても、深く探索するにつれ並大抵のことではたいした問題にならなくなる
完全ゲーム木の全ノードの集合Nに対し、評価値にバイアスがあったとする。ただしDC成分には意味が無いから差っ引いたら、評価値が負のノードと、評価値が正のノードに分かれて評価値の総和が0になるわけだが、そうした状況での探索結果はほっとけば評価値の正と負の境界を好んで選ぶふるまいになるだけで、探索木が広くなるにつれ、必勝ノードを狙い撃ったり必敗ノードを避け続けられるわけにはいかなくなるのだ、
で、結局不可知の必勝ノードや必負ノードとは無関係に、相手の探索の深さを上回った分の有利さ（もしくは下回っただけの不利さ）だけを手にする状態に近づく

*1:オーダリングによる計算量縮小の余地の存在はNP困難性となんら矛盾しない。終局まで読み切ったのと同じ知識無く行う途中で打ち切る探索では、どうあがいても探索結果の真実性において、終局まで読み切る探索に追いつくことは無いのだ