FORZA 4 IN C

24/08/2005

Forza4, il mitico gioco a turno dove occorre allineare 4 o più pedine in una scacchiera 6x7.

In questo articolo mostro come realizzare un IA abbastamza intelligente da poter giocare decentemente contro un avversario umano.

La grafica è completamente realizzata in ASCII, quindi niente di incredibile; quello che interessa è l'algorimo dell'IA e come esso è stato implementato: il minmax.

Minmax è una funzione di valutazione in grado di minimizzare (min) la massima perdita possibile e contemporaneamente massimizzare (max) il minimo guadagno. L'algorimo è applicabile a tutti i giochi a informazione completa come forza4, scacchi, dama, tris e in generale i giochi a turno.

L'algoritmo trova la mossa migliore esplorando tutto l'albero delle possibilità da quel punto del gioco in poi; in sostanza effettua una enorme quantità di simulazioni di gioco, provando tutte le prossime possibili mosse dell'avversario, tutte le possibili contromosse successive, tutte le possibili mosse successive dell'avversario e cosi' via fino alla fine di ogni partita "simulata". Ovviamente il numero dei possibili sviluppi di gioco aumenta esponenzialmente al numero delle mosse provate e quindi non è possibile esplorare completamente l'albero: occorre fermarsi prima.

Una realizzazione concreta proverà solo un ristretto numero di mosse in avanti terminate le quali verrà valutato in una scala opportuna il vantaggio del giocatore a quel preciso stato di gioco.

Codice sorgente: forza4

/* FORZA 4 - algoritmo DFS minimax */

#define SKILL 10
#define ROW 6
#define COLUMN 7


int board[ROW*COLUMN];
long int depth,skill;
unsigned long int nodes;

void display_board(void)
{
    long int i,j;
    printf("\n");
    for(j=0;j<ROW;j++)
    {
        for(i=0;i<COLUMN;i++)
        {
            if(board[i+j*COLUMN]==1) printf("X ");
            if(board[i+j*COLUMN]==-1) printf("O ");
            if(board[i+j*COLUMN]==0) printf(". ");
        }
        printf("\n");
    }
    for(i=0;i<(COLUMN*2)-1;i++) printf("-");
    printf("\n");
    for(i=0;i<COLUMN;i++) printf("%d ",i+1);
    printf("\n");
}


int checkwin(int player,int column,int lenght)
{
    long int j,r,l,i,height;
    lenght--;
    i = column;
    j = ROW-1;
    while(board[i+j*COLUMN]!=0) j--;
    j++;
    height = j;

    r = 0;
    l = 0;
    while(((++i)<COLUMN)&&(board[i+j*COLUMN]==player)) r++;
    i = column;
    while(((--i)>=0)&&(board[i+j*COLUMN]==player)) l++;
    if ((r+l)>=lenght) return 1;
    i = column;

    r = 0;
    while(((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
    if (r>=lenght) return 1;
    j = height;

    r = 0;
    l = 0;
    while(((++i)<COLUMN)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) r++;
    i = column;
    j = height;
    while(((--i)>=0)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) l++;
    if ((r+l)>=lenght) return 1;
    i = column;
    j = height;

    r = 0;
    l = 0;
    while(((++i)<COLUMN)&&((--j)>=0)&&(board[i+j*COLUMN]==player)) r++;
    i = column;
    j = height;
    while(((--i)>=0)&&((++j)<ROW)&&(board[i+j*COLUMN]==player)) l++;
    if ((r+l)>=lenght) return 1;

    return 0;
}

int extimated_value(int player)
{
    long int i,j,value,l;

    value = 0;
    for(l=2;l<4;l++)
    {
        for(i=0;i<COLUMN;i++)
        {
            if(checkwin(player,i,l)) value = value + l;
        }
    }

    return value;
}

int goodness(int player,int depth,int column,int trigger)
{
    long int max,i,value,j;
    max = -200;
    if (checkwin(-player,column,4)) return -128;
    if (depth==0) return 0;
    for(i=0;i<COLUMN;i++)
    {
        if(board[i]==0)
        {
            j = ROW-1;
            while(board[i+j*COLUMN]!=0) j--;
            board[i+j*COLUMN] = player;
            nodes++;
            value = -goodness(-player,depth-1,i,-max)/2;
            board[i+j*COLUMN] = 0;
            if (value>max) max = value;
            if (value>trigger) return max;
        }
    }
    return max;
}

int best_move(int player)
{
    long int i,j,max,value,best,same,trigger,old,att;
    long int res[COLUMN];
    max = -100;
    best = -1;
    for(i=0;i<COLUMN;i++)
    {
        if(board[i]==0)
        {
            nodes = 0;
            j = ROW-1;
            while((board[i+j*COLUMN]!=0)&&(j>=0)) j--;
            board[i+j*COLUMN] = player;
            value = -goodness(-player,skill,i,200);
            printf("\nmove %d goodness: %d   tree size for this move: %d nodes",i+1,value,nodes);
            res[i] = value;
            board[i+j*COLUMN] = 0;
            if (value>max)
            {
                max = value;
                best = i;
            }
        }
    }
    if(best==-1)
    {
        for(i=0;i<COLUMN;i++) if(board[i]==0) return i;
    }

    return best;
}




int main(void)
{
    int move,j,i,coins;
    coins = ROW*COLUMN;
    skill = SKILL-3;

    for(i=0;i<(ROW*COLUMN);i++) board[i] = 0;
    display_board();

    while(coins!=0)
    {
        if (coins==40) skill=SKILL-2; /* quick start */
        if (coins==36) skill=SKILL-1; /* improve skill level... */
        if (coins==34) skill=SKILL;   /* ...to maximum */
        do
        {
            printf("\nchoose column [1-%d]...",COLUMN);
            scanf("%d",&move);
            if(board[move-1]!=0) printf("\ncolumn is full");
        }
        while(board[move-1]!=0);
        move--;
        j = ROW-1;
        while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
        board[move+j*COLUMN] = 1;
        coins--;
        display_board();
        if(checkwin(1,move,4))
        {
            printf("\nYou win\n");
            return 1;
        }
        move = best_move(-1);

        j = ROW-1;
        while((board[move+j*COLUMN]!=0)&&(j>=0)) j--;
        board[move+j*COLUMN] = -1;
        display_board();
        printf("\nCPU move in %d",move+1);
        coins--;
        if(checkwin(-1,move,4))
        {
            display_board();
            printf("\nCPU wins\n");
            return 1;
        }
        printf("\n");


    }
    printf("\n");
    return 1;
}

Ecco l'output del programma durante una partita:

Torna alla home

FORZA 4 IN C

24/08/2005

Commenti