/*
** Nom: ******
** Prénom: Jérôme
** Groupe: 2103
** Description: Dossier LC10 - Puissance 4 (Joueur contre ordinateur)
** Dernière modification: 04/02/2013
*/

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <time.h>

#define GAME_COLUMNS 7 /* (Max: 9) */
#define GAME_LINES 6 /* (Max: 9) */

typedef enum
{
    /* Les affectations ici ne servent qu'à avoir un code compréhensible (Car l'énumération garanti ces valeurs) */
    CS_Unoccupied      = 0, /* Cellule inocupée */
    CS_OwnedByPlayer   = 1, /* Cellule possédée par le joueur */
    CS_OwnedByComputer = 2  /* Cellule possédée par l'ordinateur */
}
CellState;

typedef struct
{
    CellState cells[GAME_LINES][GAME_COLUMNS];
    unsigned int fullCellCount; /* Pour tester plus facilement le nombre de cellules pleines */
}
Game;

void ClearStdin();
int Game_AI(Game* game);
int Game_Aligned(Game* game, int line, int column, CellState state);
int Game_GetColumnScore(Game* game, int column);
int Game_GetFreeLine(Game* game, int column);
int Game_Play(Game* game, int playerId, int column);
int Game_PlayAI(Game* game, int playerId, int* column);
void Game_Print(Game* game);
void Game_Reset(Game* game);
int ReadNumeral(int* numeral);
int ReadYesNo();

int main()
{
    Game game;
    int choice;
    int newGame;
    int playing;
    int playerId = 0;
    int line;

    printf("Puissance 4 - Version joueur contre ordinateur.\n");

    srand(time(NULL)); /* Un peu d'aléatoire pour diversifier l'IA dans ses choix */

    do
    {
        Game_Reset(&game);
        Game_Print(&game);
        playing = 1;
        newGame = 0;

        do
        {
            if (playerId == 0)
            {
                printf("Au tour du joueur !\n");

                for (;;)
                {
                    printf("Choix de colonne [1,%d] => ", GAME_COLUMNS);

                    if (!ReadNumeral(&choice) || choice < 1 ||choice > GAME_COLUMNS)
                        continue;

                    choice--;

                    line = Game_Play(&game, playerId, choice);
                    if (line == -1)
                    {
                        printf("Cette colonne est pleine !\n");
                        continue;
                    }

                    break;
                }
            }
            else
            {
                printf("Au tour de l'ordinateur !\n");
                choice = Game_AI(&game);
                printf("L'ordinateur choisit la colonne %d\n", choice+1);

                line = Game_Play(&game, playerId, choice);
            }

            Game_Print(&game);

            if (Game_Aligned(&game, line, choice, CS_Unoccupied) >= 4) /* Avons-nous quatre jetons alignés ? */
            {
                playing = 0;
                printf("******** Le joueur %d a gagn%c ! ********\n", playerId+1, 130);
                printf("Voulez-vous rejouer ? (O/N) : ");
                newGame = ReadYesNo();
            }
            else if (game.fullCellCount == GAME_COLUMNS*GAME_LINES) /* Le jeu est-il plein ? */
            {
                playing = 0;
                printf("******** Match nul ! ********\n");
                printf("Voulez-vous rejouer ? (O/N) : ");
                newGame = ReadYesNo();
            }

            /* Exécuté même en cas de victoire, de sorte que le joueur perdant commence si la partie recommence */
            playerId = (playerId+1) % 2;
        }
        while (playing);
    }
    while (newGame);

    return 0;
}

/*
Input: N/A
Output: N/A
Process: Vide le buffer stdin (S'assurer qu'il contienne quelque chose avant)
*/
void ClearStdin()
{
    int c;
    while ((c = getchar()) != '\n' && c != EOF); /* On vide stdin */
}

/*
Input: Pointeur vers structure du jeu
Output: Indice de la colonne choisie par l'IA
Process: Calcule l'indice de la colonne représentant le plus gros avantage
*/
int Game_AI(Game* game)
{
    int highestScore = 0;
    int highestScoreColumn = 0;
    int i = 0;
    int score;

    for (i = 0; i < GAME_COLUMNS; ++i)
    {
        /*
        ** On donne un score à chaque colonne et on choisit celle ayant le plus gros score
        ** Ce score sera de 0 pour les colonnes pleines, il est nécessaire qu'il y ait au moins une colonne pleine lors de l'appel
        */
        score = Game_GetColumnScore(game, i);

        /* Pour que l'IA ne joue pas toujours pareil, si deux colonnes ont le même score, le choix est aléatoire */
        if (score > highestScore || (score == highestScore && rand()%2 == 0))
        {
            highestScore = score;
            highestScoreColumn = i;
        }
    }

    return highestScoreColumn;
}

