Take the 2-minute tour ×
Game Development Stack Exchange is a question and answer site for professional and independent game developers. It's 100% free, no registration required.

I am just starting to do some very very very basic game dev(in java), i'm trying to create a game of tic tac toe but i am having some trouble implementing an a computer opponent.I just wanted to know if there is anyway to do this other than check every possibility with if statements.This is my best attempt at this but it is kinda broken. ie if points (1,1) and (2,2) are equal to x then it will think that (0,2) is the "best" move but in that situation there would be no "best" move.

some background info on the code, board is a global 3,3 int array. x is just that value that would be inserted when that location is selected. Coor is a class that contain just 2 ints x and y. availableMoves is an arrayList of all the empty areas on the board.

    for (int i = 0; i < 3; i++) {
        for (int j = 0; j < 3; j++) {
            if (i <= 1 && j <= 1) {
                if (board[i][j] == x && board[i][(j + 1)] == x && availableMoves.contains(new Coor(i, ((j + 2) % 3)))) {
                    idealMove = new Coor(i, ((j + 2) % 3));
                } else if (board[i][j] == x && board[i + 1][j + 1] == x && availableMoves.contains(new Coor(((i + 2) % 3), ((j + 2) % 3)))) {
                    idealMove = new Coor(((i + 2) % 3), ((j + 2) % 3));
                } else if (board[i][j] == x && board[i + 1][(j)] == x && availableMoves.contains(new Coor(((i + 2) % 3), j))) {
                    idealMove = new Coor(((i + 2) % 3), j);
                }
            }
        }
    }

Thanks in advance for the guidance

share|improve this question
add comment

3 Answers 3

up vote 2 down vote accepted

The solution set is pretty small, so we could just brute force it, but that's no fun.

First we run a check to see if a victory condition will be met this turn for either the AI or its opponent (this should be quick; there are only 8 ways for either player to win).

If such a move exists, block/take it. Moves that cause the AI to win take priority.

Otherwise, if there is a move that contributes to your winning in the next turn, take it. Sort by number of win conditions it can meet. The side squares can meet 2 win conditions, corners meet three, and middle meets four.

Otherwise, if there is a move thate stops your opponent winning in the next turn, take it. Sort the same way.

Otherwise, simply use the Sort and randomly select from the appropriate squares.

This will give you a reasonably logical (but ultimately beatable) AI without being needlessly complex.

share|improve this answer
add comment

For games like tic-tac-toe (broadly speaking, 2 player board games), the usual method is to try all possible moves, and rank them. Obviously winning moves would rank best and losing moves worst. Between, it's up to you as programmer to recognize what features of a position constitute "better".

Once you have this, add Minmax.
Once you have minmax, add alpha-beta. Once you have that - you are well on your way, and there are whole universe of additional improvements and ways to go about it. You'll find lots of useful stuff on the web.

share|improve this answer
add comment

The Minimax algorithm would guarantee that the opponent would never lose, but you're probably looking for an opponent with flaws so it can be beaten sometimes.

A simple idea would be to keep a list of pairs of boards and a next move. You could iterate through the list, and if you find that all the marks on one of the boards corresponds to the actual game, you choose that next move. For example, here is a list of winning moves:

Board:     Next Move: 

x - -      (2,2)
- x -
- - -

x x -      (2,0)
- - -
- - -

x - -      (0,2)
x - -
- - -

If you don't find any matches in the list, maybe just choose a random coord.

share|improve this answer
    
and always try to take the middle square, except for when the AI has a bad day. –  Valmond Oct 5 '11 at 7:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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