パスワードを忘れた？ アカウント作成
Close
9715 story

5x5の碁、解かれる 106

ストーリー by Acanthopanax
先手必勝 部門より

mizna曰く、"本家ストーリーより。アメリカ囲碁協会によれば、オランダのErik Van Der Werk氏が、コンピュータを使って5x5の囲碁を「解いた」(中心から始めて黒25目勝ちになる)そうです。詳しくはオランダ科学研究機構の発表を(2002年10月に発表されていますが、2005年1月27日に証明(defend)されたようです)。囲碁はチェスに比べて遙かに難しいと言われていますが、これを足がかりに囲碁の世界チャンピオンはコンピュータプログラム、となる日が近づいたのでしょうか？"

この議論は賞味期限が切れたので、アーカイブ化されています。 新たにコメントを付けることはできません。

5x5の碁、解かれる More

  • 連珠は? (スコア:2, 興味深い)

    by yshibaya (16994) on 2005年02月23日 20時40分 (#698471) 日記
    連珠(五目並べのもっと正式なやつ)はどうなんだろう？
    学生時代に 雑誌 大学への数学で，四目並べなら先手必勝というのを
    全ての場合を尽くして証明していた記事があったのですが．

  • 要するに (スコア:2, 参考になる)

    by snd (14690) on 2005年02月23日 20時45分 (#698474)
    「5X5なら先手必勝だぜい！」ということですよね？
    「碁を解いた」の意味を一瞬考えてしまった(^^;
    碁で黒（先手）有利というのは一般に言われていますが、5X5に関しては完全に証明されたわけですか。

    • ゲーム理論では (スコア:2, 興味深い)

      by AKN (26100) on 2005年02月23日 22時13分 (#698523) 日記
      たしかゲーム理論では、囲碁には常に必勝戦略があったはず。
      必勝戦略というのは、片方がどう打とうがもう片方が勝てる打ち方。
      囲碁では二人のプレイヤーの間に先手、後手、という違いしかないので
      どんなサイズの盤面でも先手と後手のどちらかに必勝の打ち方が
      あるということになる。チェスなんかもそうらしい。

      でもそういう手があるというのは判ってても実際どんな手かは
      計算するのがひどく難しい。

      今回の件を見ると、直感的には、先手必勝なんだろうな、と思う。
      --
      -- AKN
      シェア
      親コメント
      • 二人零和有限確定完全情報ゲーム [wikipedia.org]を参考にどうぞ。
        シェア
        親コメント

    • Re:要するに (スコア:1, おもしろおかしい)

      by Anonymous Coward on 2005年02月23日 21時19分 (#698488)
      ということは、コミ25目半で白必勝ですね
      シェア
      親コメント

    • Re:要するに (スコア:1)

      by Technical Type (3408) on 2005年02月24日 0時46分 (#698612)
      3x3 とか 4x4 とかだったら、紙と鉛筆で全部の異なる指し手のパターンが列挙できそうだけど、5x5 だとニュースになる程凄いのか。。。
      シェア
      親コメント

      • ただし、プロ対プロなら (スコア:4, 興味深い)

        by sutesute (26237) on 2005年02月24日 4時09分 (#698681)
        19路盤の淵(72個所)すべてに黒石を起くと、中で白は生きることが出来ないと言われています(これは、アマ同士でやると面白い勝負になるのでやってみて下さい)。

        今回の記事は5x5の中で白が生きれないことを「証明」した訳で強い囲碁のプログラムとは何ら関係ありません。強い囲碁や将棋のプログラムを作るには、チェスやリヴァーシ（オセロ）の場合とは異なり、すべてを読み切ってはダメだと思います。
        （α-β枝刈りのことではありません。もっとヒューリスティックに枝刈りする必要があるということです。）
        人間の場合は、たとえば10合マスの問題なら着手点は3x3(+2)で9点乃至は11点ですが、これでも虱潰しに読んでは解けるものではないです（11! = 約4000万なので）。

        中手を正しく読めるライブラリを用意すれば5x5くらい簡単に解けそうなものですがね.... でも中手を正しく理解する囲碁プログラムを見たことがないので難しいんですかね。

        将来的には、私は人間が対戦して面白いと感じる囲碁プログラムその一号を作りたいと思っていますが、
        ・中手や石の死活を間違えない（明かに生ききている石に無駄な手を入れず、手を入れないと殺される石には手を入れる）。
        ・キリチガエや戦いに強くなる、戦いを恐れずにケイマのツケコシが打てる。
        ・寄せのときに無駄なダメを詰めない。
        この辺りをクリアしないと駄目ですね。

        Technical Typeさんへ
        3x3（9! = 約36万通り）や 4x4 （16! = 約21兆通り）の場合を列挙してみてください。対称性を考慮するとこれより大分少なくなるとは思いますが、3x3でへとへと、4x4は人間には無理、という感じだと思います。
        シェア
        親コメント

  • おまえはすでに負けている (スコア:2, 参考になる)

    by giggs (8330) on 2005年02月23日 21時07分 (#698482) 日記
    25目勝ちになるというのは、単に白地ができないことの別の表現ですね。先手が打った瞬間、黒地が1目減り、後手が打ったら黒地が一目増えるという具合です。リンク先 [unimaas.nl]のGIF画像では、白は全部殺されてます。

    同じところにある、Mistake at 6の図には Even 趙治勲 missed this one という興味深いコメントがありますが、これはどうなっているんでしょう？黒の負け？それはそうと、趙氏も5路盤の囲碁をたしなんでいたとは驚き。

  • 一里塚 (スコア:2, 参考になる)

    by w1allen (21025) on 2005年02月23日 21時14分 (#698487)
    一応碁のルールを知っているものとしてコメントすると、５路盤で２５目勝ちということは、正しく打たれると白は「目を作れない」（すべて死ぬ）ということを意味します。証明されたことはもちろんすごいですが、直感的・経験的には、「まあそうだろうな」というところだろうと思います。６路盤以上では、白が「目を作れない」ということはないと思いますので、今回のような結論を出すのは難しくなると思います。

  • オセロ(リバーシ)だと… (スコア:2, 参考になる)

    by tsekine (18956) on 2005年02月23日 21時34分 (#698500) ホームページ 日記
    ゲーム木の並列探索のための分散共有ハッシュ機構の設計と実現 [ipsj.or.jp] の記事は読めないのですが、確かオセロの場合は7x5だとすでに解かれてたはず。 だとすると、今日のスパコンの計算機パワーなら8x8でももう解けそうな気がするんですが、どうでしょう?

    • Re:オセロ(リバーシ)だと… (スコア:2, 参考になる)

      by aji (7257) on 2005年02月23日 22時04分 (#698519) 日記
      6×6ならありますね [nott.ac.uk]。
      オセロの場合偶数×偶数にしないと初期配置の切り違い（なぜか囲碁用語）が対称性を持たないのでよくないっぽいので、7×5はないんじゃないでしょうか。
      シェア
      親コメント

    • オセロではありえないそうですが、７×７のときのありえるオセロの置き方をN通りとしたとき、８×８の場合では新しく置ける場所は32箇所（７×４＋４）。N通りの置き方のそれぞれに対して、新たに32箇所の置き方が追加されるので32のN乗の置き方が考えられます。（実際は、重複やありえない置き方が含まれているので、もう少し小さい値になるとは思いますが）

      なんとなく、一般化するとＲ×Ｒの場合は(Ｒ－１)×(Ｒ－１)のときの置き方ｎに対して、(Ｒ×４＋４)のｎ乗の置き方があることになるのではないでしょうか？確実にマスを少なくしていくオセロでこんな感じなので、何回もマスに（升目に）置くことが可能な将棋や碁はＲの値が大きくなるととんでもない置き方の組合せ数になるんでしょう。

      --
      　　四十九次
      シェア
      親コメント
    • まだ計算はできていないとはずだけど、
      8x8の場合に白が2手目で並び取り（黒3石と白3石が並ぶ取り方）をすると、
      黒がほぼ勝ちになる定石があったと思う。
      シェア
      親コメント

  • ブッキング (スコア:1, 興味深い)

    by Anonymous Coward on 2005年02月23日 20時57分 (#698476)
    本家の記事ってトッピク二重になることがあるのね。

  • 囲碁、チェスといえば (スコア:1)

    by ef (25263) on 2005年02月23日 21時10分 (#698485)
    羽生名人が一時期チェスに取り組んでいられましたが、
    異なるゲイム間で他のゲイムの経験はプラスになのでしょうか？
    それがコンピュータ棋士にも当てはまればｎ競技制覇も夢でない？
    、実施は定石ＤＢによるところが大きいようですから簡単ではないでしょうが

    • Re:囲碁、チェスといえば (スコア:2, 興味深い)

      by Anonymous Coward on 2005年02月24日 16時54分 (#699070)
      羽生さんは名人ではありません。 [shogi.or.jp]
      現在の名人は森内さん [shogi.or.jp]です。
      ＃　名人は段位ではなくてタイトルの一つであることは、やはり世間にはなかなか認知されないのだろうか？

      チェスと将棋の違いについてはこちら [hatena.ne.jp]が参考になるかもしれません。
      上記サイトからの引用ですが、

      ＞チェスは将棋でいう序盤がなくて、いきなり中盤から始まる感じ。
      ＞チェス以外に韓国・中国の将棋などもあるが、日本の将棋が最も変わり者、ユニーク。他への応用が利かない。
      ＞チェスは終盤になると駒が少なくなり静かになっていく。将棋とは終わり方が違うので本質が違う。

      これを読む限り羽生さんはチェスの経験が将棋にプラスになるとは思っていないようですね。
      シェア
      親コメント

  • コミは？ (スコア:1)

    by Sakura Avalon (12557) on 2005年02月23日 21時29分 (#698496)
    解かれたページはザッと見ただけなのでもしかしてどこかに書かれてたかもしれませんが、これはコミは考慮しないのですよね？勝負ではなく証明なのですから当然といえば当然ですが。
    とすると逆に、これによってこれまで経験則で行われてきたコミも数値で表せるようになるわけでしょうかね。もちろん五路盤程度だとあまり意味を持たないかもしれませんが、ステップアップして最終的には19路盤での完全制覇（？）まで行くのでしょうし。

    ＃そうはいっても19路の全パターンってハノイの塔並みなんじゃなかろーかと。まだしばらくは人間様の直感と経験にアドバンテージかな？

  • 訳? (スコア:1, 参考になる)

    by Anonymous Coward on 2005年02月24日 0時08分 (#698583)
    Science Dailyの訳 [2ch.net] を出してくれた人がいますよ

typodupeerror

ハッカーとクラッカーの違い。大してないと思います -- あるアレゲ