0
\$\begingroup\$

I have a minimax player for the gomoku game, connect 5. The minimax player does not block the moves when there is potentially 5 in a row or 4 in a row. I would appreciate if anyone can show me what I am doing wrong please. Thank you very much.

    class PlayerMinimax
{
    // instance variables
    int empty = 0;
    int columns = 8;// 
    int rows = 8;// 
    int [][] intBoard;
    boolean justLauched = true;
    int aiPiece;
    int pcPiece;

    public Move chooseMove(Color[][] board, Color me) {
        setColorToInt(me); //change color to integers for both players
        intBoard = convertBoardtoInt(board,me); //convert board to integers.
        int best[] = miniMax(intBoard,3,Integer.MIN_VALUE,Integer.MAX_VALUE, true);
        return new Move(best[0],best[1]);
    }

      //minimax algorithm
    private int[] miniMax(int[][]mboard,int depth,int alpha, int beta, boolean maximizingPlayer)
    {
        if(depth == 0 || terminalReached(mboard) == true)
        {
            if (terminalReached(mboard))
            {
                if (checkIfWon(mboard, aiPiece)) // ours
                {
                    int [] ap = new int [3];
                    ap[2] = 1000000;
                    return ap;
                }
                else if (checkIfWon(mboard,pcPiece))
                {
                    int [] sp = new int [3];
                    sp[2] = -1000000;
                    return sp;
                } //dont handle game over situation as no need to.
            }
            else//depth is 0
            {
                int [] es = new int[3];
                es[2] = scorePosition(mboard,aiPiece);
                return es;
            }

        }
        if (maximizingPlayer)
        {
            int value = Integer.MIN_VALUE;
            int [][] clone = new int[rows][columns];
            int[] best = new int[3];
            for(int i = 0 ; i < rows ; i++)
            {
                for(int j = 0 ; j < columns ; j++)
                {
                    clone = cloneBoard(mboard); //clone board for each simulation
                    //simulatePlay
                    if(clone[i][j] == empty) //empty location
                    {                    
                        clone[i][j] = aiPiece; // drop the ai piece
                        int newScore = (miniMax(clone,depth -1,alpha,beta,false))[2]; //we want only the score here index 2
                        if (newScore > value)
                        {   
                            value = newScore;
                            best[0] = i;
                            best[1] = j;
                            best[2] = value;
                        }
                        alpha = Math.max(alpha,best[2]);
                        if (alpha >= beta)
                        {
                            break;
                        }
                    }
                }
            }
            return best;
        }
        else // minimizing player
        {
            int minvalue = Integer.MAX_VALUE;
            int [][] clonemin = new int[rows][columns];
            int[] bestmin = new int[3];
            for(int i = 0 ; i < rows ; i++)
            {
                for(int j = 0 ; j < columns ; j++)
                {
                    clonemin = cloneBoard(mboard); //clone board for each simulation
                    //simulatePlay
                    if(clonemin[i][j] == empty) //empty location
                    {                    
                        clonemin[i][j] = aiPiece; // drop the ai piece
                        int newScore = (miniMax(clonemin,depth -1,alpha,beta,true))[2];
                        if (newScore < minvalue)
                        {   
                            minvalue = newScore;
                            bestmin[0] = i;
                            bestmin[1] = j;
                            bestmin[2] = minvalue;
                        }
                        beta = Math.min(alpha,bestmin[2]);
                        if (alpha >= beta)
                        {
                            break;
                        }
                    }
                }
            }
            return bestmin;
        }
    }

    //check to see if any more valid moves exists, or if either player wins.
    private boolean terminalReached(int[][]curboard)
    {
        boolean term = false;
        for (int row = 0; row < rows; row ++) 
        {
            for(int col = 0; col < columns; col++)
            {
                if(curboard[row][col] == empty)
                {
                    term = false;
                    break;
                }
            }
        }
        if(checkIfWon(curboard,aiPiece) == true || checkIfWon(curboard,pcPiece) == true || term == true)
        {
            return true;
        }
        return term;
    }


