Algorytm alfa-beta

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.

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

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

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ć.

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.

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.

0

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

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

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1, botów: 0