Witam,
właśnie próbuję zaprogramować grę w kółko i krzyżyk. Mój problem dotyczy zaprogramowania ruchów komputera - postawiłem na algorytm minimax, zaimplementowałem go, jednak program mi się zapętla. Chodzi tutaj o funkcje minimax oraz ruch_przeciwnika, gdzieś w tych funkcjach jest problem, jednak od dłuższego czasu nie mogę dojść co jest nie tak ...
Z góry dziękuję za wszelkie wskazówki.
#include<iostream>
#include <cstdlib>
#include <ctime>
#include<cmath>
#include <conio.h>
#include<limits>
#include<windows.h>
using namespace std;
void reset_stream()
{
cin.clear();
cin.ignore(numeric_limits<streamsize>::max(), '\n');
}
char **alokuj(int rozmiar1, int rozmiar2)
{
char **tablica;
tablica=new char*[rozmiar1];
for(int i=1; i<=rozmiar1; i++) tablica[i]=new char[rozmiar2];
return(tablica);
}
void **dealokuj(char **tab, int rozmiar)
{
for(int i=1; i<=rozmiar; i++){
delete tab[i];
}
delete[] tab;
}
void wypisz(char **tab, int n){
system("cls");
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
cout << tab[i][j] << " ";
}
cout << endl;
cout << endl;
}
}
int sprawdz(char **tab, int n){
unsigned int i, j;
int s=0;
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(tab[i][j]!='_')
s+=1;
}
}
return s;
}
bool czy_wygrana(char **tab, int n, bool cisza){
int t=0,r=0,w=0,p=0;
bool e=false;
for(int i=1; i<=n; i++){
if(tab[i][1]!='_'){
for(int j=1; j<=n-1; j++){
if(tab[i][j]==tab[i][j+1]){
t+=1;
}
}
}
if(tab[1][i]!='_'){
for(int j=1; j<=n-1; j++){
if(tab[j][i]==tab[j+1][i]){
r+=1;
}
}
}
if(t==n-1 || r==n-1){
cout << "wygrana" << endl;
//return 1;
e=true;
}
t=0;
r=0;
}
for(int i=1; i<=n-1; i++){
if(tab[1][1]!='_'){
if(tab[i][i]==tab[i+1][i+1]){
w+=1;
}
}
}
if(w==n-1){
cout << "wygrana" << endl;
//return 1;
e=true;
}
for(int i=1; i<=n-1; i++){
if(tab[1][n]!='_'){
if(tab[i][n-(i-1)]==tab[i+1][n-i]){
p+=1;
}
}
}
if(p==n-1){
cout << "wygrana" << endl;
//return 1;
e=true;
}
if(!cisza)
return 0;
else return e;
}
bool remis(char **tab, int n)
{
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
if(tab[i][j]='_')
return false;
}
}
return true;
}
char wybor_pionka(char **tab, int n){
cout << "Wybierz krzyzyk 'X' badz kolko 'O' ..." << endl;
string znak;
cin >> znak;
while(znak!="X" && znak!="O"){
cout << "Wybrano niewlasciwy symbol, powtorz: \n" << endl;
cin >> znak;
}
return znak[0];
}
int minimax(char **tab, int n, char gracz)
{
int m, mmx;
if(czy_wygrana(tab, n,true)) return (gracz == 'O') ? 1 : -1;
if(remis(tab, n)) return 0;
gracz = (gracz == 'O') ? 'X' : 'O';
mmx = (gracz == 'X') ? n*n+1 : -n*n-1;
for(int i=1; i<=n; i++){
for(int j=1; i<=n; j++){
if(tab[i][j] == '_')
{
tab[i][j] = gracz;
m = minimax(tab, n, gracz);
tab[i][j] = '_';
if(((gracz == 'X') && (m <= mmx)) || ((gracz == 'O') && (m >= mmx))) mmx = m;
}
}
}
return mmx;
}
void ruch_przeciwnika(char **tab, int n)
{
int m, mmx,t,r;
mmx = -n*n-1;
for(int i=1; i <= n; i++){
for(int j=1; j <= n; j++){
if(tab[i][j] == '_')
{
tab[i][j] = 'O';
m = minimax(tab, n, 'O');
tab[i][j] = '_';
if(m > mmx){
mmx = m;
t=i;
r=j;
}
}
}
}
tab[t][r]='O';
}
// int k, l;
// srand(time(NULL));
//
// k=rand()%n;
// l=rand()%n;
//
// if(tablica[k][l]=='_')
// tablica[k][l]='O';
//
//
// Sleep(500); cout<<".";
// Sleep(500); cout<<".";
// Sleep(500); cout<<".";
void k_funkcja(char **tab, int n){
unsigned int i, j;
int s=0;
wypisz(tab,n);
while(s<n*n){
if(s%2==0){
cin >> i >> j;
while(!(cin)){
cout << "Ponado niewlasciwe wspolrzedne!" << endl;
cin.clear();
cin.sync();
cin >> i >> j;
}
while((tab[i][j]!='_') || (i>n) || (j>n)){
cout << "Ponado niewlasciwe wspolrzedne!" << endl;
cin >> i >> j;
// if(!(cin)){
// cin.clear();
// cin.sync();
// }
}
tab[i][j]='X';
}
else
ruch_przeciwnika(tab,n);
s=sprawdz(tab,n);
wypisz(tab,n);
if(czy_wygrana(tab,n,true)==1){
break;
}
else if(s==n*n)
cout << "Remis!\n";
}
}
void u_funkcja(char **tab, int n){
unsigned int i, j;
int s=0;
char znak[2];
znak[0]='O';
znak[1]='O';
znak[0]=wybor_pionka(tab,n);
if(znak[0]=='O')
znak[1]='X';
wypisz(tab,n);
while(s<n*n){
cin >> i >> j;
while(cin.fail()){
reset_stream();
cout << "Ponado niewlasciwe wspolrzedne!" << endl;
//cin.clear();
//cin.sync();
cin >> i >> j;
}
while(tab[i][j]!='_' || i<1 || i>n || j<1 || j>n){
cout << "Ponado niewlasciwe wspolrzedne!" << endl;
cin >> i >> j;
// if(!(cin)){
// cin.clear();
// cin.sync();
// }
}
if(s%2==0)
tab[i][j]=znak[0];
else
tab[i][j]=znak[1];
s=sprawdz(tab,n);
wypisz(tab,n);
if(czy_wygrana(tab,n,true)==1){
break;
}
else if(s==n*n)
cout << "Remis!\n";
}
}
void menu(){
cout << "1 - Graj" << endl;
cout << "2 - Wybierz rodzaj gry (uzytkownik-uzytkownik/uzytkownik-komputer)" << endl;
cout << "3 - Zobacz ranking" << endl;
cout << "4 - Zakoncz gre" << endl;
}
bool rodzaje(int n){
bool rodzaj=true;
cout << "1.Gra typu uzytkownik-uzytkownik (1)" << endl;
cout << "1.Gra typu uzytkownik-komputer (2)" << endl;
cin >> n;
if(n==2)
rodzaj=false;
return rodzaj;
}
int main(){
int i, j, n;
while(true){
menu();
int opcja;
bool rodzaj1;
cin >> opcja;
switch(opcja){
case 1:
{
cout << "Podaj rozmiar planszy: " << endl;
cin >> n;
char **tab=alokuj(n,n);
for(int i=1; i<=n; i++){
for(int j=1; j<=n; j++){
tab[i][j]='_';
}
}
if(rodzaj1==true)
u_funkcja(tab,n);
else
k_funkcja(tab,n);
}
break;
case 2:
{
rodzaj1=rodzaje(n);
}
break;
case 3:
break;
case 4:
{
cout << "Koncze dzialanie programu" << endl;
return 0;
}
default:
break;
}
}
for(; getch() != 27; );
return 0;
}