1
\$\begingroup\$

I have correctly implemented Minimax for my checkers AI till depth of 3 ( well at least that is what I think ). However I am confused on evaluating my game boards at depth 3 with heuristics. Currently I just check ( no of blacks - no of reds ) for my heuristics but then it gives duplicate values ( Tie Breaker ) for most of the game boards. I researched and found that in that case we can assign values to each position on the game board ( found on this link here here and add it to the heuristic. But how is it implemented exactly and how are those board values chosen? And do I have to apply it for each of my recursion or just at the top level for all the branch nodes?

here is my code.

    int MaxMove(TreeNode currNode, int depth, List<TreeNode> pathNodes)
    {
        if (depth == 0)
        {
            return StaticEvaluationFunction(currNode,depth);
        }
        else
        {
            depth--;
            int v = -10000;
            List<TreeNode> allPossRedMoveNodes = gameBoardScript.createNewRedBoardsFromCurrent(currNode.getCurrentBoard());
            TreeNode bestNode = null;
            foreach (TreeNode RedNode in allPossRedMoveNodes)
            {
                int v1 = MinMove(RedNode, depth, pathNodes);
                if (v1 > v)
                {
                    v = v1;
                    bestNode = RedNode;
                }
                //if the heuristic is equal then add the board piece values to the current heuristic ( I AM NOT SURE IF THIS IS CORRECT )
                else if( v1 == v) 
                {                 
                    v1 += RedNode.getBoardMove().getMovedToPiece().getTieBreakerValue();
                    v = v1;
                }
            }
            return v;
        }
    }

    int MinMove(TreeNode currNode, int depth, List<TreeNode> pathNodes)
    {
        if (depth == 0)
        {
            return StaticEvaluationFunction(currNode, depth);
        }
        else
        {
            depth--;
            int v = 10000;
            List<TreeNode> allPossBlackMoveNodes = gameBoardScript.createNewBlackBoardsFromCurrent(currNode.getCurrentBoard());
            TreeNode bestNode = null;
            foreach (TreeNode BlackNode in allPossBlackMoveNodes)
            {
                int v1 = MaxMove(BlackNode, depth,pathNodes);
                if (v1 < v)
                {        
                    v = v1;
                    bestNode = BlackNode;
                }
                //when priorities are equal
                else if (v1 == v)
                {                 
                    v1 += BlackNode.getBoardMove().getMovedToPiece().getTieBreakerValue();
                    v = v1;
                }
            }
            return v;
        }          
    }

    private int StaticEvaluationFunction(TreeNode node, int depth)
    {
        return node.getHeuristic(); // Black - Red count at the last depth
    }
\$\endgroup\$
0
\$\begingroup\$

The duplicate values are to be expected, since you're only "counting the wood". Augment your heuristic to include additional features, for example you might count the average distance to the center, or the number of pieces that are en prise. Usually these additional features would be worth a fraction of the value of a piece.

The evaluation is applied at the maximum depth of the search tree, and propagated up. It's not needed at higher levels in the search tree, at least until you add other features to the search (ie; alpha-beta pruning).

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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