3
\$\begingroup\$

I am attempting to complete an assignment, which is basically Connect 3, instead of the classic Connect 4 game. The AI I am using is the exact same as the opponent, but the opponent wins more because it goes first. I've researched for days and cannot grasp MINIMAX, or think of ways to make this AI better.

public int getBestColumn(Player[][] state, Player player) {
    for (int c = 0; c < GRID_WIDTH; c++)

    int r = top(state, c);

    if (r >= 0) {
        Player[][] hypothetical = state;
        hypothetical[r][c] = player;
        if (getWinner(hypothetical, r, c) == player)
            return c;

        Player opponent = (player == Player.PLAYERX ? Player.PLAYERO : Player.PLAYERX);
        hypothetical[r][c] = opponent;
        if (getWinner(hypothetical, r, c) == opponent)
            return c;
        if(player==opponent)
            return c;

        hypothetical[r][c] = Player.NONE;



    }
}



    return (new Random()).getBestColumn(state, player);
}
}
}
\$\endgroup\$
  • 1
    \$\begingroup\$ Your for block is missing an { opening brace... \$\endgroup\$ – Mathieu Guindon Dec 14 '14 at 3:38
5
\$\begingroup\$

I've researched for days and cannot grasp MINIMAX, or think of ways to make this AI better.

You can't really do MINIMAX without having an evaluation function. But even then, minimax is a bit complicated, but you could try something simpler:

Evaluation function

Make any function satisfying

  • f(state) = +A_LOT, if I win
  • f(state) = -A_LOT, if I lose
  • f(state) is bigger when the position looks better for me

Here, "looks better" simply means something like "me having 2 in a row is good", "me having 3 is even better". Just count things you believe are good.

Game tree search

You look at immediately wining turns, this is good. You also try to look at places where the other player can immediately win, this is also good. But you did it wrong (see below) and you don't do a real search.

A game tree search would mean, you do your hypothetical turn and then let the opponent try all moves (and so on). This can be as simple as two nested loops...

for all your turns {
  do your turn
  return if your won
  lost = false
  for all opponent's turn {
    do his turn
    lost = true if he won
    undo his turn
    break if lost
  }
  remember your turn as bad if lost
  undo your turn
}

Now you either returned with a winning move or remembered some bad moves or got no information at all. The further process should be obvious (winning move is clear, bad moves are to be avoided, that's all you know).

This can be generalized easily by using one more loop... you get one step smarter. And one more etc... however, a real depth search can go arbitrary deep, but try this for the start.

Combination

When going deeper, try using your evaluation function. This is still far from really smart, but it should be better than each idea alone.

Review

Player[][] hypothetical = state;

This looks like you'd have a state and an hypothetical state, which is not true, as it's the same array. So remove it to avoid confusion.

Player opponent = (player == Player.PLAYERX ? Player.PLAYERO : Player.PLAYERX);

Player should implement a method theOther() doing exactly this.

if (getWinner(hypothetical, r, c) == opponent)
        return c;

This alone is right, but it's in the same loop as finding your winning move. WRONG! If you can win at r=3 and the opponent can win at r=2, you'll play at r=2. You seem to be so scared of losing so that you give up a sure immediate win!

    if(player==opponent)
        return c;

WTF?

    }
}



    return (new Random()).getBestColumn(state, player);
}
}
}

WOW! So many closing braces and so nicely aligned...

The random move selection is fine if you don't know any better, but as I recently checked java.util.Random, it did not implement getBestColumn. This were a place for your evaluation function.

|improve this answer|||||
\$\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.