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

カスパロフ対DEEP JUNIORの最終結果は引き分け」記事へのコメント

  • by Anonymous Coward
    チェスや将棋のように、「過去の経験」が配列として格納できる場合、
    計算機でもDPマッチング [google.co.jp]により「直観」を実現することは可能です。
    • DP はあくまで greedy なアプローチで、最適解が得られるのは P に属する問題に限られます。さらに DP を適用して最適解を得るには、そもそも対象の問題がある特定の構造("the optimal substructure" とか "the structure of optimality" とか呼ばれる)を持たなければなりません。つまり、どの状態もその近隣の状態に非常に単純な形で依存する必要があります。

      あきらかにチェスや将棋にはそういった構造がありませんし、おそらく P で解ける問題でもないでしょう。したがって DP
      • by yu-na (10754) on 2003年02月09日 15時43分 (#254731) 日記
        "P" って何ですか?

        チェスとかにDPを適用する場合の難点は、
        ・相手がいる。(マルチエージェント)
        ・状態空間が膨大で計算量が大きい。
        という事だと思います。
        仮に、相手がある局面において決まったの手を打つと仮定すれば
        計算量は別にして、その仮定の元で最適解が得られます。
        MDP(Markov Decision Problem)だから、 Bellman 方程式を解けばよいだけです。
        本当は、相手によって最適な戦略は変わってしまいますが。

        "決まった手"と言うのは、Aを0.5、Bを0.3、Cを0.2の割合で
        選択するといった確率的なものでも構いません。
        ただし、その確率が変わる(これを相手が学習する言う)場合には、
        MDPではなくなってしまいます。

        実際には相手が居るので、例えば MIN-MAX法 [kyoto-u.ac.jp]とか
        を使ったりして、ゴリゴリすることになるのでしょう。
        # 解けるかどうか分かりませんが、できたとしても。

        ところで、254490さんの
        >> チェスや将棋のように、「過去の経験」が配列として格納できる場合、
        は、 Profit sharing [google.com] とか言われます。強化学習でも良いか。
        配列を覚えておく必要はありませんが。
        ベルマン方程式を状態遷移確率で解くか(DP:DynamicPrograming)、
        サンプル系列から解くか(Profit Sharing、Reinforcement Learning)
        見たいな違いですが。
        親コメント
        • 仮に、相手がある局面において決まったの手を打つと仮定すれば
          その「決まった手」っていうのが全域最適手だとしても、現状では求めることさえできない訳ですよね。
          • > その「決まった手」っていうのが全域最適手だとしても、
            > 現状では求めることさえできない訳ですよね。
            そうですね。これでは状態遷移確率が求められませんので、
            >> MDP(Markov Decision Problem)だから、 Bellman 方程式を解けばよいだけです。
            は明らかに間違いです。m(_ _)m
            状態遷移確率が固定であっても、不明だとDPは解けませんね。

            #強化学習なら可能ですが。
            親コメント

Stay hungry, Stay foolish. -- Steven Paul Jobs

処理中...