Play tic-tac-toe with random moves very fast

tictactoe.c

// Sample output:
//
// Win probability for first move with random agents:
// 0.115 0.102 0.116 
// 0.102 0.131 0.101 
// 0.116 0.102 0.116 
// Player 1 won 584650 times
// Player 2 won 288379 times
// 126971 ties
// 0.035250 seconds
// 28.368794 million games/sec
#include <stdint.h>
#include <stdio.h>
#include <time.h>

// It is possible to "invert" the game of tic-tac-toe for better optimization.
// Instead of trying to get 3 in a row in a 3x3 grid,
// consider a game where you try to get 3 in a row in any of 8 rows
// but each move can set a field in several rows.
static const uint32_t move_masks[9] = {
    0x40040040, 0x20004000, 0x10000404,
    0x04020000, 0x02002022, 0x01000200,
    0x00410001, 0x00201000, 0x00100110,
};

// Check if tic-tac-toe board has a winning configuration.
static inline uint32_t is_win(uint32_t player_board){
    return (player_board + 0x11111111) & 0x88888888;
}

// Compiler can optimize x % n if n is fixed.
uint32_t optimizable_mod(uint32_t x, uint32_t n){
    switch (n){
        case 2: return x % 2;
        case 3: return x % 3;
        case 4: return x % 4;
        case 5: return x % 5;
        case 6: return x % 6;
        case 7: return x % 7;
        case 8: return x % 8;
        case 9: return x % 9;
        default: return 0;
    }
}

// Fast random number generator.
uint32_t xorshift32(){
    static uint32_t x = 0x12345678;
    x ^= x << 13;
    x ^= x >> 17;
    x ^= x << 5;
    return x;
}

// Play a random game and output moves played.
uint32_t play_random_game(uint32_t player, uint32_t *moves){
    uint32_t boards[2] = {0, 0};
    uint32_t available_moves[9] = {0, 1, 2, 3, 4, 5, 6, 7, 8};
    for (uint32_t n_moves = 9; n_moves > 0; n_moves--){
        // Get board of player
        uint32_t board = boards[player - 1];
        // Choose random move.
        uint32_t i = optimizable_mod(xorshift32(), n_moves);
        uint32_t move = available_moves[i];
        // Delete move from available moves.
        available_moves[i] = available_moves[n_moves - 1];
        // Apply move to board.
        board |= move_masks[move];
        // Remember move.
        *moves++ = move;
        // Check if current player won the game and return the winner.
        if (is_win(board)) return player;
        // Update board of player.
        boards[player - 1] = board;
        // Next player, 1 -> 2, 2 -> 1.
        player = 3 - player;
    }
    // Mark end of game.
    *moves++ = -1;
    return 0;
}

int main(){
    // Run a few times to see that probabilities are consistent.
    for (int k = 0; k < 10; k++){
        // Start measuring time.
        double start_time = clock()/(double)CLOCKS_PER_SEC;
        // Count wins by player (tie, player 1, player 2).
        uint32_t wins[3] = {0, 0, 0};
        // Count wins by first move.
        uint32_t wins_by_move[9] = {0};
        // Simulate a million random games.
        int n_games = 1000*1000;
        for (int i = 0; i < n_games; i++){
            uint32_t player = 1;
            // Record which moves were played, last move is -1.
            uint32_t moves[10] = {0};
            uint32_t winner = play_random_game(player, moves);
            // Count wins.
            wins[winner]++;
            if (winner == player) wins_by_move[moves[0]]++;
        }
        // Stop measuring time.
        double delta_time = clock()/(double)CLOCKS_PER_SEC - start_time;
        // Print statistics.
        printf("Win probability for first move with random agents:\n");
        for (int y = 0; y < 3; y++){
            for (int x = 0; x < 3; x++){
                printf("%.3f ", wins_by_move[x + y*3]*1.0/wins[1]);
            }
            printf("\n");
        }
        printf("Player 1 won %u times\n", wins[1]);
        printf("Player 2 won %u times\n", wins[2]);
        printf("%u ties\n", wins[0]);
        printf("%f seconds\n", delta_time);
        printf("%f million games/sec\n", n_games*1e-6/delta_time);
        printf("\n");
    }
    
    return 0;
}