yarrg/rssearch.c

   1 /*
   2  * Route searcher - recursive iteration over all routes
   3  */
   4 /*
   5  *  This is part of the YARRG website, a tool for assisting
   6  *  players of Yohoho Puzzle Pirates.
   7  *
   8  *  Copyright (C) 2009 Ian Jackson <ijackson@chiark.greenend.org.uk>
   9  *
  10  *  This program is free software: you can redistribute it and/or modify
  11  *  it under the terms of the GNU Affero General Public License as
  12  *  published by the Free Software Foundation, either version 3 of the
  13  *  License, or (at your option) any later version.
  14  *
  15  *  This program is distributed in the hope that it will be useful,
  16  *  but WITHOUT ANY WARRANTY; without even the implied warranty of
  17  *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
  18  *  GNU Affero General Public License for more details.
  19  *
  20  *  You should have received a copy of the GNU Affero General Public License
  21  *  along with this program.  If not, see <http://www.gnu.org/licenses/>.
  22  *
  23  *  Yohoho and Puzzle Pirates are probably trademarks of Three Rings and
  24  *  are used without permission.  This program is not endorsed or
  25  *  sponsored by Three Rings.
  26  */
  27
  28 #include "rscommon.h"
  29
  30 DEBUG_DEFINE_DEBUGF(search);
  31 DEBUG_DEFINE_SOME_DEBUGF(filter,fildebugf);
  32
  33 typedef struct Neighbour {
  34   struct Neighbour *next;
  35   int islandid;
  36   int dist;
  37 } Neighbour;
  38
  39 static Neighbour **neighbours; /* neighbours[islandid]->islandid etc. */
  40 static sqlite3_stmt *ss_neigh;
  41
  42 static int ports[MAX_ROUTELEN];
  43 static int final_isle;
  44
  45 static Neighbour *get_neighbours(int isle) {
  46   Neighbour **np= &neighbours[isle];
  47   Neighbour *head= *np;
  48   if (head) return head;
  49
  50   SQL_BIND(ss_neigh, 1, isle);
  51   while (SQL_STEP(ss_neigh)) {
  52     Neighbour *add;
  53     NEW(add);
  54     add->islandid= sqlite3_column_int(ss_neigh, 0);
  55     add->dist= sqlite3_column_int(ss_neigh, 1);
  56     add->next= head;
  57     head= add;
  58   }
  59   SQL_MUST( sqlite3_reset(ss_neigh) );
  60
  61   *np= head;
  62   return head;
  63 }
  64
  65
  66 static Bucket ***buckets_base[GRANUS];
  67
  68
  69 static double process_route(int nports, int totaldist,
  70                             double overestimate_excepting_tail) {
  71   int i, ap, granui;
  72   int leagues_divisor= totaldist + nports;
  73
  74   ctr_routes_considered++;
  75
  76   int wrong_final= final_isle && ports[nports-1] != final_isle;
  77
  78   debugf("========== ROUTE");
  79   for (i=0; i<nports; i++)
  80     debugf(" %d",ports[i]);
  81   debugf("\n");
  82
  83   double guess[AP]={0,0};
  84   if (nports>=2) {
  85     int pair[2], i;
  86     pair[1]= ports[nports-1];
  87     guess[A]= overestimate_excepting_tail;
  88
  89     for (i=0; i<nports; i++) {
  90       pair[0]= ports[i];
  91       IslandPair *ip= ipair_get_maybe(pair[0], pair[1]);
  92       if (!ip) continue;
  93       if (ip->route_tail_value < 0) {
  94         ctr_subroute_tails_valued++;
  95         ip->route_tail_value= value_route(2, pair, pair[0]!=pair[1]);
  96       }
  97       guess[A] += ip->route_tail_value;
  98     }
  99     guess[P]= guess[A] / leagues_divisor;
 100
 101     if (wrong_final) {
 102       ctr_routes_wrongfinalelim++;
 103       debugf(" WFELIM\n");
 104       return guess[A];
 105     }
 106
 107     for (granui=0; granui<granus; granui++) {
 108       if (guess[A] > highscores[granui][A][0].value ||
 109           guess[P] > highscores[granui][P][0].value)
 110         goto not_quickelim;
 111     }
 112     ctr_routes_quickelim++;
 113     debugf(" QELIM %f %f\n", guess[A], guess[P]);
 114     return guess[A];
 115   not_quickelim:;
 116   }
 117
 118   int finisle= ports[nports-1];
 119   int finarch= isle2arch(finisle);
 120
 121   int midisle= ports[nports/2];
 122   int midarch= route2midarch(ports,nports);
 123
 124   Bucket *buckets[GRANUS];
 125   for (granui=0; granui<granus; granui++) {
 126     Bucket **buckets_fin;
 127     int mid, fin;
 128     switch (granui) {
 129     case 0: fin=finarch; mid=midarch; break;
 130     case 1: fin=finisle; mid=midarch; break;
 131     case 2: fin=finisle; mid=midisle; break;
 132     default: abort();
 133     }
 134     buckets_fin= ONDEMAND(buckets_base[granui][fin], granusz_mid[granui]);
 135     buckets[granui]= ONDEMAND(buckets_fin[mid], 1);
 136   }
 137
 138   if (nports>=2) {
 139     for (granui=0; granui<granus; granui++)
 140       for (ap=0; ap<AP; ap++)
 141         if (guess[ap] > buckets[granui]->prs[ap].value[ap] &&
 142             guess[ap] > highscores[granui][ap][0].value)
 143           goto not_bucketelim;
 144     ctr_routes_bucketelim++;
 145     debugf(" ELIM %f %f\n", guess[A], guess[P]);
 146     return guess[A];
 147   not_bucketelim:
 148     debugf(" COMPUTE %f %f\n", guess[A], guess[P]);
 149   }
 150
 151   ctr_routes_valued++;
 152
 153   double value[AP];
 154   value[A]= value_route(nports, ports, 0);
 155   value[P]= value[A] / leagues_divisor;
 156
 157   if (wrong_final) {
 158     ctr_routes_wrongfinal++;
 159     return value[0];
 160   }
 161
 162   for (granui=granus-1; granui>=0; granui--) {
 163     Bucket *bucket= buckets[granui];
 164
 165     if (value[A] <= bucket->prs[A].value[A] &&
 166         value[P] <= bucket->prs[P].value[P])
 167       continue;
 168
 169     debugf(" SOMEHOW %d BEST\n",granui);
 170
 171     fildebugf("granu %d f%d:%3d mid%d:%3d ",granui,
 172               finarch,finisle,midarch,midisle);
 173
 174     for (ap=0; ap<AP; ap++) {
 175       HighScoreEntry *scores= highscores[granui][ap];
 176       int nscores= nhighscores[granui][ap];
 177
 178       fildebugf("ap=%d %15f", ap, value[ap]);
 179       if (value[ap] < bucket->prs[ap].value[ap]) {
 180         debugf("      ");
 181       } else {
 182         int pos;
 183         ctr_newbests_granu[granui*AP+ap]++;
 184         bucket->prs[ap].length= totaldist;
 185         memcpy(bucket->prs[ap].value, value, sizeof(value));
 186         memcpy(bucket->prs[ap].ports, ports, sizeof(*ports) * nports);
 187         if (nports < MAX_ROUTELEN-1) bucket->prs[ap].ports[nports]= -1;
 188         fildebugf("** ");
 189         for (pos=0; pos < nscores; pos++)
 190           if (scores[pos].bucket == bucket) goto found;
 191         /* not found */
 192         pos= -1;
 193       found:
 194         for (;;) {
 195           pos++;
 196           if (pos >= nscores) break; /* new top */
 197           if (scores[pos].value >= value[ap]) break; /* found spot */
 198           if (pos>0)
 199             scores[pos-1]= scores[pos];
 200         }
 201         pos--;
 202         if (pos>0) {
 203           scores[pos].value= value[ap];
 204           scores[pos].bucket= bucket;
 205           if (granui < granus-1 &&
 206               highscores[granui][A][0].bucket &&
 207               highscores[granui][P][0].bucket) {
 208             /* both absolute and perleague are full at this granularity,
 209              * so we don't care about anything more granular */
 210             fildebugf("\n                STOP-GRANU            ");
 211             granus= granui+1;
 212           }
 213         }
 214         fildebugf("@%2d/%2d ", pos, nscores);
 215       } /* new best */
 216     } /* ap */
 217   } /* granui */
 218
 219   fildebugf(" route");
 220
 221   for (i=0; i<nports; i++)
 222     fildebugf(" %d",ports[i]);
 223   fildebugf("\n");
 224
 225   return value[0];
 226 }
 227
 228 static void recurse(int last_isle,
 229                     int nports /* excluding last_isle */,
 230                     int totaldist /* including last_isle */,
 231                     double last_estimate) {
 232   ports[nports++]= last_isle;
 233   double estimate= process_route(nports, totaldist, last_estimate);
 234   if (nports >= MAX_ROUTELEN) return;
 235
 236   Neighbour *add;
 237   for (add= get_neighbours(last_isle); add; add=add->next) {
 238     int newdist= totaldist + add->dist;
 239     if (newdist > max_dist) continue;
 240
 241     recurse(add->islandid, nports, newdist, estimate);
 242   }
 243 }
 244
 245 void search(int start_isle, int final_isle_spec,
 246             Bucket ****buckets_base_io[GRANUS]) {
 247   int granui;
 248   for (granui=0; granui<GRANUS; granui++)
 249     buckets_base[granui]=
 250       ONDEMAND(*buckets_base_io[granui], granusz_fin[granui]);
 251
 252   final_isle= final_isle_spec <= 0 ? 0 : final_isle_spec;
 253   recurse(start_isle,0,0,1e6);
 254 }
 255
 256 int nhighscores[GRANUS][AP];
 257 HighScoreEntry *highscores[GRANUS][AP];
 258 int granus=GRANUS, granusz_fin[GRANUS], granusz_mid[GRANUS];
 259
 260 int narches;
 261 char **archnames;
 262 int *islandid2arch;
 263
 264 void setup_search(void) {
 265   MCALLOC(neighbours, islandtablesz);
 266
 267   SQL_PREPARE(ss_neigh,
 268               "SELECT biid, dist FROM routes WHERE aiid=?");
 269
 270   int max_narches=
 271     sql_single_int(" SELECT count(*) FROM (\n"
 272                    "  SELECT DISTINCT archipelago\n"
 273                    "   FROM islands\n"
 274                    "  )");
 275   MCALLOC(archnames, max_narches);
 276   MCALLOC_INITEACH(islandid2arch, islandtablesz, *this=-1);
 277
 278   sqlite3_stmt *archs;
 279   SQL_PREPARE(archs,
 280               " SELECT islandid, archipelago\n"
 281               "  FROM islands\n"
 282               "  ORDER BY archipelago");
 283   while (SQL_STEP(archs)) {
 284     int isle= sqlite3_column_int(archs,0);
 285     const char *archname= (const char*)sqlite3_column_text(archs,1);
 286     int arch;
 287     for (arch=0; arch<narches; arch++)
 288       if (!strcmp(archnames[arch], archname)) goto found;
 289     assert(narches < max_narches);
 290     arch= narches++;
 291     archnames[arch]= masprintf("%s",archname);
 292   found:
 293     islandid2arch[isle]= arch;
 294   }
 295   sqlite3_finalize(archs);
 296
 297   granusz_fin[0]=                granusz_mid[0]= narches;
 298   granusz_fin[1]= islandtablesz; granusz_mid[1]= narches;
 299   granusz_fin[2]=                granusz_mid[2]= islandtablesz;
 300 }