$ make
rm -f train play 2>/dev/null
cc train.c common.h -o train -O3 -Wall -W -ffast-math -lm
cc play.c common.h -o play -O3 -Wall -W -ffast-math -lm

$ ./train 2000000
Training neural network with 2000000 games
Training neural network against 2000000 random games...
Games: 10000, Wins: 7987 (79.9%), Losses: 1003 (10.0%), Ties: 1010 (10.1%)
Games: 20000, Wins: 8621 (86.2%), Losses: 282 (2.8%), Ties: 1097 (11.0%)
Games: 30000, Wins: 8653 (86.5%), Losses: 219 (2.2%), Ties: 1128 (11.3%)
Games: 40000, Wins: 8720 (87.2%), Losses: 198 (2.0%), Ties: 1082 (10.8%)
...
Games: 1990000, Wins: 8376 (83.8%), Losses: 33 (0.3%), Ties: 1591 (15.9%)
Games: 2000000, Wins: 8409 (84.1%), Losses: 35 (0.3%), Ties: 1556 (15.6%)

Training complete!
Neural network saved to ttt_nn.bin

$ ll ttt_nn.bin
11K ttt_nn.bin

$ ./play
Neural network loaded from ttt_nn.bin
Ready to play! You are X, the computer is O.
Welcome to Tic Tac Toe! You are X, the computer is O.
Enter positions as numbers from 0 to 8 (see picture).
... 012
... 345
... 678

Your move (0-8):

Your move (0-8): 4
... 012
.X. 345
... 678

Computer\'s move:
Neural network move probabilities:
  0.0%   0.0%   0.0%
  0.0%   0.0%   0.0%
100.0%*#   0.0%   0.0%
Sum of all probabilities: 1.00

Computer placed O at position 6
... 012
.X. 345
O.. 678

Your move (0-8):

// Game board representation.
typedef struct {
    char board[9];          // Can be "." (empty) or "X", "O".
    int current_player;     // 0 for player (X), 1 for computer (O).
} GameState;

/* Neural network structure. For simplicity we have just one hidden layer and fixed sizes.
 * However for this problem going deeper than one hidden layer is useless. */
typedef struct {
    // Weights and biases.
    float weights_ih[NN_INPUT_SIZE * NN_HIDDEN_SIZE];
    float weights_ho[NN_HIDDEN_SIZE * NN_OUTPUT_SIZE];
    float biases_h[NN_HIDDEN_SIZE];
    float biases_o[NN_OUTPUT_SIZE];

    // Activations are part of the structure itself for simplicity.
    float inputs[NN_INPUT_SIZE];
    float hidden[NN_HIDDEN_SIZE];
    float raw_logits[NN_OUTPUT_SIZE]; // Outputs before softmax().
    float outputs[NN_OUTPUT_SIZE];    // Outputs after softmax().
} NeuralNetwork;

// Neural network parameters.
#define NN_INPUT_SIZE 18    // 这个大小跟棋盘状态的编码方式有关，后面会讲到。
#define NN_HIDDEN_SIZE 100
#define NN_OUTPUT_SIZE 9

    18 (inputs) * 100 (hidden) +
    100 (hidden) * 9 (outputs) weights +
    100 + 9 biases
    = 2809

/* Convert board state to neural network inputs. Note that we use a peculiar encoding I descrived here:
 * https://www.youtube.com/watch?v=EXbgUXt8fFU
 *
 * Instead of one-hot encoding, we can represent N different categories
 * as different bit patterns. In this specific case it's trivial:
 *
 * 00 = empty
 * 10 = X
 * 01 = O
 *
 * Two inputs per symbol instead of 3 in this case, but in the general case
 * this reduces the input dimensionality A LOT.
 *
 * LEARNING OPPORTUNITY: You may want to learn (if not already aware) of
 * different ways to represent non scalar inputs in neural networks:
 * One hot encoding, learned embeddings, and even if it's just my random
 * exeriment this "permutation coding" that I'm using here.
 */
static void board_to_inputs(GameState *state, float *inputs) {
    for (int i = 0; i < 9; i++) {
        if (state->board[i] == '.') {
            inputs[i*2] = 0;
            inputs[i*2+1] = 0;
        } else if (state->board[i] == 'X') {
            inputs[i*2] = 1;
            inputs[i*2+1] = 0;
        } else {  // 'O'
            inputs[i*2] = 0;
            inputs[i*2+1] = 1;
        }
    }
}

