testing tic tac toe win condition

Question

I'm looking for the most efficient java way to test if somebody has won at tic tac toe. The data is in a 2d array like so...

char[][] ticTacToe = 
    {{'X',' ','O'},
     {'O','X','O'},
     {'X',' ','X'},};

I know this isn't the professional way to initialize an array but I'm just testing here.

The best I can do for right now is an exhaustive if/else tree. Here's one of those trees...

if (ticTacToe[1][1] == 'X'){
        if (ticTacToe[0][0] == 'X'){
            if (ticTacToe[2][2] == 'X'){
                System.out.println("X wins");
            }
        }
        else if (ticTacToe[0][1] == 'X'){
             if (ticTacToe[2][1] == 'X'){
                System.out.println("X wins");
            }
        }
        else if (ticTacToe[1][0] == 'X'){
             if (ticTacToe[1][2] == 'X'){
                System.out.println("X wins");
            }
        }
        else if (ticTacToe[2][0] == 'X'){
             if (ticTacToe[0][2] == 'X'){
                System.out.println("X wins");
            }
        }
    }

This one only cares about what's in the middle

This is very basic and I want to improve it as far as minimizing lines of code goes.

Check this out:- http://stackoverflow.com/questions/1056316/algorithm-for-determining-tic-tac-toe-game-over-java — Rahul Tripathi, Aug 31 '13 at 14:26
You may as well be programming in BASIC. How about an Object Oriented approach? Make your tic tac toe board a class, and encapsulate the grid within it. Use a method, say checkEndCondition(), to determine whether the game is over. In this way, you are free to change how you represent the board and even how you test to see if the game is over without requiring any changes at all to the code that uses the grid. — scottb, Sep 07 '13 at 22:57
One way to test for the end condition would be to assign one player a value of +1, and the other player a value of -1. Iterate through the rows and columns (and the diagonals) and if any sum to a value of +3 or -3, then the game is over. — scottb, Sep 07 '13 at 22:59
@scottb, Where do you get the idea that the user has not already done that? Maybe his code is part of the `checkEndCondition()` method. — RaptorDotCpp, Sep 12 '13 at 14:52
@RaptorDotCpp: it is only possible to comment on what is shown or described. The OP described neither a Grid class nor a checkEndCondition() method. Check out MrLore's solution which is a complete application and notice how compact it is. — scottb, Sep 12 '13 at 15:06

גלעד ברקן · Answer 1 · 2013-09-09T01:56:05.713

Just for fun, keep two numbers, starting as zeros, one for X, one for O. Update them by oring with the moves. To check for a winner, first and, then xor with the mask.

277 & 273 ^ 273
0  ==> we have a winner.

276 & 273 ^ 273
1  ==> not.

277 == parseInt("100010101",2)
273 == parseInt("100010001",2)
276 == parseInt("100010100",2)

For more fun, here's an example that plays O in your favorite JavaScript console:

<!DOCTYPE html>
<html>
  <head>
    <meta http-equiv="Content-type" content="text/html;charset=UTF-8">
  </head>
  <body>
    <script>
    var x = 0, o = 0, count = 0, w = 0
        ws = [0007,0070,0700,0111,0222,0444,0124,0421]
    function t1(v){
        var w1 = 0
        for (var i in ws)
            w1 |= !(v & ws[i] ^ ws[i])
        return w1
    }
    function t(i){
        var ot = count % 2, m = 1 << (9 - i), bd = x | o
        if (!ot && (i > 9 || i < 1 || i != Math.floor(i)))
            return "Out of bounds."
        else if (m & bd)
            return "Position taken."
        if (ot){
            var n1 = 0, a1 = -2
            while (bd & (1 << n1))
                n1++
            var n = n1
            while (n1 < 9){
                var m1 = 1 << n1
                if (!(bd & m1)){
                    var bt = -mx(x,o | m1,count + 1)
                     if (bt > a1){
                         a1 = bt
                         n = n1
                     }
                }
                n1++
            }
            w = t1(o |= 1 << n)
        }
        else
            w = t1(x |= m)
        var b = "\n", p = 0400
        while (p > 0){
            if (p & x)
                b += "X"
            else if (p & o)
                b += "O"
            else b += "."
            if (p & 0110)
                b += "\n"
            p >>= 1
        }
        if (w)
            b += "\n\n" + (ot ? "O" : "X") + " wins!"
        else if (!(bd ^ 0777))
            b += "\n\nDraw."
        if (!ot){
            console.log(b + '\n\n"""')
            count++
            console.log(t(-1))
            count++
        }
        else
            return b + "\n"
        return '"'
    }
    function mx(x1,o1,c1){
        var ot1 = c1 % 2, w1 = ot1 ? t1(x1) : t1 (o1),
              b1 = x1 | o1, p = 0400
        if (w1)
            return -1
        if (!(b1 ^ 0777))
            return 0
        var a = -2
        while (p > 0){
            if (!(b1 & p))
                a = Math.max(a,-mx(ot1 ? x1 : x1 | p,ot1 ? o1 | p : o1,c1 + 1))
            p >>= 1
        }
        return a
    }
    console.log('              Plays O!'
            + '\nTo play, type t(MOVE); MOVE is from 1-9')
    </script>
  </body>
