Re: [gnugo-devel] readconnect patch

[Tristan Cazenave]

Gunnar Farneback a écrit :
> 
> Tristan wrote:
> >    A B C D E F G H J K L M N O P Q R S T
> > 19 . . . . . . 7 6 8 9 . . . . . . . . . 19
> > 18 . . . . . . 5 4 X 3 . . . . . . . . . 18
> > 17 . . . . O . X 1 O X . O . . . . . . . 17
> > 16 . . . + . . . . 2 + . . . . . X . . . 16
> > 15 . . . . O . . . . . . O . . . . . . . 15
> > 14 . . . . . . . . . . . . . . . . . . . 14
> > 13 . . . . O . O . O . O . . . . . . . . 13
> >
> > You have to recall the intersections involved in this "ladder"
> > and try them in the global search.
> >
> > In my jargon this ladder is a gi51111 one (5 forced moves of depth
> > one involved (=ip1) moves).
> >
> > The most complex position in the search is this one:
> >
> >    A B C D E F G H J K L M N O P Q R S T
> > 19 . . . . . . . . . . . . . . . . . . . 19
> > 18 . . . . . X O X X O X . . . . . . . . 18
> > 17 . . . . O . X O O X . O . . . . . . . 17
> > 16 . . . + . . . . . + . . . . . X . . . 16
> > 15 . . . . O . . . . . . O . . . . . . . 15
> > 14 . . . . . . . . . . . . . . . . . . . 14
> > 13 . . . . O . O . O . O . . . . . . . . 13
> >
> > If you want more details, maybe a good thing is to read the
> > following paper:
> >
> > http://www.ai.univ-paris8.fr/~cazenave/TheoremProvingInGo.pdf
> >
> > The ip51111 is described in this other one (in french... wait a little
> > for the english version for another game...)
> 
> I don't think I understand this fully. Please correct me where I go
> wrong in the explanation below of why test case connect:2 fails.
> 
> ----
> 
> The test case is for white to try to disconnect a black two space jump
> on the third line. The correct answer is that it can't be
> disconnected, but GNU Go from current CVS says that it is disconnected
> as it stands.

it should say it can be connected and can be disconnected.


> 
> According to the reasoning above this is an ip5 game (or is it ip6?)
> for white.
> 

the number after ip is the minimal number of moves needed to reach
the goal (ie Depth/2).
to connect when playing first, black needs at lesat 6 ip1 moves
(if we consider capturing common adjacent stones as connection).
SO it is an ip611111 game.
But a trace of the recursiveconnect call can be kept to find 
relevant moves for any game.

> In recursive_disconnect() the following code can be found:
> 
>   Moves[0] = 0;
>   if (prevent_connection_one_move(Moves, str1, str2))
>     res = 0;
>   else if (prevent_connection_two_moves(Moves, str1, str2))
>     res = 0;
>   else if (prevent_simple_connection_three_moves(Moves, str1, str2))
>     res = 0;
> 
> The three called functions try, according to the recently added
> comments, to detect ip1, ip2, and (a special case of) ip3 games. If
> all of them return false, the conclusion is that the position is
> disconnected as it stands.
>

yes.
 
> Thus, in order to solve test case 2, it's necessary to add functions
> prevent_simple_connection_four_moves() and
> prevent_simple_connection_five_moves().
> 

yes, the code can detect that it can be connected, then
when connection is proved, it can try the disconnecting moves.
This case is a hard one as I previously said, it requires ip51111
for the first example, and a simple ip6something function for the
second case. However, the second case can be simplified considering
strings linked by protected intersections as connected.


> ----
> 
> If this is correct, I'm starting to get worried about the required
> code complexity, since I don't see why ip5 should be the limit.
> 
> Consider this example, black to disconnect the two white strings on
> the second line:
> 
> |..O......
> |.OOX.....
> |.OXX.....
> |.XOX.....
> |.XOOO....
> |.XOXXX...
> |.OXX.....
> |.OOO.....
> |.........
> 
> If I understand the terminology (and read) correctly this would be an
> ipN game, where N is something large. Black's only chance to
> disconnect is to capture the five white stones in the middle in one of
> the available ladders. The five white stones can of course also be
> captured in a net, but then white can link up along the edge. Even if
> black has a lot of support outside the displayed region, it seems like
> N must be at least 12 or 13. For a ladder crossing the entire board it
> would be much larger.
> 
> Now this isn't entirely similar to test case connect:2, but it becomes
> closer if we change it to
> 
> |..O......
> |.OOX.....
> |.OXX.....
> |.XOX.....
> |.XOO.....
> |.XOXXX...
> |.OXX.....
> |.OOO.....
> |.........
> 
> where white to connect is an ipN game for some big N.
> 
> I guess I'm missing something, or is this just a too difficult
> position?
> 

