Zapałki

    -- Sebastian Pawlak, 2001.


Prezentuję tu program, który ilustruje algorytm minimax z obcinaniem alfa-beta na przykładzie pewnej wersji gry w zapałki.

Reguły gry: Jest 1 stos zapałek. Dwaj gracze na zmianę biorą co najwyżej połowę liczby zapałek ze stosu. Wygrywa ten, który weźmie ostatnią zapałkę.




Wersja bez obcinania alfa-beta


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

/* Gra w NIM 1
 * Wersja bez ciec alfa-beta.
 * Sebastian Pawlak
 * 2001
 */
#include <stdio.h>

int najlepiejWziacZapalek = -1;
int cnt = 0; /* liczba wezlow odpalonych w trakcie obliczen */

/* funkcja minimax */
int MiniMax(const int liczbaZapalek, const int glebokosc, const int gracz)
{
    int najlepszy, tmp, k;

    cnt++;

    if (!liczbaZapalek) /* jesli stos zapalek jest pusty */
        return glebokosc % 2 ? 1 : -1; /* 1 : wygrana, -1 : przegrana */

    najlepszy = glebokosc % 2 ? 10 : -10; /* +nieskonczonosc, -nieskoncz. */

    for (k = 1; k <= liczbaZapalek / 2 || k <= 1; k++) {

        /* rekurencyjne wywolanie funkcji minimaxowej */
        tmp = MiniMax(liczbaZapalek - k, glebokosc + 1, gracz);

        if (!(glebokosc % 2)) {
            if (tmp > najlepszy) {
                najlepszy = tmp;
                if (!glebokosc)
                    najlepiejWziacZapalek = k; /* najlepszy ruch */
            }
        } else if (tmp < najlepszy)
            najlepszy = tmp;
    }

    return najlepszy;
}

int main (void)
{
    int liczbaZapalek = 21; /* poczatkowa liczba zapalek na stosie */
    int zebranych = 0; /* liczba zapalek zebranych w trakcie gry */
    int gracz = 0; /* numer gracza, ktory aktualnie wykonuje ruch */

    printf("Wersja bez obcinania alfa-beta.\n");
    printf("Liczba zapalek na stosie: %d\n", liczbaZapalek);

    /* rozgrywamy cala gre - komputer vs komputer */
    while (zebranych < liczbaZapalek) {

        MiniMax(liczbaZapalek - zebranych, 0, gracz);
        printf("gracz %c bierze %d zapalki\n",
               gracz ? 'B' : 'A', najlepiejWziacZapalek);
        zebranych += najlepiejWziacZapalek;
        if (zebranych < liczbaZapalek)
            gracz = gracz ? 0 : 1;
    }

    printf("wygral gracz %c\n", gracz ? 'B' : 'A');
    printf("liczba odpalonych wezlow: %d\n", cnt);

    return 0;
}




Wersja z obcinaniem alfa-beta


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

/* Gra w NIM 1
 * Wersja z obcinaniem alfa-beta.
 * Sebastian Pawlak
 * 2001
 */
#include <stdio.h>

int najlepiejWziacZapalek = -1;
int cnt = 0; /* liczba wezlow odpalonych w trakcie obliczen */

/* funkcja minimax */
int MiniMax(const int liczbaZapalek, const int glebokosc, const int gracz)
{
    int najlepszy, tmp, k;

    cnt++;

    if (!liczbaZapalek) /* jesli stos zapalek jest pusty */
        return glebokosc % 2 ? 1 : -1; /* 1 : wygrana, -1 : przegrana */

    najlepszy = glebokosc % 2 ? 10 : -10; /* +nieskonczonosc, -nieskoncz. */

    for (k = 1; k <= liczbaZapalek / 2 || k <= 1; k++) {

        /* rekurencyjne wywolanie funkcji minimaxowej */
        tmp = MiniMax(liczbaZapalek - k, glebokosc + 1, gracz);

        if (!(glebokosc % 2)) {
            if (tmp > najlepszy) {
                najlepszy = tmp;
                if (!glebokosc)
                    najlepiejWziacZapalek = k; /* najlepszy ruch */
                if (tmp == 1)
                    break; /* wychodzimy z petli */
            }
        } else if (tmp < najlepszy) {
            najlepszy = tmp;
            if (tmp == -1)
                break; /* wychodzimy z petli */
        }
    }

    return najlepszy;
}

