CODEWITHSUNDEEP
algorithmartificial-intelligenceminimax
tath
tath

Reputation: 41

Minimax algorithm in a game

Im trying to create my first game using the minimax algorithm but i dont know how to implement this using a tree.

The game rules are the following:

Firstly we must run the minimax algorithm and then the player MAX plays with the best move.

This is the game but i cant imagine how to implement this with tree. Can anyone help me and give me an idea?

Upvotes: 1

Views: 2541

Answers (4)

Edward Doolittle
Edward Doolittle

Reputation: 4100

This game can be solved using a dynamic programming algorithm. Set up a Boolean array win[0] ... win[40]. The value in each element will be true if the state of the game is a winner for you, false if it is a loser. Initially win[0] is false. win[1] is then true because there is a move that takes 1 to 0, a losing position for the other side so a winning position for you. win[2] is then false because there is no move taking 2 to a losing position (for the other side). You can then fill in all the elements of the array in this manner.

Once you have the array, your strategy is to make moves from winning positions to losing positions. If you initially start in a losing position, all you can hope for is for the other player to make a mistake and move to a winning position for you.

Upvotes: 0

Nathan S.
Nathan S.

Reputation: 5388

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.

Upvotes: 0

Topological Sort
Topological Sort

Reputation: 2787

It's not that you create a tree, but that your search can be described as a tree.

Say it's Tic-Tac-Toe, to take a more familiar example. You are X. You have 9 options, 9 possible moves.

After that, as it happens, O will have 8 possible moves. And so on.

You can perform a depth-first search (with a depth limit to be sure), and each time you get the results back from the children, you take the min (or the max) result.

This page discusses it with a Tic-Tac-Toe example at greater length: http://neverstopbuilding.com/minimax . Note that their algorithm is recursive, which makes accumulating the children's scores relatively simple.

Upvotes: 2

Codor
Codor

Reputation: 17605

To my understanding, the usual (and perhaps most intuitive way) is not to use explicit representation of the game tree, but viewing the inner workings of the algorithm as actually performing the desired move, recursively evaluating the move and finally un-doing the move. This means that navigation in the game tree is represented by the call stack and can be seen as depth-first search on an implicitly represented tree. Succesive calls would take the perspective of either opponent, respectively.

That being said, such an implementation might not be easy to do at first try. Furthermore, note that the game you described seems to be closely related to Nim, for which more efficient algorithms might exist.

Upvotes: 0

Related Questions