■

昨日の漸化式をＣでコーディングすると

extern int f_2n(move a[N], b[N]);

int f(int n, move a[N], b[N]){

    int dummy, result, i;

    if(n==2N) return f_2n(a,b);

    if (n&1==1){ 

	result=1;

        for(i=0;i＜MOVE_MAX;i++) { b[n/2]=i;result &= f(n+1,a,b);}

    }else{

        result=0;

        for(i=0;i＜MOVE_MAX;i++) { a[n/2]=i;result |= f(n+1,a,b);}

    }

    return result;

}

main(){

    move a[N],b[N];

    if (f(0,a,b)==1) printf("先手必勝\n"); else printf("後手必勝\n");

}

て感じで再帰呼出しになる。結果的に全ての場合を調べるので計算時間は exp(N) のオーダーで実際は不可能。でも量子コンピュータでうまくやれば O(N)時間でできないかな。結果は１か０かなんでそれを確率的にでも正しく観測できればいいわけで。。。
完全情報二人ゲームの Itakura の量子アルゴリズム！！？？
始めに Σ f(A1,B1,..An,Bn)|A1B1A2B2..AnBn＞ という状態を作ってユニタリ変換をしていって、、、あーその初期状態を作るのが不可能か。O(N)回数の変換で初期状態を作れるような単純なfつまり勝敗のルールなら元々自明だろうし。やっぱダメか。

---

ノイマンの証明はあらゆる駒の配置に対して指し手を定義したものを「戦略」と定義したとき利得行列を考えるとミニマックス定理が使えて、という感じらしい。だいぶ感じが違うな。