0
\$\begingroup\$

I'm trying to implement the mixmax algorithm (without alpha-beta pruning yet) for the AI for the Connect Four game.

I know that there are a lot of papers with the best rules to handle this kind of problem but.. in my opinion they are too much complicated and i think that a simpler reasoning can bring to a very good AI too.

My heuristic is this (i have found it in a tutorial without code):

For each possible move, looks at each adjacent set of four cells and return the sum of the values of the four.

Values: 0 if blocking (in the four there are both computer's cells and player's cells) +100 if 3 computer cells +10 if 2 computer cells +1 if 1 computer cell 0 if empty (4 empty cells) -100 if 3 player cells -10 if 2 player cells -1 if 1 player cell

Actually, i can place 3 pieces horizontally and the computer will not try to block them, so i can win easly.

I think that something is missing in my code, here it is:

    /**
 * Looks at each adjacent set of four cells and return the sum of
 * the values of the four
 * 
 * Heuristic Evaluation:
 * 
 * Blocked | 3player | 2player | 1player | empty | 3computer | 2computer | 1computer
 *    0        -100      -10       -1        0        +100        +10         +1
 */
private int evaluateCell(int row, int col) {

    int result = 0;

    // horizontal sets

    // right set
    int tCol = col + 1;
    int playerCount = 0;
    int computerCount = 0;
    while(tCol < col + 5) {
        if(tCol < GameMain.COLS) {
            if(cells[row][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if(cells[row][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tCol++;
        } 
        // right border reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // left set
    tCol = col - 1;
    playerCount = 0;
    computerCount = 0;
    while(tCol > tCol - 5) {
        if(tCol >= 0) {
            if(cells[row][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if(cells[row][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tCol--;
        }
        // left border reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // vertical set (to bottom)
    int tRow = row + 1;
    playerCount = 0;
    computerCount = 0;
    while(tRow < tRow + 5) {
        if(tRow < GameMain.ROWS) {
            if(cells[tRow][col].getContent() == mySeed) {
                computerCount++;
            }
            if(cells[tRow][col].getContent() == oppSeed) {
                playerCount++;
            }
            tRow++;
        }
        // bottom border reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // diagonal (to top-right)
    tRow = row;
    tCol = col;
    tRow = tRow - 1;
    tCol = tCol + 1;
    playerCount = 0;
    computerCount = 0;
    while(tRow > tRow - 5 && tCol < tCol + 5) {
        if(tRow >= 0 && tCol < GameMain.COLS) {
            if(cells[tRow][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if(cells[tRow][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tRow--;
            tCol++;
        }
        // top-right corner reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // diagonal (to top-left)
    tRow = row;
    tCol = col;
    tRow = tRow - 1;
    tCol = tCol - 1;
    playerCount = 0;
    computerCount = 0;
    while(tRow > tRow - 5 && tCol > tCol - 5) {
        if(tRow >= 0 && tCol >= 0) {
            if(cells[tRow][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if(cells[tRow][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tRow--;
            tCol--;
        }
        // top-left corner reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // diagonal (to bottom-right)
    tRow = row;
    tCol = col;
    tRow = tRow + 1;
    tCol = tCol + 1;
    playerCount = 0;
    computerCount = 0;
    while (tRow < tRow + 5 && tCol < tCol + 5) {
        if (tRow < GameMain.ROWS && tCol < GameMain.COLS) {
            if (cells[tRow][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if (cells[tRow][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tRow++;
            tCol++;
        }
        // bottom-right corner reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    // diagonal (to bottom-left)
    tRow = row;
    tCol = col;
    tRow = tRow + 1;
    tCol = tCol - 1;
    playerCount = 0;
    computerCount = 0;
    while (tRow < tRow + 5 && tCol > tCol - 5) {
        if (tRow < GameMain.ROWS && tCol >= 0) {
            if (cells[tRow][tCol].getContent() == mySeed) {
                computerCount++;
            }
            if (cells[tRow][tCol].getContent() == oppSeed) {
                playerCount++;
            }
            tRow++;
            tCol--;
        }
        // bottom-left corner reached
        else {
            break;
        }
    }
    result += evaluateSet(playerCount, computerCount);

    return result;
}

private int evaluateSet(int playerCount, int computerCount) {
    if(playerCount == 3) {
        return -100;
    }
    if(playerCount == 2) {
        return -10;
    }
    if(playerCount == 1) {
        return -1;
    }
    if(computerCount == 3) {
        return 100;
    }
    if(computerCount == 2) {
        return 10;
    }
    if(computerCount == 1) {
        return 1;
    }
    // set blocked or empty
    return 0;
}

Obviously this is not the entire code. The minmax core code is missing and the checks for a victory.

\$\endgroup\$
  • 1
    \$\begingroup\$ Too much for us to look at and debug. Tip: have the thing output information as it works through its process to debug where the error is. \$\endgroup\$ – Almo Sep 18 '15 at 19:43
  • \$\begingroup\$ You could tell me if the heuristic is ok for example :) \$\endgroup\$ – Loris Sep 18 '15 at 20:08
  • \$\begingroup\$ @Loris you could check if your heuristics are ok by simply adding a print System.out.println at the end which prints the score. \$\endgroup\$ – Philipp Sep 19 '15 at 8:35
  • \$\begingroup\$ It is hard to check because minmax is recursive. I get hundreds of prints for each move. Anyway, the code i put is very simple to understand. My question is..should i check the specific cases in which in a set of 4 there is a winner? \$\endgroup\$ – Loris Sep 19 '15 at 9:07
  • \$\begingroup\$ I think you should have a more specific heuristic. Your current heuristic is just checking for cells around the current cell. Instead, check for patterns. If you break the other person's 4 pattern vertically, diagonally or horizontally, you get a low score. Or if you have 3 and can make 4, very low score. And high scores for the ones beside an opponent cell (if it doesn't break any pattern). This isn't perfect, and it could be improved a lot, but hopefully its shown you the right direction. \$\endgroup\$ – EvilTak Sep 19 '15 at 9:24

Your Answer

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

Browse other questions tagged or ask your own question.