基本情報技術者試験のサンプル問題（科目B）を解いてみよう。
今回のテーマは、「三目並べ」である。
三目並べにおいて自分が勝利する可能性が最も高い手を決定する。次の手順で，ゲームの状態遷移を木構造として表現し，根以外の各節の評価値を求める。その結果，根の子の中で最も評価値が高い手を，最も勝利する可能性が高い手とする。自分が選択した手を○で表し，相手が選択した手を×で表す。
〔手順〕
(1) 現在の盤面の状態を根とし，勝敗がつくか，引き分けとなるまでの考えられる全ての手を木構造で表現する。
(2) 葉の状態を次のように評価する。
① 自分が勝ちの場合は10
② 自分が負けの場合は－10
③ 引き分けの場合は0
(3) 葉以外の節の評価値は，その節の全ての子の評価値を基に決定する。
① 自分の手番の節である場合，子の評価値で最大の評価値を節の評価値とする。
② 相手の手番の節である場合，子の評価値で最小の評価値を節の評価値とする。
正解：ア
「三目並べ（○×ゲーム）におけるミニマックス法の適用」に関する問題である。
問題の概要
この問題は、三目並べ（Tic-Tac-Toe）を題材にしたゲームAIの評価アルゴリズムに関する内容である。ゲームの状態遷移を木構造で表現し、最も勝率の高い手を選ぶ手法として「ミニマックス法」が使われている。
ゲームのルールと評価値
三目並べの各ゲーム終了状態には評価値が与えられる。
評価値とは？
「評価値」とは、「その局面がどれだけ良いか・悪いか」を数値で表したものである。
・○が勝つ → +10
・引き分け → 0
・×が勝つ → -10
プレイヤー（○）が打つ手として「A」「B」「C」の選択肢があり、それぞれの手から先を辿ることで評価値が決まる。
ミニマックス法の考え方
ミニマックス法とは？
ミニマックス法は、ゲーム木において「相手は最善の手を打ってくる」と仮定し、最も有利な手を選ぶ戦略である。
名前の由来は、「自分は最大（Max）を選び、相手は最小（Min）を選ぶ」から「Minimax」から取られている。
なお、各ノード（状態）の評価方法は次の通りである。
評価値の決め方（ミニマックス法）
・自分の手番（Maxノード）では、子ノードのうち最大の評価値を選ぶ
・相手の手番（Minノード）では、子ノードのうち最小の評価値を選ぶ
つまり、「自分は最大の利益を得るように選び、相手は自分にとって最悪の選択をする」と仮定して最良の手を導いていく。
（補足）ゲーム木（Game Tree）
- ゲームの進行を木構造で表現。
- 各ノードが盤面の状態、枝が手の選択肢。
- 葉ノード（末端）には評価値（スコア）をつける。
AとBの評価値の決定
Aの手
Aの次は相手（×）の手番。
相手が選べる手の評価値は「0」と「10」。
相手は自分にとって最悪の手を選ぶ → 最小値を選ぶ。
よって、Aの評価値は 0。
Bの手
Bの次も相手の手番。
相手が選べる手の評価値は「−10」と「0」。
相手は自分にとって最悪の手を選ぶ → 最小値を選ぶ。
よって、Bの評価値は −10。
正解は、
a = 0, b = −10
となる。
（補足）手A・手B・手Cの評価値のまとめ
◎ 手A
→ 相手の選択肢は「引き分け（0）」と「○の勝ち（10）」
→ 最小値（Min）を選ぶ → 0
→ 手Aの評価値は「0」
◎ 手B
→ 相手の選択肢は「引き分け（0）」と「×の勝ち（-10）」
→ 最小値（Min）を選ぶ → -10
→ 手Bの評価値は「-10」
◎ 手C
→ 相手の選択肢は「○の勝ち（10）」
→ 最小値（Min）を選ぶ →10
→ 手Cの評価値は「10」
このように、ミニマックス法を使うことで、最も不利な展開を避けながら最善の手を見つけることができる。
それでは、本問の状態遷移図に準拠し、固定的なミニマックス法によって評価値を確認できるC言語コードをご紹介しよう。
C言語のコードで本問を確認してみよう！
#include <stdio.h>
// 評価値を計算する（勝ち：10、引き分け：0、負け：-10）
int evaluate_result(int result_code) {
if (result_code == 1) return 10; // ○の勝ち
if (result_code == -1) return -10; // ○の負け
return 0; // 引き分け
}
// 相手（Min）の選択：最小評価値を選ぶ
int opponent_move(int outcomes[], int count) {
int min = 1000;
for (int i = 0; i < count; i++) {
int score = evaluate_result(outcomes[i]);
if (score < min) min = score;
}
return min;
}
// 手A：○の勝ち or 引き分け → Minの評価値 = 0
int evaluate_A() {
int outcomes[] = {1, 0}; // ○の勝ち or 引き分け
return opponent_move(outcomes, 2);
}
// 手B：○の負け or 引き分け → Minの評価値 = -10
int evaluate_B() {
int outcomes[] = {-1, 0}; // ○の負け or 引き分け
return opponent_move(outcomes, 2);
}
// 手C：○の勝ちが即確定 → 評価値 = 10
int evaluate_C() {
return evaluate_result(1); // ○の勝ち
}
// 手を入力してその評価値を表示
void select_and_evaluate_move() {
char input;
printf("A・B・Cのいずれかの手を選んでください: ");
scanf(" %c", &input); // 空白に注意して改行をスキップ
int score;
switch (input) {
case 'A':
case 'a':
score = evaluate_A();
printf("手Aを選びました。評価値は %d です。\n", score);
break;
case 'B':
case 'b':
score = evaluate_B();
printf("手Bを選びました。評価値は %d です。\n", score);
break;
case 'C':
case 'c':
score = evaluate_C();
printf("手Cを選びました。評価値は %d です。\n", score);
break;
default:
printf("A・B・Cのいずれかを選択してください。\n");
}
}
int main() {
select_and_evaluate_move();
return 0;
}実行結果
A・B・Cのいずれかの手を選んでください: A
手Aを選びました。評価値は 0 です。
A・B・Cのいずれかの手を選んでください: B
手Bを選びました。評価値は -10 です。このコードで、選んだ手に応じて評価値を確認できる。
コメント