Znalazłam taki algorytm, czy ktoś umiałby zmienić go na taki, który ma dwuwymiarowe talice dynamiczne a wymiar tablicy zamiast 3 jest równy n i wygrywa się przy usawieniu pięciu kółek lub krzyżyków w jednej linii lub na ukos?
#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;
}