見出し画像
Photo by ki_sn0te

基本情報技術者試験の科目BをJavaとPythonのプログラムで考える　No.25

増田直実

基本情報技術者試験で出題されるプログラム言語が疑似言語に変更されましたね。合格に向けて学習を進めるにおいては、やはり普段から使っているプログラム言語に置き換えて考えてみたいですよね。
このサイトでは、IPA情報処理推進機構で公開されている科目Bのプログラミングの問題を中心に、疑似言語をJavaとPythonのコードに置き換えて解説していきます。
１日１問の解説を発信していく予定です。基本情報技術者試験の合格を目指されている方のお役に立てれば幸いです。

基本情報技術者試験 科目 B サンプル問題（2022年12月公開）

https://www.ipa.go.jp/shiken/syllabus/henkou/2022/ssf7ph000000h5tb-att/fe_kamoku_b_set_sample_qs.pdf

問１５　三目並べを木構造で考える

この問題は、三目並べの状態の変化を木構造で表現しています。

木構造とは
木の形をしたデータの整理方法の一つです。
木には根っこがあって、そこから枝が伸びていきますよね。

　「根」
　　木構造では、1つの「親」の部分（これを「根」と呼びます）が、
　　「子ども」を持つことができます。
　　この「親」と「子ども」の関係が、
　　木が上から下に広がるように続いていきます。

　「節」
　　「親」と「子ども」のそれぞれを「節」と呼びます。

　「葉」
　　木構造の一番端っこにあり、もう子を持たない節を「葉」といいます。
　　木で言うと枝の先にある葉っぱの部分です。

三目並べにおいて自分が勝利する可能性が最も高い手を木構造で考えます。
全ての節における評価値を求めます。

〔手順〕
(1) 現在の盤面の状態を根とし，勝敗がつくか，引き分けとなるまでの考えられる全ての手を木構造で表現します。
(2) 勝負がつくと、葉の状態になりますが、次のように評価します。
　　① 自分が勝ちの場合は 10
　　② 自分が負けの場合は－10
　　③ 引き分けの場合は 0
(3) 葉以外の節の評価値は，その節の全ての子の評価値を基に決定します。
　　① 自分の手番の節である場合
　　　 子の評価値で最大の評価値を節の評価値とする。
　　② 相手の手番の節である場合
　　　 子の評価値で最小の評価値を節の評価値とする。

この問題は、
上記（３）のルールに従って、葉以外の評価値を求めるわけです。

図  三目並べの状態遷移

１．Javaのコードで考えてみよう

package kamokuB;

import java.util.ArrayList;

public class R4_Sample15 {

	// 節ごとの評価値を求める
    public static int minimax(Board board, boolean isMaximizing) {
        int score = board.evaluate();

        // 終端ノードの場合は評価値を返す
        if (score == 10 || score == -10 || !board.isMovesLeft()) {
            return score;
        }

        // 自分（O）の手番の場合は最大の評価値を選択
        if (isMaximizing) {
            int best = Integer.MIN_VALUE;
            for (Board child : board.getChildren(Board.PLAYER_O)) {
                best = Math.max(best, minimax(child, false));
            }
            return best;
        } else { // 相手（X）の手番の場合は最小の評価値を選択
            int best = Integer.MAX_VALUE;
            for (Board child : board.getChildren(Board.PLAYER_X)) {
                best = Math.min(best, minimax(child, true));
            }
            return best;
        }
    }
    
    // 全ての手の組み合わせを表示（節ごとに勝敗と評価値）
    public static void printAllBoards(Board board, char currentPlayer, int depth) {
        int score = board.evaluate();

        // 終端ノードの場合は評価値を返す
        if (score == 10 || score == -10 || !board.isMovesLeft()) {
            System.out.println("階層 " + depth + " の盤面: " + board.getResult(score));
            board.printBoard();
            return;
        }

        // 子ノードを生成して再帰的に表示
        ArrayList<Board> children = board.getChildren(currentPlayer);
        int bestValue;
        // 自分（O）の手番の場合
        if (currentPlayer == Board.PLAYER_O) {
            bestValue = Integer.MIN_VALUE;
            for (Board child : children) {
                int childValue = minimax(child, false);
                bestValue = Math.max(bestValue, childValue);
            }
        } else { // 相手（X）の手番の場合
            bestValue = Integer.MAX_VALUE;
            for (Board child : children) {
                int childValue = minimax(child, true);
                bestValue = Math.min(bestValue, childValue);
            }
        }

        // 現在のノードの評価値を表示
        System.out.println("階層 " + depth + " の盤面: 評価値 " + bestValue);
        board.printBoard();

        // 子ノードを再帰的に表示
        for (Board child : children) {
            char nextPlayer = (currentPlayer == Board.PLAYER_O) ? Board.PLAYER_X : Board.PLAYER_O;
            printAllBoards(child, nextPlayer, depth + 1);
        }
    }
 
   
    
