#include <iostream> #include <list> #include <algorithm> using namespace std; const int Taille = 7; class Coup { public: char couleur; int x, y; }; class Virus { public: char damier [Taille] [Taille]; int nbNoirs, nbBlancs; int nbModifications; int pileModifications [20 * Taille * Taille]; Virus () { init (); } void init () { for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) damier [i] [j] = '+'; damier [0] [0] = '@'; damier [Taille - 1] [Taille - 1] = '@'; damier [Taille - 1] [0] = 'O'; damier [0] [Taille - 1] = 'O'; nbNoirs = 2; nbBlancs = 2; nbModifications = 0; } char adversaire (char couleur) const { if (couleur == 'O') return '@'; return 'O'; } void joue (const Coup & m) { damier [m.x] [m.y] = m.couleur; pileModifications [nbModifications] = m.x; nbModifications++; pileModifications [nbModifications] = m.y; nbModifications++; int nbSwaps = 0; if (m.couleur == '@') nbNoirs++; else nbBlancs++; char autre = adversaire (m.couleur); int debutx = m.x - 1, finx = m.x + 1; int debuty = m.y - 1, finy = m.y + 1; if (debutx < 0) debutx = 0; if (debuty < 0) debuty = 0; if (finx > Taille - 1) finx = Taille - 1; if (finy > Taille - 1) finy = Taille - 1; for (int i = debutx; i <= finx; i++) for (int j = debuty; j <= finy; j++) if (damier [i] [j] == autre) { damier [i] [j] = m.couleur; pileModifications [nbModifications] = i; nbModifications++; pileModifications [nbModifications] = j; nbModifications++; nbSwaps++; if (m.couleur == '@') { nbNoirs++; nbBlancs--; } else { nbNoirs--; nbBlancs++; } } pileModifications [nbModifications] = nbSwaps; nbModifications++; } void dejoue (const Coup & m) { int x, y, nbSwaps; char autre = adversaire (m.couleur); nbModifications--; nbSwaps = pileModifications [nbModifications]; for (int i = 0; i < nbSwaps; i++) { nbModifications--; y = pileModifications [nbModifications]; nbModifications--; x = pileModifications [nbModifications]; damier [x] [y] = autre; if (m.couleur == '@') { nbNoirs--; nbBlancs++; } else { nbNoirs++; nbBlancs--; } } nbModifications--; y = pileModifications [nbModifications]; nbModifications--; x = pileModifications [nbModifications]; damier [x] [y] = '+'; if (m.couleur == '@') nbNoirs--; else nbBlancs--; } int evaluation (char couleur) const { if (couleur == '@') return nbNoirs - nbBlancs; return nbBlancs - nbNoirs; } int evaluationSiPlusDeCoupsPossibles (char couleur) const { if (couleur == '@') return nbNoirs - (Taille * Taille - nbNoirs); else return nbBlancs - (Taille * Taille - nbBlancs); } bool coupLegal (Coup & coup) { if (damier [coup.x] [coup.y] != '+') return false; for (int x = max (coup.x - 1, 0); x <= min (coup.x + 1, Taille - 1); x++) for (int y = max (coup.y - 1, 0); y <= min (coup.y + 1, Taille - 1); y++) if (damier [x] [y] == coup.couleur) return true; return false; } list<Coup> coupsLegaux (char couleur) { list<Coup> liste; Coup coup; coup.couleur = couleur; for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) { coup.x = i; coup.y = j; if (coupLegal (coup)) liste.push_back (coup); } return liste; } friend ostream & operator << (ostream & sortie, const Virus & v); }; ostream & operator << (ostream & sortie, const Virus & 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; } sortie << "evaluation pour @ = " << v.evaluation ('@') << endl; return sortie; } Virus virus; int negamax (int depth, char joueur, Coup & meilleurCoup) { if (depth == 0) return virus.evaluation (joueur); list<Coup> listeCoups = virus.coupsLegaux (joueur); if (listeCoups.empty ()) return virus.evaluationSiPlusDeCoupsPossibles (joueur); int meilleureEvaluation = - Taille * Taille - 1; char autre = virus.adversaire (joueur); Coup coup; for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { virus.joue (*it); int eval = -negamax (depth - 1, autre, coup); if (eval > meilleureEvaluation) { meilleureEvaluation = eval; meilleurCoup = *it; } virus.dejoue (*it); } return meilleureEvaluation; } int main () { list<Coup> listeCoups; while (true) { cout << virus; listeCoups = virus.coupsLegaux ('@'); if (listeCoups.empty ()) break; cout << "Donnez votre coup : "; Coup coup; coup.couleur = '@'; do { cin >> coup.x >> coup.y; } while (!virus.coupLegal (coup)); virus.joue (coup); cout << virus; listeCoups = virus.coupsLegaux ('O'); if (listeCoups.empty ()) break; int eval = negamax (4, 'O', coup); cout << "eval = " << eval << endl; cout << "Je joue en " << coup.x << " " << coup.y << endl; virus.joue (coup); } return 0; }