    private int scorePosition(int[][] curBoard, int piece)
    {
        int score = 0;

        ArrayList<Integer> window = new ArrayList<Integer>(); //array to store 5 consecutive board pieces
        //get horizontal score on the board 
        for (int row = 0; row < rows; row ++){
            for(int col = 0; col < columns - 4; col++){
                window.clear(); //clear arraylist at each iteration
                for(int i = 0 ; i < 5; i++)
                { 
                    window.add(curBoard[row][col+i]); //create a window of 5 pieces
                }  
                score += evaluateWindow(window,piece); //getScore of that window
            }
        }
        //get vertical score of the board
        for  (int col = 0; col < columns; col++){
            for (int row = 0; row < rows - 4; row ++){
                window.clear(); 
                for(int i = 0 ; i < 5; i++) //window size of 5
                {
                    window.add(curBoard[row+i][col]); //each row, start at different columns
                }
                score += evaluateWindow(window,piece); 
            }
        }

        //check negative diagonal slope
        for  (int row = 0; row < rows - 4; row++)
        {
            for (int col = 0; col < columns - 4; col++)
            {
                window.clear(); 
                for(int i = 0 ; i < 5; i++) //window size of 5
                {
                    window.add(curBoard[row+i][col+i]); //each row, start at different columns
                }
                score += evaluateWindow(window,piece); 
            }
        }
        //check positive diagonal slope
        for  (int row = 0; row < rows - 4; row++)
        {
            for (int col = 0; col < columns - 4; col++)
            {
                window.clear(); 
                for(int i = 0 ; i < 5; i++) //window size of 5
                {
                    window.add(curBoard[row-i+4][col+i]);  
                }
                score += evaluateWindow(window,piece); 
            }
        } 
        return score;
    }

    private int evaluateWindow(List<Integer> window, int piece) 
    {
        int winScore = 0;
        int wsize = window.size();
        int oppPiece = pcPiece;
        if (piece == pcPiece){
            oppPiece = aiPiece;
        }
        int countPiece = 0; //count number of times values, 0, 1, 9 appear in the kern window. zero/one defined in constructor
        int countempty = 0;
        int countOpp = 0;
        for(int i = 0; i < wsize; i++)
        {
            if(window.get(i) == piece) 
            {
                countPiece++;   
            }
            else if (window.get(i) == empty) //empties
            {
                countempty++;;
            }
            else if(window.get(i) == oppPiece)
            {
                countOpp++;
            }
        }
        if(countPiece == 5){
            winScore = winScore + 100;
        }else if (countPiece == 4 && countempty == 1){
            winScore = winScore + 10;
        } else if (countPiece == 3 && countempty == 2){
            winScore = winScore + 5;
        }else if (countPiece == 2 && countempty == 3){
            winScore = winScore + 1;
        }

        if(countOpp == 4 && countempty == 1) {
            winScore = winScore - 100;

        } else if(countOpp == 3 && countempty == 2) {
            if(window.get(0) == empty && window.get(4) == empty) {
                winScore = winScore - 100;
            } 
            else {

                winScore = winScore - 10;
            }

        }
        return winScore;
    }

    //convert colour to integer numbers for the players
    private void setColorToInt(Color myCol)
    {
        int aiColorInt = 0;
        int pcColorInt = 0;         
        if (myCol == Color.BLACK){
            aiColorInt = 1; pcColorInt = 2;
        } else if (myCol == Color.WHITE){
            aiColorInt = 1; pcColorInt = 2; // not sure if need to swap.
        }
        aiPiece = aiColorInt;
        pcPiece = pcColorInt;
    }

    //convert the board to integer numbers and get valid moves
    private int[][] convertBoardtoInt(Color[][] board, Color me)
    {
        int [][] conBoard = new int[rows][columns]; //converted board initialised
        for (int row = 0; row < rows; row++){
            for (int col = 0; col < columns; col++){
                if(board[row][col] == null){
                    conBoard[row][col] = empty;
                }
                else if (board[row][col] == me){
                    conBoard[row][col] = aiPiece; //ai
                }
                else{
                    conBoard[row][col] = pcPiece; //computer
                }
            }
        }
        return conBoard;
    }

