Improving AI for a Connect 3 game

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);
}
}
}
• Your for block is missing an { opening brace... Dec 14 '14 at 3:38

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

lost = false
for all opponent's turn {
do his turn
lost = true if he won
undo his turn
break if lost
}
}

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.