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;
}
