-PR-
解決
済み

ゲーム木探索について教えてください。

  • 困ってます
  • 質問No.94604
  • 閲覧数321
  • ありがとう数1
  • 気になる数0
  • 回答数3
  • コメント数0

お礼率 0% (0/6)

次のような問題が出たのですが、解けなくて困っています。

「ゲーム木の深さ(根から葉までの最大距離)がh、葉以外の状態の子の数が常に2個であるとしたとき、ゲーム木の状態数とhにはどのような関係がありますか。子の数が葉を除いて常にb個であるとしたらどうでしょう。」

どなたか助けてください。
また、このような問題を解くのには、どのような本を参考にしたらよいのでしょうか?教えてください。
通報する
  • 回答数3
  • 気になる
    質問をブックマークします。
    マイページでまとめて確認できます。

質問者が選んだベストアンサー

  • 回答No.3
レベル14

ベストアンサー率 57% (1014/1775)

題意をもう少し正確な文章で表すとどうなるんでしょう?
・ここで問題にしているゲームの木は、木である。
   ノードは葉でないか、葉である。
   根(root)であるノードが1個だけある。根であるノードは葉でない。
・葉でないノードに、もし葉でないノードがぶら下がっているならば、ぶら下がっている葉でないノードの数は必ず2である。
こういう意味?

すると、
●葉でないノードが根を除いて偶数個あるのは間違いありません。根を含めると必ず奇数個です。
●深さhのとき、葉でないノードの数の最小値と最大値は幾らになるか。
 根を含めて、最小は2h+1、最大は1+2+4+.....+2^(h-1) = (2^h)-1
です。

さらに、葉でも根でもないノードの数がb個であるという制限を付けると、
●bが奇数の場合:そういうことは起こりません。
●bが偶数の場合:2h≦b≦(2^h)-2 以外の場合は生じ得ない、という以上のことは特に何も言えませんね。

ゲームの木だからゲーム理論、というのは必ずしも当たらない。ゲームの木は多くの場合、完全情報ゲームを想定していて、ゲーム理論とはちょっと条件が違います。むしろグラフ理論と探索(search)の理論が該当するでしょう。後者は特に古典的人工知能において主題だった問題です。
-PR-
-PR-

その他の回答 (全2件)

  • 回答No.1
レベル8

ベストアンサー率 42% (16/38)

プログラミング系の書籍でアルゴリズムについて書いてある本(例えば「C言語とアルゴリズム」みたいな)で「二分木」の項をみれば参考になると思います。
プログラミング系の書籍でアルゴリズムについて書いてある本(例えば「C言語とアルゴリズム」みたいな)で「二分木」の項をみれば参考になると思います。


  • 回答No.2
レベル14

ベストアンサー率 30% (2593/8599)

状態数が何を表すのか判りません。葉の数、ノード数は次の通りです。 葉の数=b^h ノード数=(b^(h+1)-1)/(b-1) 2分木の時はbに2を入れて下さい。 ゲーム木というのは囲碁、将棋、チェスなどの2人ゲームの戦略決定に使うのですね。そうだとすると2分木の探索法は参考になるとしても、戦略面では、2分木のアルゴリズムよりも、むしろ、「ゲームの理論」の方が参考になるでしょう。ミニマックス法 ...続きを読む
状態数が何を表すのか判りません。葉の数、ノード数は次の通りです。
葉の数=b^h
ノード数=(b^(h+1)-1)/(b-1)
2分木の時はbに2を入れて下さい。

ゲーム木というのは囲碁、将棋、チェスなどの2人ゲームの戦略決定に使うのですね。そうだとすると2分木の探索法は参考になるとしても、戦略面では、2分木のアルゴリズムよりも、むしろ、「ゲームの理論」の方が参考になるでしょう。ミニマックス法などがそれです。ただゲームの理論だけではおそらく不足でしょう。
実際には多分木を扱うことになるのでしょうね。
上の式を導くだけなら数学の等比級数の和の公式だけで充分でしょう。

回答は式の計算と図解(深さ2の2分木とb分木)をしてご確認下さい。
ゲーム木については下記URLを参考にしました。
このQ&Aで解決しましたか?
関連するQ&A
-PR-
-PR-
このQ&Aにこう思った!同じようなことあった!感想や体験を書こう
このQ&Aにはまだコメントがありません。
あなたの思ったこと、知っていることをここにコメントしてみましょう。

その他の関連するQ&A、テーマをキーワードで探す

キーワードでQ&A、テーマを検索する
-PR-
-PR-
-PR-

特集


関連するQ&A

-PR-

ピックアップ

-PR-
ページ先頭へ