What exactly is a board in the minimax function and how is it implemented?

Question

So I was recently looking at the minimax function which is used in zero sum games. I understood it perfectly, other then how the board is implemented for the actual function:

For example this sample implementation I found has this declaration:

int miniMax(Board eval, int iterations)

My only question is what exactly is Board? Is it a struct, class, array or some other structure? Also how would I implement a sample board for mini-max, like a tic-tac-toe board (As a example)? Couldn't find anything on Wikipedia or Google.

Answer 1

Board is just the current board game. It could be any structure you use to represent the board of the game.

When called first, the minimax function would receive the current board configuration, reached by the different plays made so far (the current state of the game). In the minimax function what you do is modify the board, each modification should represent a possible move according to the game rules. Each of those modified boards should be passed as argument to a new minimax call. Once you reach a certain depth (this is, a number of iterations), you select the best move using an evaluation function to give a score to every modified board and choosing the one with the highest score.

The algorithm you are reading is generic and could work for any game. You might define Board according to convenience, that is, what suits best for the board of the game you want to represent.

For tic-tac-toe, you might want to represent the board with a 3x3 array so you might change Board:

int miniMax(char board[3][3], int iterations)

Or perhaps, you may want to represent your board using 2 bits for each square:

typedef struct {
    unsigned square1: 2;
    unsigned square2: 2;
    unsigned square3: 2;
    unsigned square4: 2;
    unsigned square5: 2;
    unsigned square6: 2;
    unsigned square7: 2;
    unsigned square8: 2;
    unsigned square9: 2;
} Board;

Though, for tic-tac-toe you don't need a lightweight board representation since its maximum depth is just 9. I'm just giving you examples to let you understand it can be any structure you use to represent the board game.

If you are going to deal with minimax function and the game is much more complex than tic-tac-toe, you should seriously consider using alpha-beta pruning which is a big improvement.

EDIT: I think you shouldn't call your board "eval" since that can be confused with the evaluation function which is a totally different thing.

Answer 2

The board, as you write it, is just the common structure that is used an minimax and many other decisional tree algorithms.

It is meant to be the structure that contains the information about a specific state of the game. In the algorithm itself, from a logical point of view, this parameter should be unmodifiable in the sense that you will do moves on the board and generate new board snapshots (so old ones are not modified) while you are going deep in the tree of moves that you are evaluating to find the better strategy.

Indeed it is useful to internally have two elements in the board: the set of rules (that you can apply to effectively modify its state by doing moves) and a state, which will change at every iteration (even if the board itself it's still the same) and that is the object that will be used to evaluate how good a move is for a player (when reaching maximum depth so that you are forced to give an estimate of the goodness of the move just by the state).

So it can be anything, it's just a conceptual parameter. If you really want something more practical I'd imagine it in a way similar to:

class BoardSnapshot {
  Board b;

  float alpha;    
  State state;
  int evaluate();
}

class Board {
  List<Players> players;
  List<Rules> rules;

  State applyMove(State current, Player player, Rule rule, params ...);
}

So that you initialize it with a BoardSnapshot with no current state and you apply a rule and generate a new state which will be a snapshot of the tree branch currently chosen.