ORる世界 [完全版]
BonaPieceによる局面表現の集合の線形分離（重みベクトルの決定）を、デジタル回路において真理値表からデコーダを作るみたいなお手軽さでやる方法を思いついたのでここに書く、
任意の座標値を採り得る一般的なベクトルの線形分離となるとアレを使うのが常識なのですだが（アレを使うと線形分離できる場合もできない場合もそれなりに速い有限ステップで結果が出る）、後に述べるようにのBonaPieceによる将棋の盤面表現とかの2344次元（＋拡張次元）もあるベクトルの線形分離ともなると、平均的に速い方法とは言えそれなりに時間がかかることと、しくみ的に直接得られる解（および途中経過における変数値）が整数にならないことが多いのでｶﾅｰﾘ使い勝手が悪い
一方BonaPieceによる局面表現のは、2344次元（＋拡張次元）とはいえ別段任意の座標値を取ったりすることはなく、要素は0か1とゆー0-1ベクトル表現なわけで、これは見るからに単純なベクトルなのでアレを使わずに整数演算で済む単純な方法があるのではなかろうか、と思って考えたらあった、
BonaPieceとは
駒の種類×状態（味方/敵のどちらか、盤のどこにあるか、または駒台の同じ生駒の何piece目か）を整数で表したもの
例えば将棋であれば、
FU×1一、FU×1二、...、FU×9九、 vFU×1一、vFU×1二、...、vFU×9九、 KY×1一、...、 vOU×9九、 FU×駒台1枚目、FU×駒台2枚目、...、FU×駒台18枚目、...、 vFU×駒台1枚目、vFU×駒台2枚目、...、vFU×駒台18枚目、...、 HI×駒台1枚目、HI×駒台2枚目、 vHI×駒台1枚目、vHI×駒台2枚目
という具合に2344個ある。これに先頭から1～2344の整数を割り振っておく。
BonaPieceによる盤面の表現
BonaPieceを盤上の駒（将棋で駒落ち無しの場合40個）全てについて集めたら（ただし同じ位置に別の駒がある等の矛盾した選び方はしないものとして）これを盤上の駒全てについて集めたら盤面が1個定まる。（1対1対応が成立する。）
さらに、有限集合を表現する常套手段として0-1ベクトルによる表現があり、この場合2344次元（＋拡張次元）のベクトル空間を用意して、各軸が個々のBonaPieceに対応し、
軸iが1ならBonaPiece iを含む、0なら含まない
と約束することで盤面を定めるBonaPieceの集まり（1つの盤面に含まれるBonaPieceの集合）を0-1ベクトルにより表すこともできる。（これももちろん盤面と1対1対応が成立する。）
以下0-1ベクトル表現された盤面を分割しようという話なのですだが、いちいち2344次元（＋拡張次元）ものベクトルを書くのは嫌なので、BonaPieceの種類（駒の状態）が5で駒の総数が3という仮想的なチャトランガ系統のゲームの局面表現で説明す、
例：BonaPiece総数が1～5のゲームで、BonaPiece 2、3、4からなる（そのように3個の駒が配置された）盤面を表すベクトルv1：
v1 = (0 1 1 1 0)
積項の実現
まず手始めに、盤面を表すベクトルv=(a b c d e) （BonaPieceが1～5なので5次元）と重みベクトルwの内積が、v=v1のときのみ正、それ以外は負になるようにwを定めることを考える。
論理回路で言うところの、入力が「0 1 1 1 0」のときのみ「1」となるAND回路と同じようなものを線形分離でやる。
天下りだが、AND論理のためにはv、wともに拡張次元1次元が必要なのであらかじめ追加する*1：
v1' = ( 0 1 1 1 0 1) ※ サンプルのベクトルの拡張次元の値は常に1 w’ = (w1 w2 w3 w4 w5 w6) ※ w6は拡張次元の重み
すなわち、ベクトルv'=(a b c d e 1)のうちの正確にb、c、dが全て1のときのみ*2 w'・v'＞0、b、c、dのどれか1つでも0ならw'・v'＜0になることが条件である。
と考えると次の条件と同値であることがﾜｶﾙ
w2、w3、w3が全て正かつ (w2、w3、w4の上位2個の和) < -w6 < (w2、w3、w4の総和) ---(1)
答えの一例は、
w' = (0 2 2 2 0 7)
であっる。w2、w3、w4を同じ値にする必要は無く、またw6には可能な値に式(1)に示す幅があり、そもそもw'をスカラー倍しても線形分離結果は変わらないので無数にある解のうちのあくまで一つであるが、正しいことは検算したらﾜｶﾙ
積項の和の実現（タイトル回収）
v1' = ( 0 1 1 1 0 1 )に対して式(1)が出てきたのと同様に、
v2' = ( 1 0 0 1 1 1 )や
v3' = ( 1 1 0 0 1 1)といったベクトルにも、それぞれを正確に識別する重みの条件として、変数の添え字が相違するだけの式(1)と同様の式を考えることができる。
すなわち、以下の具合となる：
v1'について： (w2、w3、w4の上位2個の和) < -w6 < (w2、w3、w4の総和) ---(1) [再掲] v2'について： (w1、w4、w5の上位2個の和) < -w6 < (w1、w4、w5の総和) ---(2) v3'について： (w1、w2、w5の上位2個の和) < -w6 < (w1、w2、w5の総和) ---(3)
ベクトルv' がv1'～v3'のどれかであるときのみw'・v'＞0、それ以外のとき（v1'～v3'のどれでもないとき）はw'・v'＜0となるように重みベクトルw'を構成したら、v1'、v2'、v3'とそれ以外を識別する積和論理の完成である。
これが実現されるには以下が条件である：
max{ 式(1)～(3)の最左辺 } < -w6 < min{ 式(1)～(3)の最右辺 } --- (4)
つまり、式(4)が非成立である限り、非成立ならしめているサンプル（一般に同着複数）の重みの値を、式(4)の成立する方向に増やせば良い。
式(4)が満足されない状態から、どの重みを増やしても
min{ 式(1)～(3)の最右辺 } - max{ 式(1)～(3)の最左辺 } --- (5)
が増加しないならば、v1'、v2'、v3'のみとそれ以外を正確に識別する線形分離は不可能という結論になる*3。
Don't care値の有効活用
実は上記アルゴリズムに馬鹿正直に従うと、サンプルが増えてくると即線形分離不能に行き当たる。
これはv1'、v2'、v3'のみとそれ以外を正確に識別するというのが線形分離というしくみに対して厳しすぎるからそうなる。
この問題はラベル付けされないサンプルの識別（Don't care値に相当する）を線形分離しやすいように（好きに）想定することで緩和できる。
BonaPieceによる盤面表現は、BonaPieceの総数をN、同時に存在する駒の数をRとして、（同じ位置に別の駒がある等の矛盾した選び方も数えれば）C(N, R)個ある。ここでC(n, r)は例のコンビネーションの記号。
一般にこのC(N, R)個の全ての要素が+ or -にラベル付けされることは少なく、どちらともラベル付けされないサンプルが常に大量に存在する。
このことから、上記線形分離アルゴリズムを次のように変形して適用する：
max{ (ラベル付け「-」サンプルにおける式(1)～(3)の最右辺に相当する値) } ＜ -w6 ＜ min{ (ラベル付け「+」サンプルにおける式(1)～(3)の最右辺に相当する値) }
式(1)～(3)の最左辺の計算は不要になってしまたorz
最初からこうすれば良かったんや……|||。n_
まとめ
この技術の完成をもって、盤面の学習をプログラムに論理式の操作として取り扱わせしめる道が開かれにけり、
ニューラルネットワークがリバイバルしたものなら、
記号処理AIもリバイバルすべきものと信じる……！
*1:蛇足だが幾何学的にはサンプルが存在する5次元空間(a b c d e 0)に対してそれを見下ろす神の視座(0 0 0 0 0 1)を設け、神の視座を通る5次元の超平面とサンプルが存在する5次元空間(a b c d e 0)の交線（4次元の超平面）でサンプル(a b c d e 0)を分離する意味になる、
*2:拡張次元は常に正確に1なのでいちいち記さない。
*3:線形なのでローカルミニマムは無い。重みw_iを減らすことで式(5)が正になったとすると、減らした重みはmax{ 式(1)～(3)の最左辺 }のargであるベクトルの重みである。（w_iが式(5)を0以下にならしめているベクトルとは無関係の重みであれば、その場合はもともと式(5)が正である。）max{ 式(1)～(3)の最左辺 }のarg と min{ 式(1)～(3)の最右辺 } のarg は、BonaPieceベクトル表現の定義より1要素以上の相違が必ずあるため、両argが共有しない重みが存在し、w_iを減らす代わりにmin{ 式(1)～(3)の最右辺 } のarg のみが有する重みを増やしても式(5)を正にできる。
