#include <iostream> #include <list> #include <algorithm> using namespace std; const int Taille = 11; 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; list<Intersection> vides; 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; c.l.clear (); 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) { if (c.l.size () > 1) sortie << "("; for (list<Intersection>::iterator it = c.l.begin (); it != c.l.end (); ++it) sortie << "(" << it->x << "," << it->y << ")"; if (c.l.size () > 1) sortie << ")"; if (c.vides.size () > 0) for (list<Intersection>::iterator it = c.vides.begin (); it != c.vides.end (); ++it) sortie << "[" << it->x << "," << it->y << "]"; return sortie; } class Zone { public: unsigned long long z [3]; Zone () { init (); } void init () { z [0] = 0; z [1] = 0; z [2] = 0; } Zone operator + (Zone zone) { Zone res; res.z [0] = z [0] | zone.z[0]; res.z [1] = z [1] | zone.z[1]; res.z [2] = z [2] | zone.z[2]; return res; } bool marquee (int x, int y) { int inter = x + y * Taille; return (z [inter / 64] & (1ULL << (inter % 64))) > 0; } void marque (int x, int y) { int inter = x + y * Taille; z [inter / 64] |= (1ULL << (inter % 64)); } Zone dilate () { Zone res; for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) if (marquee (i, j)) { for (int i1 = -1; i1 <= 1; i1++) for (int j1 = -1; j1 <= 1; j1++) { Intersection inter; inter.x = i + i1; inter.y = j + j1; if (inter.legale ()) res.marque (inter.x, inter.y); } } return res; } friend ostream & operator << (ostream & sortie, Zone & z); }; ostream & operator << (ostream & sortie, Zone & z) { 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++) if (z.marquee (j, i)) sortie << "1 "; else sortie << "0 "; sortie << endl; } return sortie; } Zone zone; unsigned long long HashPierre [Taille] [Taille]; unsigned long long HashBalle [Taille] [Taille]; void initHash () { for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) { HashPierre [i] [j] = 0; for (int b = 0; b < 64; b++) if ((rand () / (RAND_MAX + 1.0)) > 0.5) HashPierre [i] [j] |= (1ULL << b); HashBalle [i] [j] = 0; for (int b = 0; b < 64; b++) if ((rand () / (RAND_MAX + 1.0)) > 0.5) HashBalle [i] [j] |= (1ULL << b); } } class Phutball { public: char damier [Taille] [Taille]; Intersection balle; unsigned long long hash; void init () { hash = 0; for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) damier [i] [j] = '+'; damier [Taille / 2] [Taille / 2] = '@'; hash ^= HashBalle [Taille / 2] [Taille / 2]; balle.x = Taille / 2; balle.y = Taille / 2; } void joue (Coup & c, Zone & z = zone) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) { damier [it->x] [it->y] = 'O'; hash ^= HashPierre [it->x] [it->y]; z.marque (it->x, it->y); } else { bool premiereModification = true; list<Intersection>::iterator precedent = it; while (true) { precedent = it; it++; if (it == c.l.end ()) break; damier [precedent->x] [precedent->y] = '+'; if (premiereModification) { premiereModification = false; hash ^= HashBalle [precedent->x] [precedent->y]; } else hash ^= HashPierre [precedent->x] [precedent->y]; z.marque (precedent->x, precedent->y); } if (precedent->legale ()) { damier [precedent->x] [precedent->y] = '@'; hash ^= HashBalle [precedent->x] [precedent->y]; z.marque (precedent->x, precedent->y); balle = *precedent; } } for (list<Intersection>::iterator it = c.vides.begin (); it != c.vides.end (); ++it) z.marque (it->x, it->y); } void dejoue (Coup & c) { list<Intersection>::iterator it = c.l.begin (); if (c.l.size () == 1) { damier [it->x] [it->y] = '+'; hash ^= HashPierre [it->x] [it->y]; } else { damier [balle.x] [balle.y] = '+'; hash ^= HashBalle [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'; hash ^= HashPierre [precedent->x] [precedent->y]; } damier [balle.x] [balle.y] = '@'; hash ^= HashBalle [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, zone); damier [balle.x] [balle.y] = '@'; return gagne; } bool coupsLegaux (int joueur, list<Coup> & liste, Zone z, int ordre, Zone & tests = zone) { liste.clear (); Coup coup; coup.l.push_back (balle); damier [balle.x] [balle.y] = '+'; bool gagne = coupsBalle (joueur, coup, liste, tests, zone); damier [balle.x] [balle.y] = '@'; Zone z1; if (ordre == 0) z1 = z; else z1 = z.dilate (); /* z1 = z; */ /* for (int i1 = -1; i1 <= 1; i1++) */ /* for (int j1 = -1; j1 <= 1; j1++) { */ /* Intersection inter = balle; */ /* inter.x += i1; */ /* inter.y += j1; */ /* if (inter.legale ()) */ /* if (damier [inter.x] [inter.y] == '+') { */ /* Coup coup; */ /* coup.l.push_back (inter); */ /* liste.push_back (coup); */ /* } */ /* } */ for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) /* if (true) { */ if (z1.marquee (i, j)) { Intersection inter; inter.x = i; inter.y = j; if (damier [inter.x] [inter.y] == '+') { Coup coup; coup.l.push_back (inter); liste.push_back (coup); } } return gagne; } bool coupsLegaux (int ordre, int joueur, list<Coup> & liste, Zone & tests = zone, Zone & raisonsGain = zone) { 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, tests, raisonsGain); if (gagne) raisonsGain.marque (balle.x, balle.y); damier [balle.x] [balle.y] = '@'; } return gagne; } bool coupsBalle (int joueur, Coup & coup, list<Coup> & liste, Zone & tests = zone, Zone & raisonsGain = zone) { bool coupGagnant = false; for (int i = -1; i <= 1; i++) for (int j = -1; j <= 1; j++) { if (!coupGagnant) raisonsGain.init (); Intersection inter = balle; inter.x += i; inter.y += j; if (inter.legale ()) { tests.marque (inter.x, inter.y); if (!coupGagnant) raisonsGain.marque (inter.x, inter.y); 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 ()) tests.marque (inter.x, inter.y); if (!coupGagnant && inter.legale ()) raisonsGain.marque (inter.x, inter.y); if (!inter.legale ()) break; if (damier [inter.x] [inter.y] != 'O') break; } if (gagne (joueur, inter)) { if (inter.legale ()) coup1.vides.push_back (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 memorise l'intersection vide coup1.vides.push_back (inter); // on ajoute le nouveau coup Coup coup2 = coup1; coup2.l.push_back (inter); liste.push_back (coup2); // on regarde les coups suivants Zone raisonsGain1; if (coupsBalle (joueur, coup1, liste, tests, raisonsGain1)) { raisonsGain = raisonsGain + raisonsGain1; 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 << *this << "bug coupsBalle \n"; } } } } return coupGagnant; } 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); } } } } 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; void affiche () { cerr << phutball; } int adversaire (int joueur) { if (joueur == JoueurGauche) return JoueurDroit; return JoueurGauche; } const int MaxOrdre = 10; class Menace { public: int nbOrdre [MaxOrdre]; Menace (int n0 = 0, int n1 = 0, int n2 = 0, int n3 = 0) { for (int i = 0; i < MaxOrdre; i++) nbOrdre [i] = 0; nbOrdre [0] = n0; nbOrdre [1] = n1; nbOrdre [2] = n2; nbOrdre [3] = n3; } void ecrete (int n) { for (int i = n; i < MaxOrdre; i++) nbOrdre [i] = 0; } int ordre () { for (int i = 0; i < MaxOrdre - 1; i++) if (nbOrdre [i + 1] == 0) return i; return 9; } Menace moitie () { Menace m; for (int i = 0; i < MaxOrdre; i++) m.nbOrdre [i] = nbOrdre [i] / 2; return m; } bool operator < (Menace & m) { bool auMoinsUnInferieur = false; for (int i = 0; i < MaxOrdre; i++) { if (nbOrdre [i] > m.nbOrdre [i]) return false; if (nbOrdre [i] < m.nbOrdre [i]) auMoinsUnInferieur = true; } if (auMoinsUnInferieur) return true; return false; } friend ostream & operator << (ostream & sortie, Menace & m); }; ostream & operator << (ostream & sortie, Menace & m) { sortie << "(" << m.nbOrdre [0] << "," << m.nbOrdre [1] << "," << m.nbOrdre [2] << "," << m.nbOrdre [3] << ")"; return sortie; } int nbMenaces = 3; Menace menaces [10]; void initMenaces () { menaces [0].nbOrdre [0] = 5; menaces [0].nbOrdre [1] = 1; menaces [1].nbOrdre [0] = 5; menaces [1].nbOrdre [1] = 0; menaces [2].nbOrdre [0] = 5; menaces [2].nbOrdre [1] = 0; menaces [2].nbOrdre [2] = 0; menaces [3].nbOrdre [0] = 5; menaces [3].nbOrdre [1] = 0; menaces [3].nbOrdre [2] = 0; menaces [3].nbOrdre [3] = 0; nbMenaces = 3; } Coup tueurMax [100], tueurMin [100]; void insereEnPremier (Coup & coup, list<Coup> & listeCoups) { for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) if (coup == *it) { listeCoups.erase (it); listeCoups.push_front (coup); break; } } bool debug = false; bool lambda (int joueur, Menace m, Zone & z, int nbCoupsMax, int nbCoupsMin, list<Coup> & vp) { Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; 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, z2, raisonsGain)) { z = z + raisonsGain; return true; } int n = m.ordre (); if (n == 0) return false; /* Menace moitie = m.moitie (); */ /* if (lambda (joueur, moitie, z, nbCoupsMax, nbCoupsMin, vp)) */ /* return true; */ /* if (n >= 3) */ /* cerr << phutball; */ phutball.coupsLegaux (n, joueur, listeCoups); insereEnPremier (tueurMax [nbCoupsMax], listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { z3.init (); phutball.joue (*it, z3); /* if (debug) */ /* cerr << phutball; */ bool menaceVerifiee = false; /* if (lambda (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; for (int o = 0; (o < n) && !menaceVerifiee; o++) { m1 = m; //m.moitie (); m1.ecrete (o + 1); z1.init (); if (lambda (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { menaceVerifiee = true; ordre = o; } } /* for (int o = 0; (o < nbMenaces) && (menaces [o] < m) && !menaceVerifiee; o++) { */ /* z1.init (); */ /* if (lambda (joueur, m, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ /* } */ /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ //m.nbOrdre [ordre + 1]--; if (m.nbOrdre [n] > 0) m.nbOrdre [n]--; else if ((n > 0) && (m.nbOrdre [n - 1] > 0)) m.nbOrdre [n - 1]--; else m.nbOrdre [ordre + 1]--; z3 = z3 + z1; bool gagneVerifie = false; if (menaceVerifiee) //if (!phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) { if (!phutball.coupsLegaux (autre, listeCoupsAdverses)) { bestvpMin.clear (); insereEnPremier (tueurMin [nbCoupsMin], listeCoupsAdverses); for (int o = 0; (o <= m.ordre ()) && !gagneVerifie; o++) { m1 = m; //m1 = m.moitie (); m1.ecrete (o + 1); gagneVerifie = true; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && gagneVerifie; ++it1) { phutball.joue (*it1, z3); /* if (debug) */ /* cerr << phutball; */ list<Coup> vptemp; if (!lambda (joueur, m1, z3, nbCoupsMax + 1, nbCoupsMin + 1, vptemp)) { tueurMin [nbCoupsMin] = *it1; gagneVerifie = false; } if (vptemp.size () >= bestvpMin.size ()) { bestvpMin = vptemp; bestvpMin.push_front (*it1); } phutball.dejoue (*it1); } } } phutball.dejoue (*it); m.nbOrdre [ordre + 1]++; if (gagneVerifie) { vp = bestvpMin; vp.push_front (*it); tueurMax [nbCoupsMax] = *it; z = z + z3; /* if (n >= 2) { */ /* cerr << phutball << "\ngagne\n" << z2; */ /* } */ return true; } if (bestvpMin.size () >= vp.size ()) { vp = bestvpMin; vp.push_front (*it); } } return false; } bool lambda1 (int joueur, Menace m, Zone & z, int nbCoupsMax, int nbCoupsMin, list<Coup> & vp); bool coupLambda1 (int joueur, Menace m, int nbCoupsMax, int nbCoupsMin, list<Coup> & listeCoupsAdverses, Zone & z3, list<Coup> & vp) { vp.clear (); insereEnPremier (tueurMin [nbCoupsMin], listeCoupsAdverses); bool gagneVerifie = true; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && gagneVerifie; ++it1) { phutball.joue (*it1, z3); /* if (debug) */ /* cerr << phutball; */ list<Coup> vptemp; if (!lambda1 (joueur, m, z3, nbCoupsMax + 1, nbCoupsMin + 1, vptemp)) { tueurMin [nbCoupsMin] = *it1; gagneVerifie = false; } if (vptemp.size () >= vp.size ()) { vp = vptemp; vp.push_front (*it1); } phutball.dejoue (*it1); } return gagneVerifie; } bool lambda1 (int joueur, Menace m, Zone & z, int nbCoupsMax, int nbCoupsMin, list<Coup> & vp) { Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; 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, z2, raisonsGain)) { z = z + raisonsGain; return true; } int n = m.ordre (); if (n == 0) return false; Menace moitie = m.moitie (); if (lambda1 (joueur, moitie, z, nbCoupsMax, nbCoupsMin, vp)) return true; /* if (n >= 3) */ /* cerr << phutball; */ phutball.coupsLegaux (n, joueur, listeCoups); insereEnPremier (tueurMax [nbCoupsMax], listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { z3.init (); phutball.joue (*it, z3); /* if (debug) */ /* cerr << phutball; */ bool menaceVerifiee = false; /* if (lambda1 (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; /* for (int o = 0; (o < n) && !menaceVerifiee; o++) { */ /* m1 = m; //m.moitie (); */ /* m1.ecrete (o + 1); */ /* z1.init (); */ /* if (lambda1 (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ /* } */ for (int o = 0; (o < nbMenaces) && (menaces [o] < m) && !menaceVerifiee; o++) { z1.init (); if (lambda1 (joueur, menaces [o], z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { menaceVerifiee = true; ordre = o; } } /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ m.nbOrdre [ordre + 1]--; z3 = z3 + z1; bool gagneVerifie = false; if (menaceVerifiee) if (!phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) { for (int o = 0; (o < nbMenaces) && (menaces [o] < m) && !gagneVerifie; o++) { if (coupLambda1 (joueur, menaces [o], nbCoupsMax, nbCoupsMin, listeCoupsAdverses, z3, bestvpMin)) gagneVerifie = true; } if (!gagneVerifie) if (coupLambda1 (joueur, m, nbCoupsMax, nbCoupsMin, listeCoupsAdverses, z3, bestvpMin)) gagneVerifie = true; } phutball.dejoue (*it); m.nbOrdre [ordre + 1]++; if (gagneVerifie) { vp = bestvpMin; vp.push_front (*it); tueurMax [nbCoupsMax] = *it; z = z + z3; /* if (n >= 2) { */ /* cerr << phutball << "\ngagne\n" << z2; */ /* } */ return true; } if (bestvpMin.size () >= vp.size ()) { vp = bestvpMin; vp.push_front (*it); } } return false; } const int Perdu = 0; const int PlusDeMenaces = 1; const int PasTermine = 2; const int PasTermineOrdre3 = 3; const int PasTermineOrdre2 = 4; const int PasTermineOrdre1 = 5; const int PasTermineOrdre0 = 6; const int Gagne = 10; int dfs1 (int joueur, int depth, Zone & z, int alpha, int beta, list<Coup> & vp) { Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; if (phutball.gagne (joueur, phutball.balle)) return Gagne; int autre = adversaire (joueur); if (phutball.gagne (autre, phutball.balle)) return Perdu; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (0, joueur, listeCoups, z2, raisonsGain)) { z = z + raisonsGain; return Gagne; } for (int o = 0; o < nbMenaces; o++) if (lambda (joueur, menaces [o], z1, 0, 0, vp)) return Gagne; if (depth == 0) return PasTermine; bool AuMoinsUneMenace = false; phutball.coupsLegaux (3, joueur, listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { z3.init (); phutball.joue (*it, z3); if (debug) cerr << phutball; bool menaceVerifiee = false; /* if (lambda (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; /* for (int o = 0; (o < n) && !menaceVerifiee; o++) { */ /* m1 = m; //m.moitie (); */ /* m1.ecrete (o + 1); */ /* z1.init (); */ /* if (lambda (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ /* } */ for (int o = 0; o < nbMenaces && !menaceVerifiee; o++) { z1.init (); if (lambda (joueur, menaces [o], z1, 0, 0, vptemp)) { menaceVerifiee = true; ordre = o; } } if (menaceVerifiee) AuMoinsUneMenace = true; /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ z3 = z3 + z1; int meilleurMin = alpha; if (menaceVerifiee) if (!phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) { meilleurMin = beta; bestvpMin.clear (); for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && alpha < meilleurMin; ++it1) { phutball.joue (*it1, z3); if (debug) cerr << phutball; list<Coup> vptemp; int eval = dfs1 (joueur, depth - 2, z3, alpha, meilleurMin, vptemp); if (eval <= meilleurMin) { meilleurMin = eval; if (vptemp.size () >= bestvpMin.size ()) { bestvpMin = vptemp; bestvpMin.push_front (*it1); } } phutball.dejoue (*it1); } } phutball.dejoue (*it); if (meilleurMin > alpha) { alpha = meilleurMin; vp = bestvpMin; vp.push_front (*it); z = z + z3; if (alpha >= beta) return alpha; } if (bestvpMin.size () >= vp.size ()) { vp = bestvpMin; vp.push_front (*it); } } if (!AuMoinsUneMenace) return PlusDeMenaces; return alpha; } int dfs (int joueur, int depth, Zone & z, int alpha, int beta, list<Coup> & vp) { Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; if (phutball.gagne (joueur, phutball.balle)) return Gagne; int autre = adversaire (joueur); if (phutball.gagne (autre, phutball.balle)) return Perdu; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (0, joueur, listeCoups, z2, raisonsGain)) { z = z + raisonsGain; return Gagne; } for (int o = 0; o < nbMenaces; o++) if (lambda (joueur, menaces [o], z1, 0, 0, vp)) return Gagne; if (depth == 0) return PasTermine; bool AuMoinsUneMenace = false; phutball.coupsLegaux (3, joueur, listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { z3.init (); phutball.joue (*it, z3); if (debug) cerr << phutball; bool menaceVerifiee = false; /* if (lambda (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; /* for (int o = 0; (o < n) && !menaceVerifiee; o++) { */ /* m1 = m; //m.moitie (); */ /* m1.ecrete (o + 1); */ /* z1.init (); */ /* if (lambda (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ for (int o = 0; (o < nbMenaces) && !menaceVerifiee; o++) { z1.init (); if (lambda (joueur, menaces [o], z1, 0, 0, vptemp)) { menaceVerifiee = true; ordre = o; } } if (menaceVerifiee) AuMoinsUneMenace = true; /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ z3 = z3 + z1; int meilleurMin = alpha; if (menaceVerifiee) { if (phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) meilleurMin = Perdu; else { bestvpMin.clear (); meilleurMin = beta; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && alpha < meilleurMin; ++it1) { phutball.joue (*it1, z3); if (debug) cerr << phutball; list<Coup> vptemp; int eval = dfs (joueur, depth - 2, z3, alpha, meilleurMin, vptemp); if (eval <= meilleurMin) { meilleurMin = eval; if (vptemp.size () >= bestvpMin.size ()) { bestvpMin = vptemp; bestvpMin.push_front (*it1); } } phutball.dejoue (*it1); } } } phutball.dejoue (*it); if (meilleurMin > alpha) { alpha = meilleurMin; vp = bestvpMin; vp.push_front (*it); z = z + z3; if (alpha >= beta) return alpha; } if (bestvpMin.size () >= vp.size ()) { vp = bestvpMin; vp.push_front (*it); } } if (!AuMoinsUneMenace) return PlusDeMenaces; return alpha; } int mid (int joueur, int depth, int menace, Zone & z, int alpha, int beta, list<Coup> & vp) { Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; if (phutball.gagne (joueur, phutball.balle)) return Gagne; int autre = adversaire (joueur); if (phutball.gagne (autre, phutball.balle)) return Perdu; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (0, joueur, listeCoups, z2, raisonsGain)) { z = z + raisonsGain; return Gagne; } /* for (int o = 0; o < nbMenaces; o++) */ for (int o = 0; o < 3; o++) if (lambda (joueur, menaces [o], z1, 0, 0, vp)) return Gagne; if (depth == 0) return PasTermine; bool AuMoinsUneMenace = false; phutball.coupsLegaux (3, joueur, listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); it != listeCoups.end (); ++it) { z3.init (); phutball.joue (*it, z3); if ((debug) || (menace == nbMenaces)) cerr << phutball; bool menaceVerifiee = false; /* if (lambda (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; /* for (int o = 0; (o < n) && !menaceVerifiee; o++) { */ /* m1 = m; //m.moitie (); */ /* m1.ecrete (o + 1); */ /* z1.init (); */ /* if (lambda (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ /* } */ for (int o = 0; (o <= menace) && !menaceVerifiee; o++) { z1.init (); if (lambda (joueur, menaces [o], z1, 0, 0, vptemp)) { menaceVerifiee = true; ordre = o; } } if (!menaceVerifiee) if (menace == nbMenaces) { menaceVerifiee = true; ordre = menace; for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) z1.marque (i, j); } if (menaceVerifiee) AuMoinsUneMenace = true; /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ z3 = z3 + z1; int meilleurMin = alpha; if (menaceVerifiee) { if (phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) meilleurMin = Perdu; else { bestvpMin.clear (); // mieux utiliser alpha et beta meilleurMin = PlusDeMenaces; for (int o = 0; (o <= menace) && (meilleurMin == PlusDeMenaces); o++) { int currentDepth = 64; if (o == menace) currentDepth = depth; meilleurMin = PasTermine; for (int d = 0; (d < currentDepth) && (meilleurMin == PasTermine); d += 2) { meilleurMin = beta; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && alpha < meilleurMin; ++it1) { phutball.joue (*it1, z3); if ((debug) || (menace == nbMenaces)) //if (debug) cerr << phutball; list<Coup> vptemp; int eval = mid (joueur, d, o, z3, alpha, meilleurMin, vptemp); if (eval <= meilleurMin) { meilleurMin = eval; if (vptemp.size () >= bestvpMin.size ()) { bestvpMin = vptemp; bestvpMin.push_front (*it1); } } phutball.dejoue (*it1); } } } } } phutball.dejoue (*it); if (meilleurMin > alpha) { alpha = meilleurMin; vp = bestvpMin; vp.push_front (*it); z = z + z3; if (alpha >= beta) return alpha; } if (bestvpMin.size () >= vp.size ()) { vp = bestvpMin; vp.push_front (*it); } } if (!AuMoinsUneMenace) return PlusDeMenaces; return alpha; } //const int SizeTT = 65535; const int SizeTT = 33554431; class Transpo { public: unsigned long long hash; int result; int ordre; Transpo * cherche (unsigned long long h) { if (hash == h) return this; return NULL; } void ajoute (unsigned long long h, int res, int ordre) { hash = h; result = res; ordre = ordre; } }; class Entree { public: list<Transpo> l; Transpo * cherche (unsigned long long h) { for (list<Transpo>::iterator it = l.begin (); it != l.end (); ++it) if (it->hash == h) return &(*it); return NULL; } void ajoute (unsigned long long h, int res, int ordre) { for (list<Transpo>::iterator it = l.begin (); it != l.end (); ++it) if (it->hash == h) { it->result = res; it->ordre = ordre; return; } Transpo t; t.hash = h; t.result = res; t.ordre = ordre; l.push_back (t); } }; class TT { public: Transpo entree [SizeTT]; Transpo * cherche (unsigned long long h) { return entree [h & SizeTT].cherche (h); } void ajoute (unsigned long long h, int res, int ordre) { entree [h & SizeTT].ajoute (h, res, ordre); } }; TT tt; int maxDepth [MaxOrdre]; int limitedDepth (int joueur, int depth, Zone & z, int alpha, int beta, list<Coup> & vp) { Transpo *t = tt.cherche (phutball.hash); if (t != NULL) { if (t->result == Gagne) return Gagne; if (t->result == Perdu) return Perdu; if (t->result == PlusDeMenaces) if (depth > maxDepth [t->ordre + 1]) return PlusDeMenaces; } Zone z1, z2, z3, ztemp, raisonsGain; list<Coup> bestvpMin, vptemp; if (phutball.gagne (joueur, phutball.balle)) return Gagne; int autre = adversaire (joueur); if (phutball.gagne (autre, phutball.balle)) return Perdu; list<Coup> listeCoups, listeCoupsAdverses; if (phutball.coupsLegaux (0, joueur, listeCoups, z2, raisonsGain)) { z = z + raisonsGain; return Gagne; } int ordreMax = 0; /* for (int o = 0; o < nbMenaces; o++) */ // for (int o = 0; o < 3; o++) for (int o = 0; o < (o < nbMenaces) && (depth < maxDepth [o]); o++) if (lambda (joueur, menaces [o], z1, 0, 0, vp)) { //tt.ajoute (phutball.hash, Gagne); return Gagne; } vp.clear (); if (depth >= maxDepth [0]) return PasTermineOrdre0; bool AuMoinsUneMenace = false; phutball.coupsLegaux (3, joueur, listeCoups); for (list<Coup>::iterator it = listeCoups.begin (); (it != listeCoups.end ()) && (alpha < beta); ++it) { z3.init (); phutball.joue (*it, z3); if (debug) cerr << phutball; else if (false && (depth < maxDepth [nbMenaces])) cerr << phutball; bool menaceVerifiee = false; /* if (lambda (joueur, m, depth - 1)) */ /* menaceVerifiee = true; */ Menace m1; int ordre = 0; /* for (int o = 0; (o < n) && !menaceVerifiee; o++) { */ /* m1 = m; //m.moitie (); */ /* m1.ecrete (o + 1); */ /* z1.init (); */ /* if (lambda (joueur, m1, z1, nbCoupsMax + 1, nbCoupsMin, vptemp)) { */ /* menaceVerifiee = true; */ /* ordre = o; */ /* } */ /* } */ for (int o = 0; (o < nbMenaces) && (depth < maxDepth [o]) && !menaceVerifiee; o++) { z1.init (); if (lambda (joueur, menaces [o], z1, 0, 0, vptemp)) { menaceVerifiee = true; ordre = o; } } if (!menaceVerifiee) if (depth < maxDepth [nbMenaces]) { menaceVerifiee = true; ordre = nbMenaces; for (int i = 0; i < Taille; i++) for (int j = 0; j < Taille; j++) z1.marque (i, j); } ordreMax = max (ordreMax, ordre); if (menaceVerifiee) AuMoinsUneMenace = true; /* if (menaceVerifiee && (n >= 1)) { */ /* cerr << phutball << "\nz1\n" << z1; */ /* } */ z3 = z3 + z1; int meilleurMin = alpha; bestvpMin.clear (); if (menaceVerifiee) { if (phutball.coupsLegaux (autre, listeCoupsAdverses, z1, ordre)) meilleurMin = Perdu; else { // mieux utiliser alpha et beta meilleurMin = beta; for (list<Coup>::iterator it1 = listeCoupsAdverses.begin (); (it1 != listeCoupsAdverses.end ()) && alpha < meilleurMin; ++it1) { phutball.joue (*it1, z3); if (debug) cerr << phutball; else if (false && (depth < maxDepth [nbMenaces])) cerr << phutball; list<Coup> vptemp; int eval = limitedDepth (joueur, depth + 2, z3, alpha, meilleurMin, vptemp); if (eval < meilleurMin) { meilleurMin = eval; bestvpMin = vptemp; bestvpMin.push_front (*it1); } else if ((eval == meilleurMin) && (((eval < Gagne) && (vptemp.size () + 1 < bestvpMin.size ())) || (((eval == Gagne) && (vptemp.size () + 1 > bestvpMin.size ())) || (bestvpMin.size () == 0)))) { bestvpMin = vptemp; bestvpMin.push_front (*it1); } phutball.dejoue (*it1); } } } phutball.dejoue (*it); /* if (depth == 0) */ /* cerr << "debug "; */ if (meilleurMin > alpha) { alpha = meilleurMin; vp = bestvpMin; vp.push_front (*it); z = z + z3; } else if ((meilleurMin == alpha) && (((meilleurMin < Gagne) && (bestvpMin.size () + 1 > vp.size ())) || (((meilleurMin == Gagne) && (bestvpMin.size () + 1 < vp.size ())) || (vp.size () == 0)))) { vp = bestvpMin; vp.push_front (*it); } } if (!AuMoinsUneMenace) alpha = PlusDeMenaces; if ((ordreMax >= 1) && (depth == maxDepth [1] - 2) && (alpha == PlusDeMenaces)) return PasTermineOrdre1; if ((nbMenaces > 2) && (ordreMax >= 2) && (depth == maxDepth [2] - 2) && (alpha == PlusDeMenaces)) return PasTermineOrdre2; if ((nbMenaces > 3) && (ordreMax >= 3) && (depth == maxDepth [3] - 2) && (alpha == PlusDeMenaces)) return PasTermineOrdre3; if (alpha == Gagne) tt.ajoute (phutball.hash, alpha, 0); else if (alpha == PlusDeMenaces) { if (depth < maxDepth [3]) tt.ajoute (phutball.hash, alpha, 3); else if (depth < maxDepth [2]) tt.ajoute (phutball.hash, alpha, 2); else if (depth < maxDepth [1]) tt.ajoute (phutball.hash, alpha, 1); else if (depth < maxDepth [0]) tt.ajoute (phutball.hash, alpha, 0); } return alpha; } const int MaxDepth = 64; int main () { list<Coup> listeCoups; initMenaces (); initHash (); phutball.init (); if (Taille == 11) { /* phutball.damier [6] [5] = 'O'; */ /* phutball.damier [4] [2] = 'O'; */ } else if (Taille == 13) { /* phutball.damier [7] [6] = 'O'; */ /* phutball.damier [5] [5] = 'O'; */ } /* phutball.damier [6] [4] = 'O'; */ /* phutball.damier [6] [6] = 'O'; */ /* phutball.damier [8] [4] = 'O'; */ /* phutball.damier [6] [8] = 'O'; */ /* phutball.damier [6] [8] = 'O'; */ /* phutball.damier [9] [5] = 'O'; */ /* phutball.damier [5] [5] = '+'; */ /* phutball.damier [5] [9] = '@'; */ /* phutball.balle.x = 5; */ /* phutball.balle.y = 9; */ /* cout << phutball; */ while (true) { cout << phutball; if (phutball.coupsLegaux (JoueurGauche, listeCoups)) { cout << "j'ai gagne !" << endl; break; } /* phutball.damier [5] [5] = '+'; */ /* phutball.damier [5] [3] = '@'; */ /* phutball.balle.x = 5; */ /* phutball.balle.y = 3; */ /* phutball.damier [6] [2] = 'O'; */ /* phutball.damier [7] [1] = 'O'; */ /* phutball.damier [8] [2] = 'O'; */ /* cout << phutball; */ //exit (1); //Menace m (40, 20, 10, 1); //Menace m (16, 8, 2, 2); //Menace m (8, 4, 2); //Menace m (6, 3, 2); int res = Perdu; list<Coup> vp; if (Taille == 9) { Menace m (4, 4, 1); res = lambda (JoueurGauche, m, zone, 0, 0, vp); cout << "test lambda " << m << " = " << res << endl; } else { // vecteur du nb de menaces autorisees // apres [0,100,100] on revient à [1,0,1] res = PasTermine; int depthStop = 0; nbMenaces = 1; for (maxDepth [nbMenaces] = 0; (maxDepth [nbMenaces] < MaxDepth) && (res != Gagne); maxDepth [nbMenaces] += 2) { res = PasTermineOrdre0; for (maxDepth [0] = 0; (maxDepth [0] < MaxDepth) && (res == PasTermineOrdre0); maxDepth [0] += 2) { vp.clear (); res = limitedDepth (JoueurGauche, 0, zone, PlusDeMenaces, Gagne, vp); cout << "test limitedDepth [" << maxDepth [0] << "," << maxDepth [1] << "," << "] = " << res << endl; for (list<Coup>::iterator it = vp.begin (); it != vp.end (); ++it) cout << *it << " "; cout << endl; } } exit (0); for (maxDepth [nbMenaces] = 0; (maxDepth [nbMenaces] < MaxDepth) && (res != Gagne); maxDepth [nbMenaces] += 2) { /* res = PasTermineOrdre3; */ /* for (maxDepth [3] = max (2, maxDepth [4]); (maxDepth [3] < MaxDepth) && (res == PasTermineOrdre3); maxDepth [3] += 2) { */ res = PasTermineOrdre2; for (maxDepth [2] = max (2, maxDepth [3]); (maxDepth [2] < MaxDepth) && (res == PasTermineOrdre2); maxDepth [2] += 2) { res = PasTermineOrdre1; for (maxDepth [1] = max (2, maxDepth [2]); (maxDepth [1] < MaxDepth) && (res == PasTermineOrdre1); maxDepth [1] += 2) { res = PasTermineOrdre0; for (maxDepth [0] = max (2, maxDepth [1]); (maxDepth [0] < MaxDepth) && (res == PasTermineOrdre0); maxDepth [0] += 2) { vp.clear (); res = limitedDepth (JoueurGauche, 0, zone, PlusDeMenaces, Gagne, vp); } cout << "test limitedDepth [" << maxDepth [0] << "," << maxDepth [1] << "," << maxDepth [2] << "," << maxDepth [3] << "," << maxDepth [4] << "] = " << res << endl; for (list<Coup>::iterator it = vp.begin (); it != vp.end (); ++it) cout << *it << " "; cout << endl; } } /* } */ if (res == PlusDeMenaces) res = PasTermine; } /* res = mid (JoueurGauche, 64, nbMenaces, zone, PasTermine, Gagne, vp); */ /* cout << "test mid " << " = " << res << endl; */ for (int d = 2; (d < 30) && (res < Gagne); d += 2) { res = dfs (JoueurGauche, d, zone, PasTermine, Gagne, vp); cout << "test dfs " << d << " = " << res << endl; } } for (list<Coup>::iterator it = vp.begin (); it != vp.end (); ++it) cout << *it << " "; Coup coup = *vp.begin (); cout << "\nJe joue en " << coup << endl; phutball.joue (coup); cout << phutball; if (phutball.coupsLegaux (JoueurDroit, listeCoups)) { cout << "vous avez gagne !" << endl; break; } cin >> coup; phutball.joue (coup); } return 0; }