黒木玄先生のConwayのOn Numbers and Gamesの組合せゲーム理論のつぶやき
-
- いいね！0
黒木玄 Gen Kuroki
@genkuroki
#掛算 ConwayのOn Numbers and Gamesの組合せゲーム理論(CGT)の定式化は現在ではその分野では当然の常識になっています。ぼくはその話に碁(Go)をからめて #CGoT タグでたくさんツイートしています http://t.co/nNB8R95X 。
2012-03-22 14:47:03
黒木玄 Gen Kuroki
@genkuroki
#CGoT #掛算 タグでついさっきしていた話の続き。次のツイートから #掛算 タグを外します。 #CGoT 碁を知っている人には組合せゲーム理論(CGT)を説明し易いです。CGTの意味でのゲームは「数」を含んでいます。「数」は囲碁では終局図に対応しています。続く
2012-03-22 14:54:20
@rounin_maiden
RT @genkuroki: #掛算 ConwayのOn Numbers and Gamesの組合せゲーム理論(CGT)の定式化は現在ではその分野では当然の常識になっています。ぼくはその話に碁(Go)をからめて #CGoT タグでたくさんツイートしています http://t.co/nNB8R95X 。
2012-03-22 14:55:40
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。囲碁の終局図は黒が先着しても白が先着してもどちらが何目勝ちになるかが同じになる局面になっています。黒n目勝ちが確定しているときその局面は自然数のnを表わしており、白n目勝ちのときその局面は-nを表わしていると考えることができます。続く
2012-03-22 14:58:06
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。CGTでのゲームの加法の定義は単純です。単に二つのゲームの局面を合わせたものです。二人のプレーヤーは次の一手をどちらに着手してもよいことにする。囲碁で言えば複数の盤で囲碁をする様子を想像して下さい。黒も白もどの盤上に着手して構わない。続く
2012-03-22 15:02:50
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。そして、黒がm目勝ちが確定している終局図と黒がn目勝ちになる終局図を合わせれば黒のm+n目勝ちが確定している終局図になる(と考えられる)。このような感じでゲームの加法から数の加法が導かれます。これを無限に拡張するにはどうすればよいか。続く
2012-03-22 15:05:51
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。碁の終局図を次のようなゲームだと考えることにしましょう。白と黒は自分の地に石を埋めて行くまたは取った石を相手に返す(パスは禁止)。自分の地が先に埋め尽くされてしまった方の負け。そして、ちらが先着するかは決められておらず、黒先と白先の両方の結果を見る。続く
2012-03-22 15:12:08
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。そのルールのもとで持碁（黒地と白地が等しい終局図）は後手必勝という条件で特徴付けられます。持碁は0という数を表現しているので、数の0が後手必勝という条件で特徴付けられているとみなせます。CGTでもそのように（0と同値なゲーム）が特徴付けられます。続く
2012-03-22 15:16:05
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。再説明。自分の地を埋める手しか打てず、パスが禁止されており、自分の手番で有効な手が無くなったときに負けるゲームでは、自分の地が相手より多ければ先後に関わらず必勝、自分の地と相手の地が等しければ後手必勝になります。再説明終わり。続く
2012-03-22 15:18:53
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。以上によって、「加法」と「0（との同値性）」が導入されました。あとは引算を導入できれば同値関係を定義してアーベル群を構成できそうなことがわかります。引算を碁で説明するのは簡単です。碁の局面Aに対して、-AとはAを白黒反転した局面のことであると定義します。続く
2012-03-22 15:24:23
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続く。碁の終局図AとBの結果(どちらが何目勝か)が同じになることと、A-Bが持碁になる(0に同値になる)ことは同値になります。これによって同値関係が定まります。適切に定式化すれば終局図に限らない碁の任意の局面(実際には組合せゲーム全体)に同値関係を拡張できます。続く
2012-03-22 15:29:23
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。実はこれによって碁の局面の同値類全体(盤は複数使うように拡張)にアーベル群の構造が入ることを示せます。実際には組合せゲームの同値類全体にアーベル群の構造を入れられます。加法の可換性は加法が二つの局面を単に合わせることによって定義したので最初から自明です。続く
2012-03-22 15:32:03
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。以上の話を順序数α、β、…に拡張して「黒地α目、白地β目」の局面について考えることにしましょう。その局面では白も黒も自分の地を埋める着手しか許されません。黒は自分のα目の地を黒石で埋めてそれ未満にしなければいけません。白についても同様です。これでどうなるか。続く
2012-03-22 15:37:51
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。例として「黒地ω目、白地ω+1目」の局面Aと「黒地1目、白地0目」の局面Bを合わせた局面A+Bが持碁（後手必勝）になることを証明しましょう。黒先の場合の最善の応酬：黒はBで1目の地を埋めて0目にする。白はAでω+1目をω目にする。黒はAでω目を有限のn目に。続く
2012-03-22 15:41:47
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。白はAでω目をn目に。これで有限の持碁の局面になったので後手番の白勝ち。白先の場合も最善の応酬の結果、後手の黒が勝つことがわかります。囲碁や将棋などのゲームになれている人にとっては「ヨミ」によってそうなることを確認できるはず。これでA+Bが0に同値に～続く
2012-03-22 15:44:45
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き～なることが証明できた。局面Aは「黒地ω目、白地0目」(これは順序数ωに対応)と「黒地0目、白地ω+1目」(順序数-ωに対応)の二つの和に分解できます。そして局面GとHが同値であることをG-Hが持碁になることと定義したのでした。続く
2012-03-22 15:48:46
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。ややこしいので誰もまじめに読んでないと思いますが、実は以上の議論は組合せゲームの同値類の可換な加法について、ωと1の和がω+1に同値になることを、ゲームを遊び切ることによって示していることになっています。1と1の和が2になることはもっと簡単に示せます。続く
2012-03-22 15:52:27
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。何らかのゲームで先読みの技術を習得していると、Conwayによる組合せゲーム理論(CGT)の定式化を理解することはかなり容易になります。演習問題：CGTの意味で (ω^ω+1)+ω=ω^ω+ω+1 が成立することを示せ。これを解けばかなり感じがつかめます。
2012-03-22 15:56:24
黒木玄 Gen Kuroki
@genkuroki
#CGoT 続き。文献。ConwayのOn Numbers and Gamesを直接読むのがベストですが、数学畑人向けの解説文がarXivにあります。 http://t.co/CBcZ3MYE
2012-03-22 16:00:09