Tic Tac Toe

Does /prog/ know an efficient algorithm to check for a win/loss/draw in the game of Tic Tac Toe?

Let board be an array of integers where same numbers represent same players or blank, e.g. -1 and 1 for the players and 0 for blank.

Is there a more efficient alternative than checking it like this:
// check if player "1" won:
if ((board[0] == 1 && board[1] == 1 && board[2] == 1)
 || (board[3] == 1 && board[4] == 1 && board[5] == 1)
 || (board[6] == 1 && board[7] == 1 && board[8] == 1)
 || (board[0] == 1 && board[3] == 1 && board[6] == 1)
 || (board[1] == 1 && board[4] == 1 && board[7] == 1)
 || (board[2] == 1 && board[5] == 1 && board[8] == 1)
 || (board[0] == 1 && board[4] == 1 && board[8] == 1)
 || (board[2] == 1 && board[4] == 1 && board[6] == 1)) {
    // player "1" won
}

This is ucking fugly.

>>1

Well, look at the cell #'s
You're either checking n+1, n+3, or n+2

If that's the total size of your board, a brute force like that is really best your bet. It's fast, and it's not difficult to understand. Anything else would be unnecessary bloat.

You could rewrite into a 2D array, and then it's a case of two fors. But I doubt it's worth it.

0 1 2
3 4 5
6 7 8

if ((board[4] == 1 && ((board[0] == 1 && board[8] == 1)
                    || (board[2] == 1 && board[6] == 1)
                    || (board[1] == 1 && board[7] == 1)
                    || (board[3] == 1 && board[5] == 1))
 || (board[0] == 1 && ((board[1] == 1 && board[2] == 1)
                    || (board[3] == 1 && board[6] == 1))
 || (board[8] == 1 && ((board[2] == 1 && board[5] == 1)
                    || (board[6] == 1 && board[7] == 1)))
my worst case: 6 comparisons
your worst case: 10 comparisons

for (rows)
    while (col++ == col);
    if (col == cols) you win;

for (cols)
    while (row++ == row);
    if (row == rows) you win;
Similar things for diagonal

in fact, OP, your worst case is 13 comparisons in this occasion:

1 0 0
0 1 0
0 0 1

Store game state as bit pattern, use lookup tables. Exploit symmetry to trade speed vs. memory use.

>>7
and by that I meant

1 1 0
1 1 0
0 0 1
and that's 15 comparisons

Why not represent the whole board as a 16-bit integer and just AND it with predetermined values to test for whatever you want? It would certainly be an ENTERPRISE C SOLUTION.

>>10
Because that would be a total of 8 comparisons in the worst case instead of 6 up there.
ENTERPRISE++

>>5
I still prefer >>1-san's version. His example is the easiest to read and maintain. If there's an error with the game logic -- for example, if one the array indices was incorrect -- I'd have to do far more work to figure out the mistake in your code than in his code. Meanwhile, I highly doubt your ENTERPRISE optimisation is going to turnkey the performance metric to realtime.

This is a case of premature optimisation. Just leave it as is, OP, until you can demonstrate that it's a bottleneck to your program. Which it definitely isn't.

>>12
If I was looking for readability I think I'd use 2 fors like >>6 did, because it'd easier to transit from "1" to "-1" when checking (it would probably be better with 1 and 2 anyway)

I've seen a very elegant solution using two 8-bit bytes, one for each player (one of the squares was implicit or something, can't remember how that was done), and a rather clever mapping of the tiles to bits allowed simple integer arithmetic to determine if the player had won. It was around 6-8 instructions but you'd never think you'd be able to come up with something as beautiful as that once you understood how it works.

>>10
That's 7 bits wasted for a standard board. Unacceptable.

/* fix this shit because OP is an idiot */
for(int i = 0; i < 9; ++i) board[i] = ((1 - board[i] ^ 1) + 1) / 2

switch((board[4] & ((board[0] & board[8]) |
                    (board[1] & board[7]) |
                    (board[2] & board[6]) |
                    (board[3] & board[5]))) |
       (board[0] & ((board[1] & board[2]) |
                    (board[3] & board[6]))) |
       (board[8] & ((board[2] & board[5]) |
                    (board[6] & board[7]))))
{ case 1:
    /* player 1 wins */
    break;
  case 2:
    /* player 2 wins */
    break;
  default:
    abort("fix your shit, moron."); }

one comparison.

>>16
and ten extra math and assignment procedures. plus, there's a bug in your code.

>>17
and how many of those are in the first line that just fixes >>1's shitty decision to use -1 and 1 instead of 2 and 1?

>>16
>>18
You don't have to fix that, just comment + assume it. I said
e.g. -1 and 1 for the players and 0 for blank.

>>n
Thanks, gave me some ideas.

The original code (not mine btw) was simply too inefficient for REAL PROGRAMMERS. Just think about checking for a win of one player, then checking for a win of the other player, then checking for a draw, and all that every single round. Holy Sussman! This universe holds no REAL SOLUTIONS for me, goodbye. *dissolves into mist while giving God a one-finger salute*