5x5の碁、解かれる 106
ストーリー by Acanthopanax
先手必勝 部門より
先手必勝 部門より
mizna曰く、"本家ストーリーより。アメリカ囲碁協会によれば、オランダのErik Van Der Werk氏が、コンピュータを使って5x5の囲碁を「解いた」(中心から始めて黒25目勝ちになる)そうです。詳しくはオランダ科学研究機構の発表を(2002年10月に発表されていますが、2005年1月27日に証明(defend)されたようです)。囲碁はチェスに比べて遙かに難しいと言われていますが、これを足がかりに囲碁の世界チャンピオンはコンピュータプログラム、となる日が近づいたのでしょうか?"
連珠は? (スコア:2, 興味深い)
学生時代に 雑誌 大学への数学で,四目並べなら先手必勝というのを
全ての場合を尽くして証明していた記事があったのですが.
Re:連珠は? (スコア:4, 参考になる)
基本珠型 [nifty.com]のうち、早いうちに先手必勝が証明されたのが、直接打ちの「花月」と間接打ちの「浦月」。それ以外でも先手の禁手なしでは先手必勝ですね。
Re:連珠は? (スコア:1)
要するに (スコア:2, 参考になる)
「碁を解いた」の意味を一瞬考えてしまった(^^;
碁で黒(先手)有利というのは一般に言われていますが、5X5に関しては完全に証明されたわけですか。
ゲーム理論では (スコア:2, 興味深い)
必勝戦略というのは、片方がどう打とうがもう片方が勝てる打ち方。
囲碁では二人のプレイヤーの間に先手、後手、という違いしかないので
どんなサイズの盤面でも先手と後手のどちらかに必勝の打ち方が
あるということになる。チェスなんかもそうらしい。
でもそういう手があるというのは判ってても実際どんな手かは
計算するのがひどく難しい。
今回の件を見ると、直感的には、先手必勝なんだろうな、と思う。
-- AKN
Re:ゲーム理論では (スコア:3, 参考になる)
Re:ゲーム理論では (スコア:2, 興味深い)
双方合意なら無勝負になるが、コンピュータは合意しないからなー。
ちなみに劫は禁止されているので、同一局面反復はおこりにくいと思うが。
それよりも、囲碁のルールと一口に言っても、日本と中国やアメリカ、ニュージーランドなど国ごとに異なるし、
日本のルールだって過去に一回改正されていて不変ではない。
たとえコンピュータが解いたとしても、即時にルールの改正が行われるのは間違いないと思う。
同一場面反復は両負けではありません (スコア:2, 参考になる)
1. 双方がパスすることにより、一端終了する
2. 終了の後、地や石の死活のために双方駄目を埋めたり、手を入(*)れたりするわけですが。その作業中に、実は本当は終了してはいけない囲碁だったことが判明。
3. そのときには、片側が圧倒的に勝っていれば、その人が対局の再開を要求するとともに相手から打たせてあげれば良いが、僅差の場合は、対局の再開を要求した側が負けるので、両方再開できないし、地が確定しないので結着も着かない。その場合が規定による両負けです。
(*)たとえば欠け継ぎになっているところはダメを埋められると固く継ぎ直す必要が出ることがあります(初心者のなかにはこれを寄せと勘違いする人も居ますが -- 今のコンピュータ囲碁もこのレベル -- おかげで終了後の手入れが発生しない、ちなみに私の棋力は級レベルですが、今のコンピュータ囲碁なら井目をコンピュータに置かせても勝てます。キリチガエ、戦いの囲碁は全くダメです)。
Re:同一場面反復は両負けではありません (スコア:1, 参考になる)
両負けになった事例もあります。
Re:同一場面反復は両負けではありません (スコア:1)
完全な同型になった場合、1.の後に2.の手入れは行わない(盤を見れば明白なので)。
双方納得すれば12条規定で無勝負だが、どちらかが相手に着手を要請すれば当然相手は拒否。
で、両負けになると思っていたのだけど。
あなたが書いてあることと矛盾しないと思うのだけど、間違ってる?
同一局面反復の場合 (スコア:2, 参考になる)
まず、誤解のないように言うと劫については、劫の形を作ること禁止されているのではなく、取られた側がすぐに取り返すことが禁止されているだけです(「劫は禁止されている」では皆さん誤解なさるといけないので -- 「劫は取り返せないから同一局面反復にならない」なら誤解はないと思います)。
また、同一局面反復の囲碁の規定では、双方合意の場合引き分けとなるだけで、双方合意しない場合は永久に続くことになっています。このことは将棋とは異なり、実際の勝負上、問題になりません(将棋では問題となるので、同一局面が4回現れた瞬間に引き分けが決定します(チェスは一回少ないので注意)--ただし連続王手の場合は王手をしている側が負けになります(すなわち王手の側が指し手を変更しなさいということ)--(これもチェスは引き分け -- ステイルメイトとの関連で面白い局面があります))。
問題にならない理由は、囲碁の同一局面反復は、長生(ちょうせい --ながいき、ではない)や三劫などの非常に特殊な場合であり、双方が望まない限りその形を作れないからです(すなわち、有利な方は避けることが可能)。
まず初心者を含む対戦では生じ得ない(まず初心者は劫を戦えないので三劫どころか(寄せの段階での半劫を除いて)劫が同時に二つできることすらないでしょうし、長生はさらに作れない)ですし、形勢判断のできる実力がある人は避けることができるでしょう(三劫や長生が出来てから譲ると損が大きいので先に避けるのです)。
将棋の場合は、矢倉からみで千日手は出てくるし、詰将棋では千日手解消をテーマにした問題もあります。チェスの場合は終盤では局面が単純化するので同一局面は現われやすく、負けそうな試合をパーペチュアルチェック(千日手の王手の連続の場合のこと)によって引き分けに持ちこむのは、よくあるテクニックです(実践でこれをやると勝ったときよりも大きな拍手がもらえる場合もあるとか)。囲碁では長生や三劫などは、実践に則した話題ではなく形式的な話題です。
囲碁と将棋は日本のルールでの話です。為念。
Re:同一局面反復の場合 (スコア:2, 参考になる)
勘違いで妙なこと書いてすまんかった。
# このコメントにプラスモデ、私の元コメントマイナスモデしといてくださいませ。>モデレータ様
Re:同一局面反復の場合 (スコア:2)
> 問題にならない理由は、囲碁の同一局面反復は、長生(ちょうせい --ながいき、ではない)や三劫などの非常に特殊な場合であり、双方が望まない限りその形を作れないからです(すなわち、有利な方は避けることが可能)。
違います。問題が発生しない理由は、
「無勝負には同意しない、けれども同一局面反復を回避せずに同じ手を永久に打ち続ける」
という、みっともないことをする人が(少なくともプロには)いないからです。
もし仮にそういうプロが現れたとしたら、「双方が同意した時」なんて表現にはせず、
将棋のように回数が明記される事でしょう。
> まず初心者を含む対戦では生じ得ない(まず初心者は劫を戦えないので三劫どころか(寄せの段階での半劫を除いて)劫が同時に二つできることすらないでしょうし、長生はさらに作れない)ですし、形勢判断のできる実力がある人は避けることができるでしょう(三劫や長生が出来てから譲ると損が大きいので先に避けるのです)。
そうではありません。確かに将棋と比較して囲碁の方が発生しづらく、かつ回避しやすい事は確かですが、
出来る前に避けたとしても何らかの不利は発生しますので、やむを得ず発生することはあります。
・「回避による不利を受けたとしても、形勢不利にはならない(続行>引き分け)」
と考えている側が、手を変えて引き分けを回避する
・双方が、「少なくとも自分が手を変えると、形勢不利になる」と考えている場合、
双方回避せず引き分けとなる
という事で、本質的には違いがありません。
> 囲碁では長生や三劫などは、実践に則した話題ではなく形式的な話題です。
例え何年に一回という話でも、実際に発生している以上形式的とは言えません。
ごめんなさい訂正 -- 将棋の場合 (スコア:1)
#ACで投稿できなかったのでsutesuteアカウント。
Re:ゲーム理論では (スコア:1)
将棋には千日手とか入玉があるというのは知っていましたが。
しかし、囲碁で先手後手同形の場合、勝とうとするならば必ず
どちらかによって石が打たれるのでは?
双方とも石を打たないということは、双方とも、打てば引き分けより
悪くなる(つまり負ける)ということのはず。
ルールによれば双方負けということはないはず。また、ゲーム理論では
プレイヤーの読み間違いや知識の不足を考えない(というか、既に
理論に含まれている)ので、双方パス>引き分けというのは
双方とも引き分けにしようと考えているのでない限りあり得ないと
思うのですが……
-- AKN
Re:ゲーム理論では (スコア:2, 参考になる)
日本囲碁規約逐条解説 [wakwak.com]
「無勝負」や「両負け」のルールがありますね。
Re:要するに (スコア:1, おもしろおかしい)
Re:要するに (スコア:1)
ただし、プロ対プロなら (スコア:4, 興味深い)
今回の記事は5x5の中で白が生きれないことを「証明」した訳で強い囲碁のプログラムとは何ら関係ありません。強い囲碁や将棋のプログラムを作るには、チェスやリヴァーシ(オセロ)の場合とは異なり、すべてを読み切ってはダメだと思います。
(α-β枝刈りのことではありません。もっとヒューリスティックに枝刈りする必要があるということです。)
人間の場合は、たとえば10合マスの問題なら着手点は3x3(+2)で9点乃至は11点ですが、これでも虱潰しに読んでは解けるものではないです(11! = 約4000万なので)。
中手を正しく読めるライブラリを用意すれば5x5くらい簡単に解けそうなものですがね.... でも中手を正しく理解する囲碁プログラムを見たことがないので難しいんですかね。
将来的には、私は人間が対戦して面白いと感じる囲碁プログラムその一号を作りたいと思っていますが、
・中手や石の死活を間違えない(明かに生ききている石に無駄な手を入れず、手を入れないと殺される石には手を入れる)。
・キリチガエや戦いに強くなる、戦いを恐れずにケイマのツケコシが打てる。
・寄せのときに無駄なダメを詰めない。
この辺りをクリアしないと駄目ですね。
Technical Typeさんへ
3x3(9! = 約36万通り)や 4x4 (16! = 約21兆通り)の場合を列挙してみてください。対称性を考慮するとこれより大分少なくなるとは思いますが、3x3でへとへと、4x4は人間には無理、という感じだと思います。
Re:ただし、プロ対プロなら (スコア:2, 興味深い)
人間側も、例えばランキング上位100人の意見を集約して最善の1手を決める、
というのはどうなんだろう。
Re:ただし、プロ対プロなら (スコア:2, すばらしい洞察)
それが一番難しいのではないでしょうか
ランキング上位100人の意見となると
簡単な枝きりで消えるような手はすでに残ってないだろうし
多数決を採るにしても, トップの人は時として他の人が思いつかない手を打てるからこそ
トップなんではないかと
Re:要するに (スコア:4, おもしろおかしい)
ありがたい。
Re:要するに (スコア:1)
「Tick Tack Toe」じゃなくて「囚人のジレンマ」では?
Re:要するに (スコア:2, 参考になる)
マラソンで二位を抜いたら何位?
Re:要するに (スコア:1)
#うろ覚え
Re:要するに (スコア:1, すばらしい洞察)
おまえはすでに負けている (スコア:2, 参考になる)
Re:おまえはすでに負けている (スコア:1, 参考になる)
でも五路って黒天元で必勝って、どっかで証明されてなかったっけ?
どちらかっつーと五路は状況を作ったうえで頭をひねる、詰め将棋的なものだと思ってた。
Re:おまえはすでに負けている (スコア:1)
9路くらいになれば全滅ってのはまずあり得ないでしょうし。
この先どういう話につながるのか、興味はありますけど。
Re:おまえはすでに負けている (スコア:1, 興味深い)
一里塚 (スコア:2, 参考になる)
Re:一里塚 (スコア:1, 参考になる)
つまり、例えば黒白10手ずつ打って、白が全滅した場合、
盤面15目+アゲハマ10目で黒25目勝ちとなります。
実際には、計算の時に相手の地にアゲハマを埋めるのですが、
全滅なら地が0なのでこういう計算をすることになりますね。
Re:一里塚 (スコア:1)
Re:一里塚 (スコア:1)
白全滅の一手前から黒が止めの手を打った時点でさらに白が着手しても、その白石も含めて死んでおり黒のアゲハマとなる。黒白同手数で白全滅が成立し、黒の25目差勝ち。
その最後の白石は、黒地を一つ減らすとともに黒のアゲハマを一つ増やす。着手による勝ち目数への影響はないので、白が最後に着手しなくても黒の25目差勝ち。
...ってことはないですか?
Re:一里塚 (スコア:1)
Re:一里塚 (スコア:1)
オセロ(リバーシ)だと… (スコア:2, 参考になる)
Re:オセロ(リバーシ)だと… (スコア:2, 参考になる)
オセロの場合偶数×偶数にしないと初期配置の切り違い(なぜか囲碁用語)が対称性を持たないのでよくないっぽいので、7×5はないんじゃないでしょうか。
Re:オセロ(リバーシ)だと… (スコア:1)
オセロではありえないそうですが、7×7のときのありえるオセロの置き方をN通りとしたとき、8×8の場合では新しく置ける場所は32箇所(7×4+4)。N通りの置き方のそれぞれに対して、新たに32箇所の置き方が追加されるので32のN乗の置き方が考えられます。(実際は、重複やありえない置き方が含まれているので、もう少し小さい値になるとは思いますが)
なんとなく、一般化するとR×Rの場合は(R-1)×(R-1)のときの置き方nに対して、(R×4+4)のn乗の置き方があることになるのではないでしょうか?確実にマスを少なくしていくオセロでこんな感じなので、何回もマスに(升目に)置くことが可能な将棋や碁はRの値が大きくなるととんでもない置き方の組合せ数になるんでしょう。
四十九次
Re:オセロ(リバーシ)だと… (スコア:1)
8x8の場合に白が2手目で並び取り(黒3石と白3石が並ぶ取り方)をすると、
黒がほぼ勝ちになる定石があったと思う。
ブッキング (スコア:1, 興味深い)
囲碁、チェスといえば (スコア:1)
異なるゲイム間で他のゲイムの経験はプラスになのでしょうか?
それがコンピュータ棋士にも当てはまればn競技制覇も夢でない?
、実施は定石DBによるところが大きいようですから簡単ではないでしょうが
Re:囲碁、チェスといえば (スコア:2, 興味深い)
現在の名人は森内さん [shogi.or.jp]です。
# 名人は段位ではなくてタイトルの一つであることは、やはり世間にはなかなか認知されないのだろうか?
チェスと将棋の違いについてはこちら [hatena.ne.jp]が参考になるかもしれません。
上記サイトからの引用ですが、
>チェスは将棋でいう序盤がなくて、いきなり中盤から始まる感じ。
>チェス以外に韓国・中国の将棋などもあるが、日本の将棋が最も変わり者、ユニーク。他への応用が利かない。
>チェスは終盤になると駒が少なくなり静かになっていく。将棋とは終わり方が違うので本質が違う。
これを読む限り羽生さんはチェスの経験が将棋にプラスになるとは思っていないようですね。
コミは? (スコア:1)
とすると逆に、これによってこれまで経験則で行われてきたコミも数値で表せるようになるわけでしょうかね。もちろん五路盤程度だとあまり意味を持たないかもしれませんが、ステップアップして最終的には19路盤での完全制覇(?)まで行くのでしょうし。
#そうはいっても19路の全パターンってハノイの塔並みなんじゃなかろーかと。まだしばらくは人間様の直感と経験にアドバンテージかな?
訳? (スコア:1, 参考になる)
Re:Comの惑星 (スコア:2, 参考になる)
囲碁は級レベル.
将棋と比べると, コンピュータ囲碁はまだまだ研究の余地がありますね.
Re:Comの惑星 (スコア:1, 興味深い)
囲碁マンセー (スコア:2, 参考になる)
playgo.to [playgo.to]の インタラクティブ囲碁入門 [playgo.to]
両者とも、要JavaApplet
Re:囲碁のルール (スコア:2, おもしろおかしい)
『ヒカルの碁』の作画担当の小畑健先生は全23巻描き切ってもまだルールを理解していないようであります。
(作者のあとがきで「原作のほったゆみさんから碁石を一個貰ったが、ほったさんは碁石が一個足りないので困るのではないか?(*)」などとトンチンカンなことを書いておられました)
*:碁石は普通、全部使い切ったりはしないので困らない。
ルールを知らなくてもアレだけ描けるのはすごいと思いました。
一応360手を越えるような勝負もあるんですが、 (スコア:2, 参考になる)