/*
Input: Pointeur vers structure du jeu, la ligne et la colonne de la case de référence, la référence
(Note: Si la référence vaut CS_Unoccupied, celle de la case de référence est prise)
Output: Le nombre de cases alignées maximum
Process: Calcule combien de cases ayant le même status sont alignées
*/
int Game_Aligned(Game* game, int line, int column, CellState state)
{
    int i, j;
    int current;
    int max = 0;
    CellState* ptr;
    CellState* limit;

    if (state == CS_Unoccupied)
    {
        state = game->cells[line][column];
        if (state == CS_Unoccupied)
            return 0;
    }

    /* Vérification horizontale (-) */
    current = 1;

    /* De gauche à droite */
    limit = &game->cells[line][GAME_COLUMNS-1];
    for (ptr = &game->cells[line][column+1]; ptr <= limit && *ptr == state; ++ptr)
        current++;

    /* De droite à gauche */
    limit = &game->cells[line][0];
    for (ptr = &game->cells[line][column-1]; ptr >= limit && *ptr == state; --ptr)
        current++;

    if (current > max)
        max = current;

    /* Vérification verticale (|) */
    current = 1;

    /* De bas en haut */
    limit = &game->cells[0][column];
    for (ptr = &game->cells[line-1][column]; ptr >= limit && *ptr == state; ptr -= GAME_COLUMNS)
        current++;

    /* De haut en bas */
    limit = &game->cells[GAME_LINES-1][column];
    for (ptr = &game->cells[line+1][column]; ptr <= limit && *ptr == state; ptr += GAME_COLUMNS)
        current++;

    if (current > max)
        max = current;

    /* Vérification première diagonale (\) */
    current = 1;

    /* Montant */

    /* On doit d'abord retrouver la case limite (Celle qui touche les bords */
    i = line;
    j = column;
    while (i > 0 && j > 0)
        i--, j--;

    limit = &game->cells[i][j];

    for (ptr = &game->cells[line-1][column-1]; ptr >= limit && *ptr == state; ptr -= GAME_COLUMNS+1)
        current++;

    /* Descendant */
    i = line;
    j = column;
    while (i < GAME_LINES-1 && j < GAME_COLUMNS-1)
        i++, j++;

    limit = &game->cells[i][j];

    for (ptr = &game->cells[line+1][column+1]; ptr <= limit && *ptr == state; ptr += GAME_COLUMNS+1)
        current++;

    if (current > max)
        max = current;

    /* Vérification seconde diagonale (/) */
    current = 1;

    /* Montant */
    i = line;
    j = column;
    while (i > 0 && j < GAME_COLUMNS-1)
        i--, j++;

    limit = &game->cells[i][j];

    for (ptr = &game->cells[line-1][column+1]; ptr >= limit && *ptr == state; ptr -= GAME_COLUMNS-1)
        current++;

    /* Descendant */
    i = line;
    j = column;
    while (i < GAME_LINES-1 && j > 0)
        i++, j--;

    limit = &game->cells[i][j];

    for (ptr = &game->cells[line+1][column-1]; ptr <= limit && *ptr == state; ptr += GAME_COLUMNS-1)
        current++;

    if (current > max)
        max = current;

    return max;
}

/*
Input: Pointeur vers structure du jeu, la colonne
Output: Le score attribué à cette colonne
Process: Calcule un score pour la colonne selon différents facteurs
*/
int Game_GetColumnScore(Game* game, int column)
{
    /*
    ** Le coeur de l'IA se situe ici
    ** Note: Elle est améliorable; elle essaye de former des suites
    ** sans vérifier qu'elle possède assez de place pour en placer 4
    */
    int line = Game_GetFreeLine(game, column);
    int computerAligned;
    int playerAligned;
    int topComputerAligned;
    int topPlayerAligned;

    if (line == -1)
        return 0; /* Cette colonne ne peut pas être jouée */

    /* Combien de jetons pouvons-nous aligner en jouant ici ? */
    computerAligned = Game_Aligned(game, line, column, CS_OwnedByComputer);

    if (computerAligned >= 4)
        return computerAligned*100; /* On peut gagner en jouant ici */
    else
    {
        /* Combien de jetons le joueur peut-il aligner en jouant ici ? */
        playerAligned = Game_Aligned(game, line, column, CS_OwnedByPlayer);
        if (playerAligned >= 4)
            return playerAligned*50; /* Le joueur peut gagner en jouant ici, bloquons-le */
        else
        {
            if (line > 0)
            {
                /* Le troisième paramètre est la possibilité de jeu du joueur après notre tour */
                topPlayerAligned = Game_Aligned(game, line-1, column, CS_OwnedByPlayer);
                if (topPlayerAligned >= 4)
                    return 1; /* Jouer ici nous ferait perdre le tour d'après (0 est la valeur pour les colonnes impossibles, donc 1) */

                /* Le quatrième paramètre est la possibilité de jeu de l'ordinateur après notre tour */
                topComputerAligned = Game_Aligned(game, line-1, column, CS_OwnedByPlayer);
            }
            else
            {
                topComputerAligned = 0;
                topPlayerAligned = 0;
            }

            /*
            ** On évalue la situation en prenant en compte ces quatre paramètres et en leur donnant un poids dans la décision
            ** Ces valeurs changent totalement la façon de jouer de l'IA, je pense les avoir suffisamment équilibrées pour
            ** que l'IA donne un minimum de challenge
            */

            return computerAligned*14 + playerAligned*17 + topComputerAligned*4 - topPlayerAligned*6;

            /*
            Autre set de valeurs donnant de bons résultats:
            return computerAligned*10 + playerAligned*18 - topComputerAligned*3 - topPlayerAligned*4;
            */
        }
    }
}

