henkma氏の問題。完全情報ゼロサム二人ゲームが先手必勝か後手必勝である、てのはノイマンが証明したんでしたっけね。ノイマンの証明方法は知らないけどやってみました。f=1 がAの勝ち、f=0 がBの勝ちとします。論理式で書くと先手必勝は:
これを念頭に、
∃A1∀B1∃A2∀B2∃A3∀B3...∃An∀Bn f(A1,B1,...An,Bn)=1 (1)
と定義する。ただし AND_x/OR_x はすべての x について論理AND/ORをとったものとする。この操作を繰り返してn=0まで計算し、f_0()=1 なら先手必勝、f_0()=0 なら後手必勝。
f_{2n-1}(A1,B1,...,An)= AND_{Bn} f_{2n}(A1,B1,A2,B2,...,Bn-1,An,Bn)
f_{2n-2}(A1,B1,...,Bn-1)= OR_{An} f_{2n-1}(A1,B1,A2,B2,...,Bn-1,An)
追記：しまたー！もっと簡単だった。後手必勝の論理式も書き下して(1)と見比べれば一発だ。
じつは少し前から雑記は月毎に違うファイルに書いて、
みたいにして作ったのをＵＬしてる。月毎のファイルもＵＬすればリンクされる時便利だけど、どうしようかな。今まではファイル容量がギリギリなので zip で固めてＵＬしてたけど今は少しは余裕あるし。あとWEB の恥は書き捨てってスタンスで、過去の駄文を検索されないように、って動機も少しあったり。書評だけでもまとめてページ作ろうとは思ってるんですけども。
cat head b0209 b0210>nikki.html
