genetic_learning_algorithm.c

#include "genetic_learning_algorithm.h"
#include <stdio.h>
#include <stdlib.h>
#include <time.h>

// random safeguard value for xorshift32 function.
uint32_t random_state = 123456789;

int main()
{
    // random seed number.
    random_state = (uint32_t)time(NULL);
    Player **gen_zero = NULL;
    int goal[MOVE_SIZE] = {0};
    int gen_num = 0;
    int gen_move_print = 0; // printing the survivability every x gens.
    int convergence_shake;  //

    // prevents 0 as initial seed
    if (random_state == 0)
    {
        random_state = 1;
    }

    gen_zero = init_gen_zero();
    init_random_moves(goal);
    compare_moves_gen_zero(gen_zero, goal);

    printf("After gen zero init.\n");

    qsort(gen_zero, SAMPLE_SIZE, sizeof(Player *), compare);

    while (gen_zero[0]->matches != MOVE_SIZE)
    {

        fill_next_gen(gen_zero, goal);

        qsort(gen_zero, SAMPLE_SIZE, sizeof(Player *), compare);
        gen_num++;
        gen_move_print++;
        convergence_shake = gen_zero[0]->matches;

        if (gen_move_print % 100 == 0)
        {
            printf("move match is: %d", gen_zero[0]->matches);
            fflush(stdout);
        }
    }

    printf("\nit took %d generations to learn moves.\n", gen_num);

    free_gen(gen_zero);

    return 0;
}

int randomize(unsigned int max_num)
{

    return xorshift32() % (max_num + 1);
}

int *make_next_gen(int parent_a[], int parent_b[], int *child)
{
    int random_crossover_point_a = randomize(MOVE_SIZE - 1);
    int random_crossover_point_b = randomize(MOVE_SIZE - 1); // cross-over points (cannot know which will be start and which end to include all possibilities).
    int start;
    int end;
    int i = 0;
    int main_genetics = xorshift32() % 2; // main parent to inherit from, 0 is parent_a 1 is parent_b for simplicity.

    if (random_crossover_point_a > random_crossover_point_b)
    {
        start = random_crossover_point_b;
        end = random_crossover_point_a;
    }
    else
    {
        start = random_crossover_point_a;
        end = random_crossover_point_b;
    }

    if (main_genetics == 0)
    {
        while (i < start)
        {
            child[i] = parent_a[i];
            i++;
        }

        while (i >= start && i <= end)
        {
            child[i] = parent_b[i];
            i++;
        }
        while (i > end && i < MOVE_SIZE)
        {
            child[i] = parent_a[i];
            i++;
        }
    }
    else
    {
        while (i < start)
        {
            child[i] = parent_b[i];
            i++;
        }

        while (i >= start && i <= end)
        {
            child[i] = parent_a[i];
            i++;
        }
        while (i > end && i < MOVE_SIZE)
        {
            child[i] = parent_b[i];
            i++;
        }
    }

    mutation(child);

    return child;
}

int *dynamic_int_arr(int size)
{
    int *arr = calloc(size, sizeof(int));

    return arr;
}

void mutation(int *genetic_arr)
{

    for (int i = 0; i < MOVE_SIZE; i++)
    {

        if (xorshift32() % MOVE_SIZE == 0)
        {
            genetic_arr[i] ^= 1;
        }
    }
}

int compare_arrays(const int *source_arr, const int *goal_arr)
{
    int matches = 0;

    for (int i = 0; i < MOVE_SIZE; i++)
    {
        if (source_arr[i] == goal_arr[i])
        {
            matches++;
        }
    }

    return matches;
}

Player *create_player()
{
    Player *temp = malloc(sizeof(Player));

    if (!temp)
    {
        fprintf(stderr, "Error: could not create player struct.\n");
        return NULL;
    }

    return temp;
}

void print_moves(Player *player)
{

    printf("Player moves are:\t");
    for (int i = 0; i < MOVE_SIZE; i++)
    {
        printf(" %d", (player->moves)[i]);
    }
}

Player **init_gen_zero()
{
    Player **gen_zero = malloc(sizeof(Player *) * SAMPLE_SIZE);
    for (int i = 0; i < SAMPLE_SIZE; i++)
    {
        gen_zero[i] = create_player();
        gen_zero[i]->moves = dynamic_int_arr(MOVE_SIZE);
        init_random_moves((gen_zero[i])->moves);
    }

    return gen_zero;
}

void init_random_moves(int *move_arr)
{

    for (int i = 0; i < MOVE_SIZE; i++)
    {
        move_arr[i] = xorshift32() % 2;
    }
}

void print_player_array(Player **player_array)
{

    for (int i = 0; i < SAMPLE_SIZE; i++)
    {
        printf("Player num %d: ", i);
        print_moves(player_array[i]);
        printf(" matches: %d \n", player_array[i]->matches);
    }
}

void compare_moves_gen_zero(Player **gen_zero, int *goal_array)
{
    int matches = 0;

    for (int i = 0; i < SAMPLE_SIZE; i++)
    {
        matches = compare_arrays(gen_zero[i]->moves, goal_array);
        gen_zero[i]->matches = matches;
    }
}

int compare(const void *a, const void *b)
{
    Player *player_a = *(Player **)a;
    Player *player_b = *(Player **)b;

    return (player_b->matches - player_a->matches);
}

void print_array(int *arr, unsigned int size)
{

    printf("Move array is: ");
    for (int i = 0; i < size; i++)
    {
        printf("%d ", arr[i]);
    }
}

void fill_next_gen(Player **prev_gen, int *goal)
{
    int random_parent_a_index;
    int random_parent_b_index;

    for (int i = SAMPLE_SIZE / 2; i < SAMPLE_SIZE; i++)
    {

        random_parent_a_index = randomize((SAMPLE_SIZE / 2) - 1);
        random_parent_b_index = randomize((SAMPLE_SIZE / 2) - 1);
        prev_gen[i]->moves = make_next_gen(prev_gen[random_parent_a_index]->moves, prev_gen[random_parent_b_index]->moves, prev_gen[i]->moves);
        prev_gen[i]->matches = compare_arrays(prev_gen[i]->moves, goal);
    }
}

void free_gen(Player **gen)
{
    Player *temp;
    for (int i = 0; i < SAMPLE_SIZE; i++)
    {
        temp = gen[i];
        free(temp->moves);
        free(temp);
    }

    free(gen);
}

uint32_t xorshift32()
{
    random_state ^= random_state << 13;
    random_state ^= random_state >> 17;
    random_state ^= random_state << 5;
    return random_state;
}