サンプル問題科目B 問15 - 基本情報技術者試験問題を解いてみる

三目並べにおいて自分が勝利する可能性が最も高い手を決定する。次の手順で，ゲームの状態遷移を木構造として表現し，根以外の各節の評価値を求める。その結果，根の子の中で最も評価値が高い手を，最も勝利する可能性が高い手とする。自分が選択した手を○で表し，相手が選択した手を×で表す。

(1) 現在の盤面の状態を根とし，勝敗がつくか，引き分けとなるまでの考えられる全ての手を木構造で表現する。

(2) 葉の状態を次のように評価する。

① 自分が勝ちの場合は 10

② 自分が負けの場合は－10

③ 引き分けの場合は 0

(3) 葉以外の節の評価値は，その節の全ての子の評価値を基に決定する。

① 自分の手番の節である場合，子の評価値で最大の評価値を節の評価値とする。

② 相手の手番の節である場合，子の評価値で最小の評価値を節の評価値とする。

ゲームが図の最上部にある根の状態のとき，自分が選択できる手は三つある。そのうち A が指す子の評価値は [ a ] であり，B が指す子の評価値は [ b ] である。

とにかく、問題文を読んで理解するのに時間がかかりますね。

ただ、ずいぶん昔に遊びでこの種のプログラムを作った記憶があります。「アルファ・ベータ枝刈り」というような名前だった気がしましたが、検索してみると少し違いました。この問題はミニマックス法を用いていて、私が作ったプログラムはアルファ・ベータ法を用いたのでした。

考え方は簡単で、次のようにします。問題文に書いてあるとおりです。

すると今回の問いはどちらも相手の手番なので、[ a ] は評価値0と10の小さい方を選んで0、[ b ] は評価値-10と0の小さい方を選んで-10になります。

問題が大がかりで解くのに手間がかかりそうに見えますが、実は難しくない問題でした。

ア