(This is a post for CS320 Boston University)

Minimax is a decision rule used in game theory for minimizing the possible loss for a worst case (maximum loss) scenario [wiki]. Alternatively, it can be thought of as maximizing the minimum gain. It is usually seen in a two player zero-sum game like tic-tac-toe.

The exercise today involves a partial implementation of an AI tic-tac-toe player using minimax algorithm. Consult [wiki] for the pesudo-code of this algorithm.

The sample code consists of the definitions for board, cell, move, position and decition tree dtree. You are required to implement

  • show_board: print the board on the screen
  • make_move: place a cell on a position of the board
  • next_moves: generate all possible next moves
  • minimax_min and minimax_max: compute the decision tree with minimax algorithm.