juegos

search.c (19540B)

---

 /* search.c - bot fuerte: ISMCTS (Monte Carlo sobre conjuntos de informacion).
  *
  * El bot no sabe que cartas de desarrollo tienen los demas ni el orden del
  * mazo. En cada iteracion se "determiniza": se sortean esas cartas entre las
  * que pueden ser (las que no tiene el bot ni se jugaron). Sobre esa version
  * se baja por un arbol unico (single-observer ISMCTS): en cada nodo se generan
  * movidas candidatas para quien tiene que actuar, se cuentan como "disponibles"
  * las que existen en esta determinizacion, se agrega una nueva o se elige con
  * UCB. Despues se juega el resto con el bot heuristico (bot_decide) hasta el
  * final o unos turnos, y el resultado (un puntaje 0..1 por jugador) se propaga
  * para arriba: cada nodo acumula el del jugador que hizo esa movida (max-n).
  *
  * El azar (dados, robos, mazo) se resuelve igual que en auth.c con el Rng de
  * la busqueda. Todo estatico: una busqueda a la vez. */
 #include <string.h>
 #include "catan.h"
 #include "bot_int.h"
 
 #ifndef SEARCH_NODES
 #define SEARCH_NODES 16384    /* hasta 32767 (indices de 16 bits); la Pico usa menos */
 #endif
 
 enum { MAXC = 48, MAXPATH = 96 };
 
 typedef struct {
     Move    m;
     int16_t child, next;      /* primer hijo, siguiente hermano (-1 = ninguno) */
     uint32_t visits, avail;
     float   score;            /* suma de puntajes del jugador m.p */
 } Node;
 
 typedef struct {
     Game    g;
     uint8_t deck[DECK_MAX];   /* se roba de deck[deck_n - 1], como en auth.c */
 } Det;
 
 static Node nodes[SEARCH_NODES];
 static int nnodes;
 
 /* ------------------------------------------------------------ determinizar */
 
 static int devs_held(const Player *pl)
 {
     int n = pl->dev_hidden;
     for (int d = 0; d < NDEV; d++) n += pl->dev[d] + pl->dev_new[d];
     return n;
 }
 
 /* Sortea las cartas ajenas y el mazo con lo que sabe "me". */
 static void determinize(Det *d, const Game *g, int me, Rng *rng)
 {
     d->g = *g;
     Game *s = &d->g;
     int pool[NDEV], knights = 0, held = 0;
     uint8_t cnt[NDEV];
     int total = dev_counts(&s->o, cnt);
     for (int k = 0; k < NDEV; k++) pool[k] = cnt[k];
     for (int p = 0; p < s->o.np; p++) {
         knights += s->p[p].knights;
         held += devs_held(&s->p[p]);
     }
     for (int k = 0; k < NDEV; k++) pool[k] -= s->p[me].dev[k] + s->p[me].dev_new[k];
     pool[D_KNIGHT] -= knights;
     /* progreso ya jugado: se sabe cuantas, no cuales (ni importa mucho) */
     int played = (total - s->deck_n) - held - knights;
     while (played-- > 0) {
         int tot = pool[D_ROADS] + pool[D_PLENTY] + pool[D_MONO];
         if (tot <= 0) break;
         int k = (int)rng_below(rng, (uint32_t)tot);
         int c = k < pool[D_ROADS] ? D_ROADS : k < pool[D_ROADS] + pool[D_PLENTY] ? D_PLENTY : D_MONO;
         pool[c]--;
     }
     uint8_t bag[DECK_MAX];
     int nb = 0;
     for (int k = 0; k < NDEV; k++)
         for (int i = 0; i < pool[k] && nb < DECK_MAX; i++) bag[nb++] = (uint8_t)k;
     for (int i = nb - 1; i > 0; i--) {
         int j = (int)rng_below(rng, (uint32_t)i + 1);
         uint8_t t = bag[i]; bag[i] = bag[j]; bag[j] = t;
     }
     int bi = 0;
     for (int p = 0; p < s->o.np; p++) {
         if (p == me) continue;
         Player *pl = &s->p[p];
         int nold = pl->dev_hidden, nnew = 0;
         for (int k = 0; k < NDEV; k++) { nold += pl->dev[k]; nnew += pl->dev_new[k]; }
         memset(pl->dev, 0, NDEV);
         memset(pl->dev_new, 0, NDEV);
         pl->dev_hidden = 0;
         for (int i = 0; i < nold; i++) pl->dev[bi < nb ? bag[bi++] : D_KNIGHT]++;
         for (int i = 0; i < nnew; i++) pl->dev_new[bi < nb ? bag[bi++] : D_KNIGHT]++;
     }
     for (int i = 0; i < s->deck_n; i++) d->deck[i] = bi < nb ? bag[bi++] : D_KNIGHT;
 }
 
 /* ------------------------------------------------------- aplicar con azar */
 
 static int random_card(Rng *rng, const uint8_t hand[NRES])
 {
     int n = res_total(hand);
     if (!n) return -1;
     int k = (int)rng_below(rng, (uint32_t)n);
     for (int r = 0; r < NRES; r++) {
         if (k < hand[r]) return r;
         k -= hand[r];
     }
     return -1;
 }
 
 /* Como auth_submit, sin validar: m tiene que ser legal. */
 static void sim_apply(Det *d, const Move *mv, Rng *rng)
 {
     Game *g = &d->g;
     Move m = *mv;
     switch (m.type) {
     case M_ROLL:
         m.r[0] = (uint8_t)(1 + rng_below(rng, 6));
         m.r[1] = (uint8_t)(1 + rng_below(rng, 6));
         m.r[2] = m.r[3] = 0;
         if (g->o.variant2p)
             do {
                 m.r[2] = (uint8_t)(1 + rng_below(rng, 6));
                 m.r[3] = (uint8_t)(1 + rng_below(rng, 6));
             } while (m.r[2] + m.r[3] == m.r[0] + m.r[1]);
         break;
     case M_ROBBER:
         m.c = (int16_t)(m.b >= 0 ? random_card(rng, g->p[m.b].res) : -1);
         break;
     case M_BUYDEV:
         m.a = g->deck_n ? d->deck[g->deck_n - 1] : D_KNIGHT;
         break;
     case M_TOKTRADE: {
         int r = game_rival(g, m.p);
         uint8_t hand[NRES] = { 0 };
         if (r >= 0) memcpy(hand, g->p[r].res, NRES);
         m.a = (int16_t)random_card(rng, hand);
         if (m.a >= 0) hand[m.a]--;
         m.b = (int16_t)random_card(rng, hand);
         break;
     }
     default:
         break;
     }
     game_apply(g, &m);
     int p = g->cur;
     if (g->winner < 0 && game_vp(g, p) >= g->o.vp_target) {
         Move w = { .type = M_WIN, .p = (int8_t)p };
         w.a = (int16_t)(g->p[p].dev[D_VP] + g->p[p].dev_new[D_VP]);
         game_apply(g, &w);
     }
 }
 
 /* Quien actua ahora: primero los que responden una oferta y los que descartan. */
 static int actor(const Game *g)
 {
     if (g->phase == PH_OVER || g->winner >= 0) return -1;
     for (int s = 0; s < g->o.np; s++)
         if (s != g->cur && game_needs(g, s)) return s;
     return game_needs(g, g->cur) ? g->cur : -1;
 }
 
 /* ------------------------------------------------------------ candidatas */
 
 typedef struct { Move m[MAXC]; int n; } Cands;
 
 static void add(Cands *c, const Game *g, int p, int type, int a, int b, int cc)
 {
     if (c->n >= MAXC) return;
     Move *m = &c->m[c->n];
     memset(m, 0, sizeof *m);
     m->type = (uint8_t)type; m->p = (int8_t)p;
     m->a = (int16_t)a; m->b = (int16_t)b; m->c = (int16_t)cc;
     if (game_check(g, m) != E_OK) return;
     for (int i = 0; i < c->n; i++)
         if (!memcmp(&c->m[i], m, sizeof *m)) return;
     c->n++;
 }
 
 /* Las k mejores segun score[] (de 0..n-1, >= minv), en orden. */
 static int top_k(const int *score, int n, int minv, int k, int *out)
 {
     int cnt = 0;
     while (cnt < k) {
         int best = -1;
         for (int i = 0; i < n; i++) {
             if (score[i] < minv) continue;
             bool used = false;
             for (int j = 0; j < cnt; j++) if (out[j] == i) used = true;
             if (!used && (best < 0 || score[i] > score[best])) best = i;
         }
         if (best < 0) break;
         out[cnt++] = best;
     }
     return cnt;
 }
 
 static void add_roads(Cands *c, const Game *g, int p)
 {
     int score[NEDGE], pick[3];
     bot_road_scores(g, p, score);
     int n = top_k(score, game_topo(g)->nedge, -999, 3, pick);
     for (int i = 0; i < n; i++) add(c, g, p, M_ROAD, pick[i], 0, 0);
     /* la que mas alarga el camino (pelea por el camino mas largo) */
     int cur = game_road_len(g, p), best = -1, bl = cur;
     if (cur >= 3) {
         Game t = *g;
         for (int e = 0; e < game_topo(g)->nedge; e++) {
             if (!game_can_road(g, p, e)) continue;
             t.eown[e] = (int8_t)p;
             int l = game_road_len(&t, p);
             t.eown[e] = -1;
             if (l > bl) { bl = l; best = e; }
         }
     }
     if (best >= 0) add(c, g, p, M_ROAD, best, 0, 0);
     if (!n && best < 0)       /* ninguna con sentido: alguna legal */
         for (int e = 0; e < game_topo(g)->nedge && c->n < MAXC; e++)
             if (game_can_road(g, p, e)) { add(c, g, p, M_ROAD, e, 0, 0); break; }
 }
 
 /* Navegantes: los 2 barcos que mejor llevan a un lugar (islas nuevas valen mas) */
 static void add_ships(Cands *c, const Game *g, int p)
 {
     if (!game_has_sea(g)) return;
     int score[NEDGE], pick[2];
     bot_ship_scores(g, p, score);
     int n = top_k(score, game_topo(g)->nedge, -999, 2, pick);
     for (int i = 0; i < n; i++) add(c, g, p, M_SHIP, pick[i], 0, 0);
 }
 
 static void add_main(Cands *c, const Game *g, int p)
 {
     const Player *pl = &g->p[p];
     add(c, g, p, M_END, 0, 0, 0);
     if (pl->cities && game_can_afford(g, p, COST_CITY))
         for (int v = 0; v < game_topo(g)->nvert; v++)
             if (game_can_city(g, p, v)) add(c, g, p, M_CITY, v, 0, 0);
     if (pl->settles && game_can_afford(g, p, COST_SETTLE)) {
         int score[NVERT], pick[4];
         for (int v = 0; v < game_topo(g)->nvert; v++)
             score[v] = game_can_settle(g, p, v, false) ? bot_vert_value(g, p, v) : -1;
         int n = top_k(score, game_topo(g)->nvert, 0, 4, pick);
         for (int i = 0; i < n; i++) add(c, g, p, M_SETTLE, pick[i], 0, 0);
     }
     if (pl->roads && game_can_afford(g, p, COST_ROAD)) add_roads(c, g, p);
     if (pl->ships && game_can_afford(g, p, COST_SHIP)) add_ships(c, g, p);
     add(c, g, p, M_BUYDEV, 0, 0, 0);
 
     if (!g->dev_played) {
         add(c, g, p, M_KNIGHT, 0, 0, 0);
         add(c, g, p, M_ROADS, 0, 0, 0);
         if (pl->dev[D_MONO])
             for (int r = 0; r < NRES; r++) {
                 int n = 0;
                 for (int q = 0; q < g->o.np; q++) if (q != p) n += g->p[q].res[r];
                 if (n >= 2) add(c, g, p, M_MONO, r, 0, 0);
             }
         if (pl->dev[D_PLENTY]) {
             static const uint8_t *const COSTS[4] = { COST_SETTLE, COST_CITY, COST_DEV, COST_ROAD };
             for (int k = 0; k < 4; k++) {
                 int a = -1, b = -1;
                 uint8_t have[NRES];
                 memcpy(have, pl->res, NRES);
                 for (int i = 0; i < 2; i++)
                     for (int r = 0; r < NRES; r++)
                         if (have[r] < COSTS[k][r]) {
                             if (a < 0) a = r; else b = r;
                             have[r]++;
                             break;
                         }
                 if (a < 0) continue;
                 if (b < 0) b = a;
                 add(c, g, p, M_PLENTY, a < b ? a : b, a < b ? b : a, 0);
             }
         }
     }
 
     /* banco: por cada recurso que falta para algo (tambien rutas y barcos: con una pila de
      * ladrillos y sin madera, antes no se le ocurria cambiar), dar el que mas sobra */
     static const uint8_t *const COSTS[5] = { COST_SETTLE, COST_CITY, COST_DEV, COST_ROAD, COST_SHIP };
     int ncosts = game_has_sea(g) && pl->ships ? 5 : 4;
     for (int want = 0; want < NRES; want++) {
         bool need = false;
         for (int k = 0; k < ncosts; k++) if (pl->res[want] < COSTS[k][want]) need = true;
         if (!need || !g->bank[want]) continue;
         int give = -1, spare = 0;
         for (int r = 0; r < NRES; r++) {
             if (r == want) continue;
             int s = pl->res[r] - game_bank_ratio(g, p, r);
             if (s >= 0 && (give < 0 || s > spare)) { give = r; spare = s; }
         }
         if (give >= 0) add(c, g, p, M_BANK, give, want, 1);
     }
 
     Move o;
     if (bot_offer(g, p, &o) && c->n < MAXC) c->m[c->n++] = o;
 
     if (g->o.variant2p) {
         add(c, g, p, M_TOKTRADE, 0, 0, 0);
         if (bot_robber_on_me(g, p)) add(c, g, p, M_TOKROBBER, 0, 0, 0);
     }
 }
 
 static void gen(const Game *g, int p, Rng *rng, Cands *c)
 {
     const Topo *t = game_topo(g);
     c->n = 0;
     if (g->offer.active && g->phase == PH_MAIN) {
         if (p != g->offer.from) {
             add(c, g, p, M_ACCEPT, 0, 0, 0);
             add(c, g, p, M_REJECT, 0, 0, 0);
             Move k;
             if (bot_counter(g, p, &k) && c->n < MAXC) c->m[c->n++] = k;
         } else {
             for (int q = 0; q < g->o.np; q++)
                 if (g->offer.resp[q] == 1 || g->offer.resp[q] == 2) add(c, g, p, M_CONFIRM, q, 0, 0);
             add(c, g, p, M_CANCEL, 0, 0, 0);
         }
         return;
     }
     switch (g->phase) {
     case PH_SETUP:
         if (g->setup_sub == 0) {
             int score[NVERT], pick[6];
             for (int v = 0; v < game_topo(g)->nvert; v++)
                 score[v] = game_can_settle(g, p, v, true) ? bot_vert_value(g, p, v) : -1;
             int n = top_k(score, game_topo(g)->nvert, 0, 6, pick);
             for (int i = 0; i < n; i++) add(c, g, p, M_SETTLE, pick[i], 0, 0);
         } else {
             for (int k = 0; k < 3; k++) {
                 int e = t->vert_edge[g->setup_v][k];
                 if (e >= 0) { add(c, g, p, M_ROAD, e, 0, 0); add(c, g, p, M_SHIP, e, 0, 0); }
             }
         }
         return;
     case PH_ROLL:
         add(c, g, p, M_ROLL, 0, 0, 0);
         add(c, g, p, M_KNIGHT, 0, 0, 0);
         if (g->o.variant2p && bot_robber_on_me(g, p)) add(c, g, p, M_TOKROBBER, 0, 0, 0);
         return;
     case PH_ROBBER: {
         int score[NHEX], pick[4];
         for (int h = 0; h < game_topo(g)->nhex; h++)
             score[h] = game_can_robber(g, p, h) ? bot_robber_score(g, p, h) : -1000000;
         int n = top_k(score, game_topo(g)->nhex, -999999, 4, pick);
         for (int i = 0; i < n; i++) add(c, g, p, M_ROBBER, pick[i], bot_robber_victim(g, p, pick[i]), 0);
         return;
     }
     case PH_ROADBUILD:
         add_roads(c, g, p);
         add_ships(c, g, p);
         if (!c->n) add(c, g, p, M_END, 0, 0, 0);
         return;
     case PH_MAIN: case PH_PAIRED:            /* add() descarta lo que no vale en la pareja */
         add_main(c, g, p);
         return;
     default:
         break;
     }
     /* descartes, devoluciones, neutrales: lo que diga la heuristica */
     Move m;
     if (bot_decide(g, p, rng, &m) && game_check(g, &m) == E_OK) c->m[c->n++] = m;
 }
 
 /* -------------------------------------------------------------- evaluacion */
 
 static float eval_player(const Game *g, int p)
 {
     const Player *pl = &g->p[p];
     int prod[NRES];
     int pips = bot_pips(g, p, prod), kinds = 0;
     for (int r = 0; r < NRES; r++) if (prod[r]) kinds++;
     int hand = hand_size(g, p);
     int devs = 0;
     for (int d = 0; d < NDEV; d++) if (d != D_VP) devs += pl->dev[d] + pl->dev_new[d];
     return (float)game_vp(g, p) + 0.05f * (float)pips + 0.1f * (float)kinds
          + 0.06f * (float)(hand > 7 ? 7 : hand) + 0.2f * (float)devs + 0.15f * (float)pl->knights;
 }
 
 /* Puntaje 0..1 por jugador: 1 al ganador; si no termino, softmax de eval. */
 static void reward(const Game *g, float out[MAXP])
 {
     int np = g->o.np;
     for (int p = 0; p < MAXP; p++) out[p] = 0;
     if (g->winner >= 0) { out[g->winner] = 1; return; }
     float e[MAXP], mx = -1e9f, sum = 0;
     for (int p = 0; p < np; p++) {
         if (g->p[p].neutral) { e[p] = -1e9f; continue; }
         e[p] = eval_player(g, p);
         if (e[p] > mx) mx = e[p];
     }
     for (int p = 0; p < np; p++) {
         if (g->p[p].neutral) continue;
         /* exp(x) aproximado sin libm: (1 + x/16)^16 */
         float x = 1.0f + (e[p] - mx) * 1.2f / 16.0f;
         if (x < 0) x = 0;
         for (int i = 0; i < 4; i++) x *= x;
         out[p] = x;
         sum += x;
     }
     if (sum > 0) for (int p = 0; p < np; p++) out[p] /= sum;
 }
 
 static void rollout(Det *d, Rng *rng, int horizon)
 {
     Game *g = &d->g;
     int end_turn = g->turn + horizon;
     for (int step = 0; step < 4000; step++) {
         if (horizon && g->turn >= end_turn) return;
         if (g->turn > 600) return;
         int s = actor(g);
         if (s < 0) return;
         Move m;
         if (!bot_decide(g, s, rng, &m) || game_check(g, &m) != E_OK) {
             memset(&m, 0, sizeof m);
             m.p = (int8_t)s;
             m.type = g->offer.active && s != g->offer.from ? M_REJECT : M_END;
             if (game_check(g, &m) != E_OK) return;
         }
         sim_apply(d, &m, rng);
     }
 }
 
 /* -------------------------------------------------------------------- arbol */
 
 static int new_node(int parent, const Move *m)
 {
     if (nnodes >= SEARCH_NODES) return -1;
     int i = nnodes++;
     Node *n = &nodes[i];
     n->m = *m;
     n->child = -1;
     n->visits = n->avail = 0;
     n->score = 0;
     if (parent >= 0) {
         n->next = nodes[parent].child;
         nodes[parent].child = (int16_t)i;
     } else {
         n->next = -1;
     }
     return i;
 }
 
 static int find_child(int parent, const Move *m)
 {
     for (int c = nodes[parent].child; c >= 0; c = nodes[c].next)
         if (!memcmp(&nodes[c].m, m, sizeof *m)) return c;
     return -1;
 }
 
 /* sqrt sin libm (Newton, alcanza para UCB) */
 static float fsqrt(float x)
 {
     if (x <= 0) return 0;
     float r = x > 1 ? x : 1;
     for (int i = 0; i < 12; i++) r = 0.5f * (r + x / r);
     return r;
 }
 
 /* ln aproximado sin libm */
 static float flog(float x)
 {
     int e = 0;
     while (x > 2) { x *= 0.5f; e++; }
     float y = (x - 1) / (x + 1), y2 = y * y;
     return 0.6931472f * (float)e + 2 * y * (1 + y2 / 3 + y2 * y2 / 5);
 }
 
 bool search_decide(const Game *g, int seat, Rng *rng, const SearchCfg *cfg, Move *out)
 {
     static Det root, d;
     static Cands c;
     if (!game_needs(g, seat)) return false;
     if (bot_offer_pending(g, seat)) return false;       /* esperando respuestas a su oferta */
 
     /* lo trivial o sin ramas utiles lo resuelve la heuristica */
     gen(g, seat, rng, &c);
     if (cfg->iters <= 0 || c.n <= 1) return bot_decide(g, seat, rng, out);
 
     nnodes = 0;
     Move none;
     memset(&none, 0, sizeof none);
     new_node(-1, &none);
     uint32_t t0 = cfg->now_ms ? cfg->now_ms() : 0;
 
     for (int it = 0; it < cfg->iters; it++) {
         if (cfg->now_ms && cfg->max_ms && (it & 15) == 15 && cfg->now_ms() - t0 >= cfg->max_ms) break;
         determinize(&root, g, seat, rng);
         d = root;
         int path[MAXPATH], plen = 0, node = 0;
         bool first = true;
         while (plen < MAXPATH) {
             int a = first ? seat : actor(&d.g);
             first = false;
             if (a < 0) break;
             gen(&d.g, a, rng, &c);
             if (c.n == 0) break;
             if (c.n == 1) { sim_apply(&d, &c.m[0], rng); continue; }
 
             int unexp[MAXC], nu = 0, kids[MAXC], nk = 0;
             for (int i = 0; i < c.n; i++) {
                 int ch = find_child(node, &c.m[i]);
                 if (ch >= 0) { nodes[ch].avail++; kids[nk++] = ch; }
                 else unexp[nu++] = i;
             }
             if (nu) {
                 const Move *m = &c.m[unexp[rng_below(rng, (uint32_t)nu)]];
                 int ch = new_node(node, m);
                 sim_apply(&d, m, rng);
                 if (ch >= 0) { nodes[ch].avail++; path[plen++] = ch; }
                 break;
             }
             if (!nk) break;
             int best = kids[0];
             float bs = -1;
             for (int i = 0; i < nk; i++) {
                 const Node *n = &nodes[kids[i]];
                 float u = n->score / (float)n->visits
                         + cfg->c_ucb * fsqrt(flog((float)n->avail) / (float)n->visits);
                 if (u > bs) { bs = u; best = kids[i]; }
             }
             sim_apply(&d, &nodes[best].m, rng);
             path[plen++] = best;
             node = best;
         }
         rollout(&d, rng, cfg->horizon);
         float r[MAXP];
         reward(&d.g, r);
         for (int i = 0; i < plen; i++) {
             Node *n = &nodes[path[i]];
             n->visits++;
             n->score += r[n->m.p];
         }
     }
 
     int best = -1;
     for (int ch = nodes[0].child; ch >= 0; ch = nodes[ch].next)
         if (best < 0 || nodes[ch].visits > nodes[best].visits) best = ch;
     if (best < 0) return bot_decide(g, seat, rng, out);
     *out = nodes[best].m;
     return game_check(g, out) == E_OK || bot_decide(g, seat, rng, out);
 }