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

チェッカーの駒の動き、完全に解読される 56

ストーリー by GetSet
絶対に負けない、というのも凄いな 部門より

backslashdot 曰く、

Slashdot本家でNatureの記事がネタにされているが、 どうやらチェッカーにて、駒の動きが完全に解読されたようである。
University of Albertaの研究チームによる Chinookというチェッカーソフトウェアのプロジェクトがあるのだが、 5×1020回もの駒の動きが解読されており、 黒が最初に動き、かつ相手が完全な動きを行ったとしても、引き分けにできるとのことで、決して負けることがないそうだ。
さて、次は何が解読されるのだろうか。

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

チェッカーの駒の動き、完全に解読される More

  • 結論は「引き分け」なんですね (スコア:3, 参考になる)

    by w1allen (21025) on 2007年07月21日 12時14分 (#1193494)
    結論は「引き分け」なんですね。

    タレこみ欄にあるwikipediaのリンクより
    ルール上偶然の要素はなく、ゲーム理論では将棋や囲碁と同じく二人零和有限確定完全情報ゲームに分類される。2007年にアルバータ大学のシェッファーを中心とした研究グループによって、プレイヤー双方が最善を尽くした場合、必ず引き分けに至ることが証明された。

  • 日本語記事 (スコア:2, 参考になる)

    by Anonymous Coward on 2007年07月21日 11時46分 (#1193475)
    駒取り合う「チェッカー」を完全解明・カナダの研究チーム [nikkei.co.jp]

    • 継続は力なり (スコア:1, 興味深い)

      by Anonymous Coward on 2007年07月21日 12時26分 (#1193504)
      18年も計算しつづけてたことのほうが驚きだと思う。18年前にプロジェクトを始めたときの計算機ってどんなものだったんだろう？
      ＃今から計算し始めたら、20年後には「将棋の駒の動きを完全シミュレーション！」というニュースで一躍有名になれるかも？
      シェア
      親コメント

      • Re:継続は力なり (スコア:2, 興味深い)

        by nezuku (25740) on 2007年07月21日 14時34分 (#1193581)
        続けて計算しているとは載っていますが，同じ計算機を
        ずっと使っていると書いていないので，時間の経過とともに
        高速な計算機へ移行していったのかなと思います．

        はじめのの数年と，ここ数年の計算機の性能の差が気になるところです．
        シェア
        親コメント

  • つまり、 (スコア:1, すばらしい洞察)

    by Anonymous Coward on 2007年07月21日 11時44分 (#1193472)
    最初にどちらが駒を動かすか決める時の必勝法が求められる訳ですね。

    • Re:つまり、 (スコア:1, 参考になる)

      by Anonymous Coward on 2007年07月21日 22時14分 (#1193787)
      現在の公式ルールでは最初の数手はランダムに打つことになっているので、先手をとっても勝てるとは限りません。
      完全解析されたということは最初の数手の手順が決まった段階ですでに勝敗は決しているので、単なるサイコロ遊びになったということでしょうか。
      シェア
      親コメント

  • ○×ではなく (スコア:1, 興味深い)

    by Anonymous Coward on 2007年07月21日 11時45分 (#1193474)
    ついに、○×ゲームではなくて、チェッカーでも勝者なしが計算される時代になりましたか。
    「本当に楽しめるチェスをやりませんか？」が有効な時代は、いつまでか。

    • Re:○×ではなく (スコア:0)

      by Anonymous Coward
      気の利いたコメントを付けたいけど、何を書いても無粋になってしまいそうだ。
      分かる人だけ分かればいいネタですね。

  • 次に知りたいのは、 (スコア:1)

    by junnno (19418) on 2007年07月21日 13時14分 (#1193540)
    お互いが完全に最適化されていない手を打った場合の、勝ち易さと負け易さ。

  • ルール変えたらどう (スコア:1)

    by ponz9 (20348) on 2007年07月21日 13時27分 (#1193549)
    それじゃ、対戦中任意の時点で１回だけバック出来ることにすれば、解析にしばらく時間かかるかも。

  • 18年かけたからこそ？ (スコア:1, 興味深い)

    by Anonymous Coward on 2007年07月21日 14時27分 (#1193577)
    「負けなし」のチェッカー対戦ソフト、アルバータ大で開発 [itmedia.co.jp]
    １８年間の時間をかけたからこそ，読みきれたと言っても信用してもらえるのかな．
    この局面探索に漏れが無い，間違いが無いという検証ってできるのでしょうか．

    • Re:18年かけたからこそ？ (スコア:3, 参考になる)

      by 306m5 (11617) on 2007年07月21日 17時40分 (#1193662)
      四色定理（四色問題） [wikipedia.org]もコンピュータを援用した証明で解決したことになっていますが、ウィキペディアを見る限りは反例がでるまでは一応信用されるという、科学的手法っぽいスタンスのように見えます。

      しかし、あまりに複雑なプログラムのため他人による検証が困難であることや、コンピュータの誤りの可能性を考慮して、この証明に疑問視する声があった。その後、プログラムの改良が進められており、現在、四色問題の解決を否定する専門家はいない。
      ウィキペディア

      Computer-assited proof (英語版) [wikipedia.org]によると、人間による検証ができないということで、証明とは認めない数学者の立場もあるようです。
      シェア
      親コメント

  • つまり、バトルは永遠に続けられると (スコア:0)

    by Anonymous Coward on 2007年07月21日 11時12分 (#1193447)
    ジャンプ少年誌にピッタリだな！(核違)

    #その前につまらなくて打ち切り

  • 完全読みできるプログラムが完成して…… (スコア:0)

    by Anonymous Coward on 2007年07月21日 11時19分 (#1193454)
    コンピュータ側が赤になった瞬間投了

  • 嘘をつくな。 (スコア:0)

    by Anonymous Coward on 2007年07月21日 11時29分 (#1193464)
    チェッカーがキレて盤をひっくり返したときの駒の動きまでは読めないだろう？

    • Re:嘘をつくな。 (スコア:1)

      by love-m4 (10412) on 2007年07月21日 11時35分 (#1193467) 日記
      それは「完全な動き」なんでしょうか？

      ＃ネタニマヂレスカコワルイ？
      シェア
      親コメント

    • Re:嘘をつくな。 (スコア:0)

      by Anonymous Coward
      盤面の状態を完全に記憶しているので復元可能です。 :-)

    • Re:嘘をつくな。 (スコア:0)

      by Anonymous Coward
      盤をひっくり返したときの駒の動き
      　　　　　　　　　　　　　　　　　　　　　　こ　　　　　　　　　う
      　　　　　　●　　　　　　　で　　　　○
      　　　　　　　　　　　　　　　　　　　　　　　す　　　　か
      　　　　　　　　　　　　　　　　　　？　わ 　　　　　　　　　○
      　　　　　　　　　　　　　　　　　　　　　　　かり　　　　○
      　　　　　　　　　●　　　　　　ま　　　　　　　　　せ
      　　　　　　　　　　　　　　　　　　　ん
      　　　　　　　　　　　　　　　　！　●
      　　　　　　　　　　　＞　＜

          　　　　　　　彡
          (,,ﾉﾟдﾟ)ﾉ

  • 「解読」？ (スコア:0)

    by Anonymous Coward on 2007年07月21日 12時09分 (#1193490)
    「解読」という言葉の使い方は変ではないか？

  • オセロの全手読み (スコア:0)

    by Anonymous Coward on 2007年07月21日 14時20分 (#1193574)
    やりたいと思ってプログラムを書いた。
    データベースと分散化ができなくて放置中。

    協力者がいれば復活したいなぁ。
    多分そんなに難しいデータベースにならないと思うのだけど…

    当方を直接知るひとには全然 Anonymous Coward じゃないけど…
    • ふーん
      オセロですか、

      ８X８の升目でそれをビットとして考えた場
      64bitの文字列として例える事ができる
      実際、置いてるか置いてないかの情報を含めると
      ３つの条件が存在するので
      最大で3^64って所ですね
      3.43368382 × 10^30

      手数として始めに４つ並んでいるので
      埋める最大の手数は６４−４の６０手

      こんな感じですか？

      • Re:オセロの全手読み (スコア:2, 参考になる)

        by zozbug (9256) on 2007年07月21日 18時01分 (#1193672)
        オセロの場合、そこに置けるかどうか（相手をはさんでひっくり返せるか）があって始めの手は4つしかないですわな。

        じゃあ結構すくないかなーっていうと始めに4つ手があったとして、そこから相手の手はどれだけあるか？　その次のこっちの手はいくつあるか？　という分岐に入り、この手のゲームは組み合わせがどんどんかけ算で増えていきます。「組み合わせ的爆発」とかまあそんなこと言いますね。

        それでもオセロは盤がどんどん埋まっていくからいずれは収束しますし、チェスもだんだんコマが少なくなりますけど、これが将棋だと大変。
        シェア
        親コメント

      • Re:オセロの全手読み (スコア:1, 興味深い)

        by Anonymous Coward on 2007年07月22日 10時11分 (#1194053)
        盤面を考えたときに全部埋まらない状態があるかもしれないけど、計算しやすくするために少々乱暴ですた、全部埋まった最終状態の組み合わせは 2^64 通りですむと考えます。
        盤面をそれを全部保存したとして、ひとつの盤面について 64 ビット→ 8 オクテットを 8 バイトとしたとき、 147,573,952T,589G,676M,412k,928 (補助によく使う文字いれました)ということで全部保存するのは意味ないなーと。
        なんかもう 10 年くらいで個人でも何とかハンドリングできそうな世界に入りそうな気がしませんか？

        しかも、ソレは三つの状態のどれか、白の勝ち、黒の勝ち、引き分けしかないわけで、結果が読めたものの手順の枝刈りができれば途中の手数はへるだろうと思います。
        多分 LDAP のような木構造のようなのを扱うデータベースが得意なのかとも想像します。

        もうひとつ、手数の爆発は 12 手目くらいまでシミュレーションして、「今はムリそう」と二年くらい前に思いました。
        しかし、 RC5 のように多くの人の協力が得られれば実はできるんじゃないかとも思ったわけです。
        上で述べた枝狩りのテクニックですが、実は最初の一手は四箇所にできるように見えますが、実は一箇所しかないです。
        それは盤面を回転、反転させるなどすれば位置関係は同じと見ていいわけです。
        手数の盤面が複数の手を経て同じ状態になる確率はどれくらいかその辺も爆発度合いに関係しそうに思います。
        さらには実際にゲームをしてみると分かりますが、たいていは 10 個所も打てるところがないということも多いわけで、手数の組み合わせは仮に平均 10 個所うてるとして 1e+60 通り、平均 5 個所だと 8.67e+41 と大きくばらつき、この間くらいではないかと勝手に想像しています。

        まぁ、そんなこんなで今(2007年)でも個人ではムリだけど、今なら RC-5 規模なら比較的早く、 10 年したら個人で全手シミュレーションして、この先はどういう手を打っても勝てる、負けるという状態を発見できるようになると思います。
        きっとソレよりも早くどこかの大学で計算機ぶん回す人がいるんじゃないかなぁと。

        シェア
        親コメント
      • > 最大で3^64って所ですね

        豪快に間違えています．

  • タレコミに誤解あり (スコア:0)

    by Anonymous Coward on 2007年07月21日 15時05分 (#1193593)
    ＞かつ相手が完全な動きを行ったとしても、引き分けにできるとのことで、決して負けることがないそうだ。

    もし負けてしまっても、相手が完全な動きをしなかったからだ！と言えるのですね。

    • Re:タレコミに誤解あり (スコア:1, すばらしい洞察)

      by Anonymous Coward on 2007年07月23日 10時12分 (#1194463)
      > もし負けてしまっても、相手が完全な動きをしなかったからだ！と言えるのですね。

      > > 相手が完全な動きを行ったとしても

      相手が完全な動きを行った場合、でない所に注目。
      # というか日本語頑張れ
      シェア
      親コメント
typodupeerror

最初のバージョンは常に打ち捨てられる。