#include <iostream> #include <list> #include <algorithm> using namespace std; const int Taille = 9; const int JoueurGauche = 0; const int JoueurDroit = 1; class Intersection { public: int x, y; bool legale () { return ((x >= 0) && (x < Taille) && (y >= 0) && (y < Taille)); } bool operator == (Intersection & inter) { if ((x != inter.x) || (y != inter.y)) return false; return true; } }; class Coup { public: list<Intersection> l; bool operator == (Coup & coup) { if (l.size () != coup.l.size ()) return false; list<Intersection>::iterator it = l.begin (); list<Intersection>::iterator it1 = coup.l.begin (); while (true) { if ((it->x != it1->x) || (it->y != it1->y)) return false; it++; it1++; if (it == l.end ()) return true; } } friend istream & operator >> (istream & entree, Coup & c); friend ostream & operator << (ostream & sortie, Coup & c); }; istream & operator >> (istream & entree, Coup & c) { Intersection inter; entree >> inter.x >> inter.y; while (true) { c.l.push_back (inter); entree >> inter.x; if (inter.x == -1) break; entree >> inter.y; } return entree; } ostream & operator << (ostream & sortie, Coup & c) { for (list<Intersection>::iterator it = c.l.begin (); it != c.l.end (); ++it) sortie << "(" << it->x << "," << it->y << ")"; return sortie; } class Phutball { public: char damier [Taille] [Taille]; Intersection balle; Phutball () { init (); } void init () { for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) damier [i] [j] = '+'; damier [Taille / 2] [Taille / 2] = '@'; balle.x = Taille / 2; balle.y = Taille / 2; } void joue (Coup & c) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) damier [it->x] [it->y] = 'O'; else { list<Intersection>::iterator precedent; while (true) { precedent = it; it++; if (it == c.l.end ()) break; damier [precedent->x] [precedent->y] = '+'; } if (precedent->legale ()) { damier [precedent->x] [precedent->y] = '@'; balle = *precedent; } } //cerr << *this; } void dejoue (Coup & c) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) damier [it->x] [it->y] = '+'; else { damier [balle.x] [balle.y] = '+'; balle = *it; it++; list<Intersection>::iterator precedent; while (true) { precedent = it; it++; if (it == c.l.end ()) break; damier [precedent->x] [precedent->y] = 'O'; } damier [balle.x] [balle.y] = '@'; } } bool gagne (int joueur, Intersection inter) { if (((joueur == JoueurDroit) && (inter.x < 0)) || ((joueur == JoueurDroit) && inter.legale () && (inter.x == 0)) || ((joueur == JoueurGauche) && (inter.x > Taille - 1)) || ((joueur == JoueurGauche) && inter.legale () && (inter.x == Taille - 1))) return true; return false; } bool coupsLegaux (int joueur, list<Coup> & liste) { liste.clear (); for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) if (damier [i] [j] == '+') { Intersection inter; inter.x = i; inter.y = j; Coup coup; coup.l.push_back (inter); liste.push_back (coup); } Coup coup; coup.l.push_back (balle); damier [balle.x] [balle.y] = '+'; bool gagne = coupsBalle (joueur, coup, liste); damier [balle.x] [balle.y] = '@'; return gagne; } bool coupsLegaux (int ordre, int joueur, list<Coup> & liste) { bool gagne = false; liste.clear (); if (ordre > 0) coupsVoisinsBalle (joueur, liste); if (ordre != 1) { Coup coup; coup.l.push_back (balle); damier [balle.x] [balle.y] = '+'; gagne = coupsBalle (joueur, coup, liste); damier [balle.x] [balle.y] = '@'; } return gagne; } bool elementCoup (Coup & coup, list<Coup> & liste) { for (list<Coup>::iterator it = liste.begin (); it != liste.end (); ++it) if (coup == *it) return true; return false; } bool ajouteCoup (Coup & coup, list<Coup> & liste) { if (!elementCoup (coup, liste)) { liste.push_back (coup); return true; } return false; } bool elementIntersection (Intersection & inter, list<Intersection> & liste) { for (list<Intersection>::iterator it = liste.begin (); it != liste.end (); ++it) if (inter == *it) return true; return false; } bool ajouteIntersection (Intersection & inter, list<Intersection> & liste) { if (!elementIntersection (inter, liste)) { liste.push_back (inter); return true; } return false; } void intersectionsBalle (Intersection interBalle, list<Intersection> & liste) { if (!elementIntersection (interBalle, liste)) { ajouteIntersection (interBalle, liste); for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { Intersection inter = interBalle; inter.x += i; inter.y += j; if (inter.legale ()) { if (damier [inter.x] [inter.y] == 'O') { while (true) { inter.x += i; inter.y += j; if (!inter.legale () || (damier [inter.x] [inter.y] != 'O')) break; } if (inter.legale () && (damier [inter.x] [inter.y] == '+')) intersectionsBalle (inter, liste); } } } } } void coupsVoisinsBalle (int joueur, list<Coup> & listeCoups) { list<Intersection> liste; intersectionsBalle (balle, liste); int meilleur, meilleurBalle; if (joueur == JoueurDroit) { meilleur = Taille; meilleurBalle = Taille; } else { meilleur = -1; meilleurBalle = -1; } for (list<Intersection>::iterator it = liste.begin (); it != liste.end (); ++it) { if (damier [it->x] [it->y] == '+') { if (((joueur == JoueurDroit) && (it->x < meilleurBalle)) || ((joueur == JoueurGauche) && (it->x > meilleurBalle))) meilleurBalle = it->x; } for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { Intersection inter = *it; inter.x += i; inter.y += j; if (inter.legale ()) if (damier [inter.x] [inter.y] == '+') { if (((joueur == JoueurDroit) && (inter.x < meilleur)) || ((joueur == JoueurGauche) && (inter.x > meilleur))) meilleur = inter.x; } } } for (list<Intersection>::iterator it = liste.begin (); it != liste.end (); ++it) { if (damier [it->x] [it->y] == '+') if (it->x == meilleurBalle) { Coup coup; coup.l.push_back (*it); ajouteCoup (coup, listeCoups); } for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { Intersection inter = *it; inter.x += i; inter.y += j; if (inter.legale ()) if (damier [inter.x] [inter.y] == '+') if (inter.x == meilleur) { Coup coup; coup.l.push_back (inter); ajouteCoup (coup, listeCoups); } } } } bool coupsBalle (int joueur, Coup & coup, list<Coup> & liste) { bool coupGagnant = false; for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { Intersection inter = balle; inter.x += i; inter.y += j; if (inter.legale ()) if (damier [inter.x] [inter.y] == 'O') { Coup coup1 = coup; list<Intersection> pierresEnlevees; while (true) { coup1.l.push_back (inter); pierresEnlevees.push_back (inter); inter.x += i; inter.y += j; if (!inter.legale () || (damier [inter.x] [inter.y] != 'O')) break; } if (gagne (joueur, inter)) { coup1.l.push_back (inter); liste.push_back (coup1); coupGagnant = true; } else if (inter.legale ()) { if (damier [inter.x] [inter.y] == '+') { // on memorise la place de la balle Intersection ancienneBalle = balle; // on deplace la balle balle = inter; // on enleve les pierres sautees for (list<Intersection>::iterator it = pierresEnlevees.begin (); it != pierresEnlevees.end (); ++it) damier [it->x] [it->y] = '+'; // on ajoute le nouveau coup Coup coup2 = coup1; coup2.l.push_back (inter); liste.push_back (coup2); // on regarde les coups suivants if (coupsBalle (joueur, coup1, liste)) coupGagnant = true; // on remet les pierres enlevees for (list<Intersection>::iterator it = pierresEnlevees.begin (); it != pierresEnlevees.end (); ++it) damier [it->x] [it->y] = 'O'; // on remet la balle balle = ancienneBalle; } else cerr << "bug coupsBalle \n"; } } } return coupGagnant; } friend ostream & operator << (ostream & sortie, Phutball & v); }; ostream & operator << (ostream & sortie, Phutball & v) { sortie << " "; for (int i = 0; i < Taille; i++) sortie << i << " "; sortie << endl; for (int i = 0; i < Taille; i++) { sortie << i << " "; for (int j = 0; j < Taille; j++) sortie << v.damier [j] [i] << " "; sortie << endl; } return sortie; } Phutball phutball; int adversaire (int joueur) { if (joueur == JoueurGauche) return JoueurDroit; return JoueurGauche; } bool lambda (int joueur, int ordre) { if (phutball.gagne (joueur, phutball.balle)) return true; int autre = adversaire (joueur); if (phutball.gagne (autre, phutball.balle)) return false; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (0, joueur, listeCoups)) return true; if (ordre == 0) return false; phutball.coupsLegaux (ordre, joueur, listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { phutball.joue (*it); bool menaceVerifiee = false; for (int o = 0; (o < ordre) && !menaceVerifiee; o++) if (lambda (joueur, o)) menaceVerifiee = true; bool gagneVerifie = false; if (menaceVerifiee) if (!phutball.coupsLegaux (autre, listeCoupsAdverses)) for (int o = 0; o <= ordre; o++) { gagneVerifie = true; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && gagneVerifie; ++it1) { phutball.joue (*it1); if (!lambda (joueur, o)) gagneVerifie = false; phutball.dejoue (*it1); } if (gagneVerifie) break; } phutball.dejoue (*it); if (gagneVerifie) return true; } return false; } int main () { list<Coup> listeCoups; while (true) { cout << phutball; listeCoups.clear (); if (phutball.coupsLegaux (JoueurGauche, listeCoups)) { cout << "j'ai gagne !" << endl; break; } for (int ordre = 0; ordre < 3; ordre++) cout << "test lambda " << ordre << " = " << lambda (JoueurGauche, ordre) << endl; Coup coupAleatoire; int i = 0, indice = rand () % listeCoups.size (); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { if (i == indice) { coupAleatoire = *it; break; } i++; } cout << "Je joue en " << coupAleatoire << endl; phutball.joue (coupAleatoire); cout << phutball; listeCoups.clear (); if (phutball.coupsLegaux (JoueurDroit, listeCoups)) { cout << "vous avez gagne !" << endl; break; } Coup coup; cin >> coup; phutball.joue (coup); } return 0; }