Kółko i krzyżyk

-- Sebastian Pawlak, 1999.

Przedstawiam grę w kółko i krzyżyk zaimplementowaną z użyciem metody mini-max.

Aby wyznaczyć pierwszy ruch dla planszy 3x3, komputer musi wykonać kilkaset tysięcy sprawdzeń (bez obcinania alfa-beta).

Wnioski: najlepszym ruchem otwierającym jest któreś z narożnych pól; najlepszą odpowiedzią na taki ruch otwierający jest obstawienie środkowego pola.

Fragment drzewa gry

Kod źródłowy pliku "tictac.c":

/* MINI-MAXowe kolko i krzyzyk
 * autor: Sebastian Pawlak
 *
 * Brak interfejsu. Zmiany na planszy nalezy wykonywac w kodzie programu
 * zmienajac odpowiednio tablice Plansza (na samym koncu programu).
 */
#include <stdio.h>

#define Nic 0
#define Gracz_X 1
#define Gracz_O 2
#define SZEROKOSC 3
#define WYSOKOSC 3
#define ROZMIAR (SZEROKOSC*WYSOKOSC)

short najlepsze_pole=-1;
long licznik;

typedef struct ListaWolnychPol
{
    short WolnePola [ROZMIAR];
    short DlugoscListy;
} WolnePola;


void PokazPlansze(const char Plansza[])
{
    int i, j;

    for (i = 0; i < WYSOKOSC; i++) {
        for (j = 0; j < SZEROKOSC; j++) {
            switch (Plansza[i * SZEROKOSC + j]) {
                case Nic: printf("."); break;
                case Gracz_X: printf("x"); break;
                case Gracz_O: printf("o"); break;
            }
        }
        printf("\n");
    }
}


char Wygrana(const char Plansza[], const char gracz)
{
    short i, j, k;

    // pionowa
    for (i = 0; i < 3; i++) {
        k = 0;
        for (j = 0; j < 3; j++)
            if (Plansza[j * 3 + i] == gracz)
                k++;

      	if (k == 3)
            return 1;
    }
    
    // pozioma
    for (i = 0; i < 3; i++) {
        k = 0;
        for (j = 0; j < 3; j++)
            if (Plansza[j + i * 3] == gracz)
                k++;

	if (k == 3)
	    return 1;
     }

    // ukosna
    k = 0;
    for (i = 0; i < 3; i++)
        if (Plansza[i + i * 3] == gracz)
            k++;
    
    if (k == 3)
        return 1;

    k = 0;
    for (i = 0; i < 3; i++)
        if (Plansza[2 - i + i * 3] == gracz)
            k++;
    
    if (k == 3)
        return 1;

    return 0;
}


WolnePola GenerujListeWolnychPol(const char Plansza[])
{
    WolnePola WP;
    short i;

    WP.DlugoscListy = -1;
    
    for (i = 0; i < ROZMIAR; i++)
        if (Plansza[i] == Nic)
	    WP.WolnePola[++WP.DlugoscListy] = i;

    return WP;
}


short MiniMax(const char Plansza[], const short glebokosc, const char gracz)
{
    WolnePola WolneRuchy;
    short Najlepszy, tmp;
    short i, k;
    char Plansza_tmp[ROZMIAR];
    char gracz_nastepny;

    if (gracz == Gracz_X)
        gracz_nastepny = Gracz_O;
    else gracz_nastepny = Gracz_X;

    if (glebokosc % 2 != 0) {
        if (Wygrana(Plansza, gracz) == 1)  // Wygralismy
            return 1;
    } else if (Wygrana(Plansza, gracz_nastepny) == 1)  // Przegralismy
        return -1;

    WolneRuchy = GenerujListeWolnychPol(Plansza);

    if (WolneRuchy.DlugoscListy == -1)  // Remis
        return 0;

    if (glebokosc % 2 == 0)
        Najlepszy = -100;
    else Najlepszy = 100;

    for (k = 0; k <= WolneRuchy.DlugoscListy; k++) {
        for (i = 0; i < ROZMIAR; i++)
            Plansza_tmp[i] = Plansza[i];

        if (glebokosc % 2 == 0)
            Plansza_tmp[WolneRuchy.WolnePola [k]]=gracz;
        else Plansza_tmp[WolneRuchy.WolnePola [k]] = gracz_nastepny;

        tmp = MiniMax(Plansza_tmp, glebokosc + 1, gracz);
	licznik++;

        if (glebokosc % 2 == 0) {
            if (tmp > Najlepszy) {
                Najlepszy = tmp;
                if (glebokosc == 0)
                    najlepsze_pole = WolneRuchy.WolnePola[k];
            }
        } else {
            if (tmp < Najlepszy)
                Najlepszy = tmp;
        }
    }

    return Najlepszy;
}


int main ()
{
/* char Plansza[ROZMIAR]= {Gracz_O,     Nic,     Nic,
                         Gracz_X, Gracz_X, Gracz_O,
                         Gracz_O, Gracz_X,     Nic};*/

    char Plansza[ROZMIAR]= {     Nic,     Nic,     Nic,
                                 Nic,     Nic,     Nic,
                                 Nic,     Nic,     Nic };

    short i;

    printf("wartosc koncowa: %d\n", MiniMax(Plansza, 0, Gracz_O));
    printf("wykonano %d sprawdzen\n", licznik);
    Plansza[najlepsze_pole] = Gracz_O;
    PokazPlansze(Plansza);

    return 0;
}