■
[AI] （1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分である
余はこの定理の証明について真に驚くべき発見をしたので喜びのあまり書く、
ていうかKPというよりPでおk
P式の評価関数とはどんなものか
○棋の駒のとり得る状態は、置駒については駒の種類を14（成り不成りを区別）として、
14×81マス×(先後の区別) 2 = 14 * 81 * 2 = 2268種類
持駒については
(∑[x∈{生駒}]{xの最大枚数})×(先後の区別) = (18+4+4+4+4+2+2+0)*2 = 76種類
の計2344種類ありぬ*1、
これがいわゆるBonaPieceと言われるﾌﾞﾂの総数だる、
で、○棋の盤上（と駒台）には常に計40個の駒が存在し、かつ同一のBonaPieceにあたる駒は2個以上は存在しない（1個または0個）
すわなち盤上（と駒台）には40個のBonaPieceが常に存在する、と言い換えても良い*2
これらBonaPiece 1～2344のそれぞれに数値を割り当て、○棋の任意の局面を盤上（と駒台）に存在する40個のBonaPieceに割り当てられた整数の合計値の大小で局面の良し悪しを評価せんとするのがPによる（Pを評価因子とする）局面評価だる
以下、BonaPiece pに割り当てられた整数をpの重み、○棋の局面に対して局面に含まれるBonaPieceの重みの合計する式をP式の評価関数、与えられた局面xについてのP式の評価関数で具体的に計算した値をxの評価値と呼ぶ
さらに、BonaPieceの総数をB（=2344）、1個の局面が含むBonaPieceの数をN（=40）とおく。
後で見るように、学習データのNが定数、というのがジワリと効いてくる
P式の評価関数の表現能力
はっきり胃って入力ベクトルB次元のパーセプトロン1個とほぼ同じ
ていうか重みベクトルを入力ベクトルに1次元足したB+1次元ベクトルと考えればパーセプトロン1個にか、完全に一致……！
（1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分であることの証明
以下パーセプトロンの入力ベクトルと重みベクトルをそれぞれ1行B列と1行B+1列の行列とみなし、要素を分ける「,」抜きで書く。
さらに、「[n]」はn個（0個以上）の列要素のDon't care、「*」を1個の列のDon't careの意味で使う。
補題1: 入力ベクトルの部分集合{ (1 0 [q]), (0 1 [q]) }と{ (0 0 [q]), (1 1 [q]) }は、全ての集合が値1の列を3個以上含み、(0 0 [q])がさらにもう一個値1の別の列を有するなら線形分離できる
パーセプトロンはXORを学習できないと言われるが、これは識別面の表側にある入力ベクトルを1、裏側にある入力ベクトルを0とラベリングするものとして、
入力ベクトルv1=(1 0)に対応する重みベクトル(w1 w2)の和 = w1 入力ベクトルv2=(0 1)に対応する重みベクトル(w1 w2)の和 = w2 入力ベクトルv3=(0 0)に対応する重みベクトル(w1 w2)の和 = 0 入力ベクトルv4=(1 1)に対応する重みベクトル(w1 w2)の和 = w1 + w2
というケースにおいてw1, w2を正負どちらに弄ってもv3以外の重みの和が同符号となり、v1とv2を正、v4を負（または0）にできないことによる。
ところが入力ベクトルv3以外に1次元、v3には2次元追加し、それらの値がいずれも0以外ならば、追加した次元の重みベクトルで重みの総和を正方向または負方向の必要な方向に任意にオフセットでき、線形分離できるようになる。
実際、重みをw1=-2、w2=-2、w3=w4=w5=w6=3、w4=-4として、簡単のため入力ベクトルのDon't care部分の重みを0と仮定したとき、次のように{ v1, v2 }と{ v3, v4 }を線形分離できる：
入力ベクトルv1=( 1 0 [a] 1 [b] )に対応する 重みベクトル(w1 w2 [a] w3 [b] )の和 = w1 + w3 = (-2) + 3 = 1 入力ベクトルv2=( 0 1 [c] 1 [d] )に対応する 重みベクトル(w1 w2 [c] w4 [d] )の和 = w2 + w4 = (-2) + 3 = 1 入力ベクトルv3=( 0 0 [e] 1 [f] 1 [g])に対応する 重みベクトル(w1 w2 [e] w5 [f] w7 [g])の和 = w5 + w7 = 3 + (-4) = -1 入力ベクトルv4=( 1 1 [h] 1 [i] )に対応する 重みベクトル(w1 w2 [h] w6 [i] )の和 = w1 + w2 + w6 = (-2) + (-2) + 3 = -1
ここで、Don't care記号 [a]～[i]は、追加した値1の列がベクトル毎にばらばらでも同じでも良いことを示す*3。
で、この場合w1とw2は符号のみが問題で絶対値はいくら大きくしても良く、w3～w7は任意のオフセットを与えられるから、以下の入力ベクトルのDon't care 部分
■ 証明終わり
（びこう）
上記補題における重みの決め方においてDon't care部分が値0ばかりな入力ベクトル(* * [q])の出力が正負どちらになるかは定まらず、さらに（同じくDon't care部分が0ばかりな）{ (1 0 0 [q]), (0 1 0 [q]) }と{ (0 0 0 [q]), (1 1 0 [q]) }は線形分離不能なままだが、後で見るように今回の応用に限って言えば、これは全く問題を生じない。（[q]の中に必要なだけの個数の値1の存在が保証され、補題1の適用パターンへの回避が常に可能
補題2: 値1の列をN個（ただし4個以上）含み、その他の列が0のベクトルは、重みベクトルを1次元拡張したパーセプトロンで互いに線形分離できる
入力ベクトル(* * [q])について、パーセプトロンの性質の既知の議論によって、以下の線形分離は可能である
{ (1 1 [q]) } と { (1 0 [q]), (0 1 [q]), (0 0 [q]) } は問題無く線形分離でくる（AND論理）
{ (1 1 [q]), (1 0 [q]), (0 1 [q]) } と { (0 0 [q]) } は問題無く線形分離でくる（OR論理）
で、XOR論理についても補題1により線形分離でくる。
なぜなら、入力ベクトルの部分集合 { (1 0 [q]), (0 1 [q]) } と { (0 0 [q]), (1 1 [q]) } の分離を考えたとき、入力ベクトルの明記されている値1の列の個数がそれぞれ1, 1, 0, 2のため、仮定より、[q]部分にはそれぞれ3、3、4、2個の値1の列が存在する。よって、補題1より、それら該当列の重みには、線形分離可能とする値が必ず存在する。
で、あとは上記該当列を除いた列からなる部分空間の線形分離可能性のみの問題となるから、上記論法を再帰的に適用し、部分空間のサイズが4次元以上の間は、該当列の重みに線形分離可能とする値が存在することが言える。
で、3次元まで入力ベクトル空間が縮小されたとき、その部分空間に含まれ得る入力ベクトルは次の8通り：
(1の個数が0) A: ( 0 0 0 ) (1の個数が1) B: ( 0 0 1 ) C: ( 0 1 0 ) D: ( 1 0 0 ) (1の個数が2) E: ( 0 1 1 ) F: ( 1 0 1 ) G: ( 1 1 0 ) (1の個数が3) H: ( 1 1 1 )
もともとの1の個数がN個（定数）の仮定により、この時点で1の個数が相違するもの同士の線形分離の必要は生じない。
1の個数が1個同士または2個同士の線形分離については、もはや(0 0 0)との線形分離が問題になることは無く、かつ、該当するベクトルの個数が高々3であるため、1次元拡張した重みベクトルがもう1列あることからその重みでオフセットすることによりXOR論理であっても線形分離可能。
■ 証明終了
（1次元拡張した）KP式の評価関数×289個の表現能力は○棋の完全解析結果を記憶するのに十分である
上で導入したBonaPieceの個数をB（=2344）、局面に含まれる駒の個数をN（=40）により、局面の総数はB_C_N個。ここでn_C_rは例のコンビネーションの記号とす、
完全解析結果を記憶するには、局面の集合を、先手/後手のうちの必勝側に有利な順に並べればおk。よって、学習モデルが局面の集合（要素数B_C_N）を値域[0, B_C_N)の整数に全単射する任意の写像を表現し得るならば、その学習モデルは完全解析結果を記憶できうる、
で、この値域[0, B_C_N)の整数というのは、2進数で表すと、log(B_C_N) ≒288.15 bit、すわなち289個の0/1の組み合わせで表せる
一方1個のパーセプトロンの出力は1個の0/1であり、パーセプトロンの収束定理があるからB次元の入力の識別を（入力が確定しておりかつ線形分離可能な集合である以上）必ず有限ステップで学習できる
この場合の線形分離可能性が保証されることは補題2で示したある
よって、（1次元拡張した）KP式の評価関数を289個束ねたﾌﾞﾂは、局面の集合（要素数B_C_N）を値域[0～B_C_N)の整数に移す任意の写像を表現できる。
よって（1次元拡張した）KP式の評価関数×289個は、○棋の完全解析結果を記憶できる
■ 証明おわり
検算
ネットにはKPじゃあ次元が足りねえわバカじゃねえのﾌﾟｹﾞﾗｷﾞｬｰｽwwwwwwww
という系の反論（？）が散見されるような木がするので本当かどうか確認汁*4、
局面の集合（要素数B_C_N）を値域[0～B_C_N)の整数に移す全単写写像はB_C_N!通りだる、これはB^Nより小さいい
一方、入力B+1次元のパーセプトロンを289個束ねたﾌﾞﾂで表せる写像の個数だが、この場合は1個のパーセプトロンは局面の集合（要素数B_C_N）のべき集合（要素数2^(B_C_N)）に含まれる1個の元を学習していることになり、それが289個束になているわけなので
(2^(B_C_N))^289 = 2^(289*B_C_N) = (2^12)^(24.083*B_C_N) > B^((24.083*B_C_N) )通り
となり、後者の圧勝
後者がなんで圧勝するのかというと、後者はN個のBonaPieceからなる局面の集合から[0, B_C_N)の整数への全単写写像だけでなく、以下の写像の表現能力を有するから*5。
まとめ
○棋の完全解析の結果を記憶するのに宇宙の原子の個数より多くの記憶セルを必要とするという議論は何だったのか…
ていうかゲームが比較的低次元のパーセプトロンで完全に説明をつけられることがわかった今、もはや○棋はAI技術のテストヘッドとしての役割を終えたのではないか、
コンピュータ○棋は解かれた…！（ﾏﾃ；
■ 追記
2人零和ゲームの評価値は1、0、-1の3値あれば良く、局面の集合を{ 1, 0, -1 }に移す任意の写像を表現できれば完全解析結果を記憶できることになるから、よく考えたら局面の集合のどれが（先手か後手のうちの必勝側の）必勝局面か否かだけを記憶するだけでも必勝手順を記憶し切れる。ということは目標をそれにﾌﾟﾁ修正した場合は（1次元拡張した）P式の評価関数1個の表現能力で十分なのかﾏｼﾞか…
*1:TO、NY、NK、NGをKIとみなすなどのせこい同一化工夫はこの際やめるとして
*2:持駒について、先手（後手）の生駒xがn枚ある状況を先手（後手）のn枚目のxのBonaPieceただ1個で代表する、みたいなせこい同一化工夫はこの際やめるとして
*3:v3に追加した2列のうち片方は、v1、v2、v4への追加列とは必然的に相違する
*4:集中して考えるためにネット絶ちしていたら何とかちゃんねるの例のスレがdat落ちしてしまったorz
*5:要検証
*6:これは証明中で述べた学習が、N個のBonaPieceからなる局面のみをinputとする想定のためこうなる。学習時にinputとして与えていないパターンについては出力が規定されず、任意の出力が有り得る
