#include <iostream> #include <list> #include <algorithm> #include <time.h> using namespace std; const int Taille = 7; class Coup { public: char couleur; int x, y; bool operator != (const Coup & c) { if ((couleur != c.couleur) || (x != c.x) || (y != c.y)) return true; return false; } friend ostream & operator << (ostream & sortie, const Coup & c); }; ostream & operator << (ostream & sortie, const Coup & c) { sortie << "(" << c.couleur << "," << c.x << "," << c.y << ")"; return sortie; } 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; } int nbCasesModifiees (Coup & m) { int nb = 1; 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) nb++; return nb; } list<Coup> coupsQuiescence (char couleur) { list<Coup> liste, l = coupsLegaux (couleur); for (list<Coup>::iterator it = l.begin (); it != l.end (); ++it) if (nbCasesModifiees (*it) > 4) liste.push_back (*it); 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; clock_t maxClock = 2 * CLOCKS_PER_SEC; // 2 secondes clock_t clockStart; const int ProfondeurMax = 64; int quiescence (int alpha, int beta, char joueur) { if (clock () - clockStart > maxClock) return 0; list<Coup> coups = virus.coupsQuiescence (joueur); if (coups.empty ()) return virus.evaluation (joueur); char autre = virus.adversaire (joueur); for (list<Coup>::iterator it = coups.begin(); it != coups.end(); ++it) { virus.joue (*it); int eval = -quiescence (-beta, -alpha, autre); virus.dejoue (*it); if (eval > alpha) alpha = eval; if (alpha >= beta) return beta; } return alpha; } Coup coupQuiTue [ProfondeurMax] [2]; void miseAJourCoupQuiTue (int d, Coup & coup) { if (coupQuiTue [d] [0] != coup) { coupQuiTue [d] [1] = coupQuiTue [d] [0]; coupQuiTue [d] [0] = coup; } } int alphabeta (int depth, int alpha, int beta, char joueur, list<Coup> & vp); void joueAlphaBeta (Coup & coup, int depth, int & alpha, int & beta, char joueur, list<Coup> &vp) { char autre = virus.adversaire (joueur); virus.joue (coup); list<Coup> vptemp; int eval = -alphabeta (depth - 1, -beta, -alpha, autre, vptemp); if (eval > alpha) { alpha = eval; vp = vptemp; vp.push_front (coup); } virus.dejoue (coup); if (alpha >= beta) miseAJourCoupQuiTue (depth, coup); } int alphabeta (int depth, int alpha, int beta, char joueur, list<Coup> & vp) { if (clock () - clockStart > maxClock) return 0; if (depth == 0) return quiescence (alpha, beta, joueur); list<Coup> listeCoups = virus.coupsLegaux (joueur); if (listeCoups.empty ()) return virus.evaluationSiPlusDeCoupsPossibles (joueur); /* Heuristique des coups qui tuent */ Coup killer = coupQuiTue [depth] [0]; Coup secondKiller = coupQuiTue [depth] [1]; if (killer.couleur == joueur) if (virus.coupLegal (killer)) joueAlphaBeta (killer, depth, alpha, beta, joueur, vp); if (alpha < beta) if (secondKiller.couleur == joueur) if (virus.coupLegal (secondKiller)) joueAlphaBeta (secondKiller, depth, alpha, beta, joueur, vp); /* Fin de l'heuristique des coups qui tuent */ for (list<Coup>::iterator it = listeCoups.begin (); (it != listeCoups.end ()) && (alpha < beta); ++it) if ((*it != killer) && (*it != secondKiller)) joueAlphaBeta (*it, depth, alpha, beta, joueur, vp); return alpha; } int approfondissementIteratif (list<Coup> & vp) { int eval = virus.evaluation ('O'); list<Coup> vpTemp; clockStart = clock (); for (int d = 1; (clock () - clockStart < maxClock) && (d < ProfondeurMax); d++) { int evalTemp = alphabeta (d, -Taille * Taille, Taille * Taille, 'O', vpTemp); if (clock () - clockStart < maxClock) { eval = evalTemp; vp = vpTemp; } } return eval; } 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; list<Coup> vp; int eval = approfondissementIteratif (vp); coup = *vp.begin (); cout << "eval = " << eval << endl; cout << "Variation : "; for (list<Coup>::iterator it = vp.begin (); it != vp.end (); ++it) cout << *it << " "; cout << endl; cout << "Je joue en " << coup.x << " " << coup.y << endl; virus.joue (coup); } return 0; }