読み手数と組合せ爆発
A社は、社内のボードゲーム大会で使う対戦AIを試作している。このゲームでは1手ごとに平均30通りの指し手がある。10手先までのすべての手順を調べる全探索では、調べる局面(手順の末端)はおよそ何通りになるか。最も適切なものを1つ選べ。
- A
約1.0×10^30通り
- B
約2.0×10^13通り
- C
約300通り
- D
約5.9×10^14通り
正解と解説を見る
正解:D
探索で調べる局面の数は、分岐数を深さの回数だけ掛けた値になり、指数関数的に増える(組合せ爆発)。そのため実際の対戦AIでは、評価関数で局面の良し悪しを見積もり、有望でない手を枝刈りして探索を絞る。
- A
誤り。10^30は、底と指数を入れ替えた値である。正しくは30^10。
- B
誤り。30^9≒1.97×10^13で、掛ける回数が1回足りない。10手先までなら30を10回掛ける。
- C
誤り。30×10と、掛け算ではなく足し算のように数えている。分岐は手を進めるたびに掛け合わされる。
- D
正しい。1手ごとに30通りに分かれるので、30を10回掛けて30^10=3^10×10^10=59,049×10^10≒5.9×10^14通りになる。
このサイトの問題は、各試験の公開されているシラバスに沿って作ったオリジナルの模擬問題です。本試験の問題ではありません。日本ディープラーニング協会(JDLA)・一般社団法人生成AI活用普及協会(GUGA)の公式サービスではありません。