current community

your communities

more stack exchange communities

Stack Exchange
tour help
Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.
up vote 0 down vote favorite

This question already has an answer here:

I am currently working on a Checkers game using Unity ( human vs computer ) I am done with the base architecture of the game ie defining the rules, moves, jumps etc.

I am currently stuck in implementation of MinMax for computer AI. I know how it works but I am confused on two things. Firstly, the heuristics ( I am using simple red checker count - black checker count ) but I am not sure if its correct. Secondly, outputting the final path of nodes for my AI to make its next turn.

Below is my MinMax implementation so far.

int MiniMax(TreeNode node)
    {
        int depth = 2;
        List<TreeNode> pathNodes = new List<TreeNode>();
        int final = MaxMove(node, depth, pathNodes);
        return final;
    }

int MaxMove(TreeNode currNode, int depth, List<TreeNode> pathNodes)
{
    if (depth == 0)
    {
        return currNode.getPriority();
    }
    else
    {
        depth--;
        int v = -10000;
        List<TreeNode> allPossRedMoveNodes = gameBoardScript.createNewRedBoardsFromCurrent(currNode.getCurrentBoard());
        foreach (TreeNode RedNode in allPossRedMoveNodes)
        {
            int v1 = MinMove(RedNode, depth,pathNodes);
            if(v1 > v)
            {                 
                v = v1;
            }
        }
        return v;
    }
}

int MinMove(TreeNode currNode, int depth, List<TreeNode> pathNodes)
{
    if (depth == 0)
    {
        return currNode.getPriority();
    }
    else
    {
        depth--;
        int v = 10000;
        List<TreeNode> allPossBlackMoveNodes = gameBoardScript.createNewBlackBoardsFromCurrent(currNode.getCurrentBoard()); 

        foreach (TreeNode BlackNode in allPossBlackMoveNodes)
        {
            int v1 = MaxMove(BlackNode, depth,pathNodes);
            if (v1 < v)
            {
                v = v1;
            }
        }
        return v;
    }          
}

Max in this case would be Black Checkers ( Computer AI ) and Min is Red Checker, the human player

Let me briefly explain what I am trying to do with my code above. I have a TreeNode structure that stores the GameBoard, next possible move and also the Heuristic value

In My Max Move, I get all the possible Red Move Nodes from the current board. Logic for finding all possible moves is working absolutely fine. And for my Min Move which would be the human player, I get all its possible black nodes.

I am currently testing the code with depths 2 to 3 for my game tree. Please correct me if my current implementation is wrong. And finally how or where do I trace the final path of all my final Tree Nodes based on Min and Max values generated and get the next move for the Black Checker?

share|improve this question

marked as duplicate by ClassicThunder, Anko, Josh Petrie♦ Oct 29 '14 at 16:04

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.
    
thanks that helped too. –  ckzilla Oct 29 '14 at 0:19

1 Answer 1

up vote 1 down vote accepted

The usual implementation for this is to have only a MaxMove function, and negate the value returned.

You only need to remember the top level move, although remembering the path to the move that constitutes the principal variation can be helpful to understand the result, you only need to make the best move and re-run the search from the new position after the opponent responds.

share|improve this answer
    
That makes sense. I understand running it every time when the human player makes the move. Just to be clear on this part, say human makes a move for the red checker. Next up the computer AI would calculate the next move using the MinMax algorithm for all the current black checkers that can make a move. In the game tree itself, the top level would always have all red checker nodes ( MIN Branch ), so then how would I get the final move for the AI from the top level? It gives me the final move for the red checker and not the black one. I am slightly confused on this part. Please correct me here. –  ckzilla Oct 29 '14 at 0:13
    
You need to erase notions of red and black from your mind, they'll just confuse you. Current player tries all possible moves, and returns the one with the best value. Usually the object representing that move will contain other things, such as the value, and the best continuation move. –  ddyer Oct 29 '14 at 4:02
    
Great, thanks! got it now –  ckzilla Oct 29 '14 at 23:47

Not the answer you're looking for? Browse other questions tagged or ask your own question.