Max and Min are playing the Tic-Tac-Toe game in which players take turns marking the cells in a 3 × 3 grid. Max marks Xs and Min marks Os. Min wins with utility −1 if any line (horizontal, vertical, or diagonal) fills up with three Os, whereas Max wins with utility +1 if any line fills up with three Xs. If there are no empty cells left and no one has won so far, the game ends in a draw with utility 0.

Consider the game state shown above. Compute the utility of the state using Minimax search, assuming Max is to play next.