/* Get the best move for the computer using the neural network.
 * Neural network foward pass (inference). We store the activations
 * so we can also do backpropagation later. */
static void forward_pass(NeuralNetwork *nn, float *inputs) {
    memcpy(nn->inputs, inputs, NN_INPUT_SIZE * sizeof(float));

    // Input to hidden layer.
    for (int i = 0; i < NN_HIDDEN_SIZE; i++) {
        float sum = nn->biases_h[i];
        for (int j = 0; j < NN_INPUT_SIZE; j++) {
            sum += inputs[j] * nn->weights_ih[j * NN_HIDDEN_SIZE + i];
        }
        nn->hidden[i] = relu(sum);
    }

    // Hidden to output (raw logits).
    for (int i = 0; i < NN_OUTPUT_SIZE; i++) {
        nn->raw_logits[i] = nn->biases_o[i];
        for (int j = 0; j < NN_HIDDEN_SIZE; j++) {
            nn->raw_logits[i] += nn->hidden[j] * nn->weights_ho[j * NN_OUTPUT_SIZE + i];
        }
    }

    // Apply softmax to get the final probabilities.
    softmax(nn->raw_logits, nn->outputs, NN_OUTPUT_SIZE);
}

/* ReLU activation function */
static float relu(float x) {
    return x > 0 ? x : 0;
}

/* Apply softmax activation function to an array input, and
 * set the result into output. */
static void softmax(float *input, float *output, int size) {
    /* Find maximum value then subtact it to avoid numerical stability issues with exp(). */
    float max_val = input[0];
    for (int i = 1; i < size; i++) {
        if (input[i] > max_val) {
            max_val = input[i];
        }
    }

    // Calculate exp(x_i - max) for each element and sum.
    float sum = 0.0f;
    for (int i = 0; i < size; i++) {
        output[i] = expf(input[i] - max_val);
        sum += output[i];
    }

    // Normalize to get probabilities.
    if (sum > 0) {
        for (int i = 0; i < size; i++) {
            output[i] /= sum;
        }
    } else {
        /* Fallback in case of numerical issues, just provide a uniform distribution. */
        for (int i = 0; i < size; i++) {
            output[i] = 1.0f / size;
        }
    }
}

get_computer_move
  |- board_to_inputs
  |- forward_pass
  |- for (i=0; i<9; i++)
  |     if (state->board[i] == '.' && (best_move == -1 || nn->outputs[i] > best_legal_prob)) {
  |         best_move = i;
  |         best_legal_prob = nn->outputs[i];
  |     }
  |- return best_move

/* Get the best move for the computer using the neural network.
 * Note that there is no complex sampling at all, we just get
 * the output with the highest value THAT has an empty tile. */
static int get_computer_move(GameState *state, NeuralNetwork *nn, int display_probs) {
    float inputs[NN_INPUT_SIZE];
    board_to_inputs(state, inputs);

    forward_pass(nn, inputs); // 得到了下一步的概率分布，保存在 nn->outputs[] 中

    int best_move = -1;
    float best_legal_prob = -1.0f;
    for (int i = 0; i < 9; i++) {
        if (state->board[i] == '.' && (best_move == -1 || nn->outputs[i] > best_legal_prob)) {
            best_move = i;
            best_legal_prob = nn->outputs[i];
        }
    }

    return best_move;
}

int main(int argc, char **argv) {
    int random_games = 150000; // Fast and enough to play in a decent way.
    const char *output_file = "ttt_nn.bin";
    
    if (argc > 1) random_games = atoi(argv[1]);
    if (argc > 2) output_file = argv[2];
    
    srand(time(NULL));

    // Initialize neural network.
    NeuralNetwork nn;
    init_neural_network(&nn);
    printf("Training neural network with %d games\n", random_games);
    
    // Train against random moves.
    if (random_games > 0) train_against_random(&nn, random_games);

    // Save the trained neural network
    save_neural_network(&nn, output_file);
    return 0;
}

