AI for Tic Tac Toe

Question

I have been working on a project , the project is to create a game of Noughts and Crosses. I have programmed the GUI , win checks e.t.c but I'm stuck on programming the AI. I have represented a 3x3 array full of JButtons . It has been very challenging.

I'm looking for ideas that could help me code much more efficient and effective code. I think my method wasn't very efficient and I want to code the AI to make marks horizontally and vertically ( offensive and defensive strategies ).

Thanks in advance

This is what I have done so far :

public class Computer {

 public void AI()
 {

     for(int i=0; i<3; i++ )
     {


         for (int j=0; j<3; j++)
         {
             // Diagonal Defensive Strategy for computerX and computerO
            if ( Game.computerX == true && Game.Board[i*1][j*1].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1+2][j*1+2].getText().equals(""))
            {
                Game.Board[i*1+2][j*1+2].setText("X");

            }


            else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1][j*1].getText().equals(""))
            {
                Game.Board[i*1][j*1].setText("X");
            }


            else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("O"))
            {
                Game.Board[i*1+1][j*1+1].setText("X");
            }


            //*************************************** For computerO *******************************

            else if ( Game.computerO == true && Game.Board[i*1][j*1].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1+2][j*1+2].getText().equals(""))
            {
                Game.Board[i*1+2][j*1+2].setText("O");

            }


            else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1][j*1].getText().equals(""))
            {
                Game.Board[i*1][j*1].setText("O");
            }


            else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("X"))
            {
                Game.Board[i*1+1][j*1+1].setText("O");
            }

            //*********************************************************************************************







            // Diagonal Offensive Strategy for computerX and computerO
            if ( Game.computerX == true && Game.Board[i*1][j*1].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1+2][j*1+2].getText().equals(""))
            {
                Game.Board[i*1+2][j*1+2].setText("X");
            }


            else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("X") && Game.Board[i*1][j*1].getText().equals(""))
            {
                Game.Board[i*1][j*1].setText("X");
            }

            else if (Game.computerX == true && Game.Board[i*1+2][j*1+2].getText().equals("X") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("X"))
            {
                Game.Board[i*1+1][j*1+1].setText("X");
            }



            //*************************************** For computerO *******************************

            else if ( Game.computerO == true && Game.Board[i*1][j*1].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1+2][j*1+2].getText().equals(""))
            {
                Game.Board[i*1+2][j*1+2].setText("O");
            }



            else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("O") && Game.Board[i*1][j*1].getText().equals(""))
            {
                Game.Board[i*1][j*1].setText("O");
            }


            else if (Game.computerO == true && Game.Board[i*1+2][j*1+2].getText().equals("O") && Game.Board[i*1+1][j*1+1].getText().equals("") && Game.Board[i*1][j*1].getText().equals("O"))
            {
                Game.Board[i*1+1][j*1+1].setText("O");
            }


            //**************************************************************************************



     }

Answer 1

Simple defensive strategy in pseudo code:

for every line
    if line is not full and opponent has two Xs in this line
        place your O in the remaining space

for every pair of lines
    if lines intersect, there is no element in the intersection and opponent has X in each line and you have no Xs in any of these two
        place your O in the intersecton

You should also try to improve the readability of your code, try to write the above algorithm like this:

