ORる世界
前回のエントリまでで述べたことは、
BonaPieceによる局面表現の集合に線形分離可能な分割の仕方が必ずある
*1、というだけであって、
BonaPieceによる局面表現の集合を任意の分割の仕方で線形分離できる
、ではなかったorz
実際、反例が存在する。こんなやつ:
↓局面 ↓ラベル [ 0] ( 0 1 0 1 ) : -1 [ 1] ( 0 1 1 0 ) : +1 [ 2] ( 1 0 0 1 ) : +1 [ 3] ( 1 0 1 0 ) : -1
これはBonaPieceの種類(駒の状態)が4で駒の総数が2という仮想的なチャトランガ系統のゲームの局面表現を線形分離しようとした例なのですだが、これを線形分離する単一の重みベクトルは存在しない。
よく見るとXORパターンなのがワカル。XOR、またお前か、、
少なくともラベル-1の要素とラベル+1の要素について共通に1であるBonaPieceばかりだと単一の重みベクトルで線形分離できない。
前回のエントリの議論では
f:{ BonaPieceによる局面 } → { 1, 2, ..., 2^2344 } (⊂N)
という写像は2344個の線形分離結果のORで実現できうる*2、という想定だったが{ BonaPieceによる局面 }に線形分離不可能なケースがあるということは積和論理の積項を1個の重みベクトルで実現でできない(ことがある)という話であって先行きに暗雲が立ち込めてきたorz
こうならない(線形分離できる)条件は一言では述べられないが、実験する限りはちょっとラベルをいじればたいてい線形分離できるっぽい*3:
[ 0] ( 1 1 0 0 0 0 ) : -1 [ 1] ( 0 0 1 0 0 1 ) : -1 [ 2] ( 0 0 0 0 1 1 ) : -1 [ 3] ( 0 1 1 0 0 0 ) : -1 [ 4] ( 1 0 0 0 1 0 ) : +1 [ 5] ( 0 0 0 1 0 1 ) : +1 [ 6] ( 0 1 0 0 0 1 ) : +1 Retrying... (1) | v [ 0] ( 1 1 0 0 0 0 ) : -1 [ 1] ( 0 0 1 0 0 1 ) : -1 [ 2] ( 0 0 0 0 1 1 ) : -1 [ 3] ( 0 1 1 0 0 0 ) : -1 [ 4] ( 1 0 0 0 1 0 ) : -1 [ 5] ( 0 0 0 1 0 1 ) : +1 [ 6] ( 0 1 0 0 0 1 ) : +1 [0] result=1 [ 0] ( 0 0 0 0 1 1 ) : -1 [ 1] ( 0 0 1 0 0 1 ) : -1 [ 2] ( 1 0 0 1 0 0 ) : -1 [ 3] ( 0 1 0 0 0 1 ) : -1 [ 4] ( 0 0 1 1 0 0 ) : +1 [ 5] ( 0 1 1 0 0 0 ) : +1 [ 6] ( 1 0 1 0 0 0 ) : +1 [1] result=1 [ 0] ( 0 0 0 0 1 1 ) : -1 [ 1] ( 0 0 1 1 0 0 ) : -1 [ 2] ( 0 0 1 0 0 1 ) : -1 [ 3] ( 0 0 0 1 0 1 ) : -1 [ 4] ( 0 0 0 1 1 0 ) : +1 [ 5] ( 1 0 0 0 1 0 ) : +1 [ 6] ( 1 0 1 0 0 0 ) : +1 [2] result=1 [ 0] ( 0 0 0 0 1 1 ) : -1 [ 1] ( 0 0 1 0 0 1 ) : -1 [ 2] ( 0 0 1 1 0 0 ) : -1 [ 3] ( 0 1 1 0 0 0 ) : -1 [ 4] ( 0 1 0 0 1 0 ) : +1 [ 5] ( 1 0 0 0 1 0 ) : +1 [ 6] ( 0 0 0 1 0 1 ) : +1 [3] result=1 [ 0] ( 1 0 0 0 1 0 ) : -1 [ 1] ( 0 0 0 1 0 1 ) : -1 [ 2] ( 0 0 1 1 0 0 ) : -1 [ 3] ( 0 1 0 0 0 1 ) : -1 [ 4] ( 1 1 0 0 0 0 ) : +1 [ 5] ( 0 0 1 0 1 0 ) : +1 [ 6] ( 1 0 0 0 0 1 ) : +1 [4] result=1 [ 0] ( 1 1 0 0 0 0 ) : -1 [ 1] ( 1 0 0 0 1 0 ) : -1 [ 2] ( 1 0 0 1 0 0 ) : -1 [ 3] ( 0 1 0 0 1 0 ) : -1 [ 4] ( 0 1 1 0 0 0 ) : +1 [ 5] ( 0 1 0 1 0 0 ) : +1 [ 6] ( 0 0 1 0 0 1 ) : +1 [5] result=1 [ 0] ( 0 1 0 0 0 1 ) : -1 [ 1] ( 1 0 0 0 1 0 ) : -1 [ 2] ( 1 1 0 0 0 0 ) : -1 [ 3] ( 0 0 1 1 0 0 ) : -1 [ 4] ( 0 1 0 0 1 0 ) : +1 [ 5] ( 0 0 0 1 0 1 ) : +1 [ 6] ( 1 0 0 1 0 0 ) : +1 [6] result=1 [ 0] ( 0 0 1 1 0 0 ) : -1 [ 1] ( 1 0 0 0 1 0 ) : -1 [ 2] ( 0 0 0 1 0 1 ) : -1 [ 3] ( 1 0 1 0 0 0 ) : -1 [ 4] ( 1 1 0 0 0 0 ) : +1 [ 5] ( 0 0 1 0 0 1 ) : +1 [ 6] ( 0 1 1 0 0 0 ) : +1 [7] result=1 [ 0] ( 0 0 0 1 0 1 ) : -1 [ 1] ( 1 0 1 0 0 0 ) : -1 [ 2] ( 0 0 0 0 1 1 ) : -1 [ 3] ( 1 0 0 1 0 0 ) : -1 [ 4] ( 1 0 0 0 0 1 ) : +1 [ 5] ( 0 0 1 1 0 0 ) : +1 [ 6] ( 0 1 0 0 0 1 ) : +1 Retrying... (1) | v [ 0] ( 0 0 0 1 0 1 ) : -1 [ 1] ( 1 0 1 0 0 0 ) : -1 [ 2] ( 0 0 0 0 1 1 ) : -1 [ 3] ( 1 0 0 1 0 0 ) : -1 [ 4] ( 1 0 0 0 0 1 ) : -1 [ 5] ( 0 0 1 1 0 0 ) : +1 [ 6] ( 0 1 0 0 0 1 ) : +1 [8] result=1 [ 0] ( 1 1 0 0 0 0 ) : -1 [ 1] ( 1 0 1 0 0 0 ) : -1 [ 2] ( 0 0 0 0 1 1 ) : -1 [ 3] ( 0 0 1 0 1 0 ) : -1 [ 4] ( 0 1 0 0 0 1 ) : +1 [ 5] ( 1 0 0 1 0 0 ) : +1 [ 6] ( 0 0 0 1 1 0 ) : +1 [9] result=1
これはBonaPieceの種類(駒の状態)が6で駒の総数が2という仮想的なチャトランガ系統のゲームの局面表現を線形分離しようとした例なのですだが、result=1が線形分離成功を表し、Retrying...は1発で線形分離できなかったのでラベルをちょっと弄ったことを意味する*4。
BonaPieceの数が増えたらベクトルが高次元になるということなので、普通線形分離しやすくなることが気体できるから、本将棋(BonaPiece数2344)とかだと写像fの実現に必要な重みベクトルの数やっぱ2344個を大きくは出ないのではないか、
そもそも写像fのように局面を自然数に写像する必要があるのは勝ち方(手数の最短化)などにこだわるからで、ただ単に勝てれば良いとみなすなら、{ BonaPieceによる局面 }を単に必勝の局面とそうでない局面にただ2分すれば良いから、必要な重みベクトルの数はなんと1+α個で賄い得る。
やっぱ将棋の神様の必勝手順は、うまいことやったら一人の人間の脳に収まりうる可能性が微レ存、