    //clone board to avoid referencing the original board
    private int[][] cloneBoard(int [][] curBoard)
    {
        int[][]clonedB = new int[rows][columns];
        for (int i = 0; i < curBoard.length; i++) 
        {   
            clonedB[i]= new int[curBoard[i].length];
            for (int j = 0; j < curBoard[i].length; j++)
            {
                clonedB[i][j] = curBoard[i][j];
            }
        }
        return clonedB;

    }

    //evaluate player's move in all directions to see if it is a win, 5 in a row.
    private boolean checkIfWon(int [][] curBoard,int piece)
    {   
        //horizontal
        for (int r = 0;  r < rows; r++) {
            for(int c = 0; c < columns - 4; c++){
                if (curBoard[r][c] == piece && curBoard[r][c+1] == piece && curBoard[r][c+2] == piece && curBoard[r][c+3] == piece  && curBoard[r][c+4] == piece){
                    return true;
                }
            }            
        }
        //vertical
        for (int r = 0; r < rows - 4; r++) {
            for(int c = 0; c < columns; c++){                
                if (curBoard[r][c] == piece && curBoard[r+1][c] == piece && curBoard[r+2][c] == piece && curBoard[r+3][c] == piece  && curBoard[r+4][c] == piece){
                    return true;
                }
            }            
        }
        //diagonals
        for (int r = 0; r < rows - 4; r++) {
            for(int c = 0; c < columns - 4; c++){
                if (curBoard[r][c] == piece && curBoard[r+1][c+1] == piece && curBoard[r+2][c+2] == piece && curBoard[r+3][c+3] == piece  && curBoard[r+4][c+4] == piece){
                    return true;
                }
            }            
        }

        for (int r = 0; r < rows - 4; r++) {
            for(int c = 0; c < columns - 4; c++){
                if (curBoard[r+4][c] == piece && curBoard[r+3][c+1] == piece && curBoard[r+2][c+2] == piece && curBoard[r+1][c+3] == piece  && curBoard[r][c+4] == piece){
                    return true;
                }
            }            
        }
        return false;
    }

}
\$\endgroup\$
  • 1
    \$\begingroup\$ Can you provide a specific scenario in which this code produces the wrong answer? (ie. a repro case) Once you have that input in hand, you can walk through your code one line at a time, looking at what each line would do when provided with that input. At what point does the code's behaviour deviate from the correct decision-making process? That exercise will help you isolate the source of the problem. \$\endgroup\$ – DMGregory Mar 5 '19 at 2:25
  • \$\begingroup\$ Hi DMGregory. Thank you for your time. When the player is playing against me and I have 4 in a row. It does not block me. Instead it is looking at other 3/2 combinations of its own and playing those lines. I am not sure about the scores, if they are the correct way to be calculated. Thanks \$\endgroup\$ – Donald18 Mar 5 '19 at 7:52
  • 2
    \$\begingroup\$ That doesn't tell us anything that's not in your question already. What I'm asking you for is "here is one complete set of the internal game state data on which this method returns the wrong result" and, based on your walkthrough of your code when passed that data, "here is the line where the algorithm does X when it should have done Y" — by using your debugging tools to narrow the problem area like this, you'll tend to get better, deeper answers, faster. Or you might even spot the error.yourself in the process. \$\endgroup\$ – DMGregory Mar 5 '19 at 10:28
  • 1
    \$\begingroup\$ This question could be improved with a minimal example. \$\endgroup\$ – Anko Mar 6 '19 at 5:12
0
\$\begingroup\$

When you evaluate possible moves you can check if the opponent of AI has some of "not blocked 4 in a row" and give a huge negative bonus for this situation (at the start for testing purpose it can be an extremely big bonus).

So other alternatives with blocking behaviour will be chosen more likely.

\$\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.