
G検定受験note(10/29)【探索・推論④ブルートフォース⑤Mini-Max法⑥αβ法】
G検定の受験のためにつけた、文字通りのノートです。
Hermes Agent(Grok 4.7)に噛み砕いて解説してもらっています!(^^)v
AIは間違うので、活用は自己責任でお願いします!(^^;
ブルートフォース
芯は一つ。ルール上できる手を、工夫せず、片っ端から試す。近道も、当たりも、先に決めない。
家の鍵をなくしたとき、いつもの場所を先に見ない。ポケットも、引き出しも、靴の中も、ルール上ありうる場所を全部開ける。幅優先探索や深さ優先探索は、その全部をどの順で開けるかだ。ブルートフォースは、開け方の名前ではなく、残さず試す、というやり方の名前だ。
だから、ゴールが木のどこかにあれば、いつか見つかる。その代わり、分かれ道が増えるほど、試す手数は急に増える。三叉路が十回続くと、通り道は三の十乗になる。頭のよさで枝を切る話ではない。人が書いたルールの中を、機械が尽くす。データから近道を覚える話でもない。
幅と深さは、この尽くし方の歩き方だ。ブルートフォースだから最短、とは限らない。最短の手数を保証しやすいのは、同じ深さを先に尽くす幅の方だ。
Exam Points
- ブルートフォースは、合法な手を、近道を使わずに全部試す。
- 幅優先探索と深さ優先探索は、その全部を歩く順番だ。ブルートフォースそのものではない。
- 答えが木の中にあれば見つかる。分かれ道が増えると、試す数は急に増える。
- 人が書くのは、合法な一手のルールだ。機械は、その中を尽くす。
- 最短の手数を保証するのは、ブルートフォースという名前ではない。それに合いやすいのは、幅優先探索だ。
Mini-Max法
芯は一つ。自分は多く取りたい。相手は、それを少なくしたい。相手は、親切に負けてくれない。
お菓子が四箱ある。中身は、3個、1個、2個、4個。先に選ぶのは、わたしだ。ただし、箱を直接は選べない。先にドアを二つから選ぶ。ドアの向こうで、相手が箱を一つ残す。
左のドアの向こうは、3個と1個だ。相手は、わたしの個数を少なくしたい。だから、3個は渡さない。残すのは、1個だ。
右のドアの向こうは、2個と4個だ。相手は、ここでも少なくする。4個は渡さない。残すのは、2個だ。
わたしは、そのあとで選ぶ。左を選ぶと、相手の手で1個になる。右を選ぶと、相手の手で2個になる。4個が右にあるから右、ではない。4個は、相手が渡さない。残る1個と2個を比べて、大きい方の右を選ぶ。取れるのは、2個だ。
これが、全部だ。先に相手の意地悪を読んで、そのあとで自分の得を最大にする。相手がうっかり4個を渡すなら、実際はもっと多くなる。この読みが保証するのは、相手も最善のときだ。
このやり方の名前が、Mini-Max法だ。相手の段が、最小。わたしの段が、最大。チェスの先読みも、このお菓子と同じ形だ。ルールと、箱の中の個数は、人が書く。機械は、その中を尽くす。
Exam Points
- 自分の番は、残る点数の大きい方を選ぶ。相手の番は、自分の点数が小さくなる方を選ぶ。
- 木の奥に大きい点数があっても、相手が渡さないなら、それは取れない。
- 先に相手の段を読んでから、自分の段を選ぶ。
- 保証するのは、相手も最善を尽くしたときの点数だ。相手がミスすれば、実際はもっと良くなり得る。
- 人が書くのは、ルールと、箱の中の点数だ。機械は、その読みを尽くす。
αβ法
芯は一つ。相手が絶対に渡さない箱は、開けなくてよい。読みの結果は、全部開けたときと同じだ。
さっきの四箱を、右から見る。右のドアの向こうは、2個と4個だ。相手は少なくするので、4個は渡さない。右を選ぶと、2個が残る。わたしは、もう「2個は取れる」と知っている。
次に、左のドアを少しだけ開ける。最初の箱は、1個だ。相手は、わたしの個数を少なくしたい。1個を渡せるなら、もう一方が100個でも、相手は1個を残す。左を選ぶと、1個より多くはならない。
だから、左のもう一つの箱は、開けない。100個でも、0個でも、わたしの選択は変わらない。右の2個の方が、大きい。取るのは、右のままだ。
全部開けたときの答えも、2個だった。αβ法は、新しい読みではない。Mini-Max法で、結果が変わらない箱を飛ばす。運が悪いと、ほとんど飛ばせない。そのときも、答えは同じだ。変わるのは、開けた箱の数だけだ。
Exam Points
- αβ法は、Mini-Max法の読みから、結果が変わらない枝を飛ばす。
- 全部開けたときと、相手も最善なら、残る点数は同じだ。
- すでに2個を確保しているなら、相手が1個にできるドアの奥は、開けなくてよい。
- 見る順番で、飛ばせる箱の数は変わる。最終的な選択は、変わらない。
- 新しい評価の方法ではない。人が書くルールと、箱の中の点数は、Mini-Max法のまま。