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

質問

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

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

どなたか助けてください。
また、このような問題を解くのには、どのような本を参考にしたらよいのでしょうか？教えてください。

回答No.3

stomachman · ベストアンサー

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

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

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

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

回答No.2

ymmasayan

状態数が何を表すのか判りません。葉の数、ノード数は次の通りです。
葉の数＝ｂ＾ｈ
ノード数＝（ｂ＾（ｈ＋１）－１）／（ｂ－１）
２分木の時はｂに２を入れて下さい。

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

回答は式の計算と図解（深さ２の２分木とｂ分木）をしてご確認下さい。
ゲーム木については下記ＵＲＬを参考にしました。

参考URL：

http://www.csci.yamanashi.ac.jp/~suzu/file.html

回答No.1

JitF

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