Checking Tic-Tac-Toe Win conditions?

[BUU]

I was hanging out on irc (freenode, #perl) this morning chatting about this and that, mostly about crappy programming languages and so forth. Someone entering the conversation mentioned that once he sat on a class of VB students who had to write a tic-tac-toe "gui" in VB, no AI, just checking for win conditions. He recounted that all of the students solved the problem by writing 16 or 20 or however many lines of code that looked like:

if( $board[0][0] eq 'x' and $board[0][1] eq 'x' and $board[0][2] eq 'x
+' ) { #win! }

Or whatever the VB equivalent happened to be. Naturally, as a Perl programmer who strives to be as concise as possible (while still being clear and understandable of course), I was horrified by all the repeated code. But then when I stopped to think how I would do it, I had problems coming up with a way that was substantially better. So I pose the question to you: Given a datastructure, how do you check for a tic-tac-toe win condition?

Feel free to assume any data structure, I have arbitrarily decided the default datastructure will be a 2d array containing 'x's, 'o's and 'undefs', whose meaning should be obvious. Using a different one is perfectly acceptable, just make sure you describe said datastructure.

(And yes, I promise I'm not going to steal *anybody's* hard work and fraudently use it to gain a job. Not that I'm bitter. This "challenge" has nothing to do with anything in the real world and is merely the result of a late night conversation on IRC.)

[Chady]

Okay, here's my take.

• my board is some kind of a 2D array.
• 'x' are 1.
• 'o' are -1.
• empty is 0.

we look for an absolute 3. But I'm sure there is a more mathematical way for this:

my @board;
while (<DATA>) {
        chomp;
        push @board, [split / /];
}

for my $i (0 .. 2) {
        my ($t1, $t2, $t3, $t4) = (0,0,0,0);
        for my $j ( 0 .. 2 ) {
                $t1 += $board[$i][$j];
                $t2 += $board[$j][$i];
                $t3 += $board[$j][$j];
                $t4 += $board[2 - $j][$j];
        }
    
        if (abs($t1) == 3 || abs($t2) == 3 
                || abs($t3) == 3 || abs($t4) == 3) {
                print "Win.\n";
                last;
        }
}


__DATA__
1 0 1
-1 1 -1
1 0 1

[ambrus]

See also (Golf) Tic Tac Toe.

[davido]

If you take each 3x3 game grid and flatten it to a string of nine characters, this can be solved with a regexp. This particular method of solving it wasn't really touched upon in (Golf) Tic Tac Toe, but works great. The conversion of a 3x3 grid to a single flat string is trivial, so I'll just demonstrate the regexp portion of the solution.

The regexp can be expressed in a way that tests for one of four conditions. I started out with a slightly more complex regexp, and then was able to see the forest through the trees, and found a way to boil it down to this common denominator.

In the following snippet, I never placed any 'o's because I wanted to keep it visually clear what was going on. The hyphens could be replaced with x's and o's as though a real game were being played, and the regexp will discover whether X or O wins. I just wanted to show each of the winning possibilities, so I used hyphens to isolate X.

Here's the code:

use strict;
use warnings;

# Assume that the 3x3 AoA has been flattened to a single string.
# Each string, therefore, equates to a single game.

my @games = (   "x---x---x",    # Diag from top left. 1
                "--x-x-x--",    # Diag from top right. 3
                "x--x--x--",    # Vert from top left. 2
                "xxx------",    # Horiz from top left. 4
                "---xxx---",    # Horiz from mid left. 4
                "------xxx",    # Horiz from bottom left. 4
                "-x--x--x-",    # Vert from top mid. 2
                "--x--x--x"  );
            

my $i;
foreach my $game ( @games ) {
    print "Game ", ++$i, "\t";
    if ( $game =~ m/ 
                    ([xo])
                    (?:
                         (?:...\1){2}
                      |  (?:..\1){2}
                      |  (?:.\1){2}
                      |  \1{2}(?=(?:...){0,2}$)
                    )
                   /ix ){
        print "$1 wins.\n";
    } else {
        print "no winner\n";
    }
}

Update:
Here's a golfier version that uses the same solution technique:

print m/([xo])((...\1){2}|(..\1){2}|(.\1){2}|\1{2}(?=(...){0,2}$))/i?
"$1 wins.\n":"No winner.\n" foreach qw/x---x---x --x-x-x-- x--x--x-- 
xxx------ ---xxx--- ------xxx -x--x--x- --x--x--x x---x-x--/;

Update2: Fixed a problem that would allow misaligned 3-in-a-rows to win when they shouldn't.

[TedPride]

Board state is stored in $b in numeric values of 0 (nothing), 1 (one person) and 2 (other person). $m keeps track of whose move it currently is, and is multiplied by -1 each turn. The board check is as follows:

for ($i = 0; $i < 3; $i++) {
    if ($b[$i][0] == $m && $b[$i][1] == $m && $b[$i][2] == $m) { &win(
+$m); }
    if ($b[0][$i] == $m && $b[1][$i] == $m && $b[2][$i] == $m) { &win(
+$m); }
}
if ($b[0][0] == $m && $b[1][1] == $m && $b[2][2] == $m) { &win($m); }
if ($b[0][0] == $m && $b[1][1] == $m && $b[2][2] == $m) { &win($m); }

It requires one loop and four check lines.

[TedPride]

Or...

@m = (0,1,2, 3,4,5, 6,7,8, 0,3,6, 1,4,7, 2,5,8, 0,4,8, 2,4,6);
for ($i = 0; $i < 22; $i += 3)
    { &win($t) if @g[@m[$i]] == $t && @g[@m[$i+1]] == $t && @g[@m[$i+2
+]] == $t; }

Where @m = win matches, $t = turn, @g = board setup.

[dragonchild]

One alternative, similar to the regex, is to use bit-wise AND. So, you'd create a bitmap of your board using vec() and compare it to known win conditions (which can be pre-generated). This is a very C-ish way of doing it.