    public static void main(String[] args) {
    	
    	// 三目並べを実現するインスタンスの生成
        Board board = new Board();
        // 根となる現在の盤面の状態をセット
        char[][] initialState = {
            {Board.PLAYER_X, Board.PLAYER_O, Board.PLAYER_X},
            {Board.PLAYER_X, Board.PLAYER_O, Board.PLAYER_O},
            {Board.EMPTY, Board.EMPTY, Board.EMPTY}
        };
        board.setBoard(initialState);
        // 現在の盤面を表示
        System.out.println("現在の盤面:");
        board.printBoard();
        // 全ての手の組み合わせを表示（節ごとに勝敗と評価値）
        System.out.println("全ての手の組み合わせ:");
        printAllBoards(board, Board.PLAYER_O, 0);
    }
}

package kamokuB;

import java.util.ArrayList;

public class Board {
    public static final int SIZE = 3;
    public static final char EMPTY = '-';
    public static final char PLAYER_X = 'X';
    public static final char PLAYER_O = 'O';

    private char[][] board;

    public Board() {
        // 初期状態の盤面を作成
        board = new char[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                board[i][j] = EMPTY;
            }
        }
    }

    // 盤面に空きマスがあるかを確認
    public boolean isMovesLeft() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == EMPTY) {
                    return true;
                }
            }
        }
        return false;
    }

    // 現在の盤面の状態を評価
    public int evaluate() {
        // 行のチェック
        for (int row = 0; row < SIZE; row++) {
            if (board[row][0] == board[row][1] && board[row][1] == board[row][2]) {
                if (board[row][0] == PLAYER_O)
                    return 10; // Oが勝ち
                else if (board[row][0] == PLAYER_X)
                    return -10; // Xが勝ち
            }
        }

        // 列のチェック
        for (int col = 0; col < SIZE; col++) {
            if (board[0][col] == board[1][col] && board[1][col] == board[2][col]) {
                if (board[0][col] == PLAYER_O)
                    return 10; // Oが勝ち
                else if (board[0][col] == PLAYER_X)
                    return -10; // Xが勝ち
            }
        }

        // 対角線のチェック
        if (board[0][0] == board[1][1] && board[1][1] == board[2][2]) {
            if (board[0][0] == PLAYER_O)
                return 10; // Oが勝ち
            else if (board[0][0] == PLAYER_X)
                return -10; // Xが勝ち
        }

        if (board[0][2] == board[1][1] && board[1][1] == board[2][0]) {
            if (board[0][2] == PLAYER_O)
                return 10; // Oが勝ち
            else if (board[0][2] == PLAYER_X)
                return -10; // Xが勝ち
        }

        // 引き分けの場合
        return 0;
    }

    // 現在の盤面から可能な次の手を生成
    // ただし、すでに勝負がついている場合は空リストを返す
    public ArrayList<Board> getChildren(char player) {
        ArrayList<Board> children = new ArrayList<>();
        if (evaluate() == 10 || evaluate() == -10 || !isMovesLeft()) {
            return children;
        }

        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                if (board[i][j] == EMPTY) {
                    Board child = new Board();
                    child.board = copyBoard();
                    child.board[i][j] = player;
                    children.add(child);
                }
            }
        }
        return children;
    }

    // 現在の盤面を表示
    public void printBoard() {
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                System.out.print(board[i][j] + " ");
            }
            System.out.println("");
        }
        System.out.println("");
    }

    // 盤面の評価結果を返す
    public String getResult(int score) {
        if (score == 10) {
            return "勝ち 評価値 10"; // Oが勝ち
        } else if (score == -10) {
            return "負け 評価値 -10"; // Xが勝ち
        } else if (!isMovesLeft()) {
            return "引き分け 評価値 0";
        }
        return "評価値 " + score;
    }

    // 盤面をコピーする
    private char[][] copyBoard() {
        char[][] newBoard = new char[SIZE][SIZE];
        for (int i = 0; i < SIZE; i++) {
            for (int j = 0; j < SIZE; j++) {
                newBoard[i][j] = board[i][j];
            }
        }
        return newBoard;
    }

    // 盤面に値をセットする
    public void setBoard(char[][] board) {
        this.board = board;
    }
}

