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とか、