平成２０年度 技術士第一次試験問題【専門科目】
Ⅳ－１５
将棋のように2人が交互に1手ずつ指し、相互の意思決定 (もしくは展開) がすべて与えられる完全情報ゲームの対戦アルゴリズムについて考える。いま、先手番のある局面Ｘにおいて、先手がとりうる手は
a、b、c、dの4つある。このうちの最適の手を求めるために、3手先までの先読みを行ったところ、下図のようなゲーム木が得られた。○内の数字は3手先の後手番の局面における評価値であり、数値が大きいほど先手が有利であることを示す。ミニマックス法を用いた場合、局面Ｘでの先手の最適な手として選ばれるものは、①～⑤のうちのどれか。
① a ② b ③ b ④ d
⑤ 最適な手は一意に定まらない
正解
④
解説
ミニマックス法は、想定される最大損害が最小になるような選択肢を選択する方法である。
3手先の後手番の局面における評価値の最も大きい方が、2手先の先手番の局面における評価値となるように選択する。つまり、左から順に以下のとおりとなる。
5、2 1 3、-1、6 4、3
2手先の先手番の局面における評価値の最も小さい方が、1手先の後手番の局面における評価値となるように選択する。
つまり、左から順に以下のとおりとなる。
2、 1、 -1、 3
1手先の後手番の局面における評価値の最も大きい方が、今の先手番の局面における評価値となるように選択する。
つまり 3 を選択する。
従って、先手の最適な手は d である。
| Ⅳ－１４ | 目次 | Ⅳ－１６ |