main
  |- init_neural_network
  |- train_against_random
  |   |- for (i=0; i<num_games; i++)
  |        play_random_game
  |          |- init_game
  |          |- while (!check_game_over(&state, &winner)) {
  |          |    if (state.current_player == 0)   // Random player's turn (X)
  |          |        move = get_random_move(&state);
  |          |    else  // Neural network's turn (O)
  |          |        move = get_computer_move(&state, nn, 0);
  |          |    char symbol = (state.current_player == 0) ? 'X' : 'O';
  |          |    state.board[move] = symbol;
  |          |    move_history[(*num_moves)++] = move;
  |          |    state.current_player = !state.current_player;
  |          |- learn_from_game
  |               |- backprop
  |- save_neural_network

/* Initialize a neural network with random weights, we should
 * use something like He weights since we use RELU, but we don't care as this is a trivial example. */
#define RANDOM_WEIGHT() (((float)rand() / RAND_MAX) - 0.5f)
void init_neural_network(NeuralNetwork *nn) {
    // Initialize weights with random values between -0.5 and 0.5
    for (int i = 0; i < NN_INPUT_SIZE * NN_HIDDEN_SIZE; i++)
        nn->weights_ih[i] = RANDOM_WEIGHT();
    for (int i = 0; i < NN_HIDDEN_SIZE * NN_OUTPUT_SIZE; i++)
        nn->weights_ho[i] = RANDOM_WEIGHT();
    for (int i = 0; i < NN_HIDDEN_SIZE; i++)
        nn->biases_h[i] = RANDOM_WEIGHT();
    for (int i = 0; i < NN_OUTPUT_SIZE; i++)
        nn->biases_o[i] = RANDOM_WEIGHT();
}

/* Train the neural network against random moves. */
void train_against_random(NeuralNetwork *nn, int num_games) {
    int move_history[9];
    int wins = 0, losses = 0, ties = 0;

    printf("Training neural network against %d random games...\n", num_games);

    int played_games = 0;
    for (int i = 0; i < num_games; i++) {
        char winner = play_random_game(nn, move_history);
    }
    printf("\nTraining complete!\n");
}

/* Play a game against random moves and learn from it.
 *
 * This is a very simple Montecarlo Method applied to reinforcement learning:
 *
 * 1. We play a complete random game (episode).
 * 2. We determine the reward based on the outcome of the game.
 * 3. We update the neural network in order to maximize future rewards.
 *
 * LEARNING OPPORTUNITY: while the code uses some Montecarlo-alike
 * technique, important results were recently obtained using
 * Montecarlo Tree Search (MCTS), where a tree structure repesents
 * potential future game states that are explored according to
 * some selection: you may want to learn about it. */
char play_random_game(NeuralNetwork *nn, int *move_history) {
    GameState state;
    char winner = 0;
    int num_moves = 0;

    init_game(&state);

    while (!check_game_over(&state, &winner)) {
        int move;

        if (state.current_player == 0) {  // Random player's turn (X)
            move = get_random_move(&state);
        } else {  // Neural network's turn (O)
            move = get_computer_move(&state, nn, 0);
        }

        /* Make the move and store it: we need the moves sequence during the learning stage. */
        char symbol = (state.current_player == 0) ? 'X' : 'O';
        state.board[move] = symbol;
        move_history[num_moves++] = move;

        // Switch player.
        state.current_player = !state.current_player;
    }

    // Learn from this game - neural network is 'O' (even-numbered moves).
    learn_from_game(nn, move_history, num_moves, 1, winner);
    return winner;
}

/* Get a random valid move, this is used for training against a random opponent.
 * Note: this function will loop forever if the board is full, but here we want simple code. */
int get_random_move(GameState *state) {
    while(1) {
        int move = rand() % 9;
        if (state->board[move] != '.') continue;
        return move;
    }
}

    while (!check_game_over(&state, &winner)) {
        int move;

        if (state.current_player == 0) {  // Random player's turn (X)
            move = get_random_move(&state);
        } else {  // Neural network's turn (O)
            move = get_computer_move(&state, nn, 0);
        }

        /* Make the move and store it: we need the moves sequence during the learning stage. */
        char symbol = (state.current_player == 0) ? 'X' : 'O';
        state.board[move] = symbol;
        move_history[num_moves++] = move;

        // Switch player.
        state.current_player = !state.current_player;
    }

    // Learn from this game - neural network is 'O' (even-numbered moves).
    learn_from_game(nn, move_history, num_moves, 1, winner);

        float move_importance = 0.5f + 0.5f * (float)move_idx/(float)num_moves;
        float scaled_reward = reward * move_importance;

/* Train the neural network based on game outcome.
 *
 * The move_history is just an integer array with the index of all the moves. */
void learn_from_game(NeuralNetwork *nn, int *move_history, int num_moves, int nn_moves_even, char winner) {
    float reward;
    char nn_symbol = nn_moves_even ? 'O' : 'X';

    if (winner == 'T') {
        reward = 0.3f;  // Small reward for draw
    } else if (winner == nn_symbol) {
        reward = 1.0f;  // Large reward for win
    } else {
        reward = -2.0f; // Negative reward for loss
    }

    GameState state;
    float target_probs[NN_OUTPUT_SIZE];

    // Process each move the neural network made.
    for (int move_idx = 0; move_idx < num_moves; move_idx++) {
        // Skip if this wasn't a move by the neural network.
        if ((nn_moves_even && move_idx % 2 != 1) || (!nn_moves_even && move_idx % 2 != 0)) {
            continue;
        }

        // Recreate board state BEFORE this move was made.
        init_game(&state);
        for (int i = 0; i < move_idx; i++) {
            char symbol = (i % 2 == 0) ? 'X' : 'O';
            state.board[move_history[i]] = symbol;
        }

        // Convert board to inputs and do forward pass.
        float inputs[NN_INPUT_SIZE];
        board_to_inputs(&state, inputs);
        forward_pass(nn, inputs);

        /* The move that was actually made by the NN, that is the one we want to reward (positively or negatively). */
        int move = move_history[move_idx];

        /* Here we can't really implement temporal difference in the strict
         * reinforcement learning sense, since we don't have an easy way to
         * evaluate if the current situation is better or worse than the previous state in the game.
         *
         * However "time related" we do something that is very effective in
         * this case: we scale the reward according to the move time, so that
         * later moves are more impacted (the game is less open to different solutions as we go forward).
         *
         * We give a fixed 0.5 importance to all the moves plus a 0.5 that depends on the move position.
         * NOTE: this makes A LOT of difference. Experiment with different values.
         *
         * LEARNING OPPORTUNITY: Temporal Difference in Reinforcement Learning
         * is a very important result, that was worth the Turing Award in
         * 2024 to Sutton and Barto. You may want to read about it. */
        float move_importance = 0.5f + 0.5f * (float)move_idx/(float)num_moves;
        float scaled_reward = reward * move_importance;

        /* Create target probability distribution: let's start with the logits all set to 0. */
        for (int i = 0; i < NN_OUTPUT_SIZE; i++)
            target_probs[i] = 0;

        /* Set the target for the chosen move based on reward: */
        if (scaled_reward >= 0) {
            /* For positive reward, set probability of the chosen move to 1, with all the rest set to 0. */
            target_probs[move] = 1;
        } else {
            /* For negative reward, distribute probability to OTHER valid moves,
             * which is conceptually the same as discouraging the move that we want to discourage. */
            int valid_moves_left = 9-move_idx-1;
            float other_prob = 1.0f / valid_moves_left;
            for (int i = 0; i < 9; i++) {
                if (state.board[i] == '.' && i != move) {
                    target_probs[i] = other_prob;
                }
            }
        }

        /* Call the generic backpropagation function, using our target logits as target. */
        backprop(nn, target_probs, LEARNING_RATE, scaled_reward);
    }
}

/* Derivative of ReLU activation function */
float relu_derivative(float x) {
    return x > 0 ? 1.0f : 0.0f;
}

/* Backpropagation function.
 * The only difference here from vanilla backprop is that we have
 * a 'reward_scaling' argument that makes the output error more/less
 * dramatic, so that we can adjust the weights proportionally to the reward we want to provide. */
void backprop(NeuralNetwork *nn, float *target_probs, float learning_rate, float reward_scaling) {
    float output_deltas[NN_OUTPUT_SIZE];
    float hidden_deltas[NN_HIDDEN_SIZE];

    /* === STEP 1: Compute deltas === */

    /* Calculate output layer deltas:
     * Note what's going on here: we are technically using softmax as output function and cross entropy as loss,
     * but we never use cross entropy in practice since we check the progresses in terms of winning the game.
     *
     * Still calculating the deltas in the output as:  output[i] - target[i]
     * Is exactly what happens if you derivate the deltas with softmax and cross entropy.
     *
     * LEARNING OPPORTUNITY: This is a well established and fundamental result in neural networks, you may want to read more about it. */
    for (int i = 0; i < NN_OUTPUT_SIZE; i++)
        output_deltas[i] = (nn->outputs[i] - target_probs[i]) * fabsf(reward_scaling);

    // Backpropagate error to hidden layer.
    for (int i = 0; i < NN_HIDDEN_SIZE; i++) {
        float error = 0;
        for (int j = 0; j < NN_OUTPUT_SIZE; j++) {
            error += output_deltas[j] * nn->weights_ho[i * NN_OUTPUT_SIZE + j];
        }
        hidden_deltas[i] = error * relu_derivative(nn->hidden[i]);
    }

    /* === STEP 2: Weights updating === */

    // Output layer weights and biases.
    for (int i = 0; i < NN_HIDDEN_SIZE; i++)
        for (int j = 0; j < NN_OUTPUT_SIZE; j++)
            nn->weights_ho[i * NN_OUTPUT_SIZE + j] -= learning_rate * output_deltas[j] * nn->hidden[i];

    for (int j = 0; j < NN_OUTPUT_SIZE; j++)
        nn->biases_o[j] -= learning_rate * output_deltas[j];

    // Hidden layer weights and biases.
    for (int i = 0; i < NN_INPUT_SIZE; i++)
        for (int j = 0; j < NN_HIDDEN_SIZE; j++)
            nn->weights_ih[i * NN_HIDDEN_SIZE + j] -= learning_rate * hidden_deltas[j] * nn->inputs[i];

    for (int j = 0; j < NN_HIDDEN_SIZE; j++)
        nn->biases_h[j] -= learning_rate * hidden_deltas[j];
}

/* Save neural network parameters to a file */
void save_neural_network(NeuralNetwork *nn, const char *filename) {
    FILE *file = fopen(filename, "wb");
    if (file == NULL) {
        printf("Error opening file for writing: %s\n", filename);
        return;
    }
    
    // Write weights and biases
    fwrite(nn->weights_ih, sizeof(float), NN_INPUT_SIZE * NN_HIDDEN_SIZE, file);
    fwrite(nn->weights_ho, sizeof(float), NN_HIDDEN_SIZE * NN_OUTPUT_SIZE, file);
    fwrite(nn->biases_h, sizeof(float), NN_HIDDEN_SIZE, file);
    fwrite(nn->biases_o, sizeof(float), NN_OUTPUT_SIZE, file);
    
    fclose(file);
    printf("Neural network saved to %s\n", filename);
}

/* Load neural network parameters from a file */
int load_neural_network(NeuralNetwork *nn, const char *filename) {
    FILE *file = fopen(filename, "rb");
    if (file == NULL) {
        printf("Error opening file for reading: %s\n", filename);
        return 1;
    }
    
    // Read weights and biases
    size_t items_read = 0;
    items_read += fread(nn->weights_ih, sizeof(float), NN_INPUT_SIZE * NN_HIDDEN_SIZE, file);
    items_read += fread(nn->weights_ho, sizeof(float), NN_HIDDEN_SIZE * NN_OUTPUT_SIZE, file);
    items_read += fread(nn->biases_h, sizeof(float), NN_HIDDEN_SIZE, file);
    items_read += fread(nn->biases_o, sizeof(float), NN_OUTPUT_SIZE, file);
    
    fclose(file);
    
    // Check if we read the expected number of items
    size_t expected_items = NN_INPUT_SIZE * NN_HIDDEN_SIZE + 
                           NN_HIDDEN_SIZE * NN_OUTPUT_SIZE + 
                           NN_HIDDEN_SIZE + 
                           NN_OUTPUT_SIZE;
    
    if (items_read != expected_items) {
        printf("Error: Read %zu items, expected %zu\n", items_read, expected_items);
        return 2;
    }
    
    printf("Neural network loaded from %s\n", filename);
    return 0;
}

int main(int argc, char **argv) {
    const char *input_file = "ttt_nn.bin";
    
    if (argc > 1) input_file = argv[1];
    
    // Load neural network from file
    NeuralNetwork nn;
    if (load_neural_network(&nn, input_file)) {
        printf("Failed to load neural network.\n");
        return 1;
    }

    printf("Ready to play! You are X, the computer is O.\n");
    
    // Play game with human
    while(1) {
        char play_again;
        play_game(&nn);

        printf("Play again? (y/n): ");
        scanf(" %c", &play_again);
        if (play_again != 'y' && play_again != 'Y') break;
    }
    return 0;
}