#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; 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]; 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); } } 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]; 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; // move = size is pass 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 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) && !go.oeil (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; } void interface () { while (true) { Intersection inter = meilleurCoupUCB (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); } } int main () { go.initHash (); interface (); }