for (Line line : allLines()) {
    if (line.has(2, "X") && line.has(0, "O")) {
        place(line.getEmptySpace(), "O");
    }

for (PairOfLines pairOfLines : allPairsOfLines()) {
    Line line1 = pairOfLines.getOne();
    Line line2 = pairOfLines.getTwo();
    if (line1.intersects(line2)
            && pairOfLines.getIntersection().isEmpty()
            && line1.has(1, "X")
            && line2.has(1, "X")
            && pairOfLines.has(0, "O")) {
        place(pairofLines.getIntersection(), "O");
    }
}

You will need to create some helper methods to make it compile, but the code is clean and you can easily see the behavior from the code.

Then you can do similarly for offensive strategy, e.g. find two intersecting lines where there is your one O and no opponent's Xs.

I gave it a try and here is what I came up with. It wasn't test driven properly (there are gaps) and it needs some more refactoring:

import org.junit.Test;

import static blah.tictactoe.Cog.O;
import static blah.tictactoe.Cog.X;
import static com.shazam.shazamcrest.MatcherAssert.assertThat;
import static com.shazam.shazamcrest.matcher.Matchers.sameBeanAs;
import static org.hamcrest.CoreMatchers.is;

public class BoardTest {

    @Test
    public void blocksLineOfTwo() {
        Board board = new Board(new Cog[][]{
                {X,    null, null},
                {null, X,    null},
                {null, null, null}
        });

        board.placeOAutomatically();

        assertThat(board, is(sameBeanAs(new Board(new Cog[][]{
                {X,    null, null},
                {null, X,    null},
                {null, null, O   }
        }))));
    }

    @Test
    public void blocksIntersectionForOneCogOnEachOfLines() {
        Board board = new Board(new Cog[][]{
                {null, null, null},
                {O,    O,    X   },
                {X,    null, null}
        });

        board.placeOAutomatically();

        assertThat(board, is(sameBeanAs(new Board(new Cog[][]{
                {null, null, null},
                {O,    O,    X   },
                {X,    null, O   }
        }))));
    }

    @Test
    public void placesWinningCog() {
        Board board = new Board(new Cog[][]{
                {O,    O,    null},
                {null, null, null},
                {X,    X,    null}
        });

        board.placeOAutomatically();

        assertThat(board, is(sameBeanAs(new Board(new Cog[][]{
                {O,    O,    O   },
                {null, null, null},
                {X,    X,    null}
        }))));
    }

}

----

public enum Cog {
    X, O
}

----

public class Field {

    private Cog cog;

    public Field(Cog cog) {
        this.cog = cog;
    }

    public Cog getCog() {
        return cog;
    }

    public boolean isEmpty() {
        return cog == null;
    }

    public void setCog(Cog cog) {
        this.cog = cog;
    }

}

----

import com.google.common.collect.ImmutableSet;
import com.google.common.collect.Sets;

import java.util.Set;

public class Line {

    private final Set<Field> fields;

    public Line(Field fieldOne, Field fieldTwo, Field fieldThree) {
        fields = ImmutableSet.of(fieldOne, fieldTwo, fieldThree);
    }

    public Set<Field> getFields() {
        return fields;
    }

    public boolean has(int count, Cog cog) {
        return fields.stream().map(Field::getCog).filter(c -> c == cog).count() == count;
    }

    public Field getEmptySpace() {
        long emptyFields = fields.stream().filter(Field::isEmpty).count();
        if (emptyFields != 1) {
            throw new IllegalStateException("there are " + emptyFields + " empty fields");
        }
        return fields.stream().filter(Field::isEmpty).findFirst().get();
    }

    public boolean intersects(Line line) {
        return !Sets.intersection(this.fields, line.fields).isEmpty();
    }

    @Override
    public boolean equals(Object o) {
        if (this == o) return true;
        if (o == null || getClass() != o.getClass()) return false;

        Line line = (Line) o;

        return fields.equals(line.fields);
    }

}

----

import com.google.common.collect.Sets;

import java.util.HashSet;
import java.util.Set;

public class PairOfLines {

    private final Line lineOne;
    private final Line lineTwo;

    public PairOfLines(Line lineOne, Line lineTwo) {
        this.lineOne = lineOne;
        this.lineTwo = lineTwo;
    }

    public Line getOne() {
        return lineOne;
    }

    public Line getTwo() {
        return lineTwo;
    }

    public Field getIntersection() {
        return Sets.intersection(lineOne.getFields(), lineTwo.getFields()).iterator().next();
    }

    public boolean has(int count, Cog cog) {
        Set<Field> allFields = new HashSet<>();
        allFields.addAll(lineOne.getFields());
        allFields.addAll(lineTwo.getFields());
        return allFields.stream().map(Field::getCog).filter(c -> c == cog).count() == count;
    }

}

----

import com.google.common.collect.ImmutableSet;

import java.util.Set;

import static blah.tictactoe.Cog.X;
import static blah.tictactoe.Cog.O;

public class Board {

    private final Field[][] matrix = new Field[3][3];

    public Board(Cog[][] matrix) {
        for (int i = 0; i < 3; i++) {
            for (int j = 0; j < 3; j++) {
                this.matrix[i][j] = new Field(matrix[i][j]);
            }
        }
    }

    public void placeOAutomatically() {
        // winning move
        for (Line line : allLines()) {
            if (line.has(2, O) && line.has(0, X)) {
                line.getEmptySpace().setCog(O);
                return;
            }
        }

        // block line of two
        for (Line line : allLines()) {
            if (line.has(2, X) && line.has(0, O)) {
                line.getEmptySpace().setCog(O);
                return;
            }
        }

        // block intersection
        for (PairOfLines pairOfLines : allPairsOfIntersectingLines()) {
            if (pairOfLines.getIntersection().isEmpty()
                    && pairOfLines.getOne().has(1, X)
                    && pairOfLines.getTwo().has(1, X)
                    && pairOfLines.has(0, O)) {
                pairOfLines.getIntersection().setCog(O);
                return;
            }
        }
    }


    private Set<Line> allLines() {
        return ImmutableSet.of(
                new Line(matrix[0][0], matrix[0][1], matrix[0][2]),
                new Line(matrix[1][0], matrix[1][1], matrix[1][2]),
                new Line(matrix[2][0], matrix[2][1], matrix[2][2]),

                new Line(matrix[0][0], matrix[1][0], matrix[2][0]),
                new Line(matrix[0][1], matrix[1][1], matrix[2][1]),
                new Line(matrix[0][2], matrix[1][2], matrix[2][2]),

                new Line(matrix[0][0], matrix[1][1], matrix[2][2]),
                new Line(matrix[0][2], matrix[1][1], matrix[2][0])
        );
    }

    private Set<PairOfLines> allPairsOfIntersectingLines() {
        ImmutableSet.Builder<PairOfLines> builder = new ImmutableSet.Builder<>();
        for (Line lineOne : allLines()) {
            for (Line lineTwo : allLines()) {
                if (!lineOne.equals(lineTwo) && lineOne.intersects(lineTwo)) {
                    builder.add(new PairOfLines(lineOne, lineTwo));
                }
            }
        }
        return builder.build();
    }

}

A few Maven dependencies needed:

<dependencies>
    <!-- COMPILE -->
    <dependency>
        <groupId>com.google.collections</groupId>
        <artifactId>google-collections</artifactId>
        <version>1.0</version>
    </dependency>

    <!-- TEST -->
    <dependency>
        <groupId>junit</groupId>
        <artifactId>junit-dep</artifactId>
        <version>4.11</version>
        <scope>test</scope>
    </dependency>
    <dependency>
        <groupId>org.hamcrest</groupId>
        <artifactId>hamcrest-library</artifactId>
        <version>1.3</version>
        <scope>test</scope>
    </dependency>
    <dependency>
        <groupId>org.hamcrest</groupId>
        <artifactId>hamcrest-core</artifactId>
        <version>1.3</version>
        <scope>test</scope>
    </dependency>
    <dependency>
        <groupId>com.shazam</groupId>
        <artifactId>shazamcrest</artifactId>
        <version>0.9</version>
        <scope>test</scope>
        <exclusions>
            <exclusion>
                <groupId>com.google.guava</groupId>
                <artifactId>guava</artifactId>
            </exclusion>
        </exclusions>
    </dependency>
</dependencies>

Answer 2

The easiest way to code an AI for this sort of game is the Minimax algorithm, which is an algorithm for 2-player games where each player is trying to make the best move available. You basically just need to code the algorithm as detailed on the wiki page and write a simple evaluation function which returns 1 for a win, 0 for a draw (or no result yet) and -1 for a loss (with more complex evaluation the algorithm can happily play chess). Tic-tac-toe is a simple enough game that you can do full depth evaluation for every move - obviously a more complex game like chess would require a cut-off.

You could also look at the slightly more complex but also more efficient version of this algorithm known as Alpha-Beta pruning.