Capture of common adjacent strings are treated
by calling the capture code in Golois.

You can define gradual games as simple functions,
you do not need to redefine gradual functions
for each game.
here is how it is done in Golois (I am sure it can be
improved), please ask me the unclear meaning of the
french words you have problem with:

int CoupsPossiblesgiATester [NbJeuxGraduels]= 
{NbJeuxGraduels,
 1, // ip1
 2, // ip2
 2, // ip311
 2, // ip4111
 2, // ip51111
 3, // ip321
 2, // ip4121
 3, // ip4211
 3, // ip4221
 3, // ip4311_2_1
 3, // ip4321_2_1
 2, // ip51121
 2, // ip51211
 3, // ip52111
 2, // ip51221
 3, // ip52121
 3}; // ip52221

int JeuipATesterDansg [NbJeuxGraduels]= 
{NbJeuxGraduels,
 ip1, // ip1
 ip1, // ip2
 ip1, // ip311
 ip1, // ip4111
 ip1, // ip51111
 ip2, // ip321
 ip1, // ip4121
 ip2, // ip4211
 ip2, // ip4221
 ip311, // ip4311_2_1
 ip321, // ip4321_2_1
 ip1, // ip51121
 ip1, // ip51211
 ip2, // ip52111
 ip1, // ip51221
 ip2, // ip52121
 ip2}; // ip52221

int JeuGraduelSuivant [NbJeuxGraduels]= 
{NbJeuxGraduels,
 ip1, // ip1
 ip1, // ip2
 ip2, // ip311
 ip311, // ip4111
 ip4111, // ip51111
 ip2, // ip321
 ip321, // ip4121
 ip311, // ip4211
 ip321, // ip4221
 ip321, // ip4311_2_1
 ip321, // ip4321_2_1
 ip4121, // ip51121
 ip4211, // ip51211
 ip4111, // ip52111
 ip4221, // ip51221
 ip4121, // ip52121
 ip4221}; // ip52221

char *ChaineJeuGraduel [NbJeuxGraduels]=
{"0",
 "ip1",     // ip1
 "ip2",     // ip2
 "ip311",   // ip311
 "ip4111",  // ip4111
 "ip51111", // ip51111
 "ip321",   // ip321
 "ip4121",  // ip4121
 "ip4211",  // ip4211
 "ip4221",  // ip4221
 "ip4311_2_1", // ip4311_2_1
 "ip4321_2_1", // ip4321_2_1
 "ip51121", // ip51121
 "ip51211", // ip51211
 "ip52111", // ip52111
 "ip51221", // ip51221
 "ip52121", // ip52121
 "ip52221"}; // ip52221


int giGraduel(int IndiceJeu,int Couleur,TableauCoups &Tab) {
  int i,res=0,TabCoups[MaxCoups];
  TableauCoups TabTemp;

  if (ButAtteignableGenerique(Couleur,Tab))
    return 1;
 
CoupsPossiblesGeneriqueAtteindre(CoupsPossiblesgiATester[IndiceJeu],Couleur,TabCoups);
  for (i=1; ((i<TabCoups[0]+1) && !res); i++) {
    // on reinitialise a chaque fois puisque ce n'est
    // que le coup gagnant qui a besoin d'etre refute
    TabTemp.Init();
    JoueGenerique(TabCoups[i],Couleur,TabTemp);
    //if ((TableauCoups[i]==6)&&(n==3))
    //  fprintf(stderr,"Debug gi\n");
   
res=gGraduel(JeuipATesterDansg[IndiceJeu],JeuGraduelSuivant[IndiceJeu],Couleur,TabTemp);
    //if (res && (n==3))
    //  fprintf(stderr,"Debug gi %d\n",TableauCoups[i]);
    DejoueGenerique();
  }
  if (res)
    Tab.Ajoute(TabTemp);
  return res;
}

// ip1:
// O O O
// O @ O
// + + +
// ip311 :
// O O O
// O @ +
// O + +
// O + +
// - - -
// ip321 :
// O O O O
// O @ @ +
// O + + O
// + + + O
// - - - -
// seules les libertes des chaines a 3 libertes sont a envisager
// pour un jeu ip321 !
// non aussi chaines adjacentes en atari si deux libertes!
// beaucoup moins que la trace du jeu, a expliquer dans papier
//
// ip4121 :
// + + + + +
// O + + + +
// O @ + + +
// O + O O +
// O @ @ + +
// O O O @ +
// + + + @ +
// + + + + +
// - - - - +
// ip4211 :
// pas d'exemple ?
// ip4221 :
// - - - - \
// + + + + |
// O + O + |
// O @ @ + |
// @ O + + |
// + O + + |
// + + + + |
// - - - - /
// ip4311_2_1 :
// - - - - \
// + + + + |
// O O + + |
// O @ @ + |
// @ O + + |
// + O + + |
// + + + + |
// - - - - /

