Algorytm alfa-beta :: 4programmers.net

kaminie318

2020-07-16T17:36:16+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 21

0

Hej. Piszę grę w kółko i krzyżyk w c i mam pewien problem mianowicie chodzi o symulowanie ruchu komputera.Znalazłem coś na internecie. Czy jest ktoś w stanie pomóc mi z przerobieniem tego kawałka kodu na algorytm alfa-beta ? Samą ideę algorytmu rozumiem, jednak dłuższy czas głowię się nad implementacją i nie potrafię sobie z tym poradzić. Pozostała część kodu gry wydaje mi się działająca. Bardzo proszę o pomoc.

Kopiuj

int minimax(int* plansza, int player)
{
    int winner = rezultatGry(plansza);
    if (winner != 0)
    {
        return winner * player;
    }
 
    int move = -1;
    int score = -2;
 
    for (int i = 0; i < 25; ++i)
    {
        if (plansza[i] == 0)
        {
            plansza[i] = player;
            int thisScore = -minimax(plansza, player * -1);
            if (thisScore > score)
            {
                score = thisScore;
                move = i;
            }
            plansza[i] = 0;
        }
    }
    if (move == -1) return 0;
    return score;
}
 
void ruchKomputera(int* plansza)
{
    int ruch;
    int wynik = -2;
    for (int i = 0; i < 25; ++i)
    {
        if (plansza[i] == 0)
        {
            plansza[i] = 1;
            int tempScore = -minimax(plansza, -1);
            plansza[i] = 0;
            if (tempScore > wynik)
            {
                wynik = tempScore;
                ruch = i;
            }
        }
    }
    plansza[ruch] = 1;
}

AnyKtokolwiek

2020-07-16T17:56:01+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 3561

1

Czyli znalazłeś jabłka, mamy CI przerobić na brzoskwinie?

kaminie318

2020-07-16T18:10:15+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 21

0

Wydaje mi się że bardziej przerobić jabłko na sok jabłkowy bo z tego co wyczytałem należy jedynie dodać odcięcia alfa-beta i nie potrafię się z tym uporać.

99xmarcin

2020-07-16T18:39:08+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 2420

1

Nie wiem po co taka zmiana? Przy kółko i krzyżyk alfa-beta i mini-max ma tą samą złożoność O(1) :D
Trzeba mocno spier*** żeby było więcej.
Radzę poczytać Ważniak MiniMax i AlfaBeta i przerobić samemu.

kaminie318

2020-07-16T23:29:35+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 21

0

Dokładnie, jest to gra 5x5 więc minmax odpada, czytałem ten wątek z wazniaka, ale nie potrafię przerobić tego pseudokodu. O ile zrozumienie algorytmu w teorii, jak działa jest w miarę jasne, to cały czas gubię się i nie potrafię zrozumieć kodu implementacji alfa-beta jak i minmax.

kaminie318

2020-07-17T23:19:32+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 21

0

Chyba mam "wersje roboczą". Ma to choć trochę sensu? Rozumiem, że -int i +inf to maksymalne i minimalne pole tablicy ?

Kopiuj

int alfaBeta(int*plansza,int gracz,int alfa,int beta,bool maximizingPlayer)
{
   int wygrany = rezultatGry(plansza); //jezeli stan koncowy(1 albo - 1) 
   if (wygrany != 0)
   {
       return wygrany * gracz;
   }

   if (maximizingPlayer == true)
   {
       for (int i = 0; i < 25; i++)
       {
           alfa = max(alfa, alfaBeta(plansza[i], gracz - 1, alfa, beta, false));
           if (alfa >= beta)
           {
               break;  //odciecia
           }
           
           return alfa;
       }
   }
   else if (maximizingPlayer == false)
   {
       for (int i = 0; i < 25; i++)
       {
           beta = min(beta, alfaBeta(plansza[i], gracz - 1, alfa, beta, true));
           if (alfa >= beta)
           {
               break;
           }
       }

       return beta;
   }
}

void ruchKomputera(int* plansza)
{
   int ruch;
   int wynik = -2;
   for (int i = 0; i < 25; ++i)
   {
       if (plansza[i] == 0)
       {
           plansza[i] = 1;
           int tempScore = -alfaBeta(plansza, -1,0,25,true);
           plansza[i] = 0;
           if (tempScore > wynik)
           {
               wynik = tempScore;
               ruch = i;
           }
       }
   }
   plansza[ruch] = 1;
}

kaminie318

2020-07-20T22:51:49+02:00

Rejestracja: dni
Ostatnio: dni
Postów: 21

0

Czy ktoś za pieniądze jest w stanie ogarnąć mi ten ruch komputera? W razie czego proszę o priv.