２．Pythonのコードで考えてみよう

# R4_Sample15.py モジュール 

import board

# 評価値を計算
def minimax(board_state, is_maximizing):
    score = board.evaluate(board_state)

    # 終端ノードの場合は評価値を返す
    if score in [10, -10] or not board.is_moves_left(board_state):
        return score

    if is_maximizing:
        best = float('-inf')
        for child in board.get_children(board_state, board.PLAYER_O):
            best = max(best, minimax(child, False))
        return best
    else:
        best = float('inf')
        for child in board.get_children(board_state, board.PLAYER_X):
            best = min(best, minimax(child, True))
        return best

# 全ての手の組み合わせを表示（節ごとに勝敗と評価値）
def print_all_boards(board_state, current_player, depth):
    score = board.evaluate(board_state)
    # 終端ノードの場合は評価値を表示して終了
    if score in [10, -10] or not board.is_moves_left(board_state):
        print(f"階層 {depth} の盤面: {board.get_result(board_state, score)}")
        board.print_board(board_state)
        return

    # 子ノードを生成して再帰的に表示
    children = board.get_children(board_state, current_player)
    best_value = None

    if current_player == board.PLAYER_O:
        best_value = float('-inf')
        for child in children:
            child_value = minimax(child, False)
            best_value = max(best_value, child_value)
    else:
        best_value = float('inf')
        for child in children:
            child_value = minimax(child, True)
            best_value = min(best_value, child_value)

    # 現在のノードの評価値を表示
    print(f"階層 {depth} の盤面: 評価値 {best_value}")
    board.print_board(board_state)

    # 子ノードを再帰的に表示
    for child in children:
        next_player = board.PLAYER_X if current_player == board.PLAYER_O else board.PLAYER_O
        print_all_boards(child, next_player, depth + 1)


# 三目並べの初期盤面を設定
initial_state = [
    [board.PLAYER_X, board.PLAYER_O, board.PLAYER_X],
    [board.PLAYER_X, board.PLAYER_O, board.PLAYER_O],
    [board.EMPTY, board.EMPTY, board.EMPTY]
]

print("現在の盤面:")
board.print_board(initial_state)
print("全ての手の組み合わせ:")
print_all_boards(initial_state, board.PLAYER_O, 0)
# board.py モジュール 

SIZE = 3
EMPTY = '-'
PLAYER_X = 'X'
PLAYER_O = 'O'

# 盤面に空きマスがあるかを確認
def is_moves_left(board):
    for row in board:
        if EMPTY in row:
            return True
    return False

# 現在の盤面の状態を評価
def evaluate(board):
    # 行のチェック
    for row in board:
        if row[0] == row[1] == row[2] != EMPTY:
            if row[0] == PLAYER_O:
                return 10  # Oが勝ち
            else:
                return -10  # Xが勝ち

    # 列のチェック
    for col in range(SIZE):
        if board[0][col] == board[1][col] == board[2][col] != EMPTY:
            if board[0][col] == PLAYER_O:
                return 10  # Oが勝ち
            else:
                return -10  # Xが勝ち

    # 対角線のチェック
    if board[0][0] == board[1][1] == board[2][2] != EMPTY:
        if board[0][0] == PLAYER_O:
            return 10  # Oが勝ち
        else:
            return -10  # Xが勝ち

    if board[0][2] == board[1][1] == board[2][0] != EMPTY:
        if board[0][2] == PLAYER_O:
            return 10  # Oが勝ち
        else:
            return -10  # Xが勝ち

    # 引き分けの場合
    return 0

# 現在の盤面から可能な次の手を生成
def get_children(board, player):
    children = []
    if evaluate(board) in [10, -10] or not is_moves_left(board):
        return children

    for i in range(SIZE):
        for j in range(SIZE):
            if board[i][j] == EMPTY:
                # 盤面をコピーして新しい手を作成
                child = [row[:] for row in board]
                child[i][j] = player
                children.append(child)
    return children

# 現在の盤面を表示
def print_board(board):
    for row in board:
        print(' '.join(row))
    print()  # 空行を追加して視覚的に区切りを入れる

# 盤面の評価結果を返す
def get_result(board, score):
    if score == 10:
        return "勝ち 評価値 10"  # Oが勝ち
    elif score == -10:
        return "負け 評価値 -10"  # Xが勝ち
    elif not is_moves_left(board):
        return "引き分け 評価値 0"
    return f"評価値 {score}"

いかがでしょうか。
この問題ではプログラムは登場しませんが、ご参考までに。

いいなと思ったら応援しよう！