Magic Square

[Mathhead200]

Let the tic-tac-toe board be represented by a map from int to Mark (some type that represents a mark, possibly an enum), and with its indexes organized as a magic square: http://en.wikipedia.org/wiki/Magic_square

//(This has been translated from Java.)
//Don't take too literally. Read as pseudo-code.
//-- Christopher D'Angelo

const int S = 3; //side
const int N = S * S; //total number of squares
const int SUM = S * (N + 1) / 2;

bool hasWinner(map<int, Mark> board, int move) {
	Mark mark = board[move];
	int d = SUM - move;
	int n = (d - 1) / 2;
	for( int a = 1; a <= n; a++ ) {
		if( a == move )
			continue;
		int b = d - a;
		if( b != move && b <= N && board.get(a) == mark && board.get(b) == mark )
			return true;
	}
	return false;
}

1. Does this algorithm work? (It seems to.)
2. Is it efficient? (Optimization?)
3. Can it be expanded to a more general case?

(Let me know if you have questions...)

[ne555]

1- Yes, for 3x3 squares.
2- No. b<=N is losing time.
3- But the disposition is not unique...

[Mathhead200]

b<=N is losing time

What do you mean? (That's little n == (d - 1) / 2, not big N.)

But the disposition is not unique...

Care to elaborate?

[ne555]

About losing time, make a desk test.

About disposition, in bigger n you may test cells that make the sum but are not aligned.

[helios]

S * (N + 1) / 2

Is this supposed to be Gauss' expression for calculating

int sum=0;
for (int i=1;i<=n;i++)
    sum+=i;

?
If so, it's incorrect. You put a third degree polynomial in there. It should be either (S * (S + 1) / 2) or (N * (N + 1) / 2), depending on exactly what you're trying to sum.

Honestly, I don't get what SUM is supposed to be.

[ne555]

The sum of the magic square.
Like in a 3x3 every line sum 15.

[Mathhead200]

I still don't see what you mean about losing time...

As for squares not being aligned in non-3x3 I'll look at it, but is there perhaps another condition (more general condition) that will keep that from happening, or is this just a fluke that it works for a 3x3?

[ne555]

You don't understand the algorithm.
I doubt that you have done a desk test.

In tic-tac-toe you need to check every row, column and the principal diagonals. This is done every time you make a play, only in the affected lines.
The `trick' with the magic 3x3 square is that every row, column or diagonal sum 15 and the reverse also holds. If there is a way to add up to 15 (with different numbers), then those cells are aligned.

Now losing time:
Suppose that we play the `1' position.
d: the difference that we need to get is 14.
n: is 6. That means that the loop will execute 6 times. However look at the magic square, the `1' is in just 2 lines.

Follow the loop. You'll realize that test every cell to try to get to the sum.
`1' repeated cell, by-pass
`2' will need a `12', too much
`3' will need a `11', too much
`4' will need a `10', too much
`5' will need a `9', OK they are aligned, test (1,5,9) for the same `figure'
`6' will need a `8', OK they are aligned, test (1,6,8) for the same `figure'

As you can see we are starting the loop too soon.

[Mathhead200]

ne555 wrote:

As you can see we are starting the loop too soon.

I came up with this, based on what you pointed out:

const int S = 3; //side
const int N = S * S; //total number of squares
const int SUM = S * (N + 1) / 2;

bool hasWinner(map<int, Mark> board, int move) {
	Mark mark = board[move];
	int d = SUM - move;
	int n = (d - 1) / 2;
	int a = d - N; //new starting point
	if( a < 1 )
		a = 1;
	int b = d - a;
	while( a <= n ) {
		if( a != move && b != move && board.get(a) == mark && board.get(b) == mark )
			return true;
		a++;
		b--;
	}
	return false;
}

I haven't run this yet though. Does it look like it will work? (It seems it will run faster.)

ne555 wrote:

You don't understand the algorithm.

I can up with it last semester in my AI class. (I wanted a more elegant way to check for a win in Tic-Tac-Toe.) What made you think that I didn't understand it?

ne555 wrote:

... the reverse also holds. If there is a way to add up to 15 (with different numbers), then those cells are aligned.

I found three criteria:
(1) a, b, c in [1,9] = [1,N]
(2) a, b, c are unique
(3) a + b + c = 15

I found by testing that win iff (1) and (2) and (3), but I really don't know how to prove it, other then by exhaustion. (Why does this happen?) I was searching for a discussion, and possibly a way to add new/more "criteria" so that the algorithm holds true for larger magic squares, (but I suspect that it doesn't.) For instance, what about Connect 4? (I know that's not a square.) I would also like to examine the efficiency of this algorithm compared to other Tic-Tac-Toe win-check algorithms: e.g. a chain of if statements, loop(s), etc...

[Mathhead200]

(bump) Any other thoughts?