int main (void)
{
    int liczbaZapalek = 21; /* poczatkowa liczba zapalek na stosie */
    int zebranych = 0; /* liczba zapalek zebranych w trakcie gry */
    int gracz = 0; /* numer gracza, ktory aktualnie wykonuje ruch */

    printf("Wersja z obcinaniem alfa-beta.\n");
    printf("Liczba zapalek na stosie: %d\n", liczbaZapalek);

    /* rozgrywamy cala gre - komputer vs komputer */
    while (zebranych < liczbaZapalek) {

        MiniMax(liczbaZapalek - zebranych, 0, gracz);
        printf("gracz %c bierze %d zapalki\n",
               gracz ? 'B' : 'A', najlepiejWziacZapalek);
        zebranych += najlepiejWziacZapalek;
        if (zebranych < liczbaZapalek)
            gracz = gracz ? 0 : 1;
    }

    printf("wygral gracz %c\n", gracz ? 'B' : 'A');
    printf("liczba odpalonych wezlow: %d\n", cnt);

    return 0;
}




Wersja z obcinaniem alfa-beta oraz interakcją z graczem


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

/* Gra w NIM 1
 * Wersja z obcinaniem alfa-beta.
 * Wersja interaktywna.
 * Sebastian Pawlak
 * 2001
 */
#include <stdio.h>

int najlepiejWziacZapalek = -1;

/* funkcja minimax */
int MiniMax(const int liczbaZapalek, const int glebokosc, const int gracz)
{
    int najlepszy, tmp, k;

    if (!liczbaZapalek) /* jesli stos zapalek jest pusty */
        return glebokosc % 2 ? 1 : -1; /* 1 : wygrana, -1 : przegrana */

    najlepszy = glebokosc % 2 ? 10 : -10; /* +nieskonczonosc, -nieskoncz. */

    for (k = 1; k <= liczbaZapalek / 2 || k <= 1; k++) {

        /* rekurencyjne wywolanie funkcji minimaxowej */
        tmp = MiniMax(liczbaZapalek - k, glebokosc + 1, gracz);

        if (!(glebokosc % 2)) {
            if (tmp > najlepszy) {
                najlepszy = tmp;
                if (!glebokosc)
                    najlepiejWziacZapalek = k; /* najlepszy ruch */
                if (tmp == 1)
                    break; /* wychodzimy z petli */
            }
        } else if (tmp < najlepszy) {
            najlepszy = tmp;
            if (tmp == -1)
                break; /* wychodzimy z petli */
        }
    }

    return najlepszy;
}

int main (void)
{
    int liczbaZapalek; /* poczatkowa liczba zapalek na stosie */
    int zebranych = 0; /* liczba zapalek zebranych w trakcie gry */
    int ileZebrac;
    int gracz; /* numer gracza, ktory aktualnie wykonuje ruch */

    printf("Wersja z obcinaniem alfa-beta.\n");

    printf("Kto pierwszy wyciaga zapalki ?\na - komputer, b - gracz\n");
    gracz = 1;
    if (getchar() == 'a')
        gracz = 0;

    do {
        printf("Prosze podac liczbe zapalek na stosie:\n");
        scanf("%d", &liczbaZapalek);
    } while (liczbaZapalek <= 0);


    /* rozgrywamy cala gre - komputer vs komputer */
    while (zebranych < liczbaZapalek) {

        printf("\nLiczba zapalek na stosie: %d\n", liczbaZapalek - zebranych);
        if (gracz == 1) {
            printf("ile zapalek bierzesz:\n");
            do {
                scanf("%d", &ileZebrac);
            } while (ileZebrac <= 0 || (ileZebrac > (liczbaZapalek - zebranych) / 2 &&
                     ileZebrac != 1));
	    najlepiejWziacZapalek = ileZebrac;
        } else
            MiniMax(liczbaZapalek - zebranych, 0, gracz);
        printf("gracz %c bierze %d zapalki\n",
               gracz ? 'B' : 'A', najlepiejWziacZapalek);
        zebranych += najlepiejWziacZapalek;
        if (zebranych < liczbaZapalek)
            gracz = gracz ? 0 : 1;
    }

    printf("wygral gracz %c\n", gracz ? 'B' : 'A');

    return 0;
}
w3cw3c
automatyka przemysłowa