The minimax computation should be performed by a depth first search. The best way to do so is to abstract your state space slightly. Implement a function called GetMoves that returns all valid moves, as well as a GameOver function that returns if the game is over. You should also limit the depth of your search if you can't search the whole tree (this will enable iterative deepening). Then your code is something like (this is just pseudo-code):
double maxPlayer(state, depth)
{
if (state.GameOver() || depth == 0)
return state.eval;
auto moves = state.GetMoves();
int best = NINF;
for (m : moves)
{
state.ApplyMove(m);
int tmp = minPlayer(state, depth-1);
if (tmp > best)
best = tmp;
state.UndoMove(m);
}
return best;
}
Here you'd need to write a corresponding minPlayer function. Note that this doesn't include alpha-beta pruning. It also doesn't return the best move. You could also use a negamax formation to write a single function instead of two for the max/min players.
In your case your moves might be just integers, 1 or L. Applying a move subtracts 1 or L cubes, and undoing a move adds 1 or L cubes.
Note that in this formulation we aren't checking for duplicates in the tree, so it will be exponential in the number of cubes. But, since you don't care about the history of actions in determining the winner, you actually only need 2M nodes in the full tree. Using a table to store the result of the search (memoization/transposition table) will reduce the tree to at most 2M nodes instead of 2^M.