// A faire : reecrire les fonctions pour partager le travail de verifier
le
// premier ip2 pour ip321 et ip4221 par exemple, au lieu de le retenter
a chaque
// fois (TT ?)
// A faire : dans TT globale memoriser les coups ip, ainsi que l'ordre
max essaye
// si tous les jeux ip ont echoués (pour ne pas les retenter si on sait
qu'ils
// ont deja echoués) -> ameliore Iterative Widening
// A faire : si max libertes 3 dans jeu gi -> coups ip sur chaine 3 libs
+ trace
// ce qui compte ce n'est pas l'ordre max parce que ip4311_2_1 a pour
ordre max
// 3 mais seuls les coups sur les chaines 3 libs (ou lib et lib2 de
chaines 2 lib)
// peuvent empecher. Est ce que ce n'est pas deja pris en compte par les
coups
// ip dans la trace ? -> oui, marquer les chaines 3 libs dans la trace
parce
// qu'elles ont une lib de plus que le min pour etre attaquee si Ordre=2
?
// faire des fonction speciales empecher pour chaque jeu graduel ? 
// -> peut etre en utilisant la trace

int ipGraduel(int IndiceJeu,int Couleur,TableauCoups
&TableauCoupsip,TableauCoups &Tab) {
  int i,j,res=0,PasDeJeuxgi;
  TableauCoups TabCoups,TabTemp;
  clock_t ClockInitial=clock();

  TableauCoupsip.Init();
  // bug: si on enleve les lignes en dessous, on joue les
  // coups gagnants pour empecher, mais il ne sont pas
  // detectes comme gagnants
  if (ButAtteignableGenerique(Couleur,Tab))
    return 0;
  // A faire : memoriser la trace du jeu gi pour trouver
  // les coups forces
  if (giGraduel(IndiceJeu,AutreCouleur(Couleur),TabCoups)) {
    res=1;
    // ajouter les coups qui mettent atari si OrdreMax(IndiceJeu)=1
    // ajouter les coups sur chaines 3 libs si OrdreMax(IndiceJeu)=2
    // autrement essayer tous les coups
   
CoupsPossiblesGeneriqueEmpecher(CoupsPossiblesgiATester[IndiceJeu],Couleur,TabTemp);
    TabCoups.Ajoute(TabTemp);
    for (TabCoups.Debut(); TabCoups.Fin(); TabCoups.Suivant())
      if (CoupLegalIncremental (TabCoups.Coup(),Couleur)) {
        JoueGenerique(TabCoups.Coup(),Couleur,Tab);
        PasDeJeuxgi=1;
        //if ((TableauCoups[i]==18)&&(n==2))
        //fprintf(stderr,"Debug ip\n");
        //for (j=1; ((j<n+1) && PasDeJeuxgi); j++)
        if (giGraduel(IndiceJeu,AutreCouleur(Couleur),Tab))
          PasDeJeuxgi=0;
        if (PasDeJeuxgi)
          TableauCoupsip.Append(TabCoups.Coup());
        DejoueGenerique();
      }
  }
  Tab.Ajoute(TabCoups);
  // a ne faire que maintenant pour ne pas compter les coupes directes
ButAtteignable
  NombreAppelsJeuGraduel[IndiceJeu]++;
  TempsJeuGraduel[IndiceJeu]+=clock()-ClockInitial;
  //if (res&&(IndiceJeu==ip4211)) {
  //  fprintf(stderr,"Exemple de jeu ip4211 pour
%c:\n",CarCoul(Couleur));
  //  AfficheDamier(stderr,DamierIncremental);
  //}
  return res;
}

int gGraduel(int JeuipATester,int JeuGraduelSuivant,int
Couleur,TableauCoups &Tab) {
  int i,j,k,res=0,UnJeuxip=0,DesJeuxgi;
  TableauCoups TableauCoupsip,TabTemp;

  //if (n==2)
  //  fprintf(stderr,"Debug ip\n");
  if
(ipGraduel(JeuipATester,AutreCouleur(Couleur),TableauCoupsip,TabTemp)) {
    res=1;
    for (TableauCoupsip.Debut(); ((TableauCoupsip.Fin()) && res);
TableauCoupsip.Suivant()) {
      // bug : i a la place du j => plantage dans UndoIncremental!
      JoueGenerique(TableauCoupsip.Coup(),AutreCouleur(Couleur));
      DesJeuxgi=0;
      if (giGraduel(JeuGraduelSuivant,Couleur,TabTemp))
        DesJeuxgi=1;
      if (!DesJeuxgi)
        res=0;
      DejoueGenerique();
    }
  }
  if (res)
    Tab.Ajoute(TabTemp);
  return res;
}