IPA FE Subject B sample Question 15

Topic: Graph Traversal

A question IPA Japan published in 基本情報技術者試験 科目B サンプル問題 問15, translated into English. ITPEC is based on the same exams.

From the answer group below, select the correct combination of answers to be inserted into A and B in the description.

In tic-tac-toe, the move with which you have the highest possibility of winning is determined. With the following procedure, the state transitions of the game are represented as a tree structure, and the evaluation value of each node other than the root is calculated. As a result, the move with the highest evaluation value among the children of the root is regarded as the move with the highest possibility of winning. A move selected by you is represented by ○, and a move selected by the opponent is represented by ×.

[Procedure](1)With the current state of the board as the root, all the possible moves until either side wins or the game ends in a draw are represented in a tree structure.(2)The states of the leaves are evaluated as follows. ①If you win, 10 ②If you lose, −10 ③If it is a draw, 0(3)The evaluation value of each node other than the leaves is determined based on the evaluation values of all the children of the node. ①If the node is at your turn, the maximum evaluation value among the evaluation values of the children is regarded as the evaluation value of the node. ②If the node is at the opponent's turn, the minimum evaluation value among the evaluation values of the children is regarded as the evaluation value of the node.

When the game is in the state of the root at the top of the figure, there are three moves you can select. Of them, the evaluation value of the child pointed to by A is A, and the evaluation value of the child pointed to by B is B.

State of the rootYour turnABWinEvaluation value 10Opponent's turnLoseEvaluation value −10Your turnDrawEvaluation value 0WinEvaluation value 10DrawEvaluation value 0

Figure State transitions of tic-tac-toe

Answer group

OptionAB

Explanation

A: 0, B: −10 — evaluate from the leaves up: at the opponent's turn a node takes the minimum of its children, at your turn the maximum.

Child A (○ bottom left), the opponent's turn, has two children:

  • •× bottom middle: you take the last cell, bottom right, a draw: 0
  • •× bottom right: you play bottom middle and complete the middle column: win, 10

The opponent's node takes the minimum, min(0, 10) = 0: the opponent blocks your column.

Child B (○ bottom right), the opponent's turn, has two children:

  • •× bottom left completes the left column of ×: a leaf, lose, −10
  • •× bottom middle: you take the last cell, a draw: 0

Minimum: min(−10, 0) = −10. The middle child wins at once (10), so it is the move the procedure picks.

Answer (a)

Why not others:

  • •(c) and (d) — A = 10 takes the maximum at A's node, but it is the opponent's turn there, so the minimum counts
  • •(b) — B = 0 overlooks the opponent's winning reply × bottom left; the minimum includes that −10

Key rule: In a minimax tree, assume the opponent always picks the reply worst for you: take the minimum at the opponent's nodes and the maximum at yours.

Graph Traversal · AI-written, may contain errors

Practice this exam

This question comes from the past questions IPA Japan publishes, translated into English by ITPEC Practice. ITPEC Practice is an independent study tool and is not affiliated with IPA or ITPEC. See the original paper (PDF) or Report an issue.