</html>

Nice suggestion! If he updates the masks as the players make moves then this makes it very simple to check. However, I'd recommend writing the [integer literals](http://docs.oracle.com/javase/specs/jls/se7/html/jls-3.html#jls-3.10.1) for the masks in [octal](http://en.wikipedia.org/wiki/Octal) rather than decimal, since one octal digit would correspond to each row of the tic-tac-toe board. E.g., `273 == 0421`. It's way easier for me to translate that into the binary representation of the board in my head than a base-10 or even base-16 version of the mask. — DaoWen, Sep 01 '13 at 21:23

Marcin Szymczak · Answer 2 · 2016-01-08T14:19:41.163

13

Mark board as 3x3 magicSquare and you have win when sum in line is 15.

enter image description here

edited Jan 08 '16 at 14:19

answered Sep 08 '13 at 00:11

Marcin Szymczak

11,199
5
55
63

That's exactly what I was thinking of but didn't get around to using that solution. – wjhplano Oct 21 '13 at 16:48

score 3 · Accepted Answer · answered Aug 31 '13 at 14:37

It's a bit verbose, but I think this is probably the most efficient way to do it (unless someone can come up with a clever way to check both diagonals at once).

public class TicTacToe
{
    char[][] ticTacToe = 
    {{'X',' ','O'},
     {'O','X','O'},
     {'X',' ','X'},};

    private Character winner = null;

    public Character getWinner()
    {
        return this.winner;
    }

    public boolean isSolved()
    {
        this.checkSolved();
        return this.winner != null;
    }

    private void checkSolved()
    {
        for(int i = 0; i < ticTacToe.length; i++)
        {
            Character win = checkRow(i);
            if(win != null || (win = checkColumn(i)) != null)
            {
                this.winner = win;
                return;
            }
        }
        //Check diagonal top left to bottom right
        if(this.ticTacToe[0][0] != ' ')
        {
            if(this.ticTacToe[0][0] == this.ticTacToe[1][1] &&
               this.ticTacToe[1][1] == this.ticTacToe[2][2])
            {
                this.winner = this.ticTacToe[0][0];
            }
        }
        //Check diagonal top right to bottom left
        else if(this.ticTacToe[0][2] != ' ')
        {
            if(this.ticTacToe[0][2] == this.ticTacToe[1][1] &&
               this.ticTacToe[1][1] == this.ticTacToe[2][0])
            {
                this.winner = this.ticTacToe[0][2];
            }
        }
    }

    private Character checkRow(int row)
    {
        if(this.ticTacToe[row][0] == ' ')
        {
            return null;
        }
        if(this.ticTacToe[row][0] == this.ticTacToe[row][1] &&
           this.ticTacToe[row][1] == this.ticTacToe[row][2])
        {
            return this.ticTacToe[row][0];
        }
        return null;
    }

    private Character checkColumn(int column)
    {
        if(this.ticTacToe[0][column] == ' ')
        {
            return null;
        }
        if(this.ticTacToe[0][column] == this.ticTacToe[1][column] &&
           this.ticTacToe[1][column] == this.ticTacToe[2][column])
        {
            return this.ticTacToe[column][0];
        }
        return null;
    }

    public static void main(String[] args)
    {
        TicTacToe ttt = new TicTacToe();
        if(ttt.isSolved())
        {
            System.out.println(ttt.getWinner());  // X
        }
    }
}

gee wiz. that is a pretty compact way of doing things. Thanks! — wjhplano, Sep 03 '13 at 11:55

score 1 · Answer 4 · answered Sep 01 '13 at 13:27

For a player, say 'x', there are 8 ways to win and each corresponds to 3 'x' in a row/column/diagonal. Hence, you can create an array of length 8 and each item corresponds to the number of 'x' in that row/column/diagonal. When the player chooses a move, then you update the array and check whether there exists 3 in the array. Although it needs more space, it is easier to generalize to a large board.

score 0 · Answer 5 · answered Aug 31 '13 at 15:45

0

There are four different ways to win at tick-tack-toe:

form a horizontal line
form a vertical line
form a diagonal line from the upper-left to the lower-right corner
form a diagonal line from the lower-left to the upper-right corner

All of these four win-conditions can be solved with a for-loop. The advantage of this solution is that it can be applied to any matrix-size.

answered Aug 31 '13 at 15:45

Philipp

67,764
9
118
153

this method is basically Brute Force, it is fine for 3x3 matrix but the performance will degrade for matrices greater than 3x3. – HQuser Mar 05 '17 at 19:45

testing tic tac toe win condition

5 Answers5

Linked