#include <stdio.h> #include <stdlib.h> #include <math.h> #include <iostream> #include <stack> #include <list> using namespace std; const int Noir = 0; const int Blanc = 1; const int Vide = 2; const int Exterieur = 3; const int MaxCoups = 300; const int Taille = 9; float Constante = 0.3; float ConstanteRaveUCT = 0.001; float ConstanteRave = 0.001; class Intersection { public : int _x, _y; Intersection (int x = 0, int y = 0) { _x = x; _y = y; } Intersection voisine (int indice) { if (indice == 0) return Intersection (_x - 1, _y); if (indice == 1) return Intersection (_x, _y - 1); if (indice == 2) return Intersection (_x + 1, _y); if (indice == 3) return Intersection (_x, _y + 1); } Intersection diagonale (int indice) { if (indice == 0) return Intersection (_x - 1, _y - 1); if (indice == 1) return Intersection (_x + 1, _y - 1); if (indice == 2) return Intersection (_x + 1, _y + 1); if (indice == 3) return Intersection (_x - 1, _y + 1); } }; class Marquage { unsigned long long _marqueur; unsigned long long _marquee [Taille + 2] [Taille + 2]; public: Marquage () { _marqueur = 1; for (int i = 0; i < Taille + 2; i++) for (int j = 0; j < Taille + 2; j++) _marquee [i] [j] = 0; } void init () { _marqueur++; } bool marquee (int i, int j) { return (_marquee [i] [j] == _marqueur); } void marque (int i, int j) { _marquee [i] [j] = _marqueur; } bool marquee (Intersection inter) { return (_marquee [inter._x] [inter._y] == _marqueur); } void marque (Intersection inter) { _marquee [inter._x] [inter._y] = _marqueur; } }; Marquage dejavu, dejavu2; unsigned long long HashArray [2] [Taille + 2] [Taille + 2]; unsigned long long HashTurn; class Go { public: char goban [Taille + 2] [Taille + 2]; int nbCoupsJoues; Intersection moves [MaxCoups]; unsigned long long hash; unsigned long long HashHistory [MaxCoups]; float komi, score [2]; Go () { komi = 7.5; hash = 0; nbCoupsJoues = 0; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) goban [i] [j] = Vide; for (int i = 0; i < Taille + 2; i++) { goban [0] [i] = Exterieur; goban [i] [0] = Exterieur; goban [Taille + 1] [i] = Exterieur; goban [i] [Taille + 1] = Exterieur; } } void initHash () { for (int c = 0; c < 2; c++) for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { HashArray [c] [i] [j] = 0; for (int b = 0; b < 64; b++) if ((rand () / (RAND_MAX + 1.0)) > 0.5) HashArray [c] [i] [j] |= (1ULL << b); } HashTurn = 0; for (int j = 0; j < 64; j++) if ((rand () / (RAND_MAX + 1.0)) > 0.5) HashTurn |= (1ULL << j); } bool coupLegal (Intersection inter, int couleur) { if ((inter._x == 0) && (inter._y == 0)) return true; if (goban [inter._x] [inter._y] != Vide) return false; for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if (goban [voisine._x] [voisine._y] == Vide) return true; } for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if (goban [voisine._x] [voisine._y] == couleur) if (minLib (voisine, 2) > 1) return true; } unsigned long long h = hashSiJoue (inter, couleur); for (int i = nbCoupsJoues - 1; i >= 0; i--) if (HashHistory [i] == h) return false; return (minLibIfPlay (inter, couleur, 1) > 0); } unsigned long long hashSiJoue (Intersection inter, int couleur) { unsigned long long h = hash; int adversaire = Noir; if (couleur == Noir) adversaire = Blanc; dejavu2.init (); dejavu2.marque (inter); h ^= HashArray [couleur] [inter._x] [inter._y]; h ^= HashTurn; for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if (!dejavu2.marquee (voisine)) { if (goban [voisine._x] [voisine._y] == adversaire) if (minLib (voisine, 2) == 1) { stack<Intersection> st; dejavu2.marque (voisine); st.push (voisine); while (!st.empty ()) { Intersection courante = st.top (); st.pop (); h ^= HashArray [goban [voisine._x] [voisine._y]] [courante._x] [courante._y]; for (int j = 0; j < 4; j++) { Intersection pierre = courante.voisine (j); if (goban [pierre._x] [pierre._y] == adversaire) if (!dejavu2.marquee (pierre)) { dejavu2.marque (pierre); st.push (pierre); } } } } } } return h; } int minLib (Intersection inter, int min) { stack<Intersection> st; int compteur = 0, couleur = goban [inter._x] [inter._y]; dejavu.init (); dejavu.marque (inter); st.push (inter); while (!st.empty ()) { Intersection inter = st.top (); st.pop (); for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if (!dejavu.marquee (voisine)) { dejavu.marque (voisine); if (goban [voisine._x] [voisine._y] == Vide) { compteur++; if (compteur >= min) return compteur; } else if (goban [voisine._x] [voisine._y] == couleur) st.push (voisine); } } } return compteur; } int minLibIfPlay (Intersection intersection, int couleur, int min) { stack<Intersection> st; int compteur = 0; if (goban [intersection._x] [intersection._y] == Vide) { dejavu2.init (); dejavu2.marque (intersection); st.push (intersection); while (!st.empty ()) { Intersection inter = st.top (); st.pop (); for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if (!dejavu2.marquee (voisine)) { dejavu2.marque (voisine); if (goban [voisine._x] [voisine._y] == Vide) { compteur++; if (compteur >= min) return compteur; } if (goban [voisine._x] [voisine._y] == couleur) st.push (voisine); } } } int adversaire = Noir; if (couleur == Noir) adversaire = Blanc; for (int i = 0; i < 4; i++) { Intersection voisine = intersection.voisine (i); if (goban [voisine._x] [voisine._y] == adversaire) if (minLib (voisine, 2) == 1) { compteur++; if (compteur >= min) return compteur; } } } return compteur; } void joue (Intersection inter, int couleur) { HashHistory [nbCoupsJoues] = hash; moves [nbCoupsJoues] = inter; hash ^= HashTurn; if (inter._x != 0) { posePierre (inter, couleur); enlevePrisonniers (inter, couleur); } nbCoupsJoues++; } void posePierre (Intersection inter, int couleur) { goban [inter._x] [inter._y] = couleur; hash ^= HashArray [couleur] [inter._x] [inter._y]; } void enlevePrisonniers (Intersection inter, int couleur) { stack<Intersection> st; int adversaire = Noir; if (couleur == Noir) adversaire = Blanc; for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if ((goban [voisine._x] [voisine._y] == adversaire)) if (minLib (voisine, 1) == 0) st.push (voisine); } while (!st.empty ()) { Intersection voisine = st.top (); st.pop (); if ((goban [voisine._x] [voisine._y] == adversaire)) enleveChaine (voisine); } } void enleveChaine (Intersection intersection) { stack<Intersection> st; int couleur = goban [intersection._x] [intersection._y]; st.push (intersection); while (!st.empty ()) { Intersection inter = st.top (); st.pop (); hash ^= HashArray [couleur] [inter._x] [inter._y]; goban [inter._x] [inter._y] = Vide; for (int i = 0; i < 4; i++) { Intersection voisine = inter.voisine (i); if ((goban [voisine._x] [voisine._y] == couleur)) st.push (voisine); } } } bool entouree (Intersection intersection, int couleur) { if (goban [intersection._x] [intersection._y] != Vide) return false; for (int i = 0; i < 4; i++) { Intersection voisine = intersection.voisine (i); if ((goban [voisine._x] [voisine._y] != couleur) && (goban [voisine._x] [voisine._y] != Exterieur)) return false; } for (int i = 0; i < 4; i++) { Intersection voisine = intersection.voisine (i); if ((goban [voisine._x] [voisine._y] == couleur)) if (minLib (voisine, 2) == 1) return false; } return true; } bool protegee (Intersection inter, int couleur, bool & bord) { if (goban [inter._x] [inter._y] == Exterieur) { bord = true; return true; } if (goban [inter._x] [inter._y] == Vide) if (entouree (inter, couleur)) return true; if (goban [inter._x] [inter._y] == couleur) return true; return false; } bool oeil (Intersection inter, int couleur) { if (!entouree (inter, couleur)) return false; int nbDiagonalesProtegees = 0; bool bord = false; for (int i = 0; i < 4; i++) { Intersection diagonale = inter.diagonale (i); if (protegee (diagonale, couleur, bord)) nbDiagonalesProtegees++; } if (bord && (nbDiagonalesProtegees == 4)) return true; if (!bord && (nbDiagonalesProtegees > 2)) return true; return false; } /* score a la chinoise : nb de pierres sur le goban */ void calculeScores () { score [Noir] = 0; score [Blanc] = komi; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) if (goban [i] [j] == Vide) { Intersection inter (i, j); if (entouree (inter, Noir)) score [Noir] += 1.0; else if (entouree (inter, Blanc)) score [Blanc] += 1.0; } else score [goban [i] [j]] += 1.0; if (true) { if (score [Blanc] > score [Noir]) { score [Blanc] = 1.0; score [Noir] = 0.0; } else { score [Blanc] = 0.0; score [Noir] = 1.0; } } } bool gameOver () { int last = nbCoupsJoues - 1, nbPass = 0; while ((last > 0) && (moves [last]._x == 0)) { last--; nbPass++; } if (nbPass >= 2) return true; return false; } Intersection choisirUnCoup (int couleur) { int urgence [Taille + 2] [Taille + 2], nbUrgences = 0; Intersection inter; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) if (goban [i] [j] == Vide) { urgence [i] [j] = 1; nbUrgences++; } else urgence [i] [j] = 0; do { if (nbUrgences <= 0) return Intersection (0, 0); int index = (int) (nbUrgences * (rand () / (RAND_MAX + 1.0))); int somme = 0; for (int i = 1; ((i <= Taille) && (somme <= index)); i++) for (int j = 1; ((j <= Taille) && (somme <= index)); j++) if (urgence [i] [j] > 0) { somme += urgence [i] [j]; if (somme > index) { inter = Intersection (i, j); } } nbUrgences -= urgence [inter._x] [inter._y]; urgence [inter._x] [inter._y] = 0; } while (entouree (inter, couleur) || !coupLegal (inter, couleur)); return inter; } void playout (int couleur) { for (;;) { if ((nbCoupsJoues >= MaxCoups) || gameOver ()) break; Intersection inter = choisirUnCoup (couleur); joue (inter, couleur); if (couleur == Noir) couleur = Blanc; else couleur = Noir; } calculeScores (); } }; Go go; int nbPlayouts = 5000; Intersection meilleurCoupSampling (int couleur) { float meilleurScore = 0; Intersection meilleur (0, 0); for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); float somme = 0; if (go.coupLegal (inter, couleur) && !go.oeil (inter, couleur)) { for (int k = 0; k < 100; k++) { Go tmpgo = go; tmpgo.joue (inter, couleur); if (couleur == Noir) tmpgo.playout (Blanc); else tmpgo.playout (Noir); somme += tmpgo.score [couleur]; } } if (somme > meilleurScore) { meilleurScore = somme; meilleur = inter; } } return meilleur; } Intersection meilleurCoupUCB (int couleur) { float sommeScore [Taille + 2] [Taille + 2]; int nbPlayoutsCoup [Taille + 2] [Taille + 2]; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { sommeScore [i] [j] = 0; nbPlayoutsCoup [i] [j] = 0; } Intersection meilleurUCB (0, 0); for (int p = 0; p < nbPlayouts; p++) { float meilleurScore = 0; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); float score = 0; if (go.coupLegal (inter, couleur)) if (nbPlayoutsCoup [i] [j] == 0) score = 1000; else score = sommeScore [i] [j] / nbPlayoutsCoup [i] [j] + Constante * sqrt (log (p) / nbPlayoutsCoup [i] [j]); if (score > meilleurScore) { meilleurScore = score; meilleurUCB = inter; } } Go tmpgo = go; tmpgo.joue (meilleurUCB, couleur); if (couleur == Noir) tmpgo.playout (Blanc); else tmpgo.playout (Noir); sommeScore [meilleurUCB._x] [meilleurUCB._y] += tmpgo.score [couleur]; nbPlayoutsCoup [meilleurUCB._x] [meilleurUCB._y]++; } for (int i = 0; i < Taille + 2; i++) { for (int j = 0; j < Taille + 2; j++) if (go.goban [j] [i] == Exterieur) cout << " -"; else if (go.goban [j] [i] == Noir) cout << " @"; else if (go.goban [j] [i] == Noir) cout << " O"; else cout << " " << nbPlayoutsCoup [j] [i]; cout << endl; } float meilleurScore = 0; Intersection meilleur (0, 0); for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { Intersection inter (i, j); if (go.coupLegal (inter, couleur) && !go.oeil (inter, couleur)) if (nbPlayoutsCoup [i] [j] > meilleurScore) { meilleurScore = nbPlayoutsCoup [i] [j]; meilleur = inter; } } return meilleur; } Intersection meilleurCoupPermutation (int couleur) { int nbParties = 0; float scorePartie [2] [nbPlayouts]; bool partieContenantCoup [2] [Taille + 2] [Taille + 2] [nbPlayouts]; Intersection meilleur (0, 0); bool partiePossible [nbPlayouts]; int couleurCourante = couleur; for (int p = 0; p < nbPlayouts; p++) { nbParties = p; for (int i = 0; i < p; i++) partiePossible [i] = true; Go tmpgo = go; do { float meilleurScore = 0; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); if (tmpgo.coupLegal (inter, couleurCourante)) { int nbPartiesCoup = 0; float sommeScores = 0, score; for (int numeroPartie = 0; numeroPartie < p; numeroPartie++) { if (partiePossible [numeroPartie]) if (partieContenantCoup [couleurCourante] [i] [j] [numeroPartie]) { nbPartiesCoup++; sommeScores += scorePartie [couleurCourante] [numeroPartie]; } } if (nbPartiesCoup == 0) score = 1000; else score = sommeScores / nbPartiesCoup + 0.0 * sqrt (log (nbParties) / nbPartiesCoup); if (score > meilleurScore) { meilleurScore = score; meilleur = inter; } } } tmpgo.joue (meilleur, couleurCourante); nbParties = 0; for (int k = 0; k < p; k++) if (partiePossible [k]) { if (!partieContenantCoup [couleurCourante] [meilleur._x] [meilleur._y] [k]) partiePossible [k] = false; else nbParties++; } if (couleurCourante == Noir) couleurCourante = Blanc; else couleurCourante = Noir; } while (nbParties != 0); tmpgo.playout (couleurCourante); scorePartie [Noir] [p] = tmpgo.score [Noir]; scorePartie [Blanc] [p] = tmpgo.score [Blanc]; for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { partieContenantCoup [Noir] [i] [j] [p] = false; partieContenantCoup [Blanc] [i] [j] [p] = false; } couleurCourante = Noir; for (int i = 0; i < tmpgo.nbCoupsJoues; i++) { partieContenantCoup [couleurCourante] [tmpgo.moves [i]._x] [tmpgo.moves [i]._y] [p] = true; if (couleurCourante == Noir) couleurCourante = Blanc; else couleurCourante = Noir; } } float meilleurScore = 0; for (int i = 0; i < Taille + 2; i++) { for (int j = 0; j < Taille + 2; j++) if (go.goban [j] [i] == Exterieur) cout << " -"; else if (go.goban [j] [i] == Noir) cout << " @"; else if (go.goban [j] [i] == Blanc) cout << " O"; else { Intersection inter (i, j); if (go.coupLegal (inter, couleur)) { int nbPartiesCoup = 0; float sommeScores = 0, score; for (int numeroPartie = 0; numeroPartie < nbPlayouts; numeroPartie++) { if (partieContenantCoup [couleur] [i] [j] [numeroPartie]) { nbPartiesCoup++; sommeScores += scorePartie [couleur] [numeroPartie]; } } if (nbPartiesCoup == 0) score = 0; else score = sommeScores / nbPartiesCoup; if (score > meilleurScore) { meilleurScore = score; meilleur = inter; } cout << " " << score; } else cout << " +"; } cout << endl; } return meilleur; } class Noeud { public: float sommeScore [Taille + 2] [Taille + 2]; int nbPlayoutsCoup [Taille + 2] [Taille + 2]; unsigned long long hash; int abscisse, ordonnee; Noeud * fils [Taille + 2] [Taille + 2]; void init () { abscisse = 0; ordonnee = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { sommeScore [i] [j] = 0; nbPlayoutsCoup [i] [j] = 0; fils [i] [j] = NULL; } } float moyenne (int profondeur) { int nb = 0; float somme = 0.0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) { nb += nbPlayoutsCoup [i] [j]; somme += sommeScore [i] [j]; } else { if (fils [i] [j] != NULL) { int nbPlayoutFils = fils [i] [j]->nbPlayouts (profondeur - 1); nb += nbPlayoutFils; somme += nbPlayoutFils * (1.0 - fils [i] [j]->moyenne (profondeur - 1)); } } if (nb == 0) return 0.0; return somme / nb; } float moyenne (int i, int j, int profondeur) { if (profondeur == 0) { if (nbPlayoutsCoup [i] [j] == 0) return 0.0; return sommeScore [i] [j] / nbPlayoutsCoup [i] [j]; } else if (fils [i] [j] != NULL) return 1.0 - fils [i] [j]->moyenne (profondeur - 1); else { if (nbPlayoutsCoup [i] [j] == 0) return 0.0; return sommeScore [i] [j] / nbPlayoutsCoup [i] [j]; } } int nbPlayouts (int profondeur) { int nb = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) nb += nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) { nb += fils [i] [j]->nbPlayouts (profondeur - 1); } return nb; } int nbPlayoutsFils (int i, int j, int profondeur) { if (profondeur == 0) return nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) return fils [i] [j]->nbPlayouts (profondeur - 1); else return nbPlayoutsCoup [i] [j]; } void descente (Go & goban, int couleur); }; const int TailleTable = 65535; class Table { public: list<Noeud *> table [TailleTable + 1]; Noeud * present (unsigned long long hash) { for (list<Noeud *>::iterator iter = table [hash & TailleTable].begin (); iter != table [hash & TailleTable].end (); iter++) if ((*iter)->hash == hash) return *iter; return NULL; } void ajoute (Noeud *n) { table [n->hash & TailleTable].push_back (n); } void clear () { for (int i = 0; i < TailleTable + 1; i++) table [i].clear (); } }; Table table; const int MaxNoeud = 100000; int nbNoeuds = MaxNoeud; Noeud pileNoeud [MaxNoeud]; Noeud racine; int nmoy = 0, npere = 0, nfils = 0; bool pasDeTranspo = false; void Noeud::descente (Go & goban, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if ((goban.nbCoupsJoues >= MaxCoups) || goban.gameOver ()) { goban.calculeScores (); return; } while (ordonnee != Taille + 1) { Intersection inter (abscisse, ordonnee); abscisse++; if (abscisse == Taille + 1) { abscisse = 1; ordonnee++; } if (goban.coupLegal (inter, couleur) && !goban.oeil (inter, couleur)) { goban.joue (inter, couleur); Noeud *n = table.present (goban.hash); if (pasDeTranspo) n = NULL; if (n == NULL) { nbNoeuds--; n = &pileNoeud [nbNoeuds]; n->init (); n->hash = goban.hash; table.ajoute (n); fils [inter._x] [inter._y] = n; goban.playout (autre); sommeScore [inter._x] [inter._y] = goban.score [couleur]; nbPlayoutsCoup [inter._x] [inter._y] = 1; return; } fils [inter._x] [inter._y] = n; n->descente (goban, autre); sommeScore [inter._x] [inter._y] = goban.score [couleur]; nbPlayoutsCoup [inter._x] [inter._y] = 1; return; } } float meilleurScore = -1.0; Intersection meilleur (0, 0); for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); if (goban.coupLegal (inter, couleur) && (fils [i] [j] != NULL)) { float moy = moyenne (i, j, nmoy); int playoutsFils = nbPlayoutsFils (i, j, nfils); int playoutsPere = nbPlayouts (npere); float score = moy + Constante * sqrt (log (playoutsPere) / playoutsFils); if (score > meilleurScore) { meilleurScore = score; meilleur = inter; } } } goban.joue (meilleur, couleur); fils [meilleur._x] [meilleur._y]->descente (goban, autre); sommeScore [meilleur._x] [meilleur._y] += goban.score [couleur]; nbPlayoutsCoup [meilleur._x] [meilleur._y]++; } Intersection meilleurCoupUCT (int couleur) { racine.init (); nbNoeuds = MaxNoeud; table.clear (); for (int p = 0; p < nbPlayouts; p++) { Go tmpgo = go; racine.descente (tmpgo, couleur); } int meilleurScore = -1; Intersection meilleur (0, 0); for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { Intersection inter (i, j); if (go.coupLegal (inter, couleur) && !go.oeil (inter, couleur)) { if (racine.nbPlayoutsCoup [i] [j] > meilleurScore) { meilleurScore = racine.nbPlayoutsCoup [i] [j]; meilleur = inter; } } } return meilleur; } class NoeudRaveUCT { public: float sommeScore [Taille + 2] [Taille + 2]; int nbPlayoutsCoup [Taille + 2] [Taille + 2]; unsigned long long hash; int abscisse, ordonnee; NoeudRaveUCT * fils [Taille + 2] [Taille + 2]; float sommeScoreAMAF [Taille + 2] [Taille + 2]; int nbPlayoutsCoupAMAF [Taille + 2] [Taille + 2]; void init () { abscisse = 0; ordonnee = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { sommeScore [i] [j] = 0; nbPlayoutsCoup [i] [j] = 0; fils [i] [j] = NULL; sommeScoreAMAF [i] [j] = 0; nbPlayoutsCoupAMAF [i] [j] = 0; } } float moyenne (int profondeur) { int nb = 0; float somme = 0.0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) { nb += nbPlayoutsCoup [i] [j]; somme += sommeScore [i] [j]; } else { if (fils [i] [j] != NULL) { int nbPlayoutFils = fils [i] [j]->nbPlayouts (profondeur - 1); nb += nbPlayoutFils; somme += nbPlayoutFils * (1.0 - fils [i] [j]->moyenne (profondeur - 1)); } } if (nb == 0) return 0.0; return somme / nb; } float moyenne (int i, int j, int profondeur) { if (profondeur == 0) { if (nbPlayoutsCoup [i] [j] == 0) return 0.0; return sommeScore [i] [j] / nbPlayoutsCoup [i] [j]; } else if (fils [i] [j] != NULL) return 1.0 - fils [i] [j]->moyenne (profondeur - 1); else { if (nbPlayoutsCoup [i] [j] == 0) return 0.0; return sommeScore [i] [j] / nbPlayoutsCoup [i] [j]; } } int nbPlayouts (int profondeur) { int nb = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) nb += nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) { nb += fils [i] [j]->nbPlayouts (profondeur - 1); } return nb; } int nbPlayoutsFils (int i, int j, int profondeur) { if (profondeur == 0) return nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) return fils [i] [j]->nbPlayouts (profondeur - 1); else return nbPlayoutsCoup [i] [j]; } void modifieAMAF (int nbCoups, Go & goban, int couleur) { dejavu.init (); for (int i = nbCoups; i < goban.nbCoupsJoues; i ++) { Intersection inter = goban.moves [i]; if (inter._x != 0) { if (!dejavu.marquee (inter)) { dejavu.marque (inter); if (((i - nbCoups) & 1) == 0) { sommeScoreAMAF [inter._x] [inter._y] += goban.score [couleur]; nbPlayoutsCoupAMAF [inter._x] [inter._y]++; } } } } } void descente (Go & goban, int couleur); }; class TableRaveUCT { public: list<NoeudRaveUCT *> table [TailleTable + 1]; NoeudRaveUCT * present (unsigned long long hash) { for (list<NoeudRaveUCT *>::iterator iter = table [hash & TailleTable].begin (); iter != table [hash & TailleTable].end (); iter++) if ((*iter)->hash == hash) return *iter; return NULL; } void ajoute (NoeudRaveUCT *n) { table [n->hash & TailleTable].push_back (n); } void clear () { for (int i = 0; i < TailleTable + 1; i++) table [i].clear (); } }; TableRaveUCT tableRaveUCT; const int MaxNoeudRaveUCT = 100000; int nbNoeudsRaveUCT = MaxNoeudRaveUCT; NoeudRaveUCT pileNoeudRaveUCT [MaxNoeudRaveUCT]; NoeudRaveUCT racineRaveUCT; void NoeudRaveUCT::descente (Go & goban, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if ((goban.nbCoupsJoues >= MaxCoups) || goban.gameOver ()) { goban.calculeScores (); return; } int nbCoups = goban.nbCoupsJoues; while (ordonnee != Taille + 1) { Intersection inter (abscisse, ordonnee); abscisse++; if (abscisse == Taille + 1) { abscisse = 1; ordonnee++; } if (goban.coupLegal (inter, couleur) && !goban.oeil (inter, couleur)) { goban.joue (inter, couleur); NoeudRaveUCT *n = tableRaveUCT.present (goban.hash); if (pasDeTranspo) n = NULL; if (n == NULL) { nbNoeudsRaveUCT--; n = &pileNoeudRaveUCT [nbNoeudsRaveUCT]; n->init (); n->hash = goban.hash; tableRaveUCT.ajoute (n); fils [inter._x] [inter._y] = n; goban.playout (autre); sommeScore [inter._x] [inter._y] = goban.score [couleur]; nbPlayoutsCoup [inter._x] [inter._y] = 1; modifieAMAF (nbCoups, goban, couleur); return; } fils [inter._x] [inter._y] = n; n->descente (goban, autre); sommeScore [inter._x] [inter._y] = goban.score [couleur]; nbPlayoutsCoup [inter._x] [inter._y] = 1; modifieAMAF (nbCoups, goban, couleur); return; } } float meilleurScore = -1.0; Intersection meilleur (0, 0); for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); if (goban.coupLegal (inter, couleur) && (fils [i] [j] != NULL)) { float moy = moyenne (i, j, nmoy); int playoutsFils = nbPlayoutsFils (i, j, nfils); int playoutsPere = nbPlayouts (npere); float UCB = moy + Constante * sqrt (log (playoutsPere) / playoutsFils); float moyenneAMAF = 1.0; if (nbPlayoutsCoupAMAF [i] [j] > 0) moyenneAMAF = sommeScoreAMAF [i] [j] / nbPlayoutsCoupAMAF [i] [j]; float beta = (nbPlayoutsCoupAMAF [i] [j] / (nbPlayoutsCoupAMAF [i] [j] + playoutsFils + ConstanteRaveUCT * nbPlayoutsCoupAMAF [i] [j] * playoutsFils)); float score = (1.0 - beta) * moy + beta * moyenneAMAF; if (ConstanteRaveUCT == 0.0) score = UCB; if (score > meilleurScore) { meilleurScore = score; meilleur = inter; } } } goban.joue (meilleur, couleur); fils [meilleur._x] [meilleur._y]->descente (goban, autre); sommeScore [meilleur._x] [meilleur._y] += goban.score [couleur]; nbPlayoutsCoup [meilleur._x] [meilleur._y]++; modifieAMAF (nbCoups, goban, couleur); } Intersection meilleurCoupRaveUCT (int couleur) { racineRaveUCT.init (); nbNoeudsRaveUCT = MaxNoeudRaveUCT; tableRaveUCT.clear (); for (int p = 0; p < nbPlayouts; p++) { Go tmpgo = go; racineRaveUCT.descente (tmpgo, couleur); } int meilleurScore = -1; Intersection meilleur (0, 0); for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { Intersection inter (i, j); if (go.coupLegal (inter, couleur) && !go.oeil (inter, couleur)) { //cout << "(" << i << "," << j << ")->" << racineRaveUCT.nbPlayoutsCoup [i] [j] << " "; if (racineRaveUCT.nbPlayoutsCoup [i] [j] > meilleurScore) { meilleurScore = racineRaveUCT.nbPlayoutsCoup [i] [j]; meilleur = inter; } } } return meilleur; } class NoeudRave { public: float sommeScore [Taille + 2] [Taille + 2]; int nbPlayoutsCoup [Taille + 2] [Taille + 2]; unsigned long long hash; int abscisse, ordonnee; NoeudRave * fils [Taille + 2] [Taille + 2]; float sommeScoreAMAF [Taille + 2] [Taille + 2]; int nbPlayoutsCoupAMAF [Taille + 2] [Taille + 2]; void init () { abscisse = 0; ordonnee = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { sommeScore [i] [j] = 0; nbPlayoutsCoup [i] [j] = 0; fils [i] [j] = NULL; sommeScoreAMAF [i] [j] = 0; nbPlayoutsCoupAMAF [i] [j] = 0; } } float moyenne (int profondeur) { int nb = 0; float somme = 0.0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) { nb += nbPlayoutsCoup [i] [j]; somme += sommeScore [i] [j]; } else { if (fils [i] [j] != NULL) { int nbPlayoutFils = fils [i] [j]->nbPlayouts (profondeur - 1); nb += nbPlayoutFils; somme += nbPlayoutFils * (1.0 - fils [i] [j]->moyenne (profondeur - 1)); } } if (nb == 0) return 0.0; return somme / nb; } float moyenne (int i, int j, int profondeur) { if (profondeur == 0) { return (sommeScore [i] [j] + 1) / (nbPlayoutsCoup [i] [j] + 2); } else if (fils [i] [j] != NULL) return 1.0 - fils [i] [j]->moyenne (profondeur - 1); else { if (nbPlayoutsCoup [i] [j] == 0) return 0.0; return sommeScore [i] [j] / nbPlayoutsCoup [i] [j]; } } int nbPlayouts (int profondeur) { int nb = 0; for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) if (profondeur == 0) nb += nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) { nb += fils [i] [j]->nbPlayouts (profondeur - 1); } return nb; } int nbPlayoutsFils (int i, int j, int profondeur) { if (profondeur == 0) return nbPlayoutsCoup [i] [j]; else if (fils [i] [j] != NULL) return fils [i] [j]->nbPlayouts (profondeur - 1); else return nbPlayoutsCoup [i] [j]; } void modifieAMAF (int nbCoups, Go & goban, int couleur) { dejavu.init (); for (int i = nbCoups; i < goban.nbCoupsJoues; i ++) { Intersection inter = goban.moves [i]; if (inter._x != 0) { if (!dejavu.marquee (inter)) { dejavu.marque (inter); if (((i - nbCoups) & 1) == 0) { sommeScoreAMAF [inter._x] [inter._y] += goban.score [couleur]; nbPlayoutsCoupAMAF [inter._x] [inter._y]++; } } } } } void descente (Go & goban, int couleur); }; class TableRave { public: list<NoeudRave *> table [TailleTable + 1]; NoeudRave * present (unsigned long long hash) { for (list<NoeudRave *>::iterator iter = table [hash & TailleTable].begin (); iter != table [hash & TailleTable].end (); iter++) if ((*iter)->hash == hash) return *iter; return NULL; } void ajoute (NoeudRave *n) { table [n->hash & TailleTable].push_back (n); } void clear () { for (int i = 0; i < TailleTable + 1; i++) table [i].clear (); } }; TableRave tableRave; const int MaxNoeudRave = 10000; int nbNoeudsRave = MaxNoeudRave; NoeudRave racineRave; NoeudRave pileNoeudRave [MaxNoeudRave]; void NoeudRave::descente (Go & goban, int couleur) { int autre = Noir; if (couleur == Noir) autre = Blanc; if ((goban.nbCoupsJoues >= MaxCoups) || goban.gameOver ()) { goban.calculeScores (); return; } int nbCoups = goban.nbCoupsJoues; float meilleurScore = -1.0; Intersection meilleur (0, 0); for (int i = 1; i <= Taille; i++) for (int j = 1; j <= Taille; j++) { Intersection inter (i, j); if (goban.coupLegal (inter, couleur) && !goban.oeil (inter, couleur)) { float moy = moyenne (i, j, nmoy); int playoutsFils = nbPlayoutsFils (i, j, nfils); float moyenneAMAF = (sommeScoreAMAF [i] [j] + 1) / (nbPlayoutsCoupAMAF [i] [j] + 2); float beta = (nbPlayoutsCoupAMAF [i] [j] / (1 + nbPlayoutsCoupAMAF [i] [j] + playoutsFils + ConstanteRave * nbPlayoutsCoupAMAF [i] [j] * playoutsFils)); float score = (1.0 - beta) * moy + beta * moyenneAMAF; if (score > meilleurScore) { meilleurScore = score; meilleur = inter; } } } goban.joue (meilleur, couleur); if (fils [meilleur._x] [meilleur._y] != NULL) fils [meilleur._x] [meilleur._y]->descente (goban, autre); else { NoeudRave *n = tableRave.present (goban.hash); if (pasDeTranspo) n = NULL; if (n == NULL) { nbNoeudsRave--; n = &pileNoeudRave [nbNoeudsRave]; n->init (); n->hash = goban.hash; tableRave.ajoute (n); fils [meilleur._x] [meilleur._y] = n; goban.playout (autre); } else { fils [meilleur._x] [meilleur._y] = n; n->descente (goban, autre); } } sommeScore [meilleur._x] [meilleur._y] += goban.score [couleur]; nbPlayoutsCoup [meilleur._x] [meilleur._y]++; modifieAMAF (nbCoups, goban, couleur); } Intersection meilleurCoupRave (int couleur) { racineRave.init (); nbNoeudsRave = MaxNoeudRave; tableRave.clear (); for (int p = 0; p < nbPlayouts; p++) { Go tmpgo = go; racineRave.descente (tmpgo, couleur); } int meilleurScore = -1; Intersection meilleur (0, 0); for (int i = 0; i <= Taille; i++) for (int j = 0; j <= Taille; j++) { Intersection inter (i, j); if (go.coupLegal (inter, couleur) && !go.oeil (inter, couleur)) { if (racineRave.nbPlayoutsCoup [i] [j] > meilleurScore) { meilleurScore = racineRave.nbPlayoutsCoup [i] [j]; meilleur = inter; } } } return meilleur; } class Algorithme { public: int nmoy, npere, nfils; bool pasDeTranspo, raveUCT; float constanteRave; }; bool match (Algorithme a, Algorithme b) { int couleur = Noir; for (;;) { if ((go.nbCoupsJoues >= MaxCoups) || go.gameOver ()) break; Intersection inter; if (couleur == Noir) { //inter = meilleurCoupPermutation (Noir); nmoy = a.nmoy; npere = a.npere; nfils = a.nfils; pasDeTranspo = a.pasDeTranspo; ConstanteRave = a.constanteRave; ConstanteRaveUCT = a.constanteRave; if (a.raveUCT) inter = meilleurCoupRaveUCT (Noir); else inter = meilleurCoupRave (Noir); } else { //inter = meilleurCoupUCB (Blanc); nmoy = b.nmoy; npere = b.npere; nfils = b.nfils; pasDeTranspo = b.pasDeTranspo; ConstanteRave = b.constanteRave; ConstanteRaveUCT = b.constanteRave; if (b.raveUCT) inter = meilleurCoupRaveUCT (Blanc); else inter = meilleurCoupRave (Blanc); } go.joue (inter, couleur); for (int i = 0; i < Taille + 2; i++) { for (int j = 0; j < Taille + 2; j++) if (go.goban [j] [i] == Exterieur) cout << " -"; else if (go.goban [j] [i] == Vide) cout << " +"; else if (go.goban [j] [i] == Noir) cout << " @"; else cout << " O"; cout << endl; } if (couleur == Noir) couleur = Blanc; else couleur = Noir; } go.calculeScores (); return true; } int nbPartiesRencontre = 10; int rencontre (Algorithme a, Algorithme b) { Go tmp; int gains = 0; for (int i = 0; i < nbPartiesRencontre / 2; i++) { go = tmp; match (a, b); if (go.score [Noir] > go.score [Blanc]) gains++; cout << "gains = " << gains << "/" << i + 1 << endl; } for (int i = 0; i < nbPartiesRencontre / 2; i++) { go = tmp; match (b, a); if (go.score [Blanc] > go.score [Noir]) gains++; cout << "gains = " << gains << "/" << nbPartiesRencontre / 2 + i + 1 << endl; } return gains; } void interface () { while (true) { //Intersection inter = meilleurCoupSampling (Noir); //Intersection inter = meilleurCoupUCB (Noir); Intersection inter = meilleurCoupPermutation (Noir); cout << "meilleur coup en " << inter._x << "," << inter._y << endl; go.joue (inter, Noir); for (int i = 0; i < Taille + 2; i++) { for (int j = 0; j < Taille + 2; j++) if (go.goban [j] [i] == Exterieur) cout << " -"; else if (go.goban [j] [i] == Vide) cout << " +"; else if (go.goban [j] [i] == Noir) cout << " @"; else cout << " O"; cout << endl; } do { cout << "Votre coup : "; cin >> inter._x >> inter._y; } while (!go.coupLegal (inter, Blanc)); go.joue (inter, Blanc); } } void rencontresUCT () { Algorithme a, b; int gains [2] [2] [2]; a.nmoy = 0; a.npere = 0; a.nfils = 0; a.pasDeTranspo = false; a.raveUCT = true; a.constanteRave = 0.0; for (int m = 0; m < 2; m++) for (int p = 0; p < 2; p++) for (int f = 0; f < 2; f++) if ((m != 0) || (p != 0) || (f != 0)) { b.nmoy = m; b.npere = p; b.nfils = f; b.pasDeTranspo = false; b.raveUCT = true; b.constanteRave = 0.0; gains [m] [p] [f] = rencontre (b, a); cout << "gains (" << m << "," << p << "," << f << ")= " << gains [m] [p] [f] << "/" << nbPartiesRencontre << endl; } for (int m = 0; m < 3; m++) for (int p = 0; p < 3; p++) for (int f = 0; f < 3; f++) cout << "gains (" << m << "," << p << "," << f << ")= " << gains [m] [p] [f] << "/" << nbPartiesRencontre << endl; } void rencontresRaveUCT () { Algorithme a, b; a.nmoy = 0; a.npere = 0; a.nfils = 0; a.pasDeTranspo = false; a.constanteRave = 0.0; b.nmoy = 0; b.npere = 0; b.nfils = 0; b.pasDeTranspo = false; b.constanteRave = 0.001; for (float c = 0.0005; c < 0.01; c = 2 * c) { b.constanteRave = c; int g = rencontre (b, a); cout << "gains (" << c << ")= " << g << "/" << nbPartiesRencontre << endl; } } void rencontresRaveRave () { Algorithme a, b; a.nmoy = 0; a.npere = 0; a.nfils = 0; a.pasDeTranspo = false; a.constanteRave = 0.001; b.nmoy = 0; b.npere = 0; b.nfils = 0; b.pasDeTranspo = false; b.constanteRave = 0.001; for (float c = 0.00025; c < 0.01; c = 2 * c) if (c != 0.001) { b.constanteRave = c; int g = rencontre (b, a); cout << "gains (" << c << ")= " << g << "/" << nbPartiesRencontre << endl; } } void rencontresRaveRaveUCT () { Algorithme a, b; a.nmoy = 0; a.npere = 0; a.nfils = 0; a.pasDeTranspo = false; a.raveUCT = false; a.constanteRave = 0.001; b.nmoy = 0; b.npere = 0; b.nfils = 0; b.pasDeTranspo = false; b.raveUCT = true; b.constanteRave = 0.001; int g = rencontre (a, b); cout << "gains Rave = " << g << "/" << nbPartiesRencontre << endl; } int main () { go.initHash (); rencontresUCT (); //rencontresRaveUCT (); //rencontresRaveRaveUCT (); }