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

New to Julia
1

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 1s represent player 1, -1s represent player 2 and 0s 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.

2

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

3

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
4

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).

5

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.

6

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. :wink:

7

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.