# Evaluating if a tic-tac-toe configuration is a win

Does anyone know of an easy way to tell if an a two dimensional array is a tic-tac-toe victory? Ie. if we let `1`s represent player 1, `-1`s represent player 2 and `0`s are empty tiles then

`````` 1 -1  0
1 -1 -1
1  0  0
``````

is a win for player 1. I’d basically want a simple, fast function that returns true if a configuration is a win and false if not. Right now, the only thing I could think of is

``````function winq(board::Array{Int, 2}, player::Int)
combos = [[1, 2, 3],
[4, 5, 6],
[7, 8, 9],
[1, 4, 7],
[2, 5, 8],
[3, 6, 9],
[1, 5, 9],
[3, 5, 7]];
bools = board .== player
for combo in combos
if [bools[i] for i in combo] == [true, true, true]
return true
end
end
return false
end
``````

now if the above array is `tile`, then `winq(tile, +1) == true` and likewise, `winq(tile, -1) == false`

But I feel that there’s probably a way better way than explicitly writing out all the combos of indices that need to be checked for a victory. Does anyone have any suggestions using some array magic? I’d like this to be somewhat performant.

Test whether any summation of rows/columns/diagonals is equal to `3*player`?

These assume players are 1 and -1 as in your example, not 1 and 2 as in your description.
Array magic:

``````function winq2(A, player)
B = [1 1 1 0 0 0 0 0 0
0 0 0 1 1 1 0 0 0
0 0 0 0 0 0 1 1 1
1 0 0 1 0 0 1 0 0
0 1 0 0 1 0 0 1 0
0 0 1 0 0 1 0 0 1
1 0 0 0 1 0 0 0 1
0 0 1 0 1 0 1 0 0]
return any(B * vec(A) .== 3 * player)
end
``````

Speed:

``````function winq3(A, player)
win = 3 * player
@inbounds A[1] + A[2] + A[3] == win && return true
@inbounds A[4] + A[5] + A[6] == win && return true
@inbounds A[7] + A[8] + A[9] == win && return true
@inbounds A[1] + A[4] + A[7] == win && return true
@inbounds A[2] + A[5] + A[8] == win && return true
@inbounds A[3] + A[6] + A[9] == win && return true
@inbounds A[1] + A[5] + A[9] == win && return true
@inbounds A[3] + A[5] + A[7] == win && return true
return false
end
``````

Whoops, fixed the typo, thanks.

Thanks for the examples! I was thinking that there might be some fancy way of doing it fast without explicitly writing out the combinations of indices to check by hand (ie. imagine if instead, this was a 10x10 board) but that’s fine as I’m not dealing with a bigger board (… at least not yet).

Nothing magic, more of first principles, but this should work for arbitrary size (untested though).

``````function winq4(A, player)
N = size(A, 1)
@assert size(A, 2) == N
win = N * player
any(sum(A, 1) .== win) && return true
any(sum(A, 2) .== win) && return true
sum(A[i, i] for i = 1:N) == win && return true
sum(A[i, N + 1 - i] for i = 1:N) == win && return true
return false
end
``````

If you want it to be really fast you should look into meta-programming of a generalization of `winq3`, but that’s far more advanced.

Fastest way? Compute the answer any way you want for every possible game (e.g. using `winq3` above) and then store the results in a matrix with the index corresponding to the binary A for each player or a vector with the trinary index for the board.

it doesn’t take very long to determine that a game is not a win. A faster algorithm would probably loop through each row and column and quit as soon as you see something that isn’t the first element of that row or column.