Panel użytkownika
Nazwa użytkownika:
Hasło:
Nie masz jeszcze konta?

Kółko i krzyżyk Minimax Alfa Beta

Ostatnio zmodyfikowano 2021-06-16 06:46
Autor Wiadomość
Maren
Temat założony przez niniejszego użytkownika
Kółko i krzyżyk Minimax Alfa Beta
» 2021-06-16 00:08:18
Witam,
mam problem z moim programem, a dokładniej z algorytmem minimax. Algorytm wybiera dziwne ruchy, nie prowadzące do wygranej. Nie robi też ruchów po kolei, ruchy wydają się jakby losowe. Proszę o jakieś sugestie.
C/C++
#include <iostream>

using namespace std;

void plansza( char p[ ] )
{
   
for( int i = 1; i <= 9; i++ )
   
{
       
cout << " " << p[ i ] << " ";
       
if( i % 3 )
           
 cout << "|";
       
else if( i == 3 || i == 6 )
           
 cout << "\n---+---+---\n";
       
else
           
 cout << endl;
       
   
}
}

// Funkcja zwraca true, jeśli ktoś wygrał
bool wygrana( char t[ ], char g, bool cisza )
{
   
bool test;
   
int i;
   
   
test = false;
   
   
//wiersze
   
   
for( i = 1; i <= 7; i += 3 ) test |=(( t[ i ] == g ) &&( t[ i + 1 ] == g ) &&( t[ i + 2 ] == g ) );
   
   
//kolumny  
   
   
for( i = 1; i <= 3; i++ ) test |=(( t[ i ] == g ) &&( t[ i + 3 ] == g ) &&( t[ i + 6 ] == g ) );
   
   
//przekątną 1-5-9
   
   
test |=(( t[ 1 ] == g ) &&( t[ 5 ] == g ) &&( t[ 9 ] == g ) );
   
   
//przekątną 3-5-7
   
   
test |=(( t[ 3 ] == g ) &&( t[ 5 ] == g ) &&( t[ 7 ] == g ) );
   
   
if( test )
   
{
       
if( !cisza )
       
{
           
plansza( t );
           
cout << "\nGRACZ " << g << " WYGRYWA!!!\n\n";
       
}
       
return true;
   
}
   
return false;
}

bool remis( char t[ ], bool cisza )
{
   
   
for( int i = 1; i <= 9; i++ ) if( t[ i ] == ' ' ) return false;
   
   
if( !cisza )
   
{
       
plansza( t ); cout << "\nREMIS !!!\n\n";
   
}
   
return true;
}


int minimax( char t[ ], int glebokosc, char gracz, int alfa, int beta )
{
   
int eval, mineval, maxeval;
   
   
   
if( wygrana( t, gracz, true ) )
   
{
       
if( gracz == 'X' )
           
 return 1;
       
else
           
 return - 1;
       
   
}
   
   
   
if( remis( t, true ) )
       
 return 0;
   
   
if( gracz == 'O' )
   
{
       
maxeval = - 999;
       
for( int i = 1; i <= 9; i++ )
       
{
           
if( t[ i ] == ' ' )
           
{
               
t[ i ] = gracz;
               
eval = minimax( t, glebokosc + 1, gracz, alfa, beta );
               
t[ i ] = ' ';
               
maxeval = max( maxeval, eval );
               
alfa = max( alfa, maxeval );
               
if( beta <= alfa )
                   
 break;
               
           
}
        }
       
return maxeval;
   
}
   
if( gracz == 'X' )
   
{
       
mineval = 999;
       
for( int i = 1; i <= 9; i++ )
       
{
           
if( t[ i ] == ' ' )
           
{
               
t[ i ] = gracz;
               
eval = minimax( t, glebokosc + 1, gracz, alfa, beta );
               
t[ i ] = ' ';
               
mineval = min( mineval, eval );
               
beta = min( beta, mineval );
               
if( beta <= alfa )
                   
 break;
               
           
}
        }
       
return mineval;
   
}
}

int komputer( char t[ ], int glebokosc, int alfa, int beta )
{
   
int ruch = - 1, i, m, mmx;
   
   
mmx = - 999;
   
for( i = 1; i <= 9; i++ )
   
{
       
if( t[ i ] == ' ' )
       
{
           
t[ i ] = 'X';
           
m = minimax( t, glebokosc + 1, 'X', alfa, beta );
           
t[ i ] = ' ';
           
alfa = max( alfa, mmx );
           
if( beta <= alfa )
           
{
               
break;
           
}
           
if( m > mmx )
           
{
               
mmx = m;
               
ruch = i;
           
}
        }
    }
   
return ruch;
}

void ruch( char t[ ], char & gracz )
{
   
int r;
   
   
plansza( t );
   
if( gracz == 'O' )
   
{
       
cout << "\nWybier wolne pole : ";
       
cin >> r;
   
}
   
else
   
{
       
r = komputer( t, 0, - 999, 999 );
       
cout << "\nKOMPUTER : wybiera ruch : " << r << endl;
   
}
   
   
cout << "---------------------------\n\n";
   
if(( r >= 1 ) &&( r <= 9 ) &&( t[ r ] == ' ' ) )
   
{
       
t[ r ] = gracz;
       
gracz =( gracz == 'O' ) ? 'X'
           
: 'O'; //zmiana zawodnika
   
}
   
else
   
{
       
cout << "To nie jest wolne pole!" << endl;
   
}
   
   
}

main()
{
   
char t[ 10 ], gracz, wybor, wybor2;
   
   
do
   
{
       
cout << "Gra w Kolko i Krzyzyk dla gracza i komputera\n"
        "============================================\n\n"
        "Kto zaczyna?\n"
        "g-gracz\n"
        "k-komputer\n\n"
;
       
       
cin >> wybor2;
       
       
if( wybor2 == 'g' )
       
{
           
for( int i = 1; i <= 9; i++ ) t[ i ] = ' ';
           
           
gracz = 'O';
       
}
       
else if( wybor2 == 'k' )
       
{
           
for( int i = 1; i <= 9; i++ ) t[ i ] = ' ';
           
           
gracz = 'X';
       
}
       
       
       
       
while( !wygrana( t, 'X', false ) && !wygrana( t, 'O', false ) && !remis( t, false ) ) ruch( t, gracz );
       
       
       
   
} while(( wybor == 'T' ) ||( wybor == 't' ) );
   
}
P-178782
pekfos
» 2021-06-16 06:46:33
Wywołanie rekurencyjne minimax() powinno mieć ustawione przeciwnego gracza od aktualnie rozważanego.
C/C++
eval = minimax( t, glebokosc + 1, 'X', alfa, beta ); // X, bo całość jest w if( gracz == 'O' ), analogicznie dla drugiego przypadku
Upewnij się jeszcze że testujesz wygraną dla właściwego gracza, bo sama ta zmiana nie zadziała z tym, gdzie masz testowanie wygranej.
P-178783
« 1 »
  Strona 1 z 1