/*
Input: Pointeur vers structure du jeu, la ligne, la colonne
Output: Le numéro de la première ligne libre en partant du bas ou -1 si colonne pleine
Process: Parcourt les lignes de la colonne de bas en haut pour retrouver la première libre
*/
int Game_GetFreeLine(Game* game, int column)
{
    int i;

    CellState* ptr = &game->cells[GAME_LINES-1][column]; /* Pour avoir un pointeur */
    for (i = GAME_LINES-1; i >= 0; --i)
    {
        if (*ptr == CS_Unoccupied)
            return i;

        ptr -= GAME_COLUMNS;
    }

    return -1;
}

/*
Input: Pointeur vers structure du jeu, l'identifiant du joueur et la colonne
Output: La ligne où le pion a été placé (-1 si colonne pleine)
Process: Insère un pion appartenant à un certain joueur dans la colonne donnée.
*/
int Game_Play(Game* game, int playerId, int column)
{
    int line = Game_GetFreeLine(game, column);

    if (line != -1)
    {
        game->cells[line][column] = (CS_Unoccupied + playerId + 1);
        game->fullCellCount++;
    }

    return line;
}

/*
Input: Pointeur vers structure du jeu
Output: N/A
Process: Affiche la grille de jeu
*/
void Game_Print(Game* game)
{
    char CellStateToChar[] =
    {
        ' ', /* CS_Unoccupied */
        'X', /* CS_OwnedByPlayer */
        'O'  /* CS_OwnedByComputer */
    };
    int i, j;
    CellState* cell = &game->cells[0][0]; /* Pour utiliser un pointeur */

    putchar('\n');

    for (i = 0; i < GAME_LINES; ++i)
    {
        printf("\t|");
        for (j = 0; j < GAME_COLUMNS; ++j)
            printf(" %c |", CellStateToChar[*cell++]);

        putchar('\n');
    }

    /* Ligne de séparation */
    printf("\t-");
    for (j = 0; j < GAME_COLUMNS; ++j)
        printf("----");

    putchar('\n');

    /* Numéros de colonne */
    printf("\t|");
    for (j = 1; j <= GAME_COLUMNS; ++j)
        printf(" %hd |", j);

    puts("\n\n");
}

/*
Input: Pointeur vers structure du jeu
Output: N/A
Process: Fait repartir le jeu de zéro en vidant la grille
*/
void Game_Reset(Game* game)
{
    memset(game->cells, CS_Unoccupied, GAME_COLUMNS*GAME_LINES*sizeof(CellState));
    game->fullCellCount = 0;
}

/*
Input: Pointeur vers le chiffre
Output: 1 en cas de succès et 0 en cas d'échec
Process: Lit un chiffre seul depuis stdin, tout en prenant soin de vider ce dernier
*/
int ReadNumeral(int* numeral)
{
    int c;

    c = getchar();
    if (c >= '0' && c <= '9') /* Le caractère est-il un chiffre ? */
    {
        *numeral = c - '0'; /* Sortie du chiffre */

        /*
        ** Est-ce que c'était tout ce que contenait stdin ?
        ** Cet appel permet également de vider le buffer
        */
        c = getchar();
        if (c == '\n')
            return 1; /* Oui, l'utilisateur a bien entré un chiffre */
        else /* Non, il reste encore quelque chose dans stdin */
        {
            ClearStdin(); /* On vide stdin */
            return 0; /* Il y avait d'autres caractères, ce n'était pas un simple chiffre */
        }
    }
    else /* Pas un chiffre */
    {
        if (c != '\n') /* L'utilisateur a-t-il entré quelque chose ? */
            ClearStdin(); /* Non, nous vidons stdin */

        return 0; /* Pas un chiffre */
    }
}

/*
Input: N/A
Output: 1 si oui, 0 si non
Process: Lit une confirmation de l'utilisateur (Basée sur la première lettre: O/Y pour oui, autre pour non)
*/
int ReadYesNo()
{
    int c;

    c = getchar();
    if (c == 'O' || c == 'o' || c == 'Y' || c == 'y')
    {
        ClearStdin();
        return 1;
    }
    else if (c != '\n')
        ClearStdin();

    return 0;
}