Modular•2mo ago

Most efficient way to check for tictactoe board win

I want to write a litle tictactoe game (with arbitrary board size) in Mojo and was thinking how to go the hardest on optimizing it (just for fun). I was thinking of using a SIMD to hold the board where 0 is empty, 1 is player X and 2 is player O. Then i can check for a full board like:

all(board != 0)

all(board != 0)

For checking for a win i thought i could just pregenerate the wincombinations at compile time:

(1,1,0,0)
(1,0,1,0)
(1,0,0,1)
(0,1,1,0)
(0,1,0,1)
(0,0,1,1)

(1,1,0,0)
(1,0,1,0)
(1,0,0,1)
(0,1,1,0)
(0,1,0,1)
(0,0,1,1)

for a 2x2 board and then run

(board & reference).reduce_bit_count() == size

(board & reference).reduce_bit_count() == size

against all of these. But i am not sure how i can pregenerate all of these references at compile time.

2 Replies

DobyDabaDu•2mo ago

As I know, if u define the board size this way: alias b_size = 2 Then u can generate combinations at compile time, but if u want to get the size from user at runtime, it will not be possible One approach might be defining a max size then keeping the unnecessary cells 0

JanEric1OP•2mo ago

This is the signature i am thinking of:

fn _is_winner[size: Int, //, player: UInt8](board: BOARD[size*size]) -> Bool:

fn _is_winner[size: Int, //, player: UInt8](board: BOARD[size*size]) -> Bool:

So it should be doable at compile time, but i am just not sure how to go about it exactly. Thinking something like this:

    var reference: SIMD[DType.uint8, board.size]
    @parameter
    for row in range(size):
        reference = SIMD[DType.uint8, board.size](0)
        @parameter
        for col in range(size):
            reference[row * size + col] = player
        if (board & reference).reduce_bit_count() == size:
            return True

    var reference: SIMD[DType.uint8, board.size]
    @parameter
    for row in range(size):
        reference = SIMD[DType.uint8, board.size](0)
        @parameter
        for col in range(size):
            reference[row * size + col] = player
        if (board & reference).reduce_bit_count() == size:
            return True

But i dont know if that actually does everything i want at compile time or if i need other facilities Does anyone have ideas how I can improve this and ensure as much as possible happens at compile time?

Gaming

Programming

Most efficient way to check for tictactoe board win