Witam, napisałem grę Connect4 w C++ dla dwóch graczy, tutaj info gdyby ktoś nie znał:
To jest zwykle kolko-krzyzyk z tym, ze wrzucamy zetony od gory.
Chciałbym jednak grać przeciwko boot'owi, czyli potrzebuję jakąś sztuczną inteligencję do tej gry. Nie wiem jak się do tego zabrać, czy ktoś mógłby coś podpowiedzieć, lub też podsunąć częsciowe rozwiązanie przynajmniej ?
algorytm min-max?
Zależy na ile dobrze chcesz, żeby bot grał. Najszybciej i najprościej faktycznie minimax z jakąś nieskomplikowaną heurystyką. Gra jest generalnie rozwiązana - rozpoczynający gracz zawsze wygrywa; w necie są źródła bota Velena, który gra doskonale (zawsze wygrywa jeśli zaczyna).
Zajechałem się, wstawiam fragment kodu, gdy jest ruch komputera, wywoływana jest funkcja komputer(plansza), ktora ma mi zwrocic, ktora kolumne on wybiera.
Program jednak 'muli' , a gdy do kodu wrzuciłem przykładowe cout'y w roznych miejscach by sprawdzic co jest to w nieskonczonosc wypisuje mi "koncze minimax" ( koniec funkcji minimax), napis 'zrobilem minimax', nie wysiwetla sie ani razu... . Nie wiem co tutaj nie gra, wzorowałem się na grze kolkokrzyzyk, bo znalazlem gotowiec, wszystko sprawdzilem 2 razy powinno byc ok, a jednak nie :(
PRogram wchodzi do funkcji minimax, wywolanej wew funkcji komputer(), i tam zostaje juz do konca nie mogac jej zakonczyc, nie wiem dlaczego
bool wygrana(char plansza[10][20], char g, bool cisza){
bool test;
int i;
test = false; // Zmienna przyjmuje true, jeśli zawodnik ma 5 figur
// w wierszu, kolumnie lub na przekątnych
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j]==g){
test=Sprawdz(i,j,plansza);
}
}
if(test)
{
if(!cisza)
{
Wyswietl_Plansze(plansza);
cout << "\nGRACZ " << g << " WYGRYWA!!!\n\n";
}
return true;
}
return false;
}
bool remis(char plansza[10][20], bool cisza)
{
// Jeśli napotkamy spację, to plansza posiada wolne pola - zwracamy false
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j]==' '){
return false;
}
}
// Jeśli pętla for zakończyła się normalnie, to na żadnym polu planszy nie było
// spacji. Mamy do czynienia z remisem - zwracamy true
if(!cisza)
{
Wyswietl_Plansze(plansza); cout << "\nREMIS !!!\n\n";
}
return true;
}
//////////////////////// MINIMAX //////////
int minimax(char plansza[10][20], char gracz){
int m, mmx;
//cout<<" ROBIE MINIMAX"<<endl;
// Najpierw sprawdzamy, czy bieżący gracz wygrywa na planszy. Jeśli tak, to
// zwracamy jego maksymalny wynik
if(wygrana(plansza,gracz,true)) return (gracz == 'x') ? 1 : -1;
// Następnie sprawdzamy, czy nie ma remisu. Jeśli jest, zwracamy wynik 0
if(remis(plansza,true)) return 0;
// Będziemy analizować możliwe posunięcia przeciwnika. Zmieniamy zatem
// bieżącego gracza na jego przeciwnika
gracz = (gracz == 'x') ? 'o' : 'x';
// Algorytm MINIMAX w kolejnych wywołaniach rekurencyjnych naprzemiennie analizuje
// grę gracza oraz jego przeciwnika. Dla gracza oblicza maksimum wyniku gry, a dla
// przeciwnika oblicza minimum. Wartość mmx ustawiamy w zależności od tego, czyje
// ruchy analizujemy:
// X - liczymy max, zatem mmx <- -10
// O - liczymy min, zatem mmx <- 10
mmx = (gracz == 'o') ? 10 : -10;
// Przeglądamy planszę szukając wolnych pół na ruch gracza. Na wolnym polu ustawiamy
// literkę gracza i wyznaczamy wartość tego ruchu rekurencyjnym wywołaniem
// algorytmu MINIMAX. Planszę przywracamy i w zależności kto gra:
// X - wyznaczamy maximum
// O - wyznaczamy minimum
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++)
if(plansza[i][j] == ' ')
{
plansza[i][j] = gracz;
m = minimax(plansza,gracz);
plansza[i][j] = ' ';
if(((gracz == 'o') && (m < mmx)) || ((gracz == 'x') && (m > mmx))) mmx = m;
}
cout<<"koncze minimax"<<endl;
return mmx;
}
/////////kopiuje
int komputer(char plansza[10][20]){
int ruch, i,j, m, mmx;
mmx = -10;
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j] == ' '){ // szuka pustych miejsc
plansza[i][j] = 'x';
m = minimax(plansza,'x');
cout<<"zrobilem minimax"<<endl;
plansza[i][j] = ' ';
if(m > mmx) // szuka maksimum
{
mmx = m; ruch = j;
}
}
}
cout<<"finito"<<endl;
return (ruch+1);
}
Wklejam kod całego programu, proszę o ew. pomoc, edycje bo ja tutaj narpawde nie wiem co jest nie tak :(
#include <iostream>
#include <string>
#include <ctime>
#include <cstdlib>
#include <Windows.h>
using namespace std;
void Zeruj_Plansze(char plansza[10][20]){
for(int x=0;x <= 9; x++)
for(int y=0; y <= 19; y++)
plansza[x][y] = ' ';
}
void Wyswietl_Plansze(char plansza[10][20]){
cout<<" 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20\n";
for(int a = 0; a<= 9; a++)
{
for(int b =0; b <= 19; b++) cout<<char(218)<<char(196)<<char(191)<<" ";
cout<<'\n';
for(int b =0; b <= 19; b++) cout<<char(179)<<plansza[a][b]<<char(179)<<" ";
cout<<'\n';
for(int b =0; b <= 19; b++) cout<<char(192)<<char(196)<<char(217)<<" ";
cout<<'\n';
}
}
int Wrzuc(int kol, char gracz,char plansza[10][20]){
if(kol >=0 && kol<= 19){
if(plansza[0][kol] == ' '){
int i;
for(i = 0; plansza[i][kol] == ' ';i++)
if(i == 9)
{ plansza[i][kol] = gracz;
return i;}
i--;
plansza[i][kol] =gracz;
return i;
}
else{
return -1;
}
}
else{
return -1;
}
}
bool Sprawdz (int x, int y, char plansza[10][20]){
int pionowo = 1; //(|)
int poziomo = 1; //(-)
int skos1 = 1; //(\)
int skos2 = 1; //(/)
char znak = plansza[x][y]; // poszukiwany znak
int licz1; // licznik pionowy indeksow
int licz2; // licznik poziomy indeksow
//sprawdzanie PIONOWE
for(licz1 = (x +1); plansza[licz1][y] ==znak && licz1 <= 9; licz1++,pionowo++); // w góre
for(licz1 = (x -1); plansza[licz1][y] ==znak && licz1 >= 0; licz1--,pionowo++); // w dół
if(pionowo >= 5) return true;
//sprawdzanie POZIOME
for(licz2 = (y -1); plansza[x][licz2] == znak && licz2 >= 0; licz2--,poziomo++); //w lewo
for(licz2 = (y +1); plansza[x][licz2] == znak && licz2 <= 19; licz2++,poziomo++); //w prawo
if(poziomo >= 5) return true;
//sprawdzanie skos1 (\)
for(licz1 = (x -1), licz2= (y -1); plansza[licz1][licz2] == znak && licz1>=0 && licz2 >=0; skos1++, licz1--, licz2--);// w gore i w lewo
for(licz1 = (x +1) , licz2 = (y+1); plansza[licz1][licz2] == znak && licz1<=9 && licz2 <=19; skos1++, licz1++, licz2++);// w dol i w prawo
if(skos1 >= 5) return true;
//sprawdzanie skos2 (/)
for(licz1 = (x-1), licz2=(y+1); plansza[licz1][licz2] == znak && licz1>=0 && licz2 <= 19; skos2++, licz1--, licz2++);// gora i w prawo
for(licz1 = (x +1), licz2=(y-1); plansza[licz1][licz2] == znak && licz1<=9 && licz2 >=0; skos2++, licz1++, licz2--);// gora i w lewo
if(skos2 >= 5) return true;
return false;
}
bool wygrana(char plansza[10][20], char g, bool cisza){
bool test;
int i;
int flaga=0;
test = false; // Zmienna przyjmuje true, jeśli zawodnik ma 5 figur
// w wierszu, kolumnie lub na przekątnych
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j]==g){
test=Sprawdz(i,j,plansza);
if(test==true){
flaga=1;
return true;
}
}
}
if(flaga)
{
if(!cisza)
{
Wyswietl_Plansze(plansza);
cout << "\nGRACZ " << g << " WYGRYWA!!!\n\n";
}
return true;
}
return false;
}
bool remis(char plansza[10][20], bool cisza)
{
// Jeśli napotkamy spację, to plansza posiada wolne pola - zwracamy false
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j]==' '){
return false;
}
}
// Jeśli pętla for zakończyła się normalnie, to na żadnym polu planszy nie było
// spacji. Mamy do czynienia z remisem - zwracamy true
if(!cisza)
{
Wyswietl_Plansze(plansza); cout << "\nREMIS !!!\n\n";
}
return true;
}
int licznik=0;
//////////////////////// MINIMAX //////////
int minimax(char plansza[10][20], char gracz){
int m, mmx;
// cout<<" ROBIE MINIMAX"<< ++licznik <<endl;
// Najpierw sprawdzamy, czy bieżący gracz wygrywa na planszy. Jeśli tak, to
// zwracamy jego maksymalny wynik
if(wygrana(plansza,gracz,true)) return (gracz == 'x') ? 1 : -1;
// Następnie sprawdzamy, czy nie ma remisu. Jeśli jest, zwracamy wynik 0
if(remis(plansza,true)) return 0;
// Będziemy analizować możliwe posunięcia przeciwnika. Zmieniamy zatem
// bieżącego gracza na jego przeciwnika
gracz = (gracz == 'x') ? 'o' : 'x';
// Algorytm MINIMAX w kolejnych wywołaniach rekurencyjnych naprzemiennie analizuje
// grę gracza oraz jego przeciwnika. Dla gracza oblicza maksimum wyniku gry, a dla
// przeciwnika oblicza minimum. Wartość mmx ustawiamy w zależności od tego, czyje
// ruchy analizujemy:
// X - liczymy max, zatem mmx <- -10
// O - liczymy min, zatem mmx <- 10
mmx = (gracz == 'o') ? 10 : -10;
// Przeglądamy planszę szukając wolnych pół na ruch gracza. Na wolnym polu ustawiamy
// literkę gracza i wyznaczamy wartość tego ruchu rekurencyjnym wywołaniem
// algorytmu MINIMAX. Planszę przywracamy i w zależności kto gra:
// X - wyznaczamy maximum
// O - wyznaczamy minimum
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++)
if(plansza[i][j] == ' ')
{
plansza[i][j] = gracz;
m = minimax(plansza,gracz);
plansza[i][j] = ' ';
if(((gracz == 'o') && (m < mmx)) || ((gracz == 'x') && (m > mmx))) mmx = m;
}
// cout<<"koncze minimax"<<endl;
return mmx;
}
/////////kopiuje
int komputer(char plansza[10][20]){
int ruch, i,j, m, mmx;
mmx = -10;
for(int i=0; i <= 9; i++)
for(int j=0; j <= 19; j++){
if(plansza[i][j] == ' '){ // szuka pustych miejsc
plansza[i][j] = 'x';
m = minimax(plansza,'x');
cout<<"zrobilem minimax 99999999999999999999999999999999"<<endl;
Sleep(1000);
plansza[i][j] = ' ';
if(m > mmx) // szuka maksimum
{
mmx = m; ruch = j;
}
}
}
cout<<"finito"<<endl;
return (ruch+1);
}
int main(){
char plansza[10][20]; // plansza do gry
Zeruj_Plansze(plansza);
Wyswietl_Plansze(plansza);
/////////////////////////////////////////
int wybor; // ktora kolumne wybrano
int wiersz_wrzucony = 0; // do ktorego wiersza wrzucono zeton
int wrzucono = 0; // ile zetonow juz wrzucono
bool koniec = false; // czy koniec gry
char gracz = 'x' ; // zaczyna czlowiek , czyli o, a tutaj dalem x
while(!koniec){//will stop when game is won, ! means NOT makes the oppisite be checked
if(wiersz_wrzucony != -1){ // gdy -1 to blednie wrzucono zeton
if(gracz == 'x'){
cout<<"Wybierz kolumne ----- > ";
gracz = 'o'; }//oooooooooooo
else{
cout<<"Teraz boot";
gracz = 'x'; //xxxx
}
}
///////// WCZYTYWANIE WRZUCONEGO ZETONU ////
while(1){
if(wrzucono== 200) break; // remis
if(gracz=='x'){
Sleep(1000);
//wybor=(rand()%20+1);
wybor=komputer(plansza);
cout<<"KOMPUTER WYBRAŁ"<<endl;
Sleep(10000);
}
else{
cin>>wybor; // decyzja uzytkownika
}
--wybor;// do sprawdzenia czy nie przekroczono zakresu planszy
if(wybor <=19 && wybor >= 0) break;
else cout<< "\nProsze wybrac kolumne z zakresu od 1 do 20 :";
if (cin.fail()) // bledny numer kolumny
{
cin.clear();
char c;
cin>>c;
}
}
///////////
if(wrzucono== 200) break; // remis
wiersz_wrzucony = Wrzuc(wybor,gracz,plansza);
if(wiersz_wrzucony == -1) cout<<"Wybrana kolumna jest juz pelna\nProsze wybrac inny numer kolumny z zakresu 1-20:";
else{
koniec= Sprawdz(wiersz_wrzucony,wybor,plansza);
wrzucono++;
system("cls"); // czyszczenie ekranu
Wyswietl_Plansze(plansza); //pokazuje zmieniona plansze
}
}
system("cls");
if(wrzucono == 200){
cout<<" KONIEC GRY -> REMIS \n";
system("pause");
return 0;
}
if(gracz == 'o') // wybral czlowiek
cout<<"WYGRAŁ: komputer \n";
else cout<<"WYGRAŁ : czlowiek\n";
system("pause");
///////////////////////////////////////////////////////////
getchar();
return 0;
}
Nie odpalałem tego, ale sam kod minimaxa wygląda ok. Tyle że Ty próbujesz przeliczyć całe drzewo przeszukiwań, zastanów się, ile tego jest :D Jeśli nie zabraknie czasu, przepełni się stos rekurencyjnym wywoływaniem funkcji minimax. W prawie żadnej grze nie da rady przeszukać całego drzewa, poza trywialnymi przypadkami jak kółko i krzyżyk (tam jest tylko 9 pól). Dlatego stosując minimax musisz zdecydować się na jakąś głębokość rekurencji, zatrzymać się na niej i ocenić, kto ma przewagę - tzw. heurystyka, o której wspomniałem. Napisanie dobrej heurystyki jest zawsze kluczem do ai (komputer może obejrzeć miliony plansz na sekundę, ale to człowiek jest w stanie rzucić okiem na planszę i natychmiast widzieć wszystkie okazje/zagrożenia - zazwyczaj jest to intuicyjne i ciężko opisać to algorytmem).
Oprócz tego minimax możesz trochę ulepszyć - alfa/beta odcięcia, pogłębianie iteracyjne (jeżeli masz określony czas na ruch).
Widzę, że nie robisz już connect4, a gomoku na planszy 10x19. Implementacja rozsądnego AI dla tego drugiego jest znacznie trudniejsza - większa plansza, nieporównywalnie więcej ruchów, żeby zrobić minimax, trzeba rozsądnie wybrać pewien podzbiór potencjalnych ruchów. Możesz poczytać o czymś takim jak threat-space search. Ale radziłbym wrócić do poprzedniej koncepcji i zrobić connect4.
A przede wszystkim, pomijając jakąkolwiek algorytmikę, moim zdaniem powinieneś popracować nad samą jakością kodu.