基本情報技術者試験〔科目B〕演習 2022年サンプル問題 問15（木構造）
問15（木構造）
次の記述中の□a と□b に入れる正しい答えの組み合わせを、解答群の中から選べ。
三目並べにおいて自分が勝利する可能性が最も高い手を決定する。次の手順で、ゲームの状態遷移を木構造として表現し、根以外の各節の評価値を求める。その結果、根の子の中で最も評価値が高い手を、最も勝利する可能性が高い手とする。自分が選択した手を〇で表し、相手が選択した手を×で表す。
〔手順〕
(1) 現在の盤面の状態を根とし、勝敗が付くか、引き分けとなるまでの考えられる全ての手を木構造で表現する。
(2) 葉の状態を次のように評価する。
① 自分が勝ちの場合は10
② 自分が負けの場合は -10
③ 引き分けの場合は 0
(3) 葉の以外の節の評価値は、その節の全ての子の評価値を基に決定する。
① 自分の手番の節である場合、子の評価値で最大の評価値を節の評価値とする。
② 相手の手番の節である場合、子の評価値で最小の評価値を節の評価値とする。
ゲームが図の最上部にある根の状態の時、自分が選択できる手は三つある。そのうちAが指すこの評価値は□a であり、Bが指す子の評価値は□b である。
解答群： a: 0 b: -10
解説
1. 問題の考え方
三目並べのゲームで、「次にどこに打てば勝ちやすいか」を判断するために、考えられる全ての手を 木構造（ツリー） にして整理する。
この時、「どの手が良いか」を評価する方法が ミニマックス法 である。
2. 木構造の見方
問題の図では、
一番上（根の状態） が現在の盤面
そこから 3つの手（A・B・もう1つ） に分岐
さらに、それぞれの手から相手の手番に分岐
このようにして、ゲームのすべての展開を 木のように広げる 方法を使う。
3. 葉の評価値
まず、一番下の「ゲームが終了している状態」（葉ノード）に数値をつける。
評価値のルールは以下の通りである：
自分が勝っている → 10
自分が負けている → -10
引き分け → 0
4. 親ノードの評価値の決め方
① 相手の手番（×が打つターン）
→ 相手は自分を負かしたいので、できるだけ悪い（最小の）評価を選ぶ
つまり、そのノードの子の評価値の中で最も小さいものを選ぶ。
② 自分の手番（〇が打つターン）
→ 自分は勝ちたいので、できるだけ良い（最大の）評価を選ぶ
つまり、そのノードの子の評価値の中で最も大きいものを選ぶ。
5. AとBの評価値の決め方
Aの評価値（□a）
Aの次の相手の手番を見ると、相手が打てる盤面が2つある。
1つは引き分け（評価値 0）
1つは自分の勝ち（評価値 10）
相手の手番では最小の値を選ぶので、
Min(0, 10) = 0
よって、Aの評価値（□a）は 0。
Bの評価値（□b）
Bの次の相手の手番を見ると、相手が打てる盤面が2つある。
1つは引き分け（評価値 0）
1つは自分の負け（評価値 -10）
相手の手番では最小の値を選ぶので、
Min(0, -10) = -10
よって、Bの評価値（□b）は -10。
6. 答え
a = 0
b = -10
まとめ
ミニマックス法は、
自分の手番なら「最大値を選ぶ」
相手の手番なら「最小値を選ぶ」
というシンプルなルールで手を選ぶ方法である。
この問題では、AとBの評価値を決めるために、相手が選ぶ手 を考えて、最も小さい評価値を取ることがポイントである。
補足
三目並べ（Tic-Tac-Toe）とは？
三目並べ（Tic-Tac-Toe）は、2人で遊ぶシンプルなボードゲームである。
プレイヤーは交互に「○」または「×」を空いているマスに置いて、縦・横・斜めのいずれかに3つ並べることを目指す。
1. ルール
① 3×3のマス（9マス）を使う
9つのマス目がある盤面を使う。
② 「○」と「×」を交互に置く
1人目のプレイヤー → 「○」
2人目のプレイヤー → 「×」
交互に空いているマスに記号を置いていく。
③ 3つそろえたら勝ち
縦・横・斜めのいずれかに3つ並べた人が勝ち になる。
④ 全部埋まっても勝敗がつかない場合は引き分け
すべてのマスが埋まっても「○」か「×」が3つ並ばなかった場合、引き分け である。
2. 戦略の基本
真ん中（中央）を取るのが有利
真ん中を取ると、勝ち筋が増えるため有利。
相手の勝ちを防ぐ
相手が次の一手で勝ちそうなら、そのマスを先に埋める。
2つ並んだらすぐ3つ目を狙う
例えば、「○○」と並んだら、3つ目を置いて勝つ。
4. コンピュータでの対戦
三目並べはすべての手を計算できるため、最適な手を選べば必ず負けないゲームである。
これを使った戦略が「ミニマックス法」である。
まとめ
三目並べは○と×を交互に置いて、縦・横・斜めのどれかに3つそろえるゲーム。
9マスしかないのでシンプルだけど、最適な戦略を考えると奥が深い。
コンピュータはミニマックス法を使って最適な手を選ぶ。
Java と Python で三目並べの問題を解くコード（ミニマックス法を使った最適手の計算）をコーディング
以下のコードは、盤面を評価し、最も勝率の高い手を決定する プログラムである。
Java 実装
import java.util.*;
class TicTacToe {
static final int PLAYER = 1; // 自分（○）
static final int OPPONENT = -1; // 相手（×）
static final int EMPTY = 0;
static int[][] board = {
{1, -1, 1},
{-1, -1, 0},
{0, 0, 0}
};
public static void main(String[] args) {
int[] bestMove = findBestMove(board);
System.out.println("最適な手: (" + bestMove[0] + ", " + bestMove[1] + ")");
}
static int[] findBestMove(int[][] board) {
int bestVal = Integer.MIN_VALUE;
int[] bestMove = {-1, -1};
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == EMPTY) {
board[i][j] = PLAYER;
int moveVal = minimax(board, 0, false);
board[i][j] = EMPTY;
if (moveVal > bestVal) {
bestMove[0] = i;
bestMove[1] = j;
bestVal = moveVal;
}
}
}
}
return bestMove;
}
static int minimax(int[][] board, int depth, boolean isMax) {
int score = evaluate(board);
if (score == 10 || score == -10) return score;
if (!isMovesLeft(board)) return 0;
if (isMax) {
int best = Integer.MIN_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == EMPTY) {
board[i][j] = PLAYER;
best = Math.max(best, minimax(board, depth + 1, false));
board[i][j] = EMPTY;
}
}
}
return best;
} else {
int best = Integer.MAX_VALUE;
for (int i = 0; i < 3; i++) {
for (int j = 0; j < 3; j++) {
if (board[i][j] == EMPTY) {
board[i][j] = OPPONENT;
best = Math.min(best, minimax(board, depth + 1, true));
board[i][j] = EMPTY;
}
}
}
return best;
}
}
static boolean isMovesLeft(int[][] board) {
for (int i = 0; i < 3; i++)
for (int j = 0; j < 3; j++)
if (board[i][j] == EMPTY)
return true;
return false;
}
static int evaluate(int[][] b) {
for (int row = 0; row < 3; row++) {
if (b[row][0] == b[row][1] && b[row][1] == b[row][2]) {
if (b[row][0] == PLAYER) return 10;
if (b[row][0] == OPPONENT) return -10;
}
}
for (int col = 0; col < 3; col++) {
if (b[0][col] == b[1][col] && b[1][col] == b[2][col]) {
if (b[0][col] == PLAYER) return 10;
if (b[0][col] == OPPONENT) return -10;
}
}
if (b[0][0] == b[1][1] && b[1][1] == b[2][2]) {
if (b[0][0] == PLAYER) return 10;
if (b[0][0] == OPPONENT) return -10;
}
if (b[0][2] == b[1][1] && b[1][1] == b[2][0]) {
if (b[0][2] == PLAYER) return 10;
if (b[0][2] == OPPONENT) return -10;
}
return 0;
}
}
Python 実装
import numpy as np
PLAYER = 1 # 自分（○）
OPPONENT = -1 # 相手（×）
EMPTY = 0
board = np.array([
[1, -1, 1],
[-1, -1, 0],
[0, 0, 0]
])
def find_best_move(board):
best_val = -float('inf')
best_move = (-1, -1)
for i in range(3):
for j in range(3):
if board[i][j] == EMPTY:
board[i][j] = PLAYER
move_val = minimax(board, 0, False)
board[i][j] = EMPTY
if move_val > best_val:
best_move = (i, j)
best_val = move_val
return best_move
def minimax(board, depth, is_max):
score = evaluate(board)
if score in [10, -10]:
return score
if not is_moves_left(board):
return 0
if is_max:
best = -float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == EMPTY:
board[i][j] = PLAYER
best = max(best, minimax(board, depth + 1, False))
board[i][j] = EMPTY
return best
else:
best = float('inf')
for i in range(3):
for j in range(3):
if board[i][j] == EMPTY:
board[i][j] = OPPONENT
best = min(best, minimax(board, depth + 1, True))
board[i][j] = EMPTY
return best
def is_moves_left(board):
return np.any(board == EMPTY)
def evaluate(board):
for row in range(3):
if np.all(board[row, :] == PLAYER):
return 10
if np.all(board[row, :] == OPPONENT):
return -10
for col in range(3):
if np.all(board[:, col] == PLAYER):
return 10
if np.all(board[:, col] == OPPONENT):
return -10
if np.all(np.diag(board) == PLAYER) or np.all(np.diag(np.fliplr(board)) == PLAYER):
return 10
if np.all(np.diag(board) == OPPONENT) or np.all(np.diag(np.fliplr(board)) == OPPONENT):
return -10
return 0
best_move = find_best_move(board)
print(f"最適な手: {best_move}")
解説
minimax 関数: ミニマックス法を使い、最適な手を探索
evaluate 関数: 盤面の評価（勝ち → 10、負け → -10、引き分け → 0）
is_moves_left 関数: まだ打てる場所があるか判定
find_best_move 関数: 最適な手を見つける
どちらのコードも、現在の盤面から最も勝率の高い手を決定するアルゴリズムを実装している。
Javaは二重ループで処理し、Pythonはnumpyを使ってシンプルにしている。
コードの実行結果：最適な手: (1, 2)
出力結果の解説
(1, 2) という出力は、「最適な手が、盤面の 1 行目（0-indexed）・2 列目（0-indexed）の位置にある」 という意味である。
Java コードでは、配列のインデックスは 0 から始まるので、
実際の 三目並べの盤面 で見ると 「2 行目・3 列目」 になる。
1. 盤面の確認
コードの board 配列は、以下のような 3×3 の盤面である。
0 1 2
0 O | X | O
------------
1 X | X | .
------------
2 . | . | .
1 (O) は プレイヤー の手
-1 (X) は 相手 の手
0 (.) は 空きマス
2. (1, 2) の位置
出力された (1, 2) を 0-indexed で考える と、「2 行目・3 列目（右上のマス）」 を表す。
1 2 3
1 O | X | O
------------
2 X | X | ◎ ← ここ
------------
3 . | . | .
つまり、このマスに O を置くのが最適な手 という意味になる。
3. その手が最適な理由
(1, 2) に O を置くことで、次のターンで勝てる。
例えば (2, 0) や (2, 1) に置いても、即勝ちはできない。
ミニマックス法 により、「相手が最善手を打っても、自分が最も有利になる手」を選ぶ。
このようなロジックに基づいて、 (1, 2) のマスが選ばれた。
4. まとめ
(1, 2) の意味：2 行目・3 列目のマスに O を置くのが最適
最適な手とは：自分が最も有利になる手を選択した結果
Java の 0-indexed 表記 なので、人間の感覚では (2, 3) の位置
以上。