El Farol Bar Problem

// El Farol Bar Problem — Brian Arthur 1994.
// 100 agents decide each week whether to go to the bar. The bar is fun
// iff fewer than 60 show up. Each agent keeps a personal stable of
// predictors and uses the one with the best running track record.
// No predictor can be globally correct: if it forecasts <60 and so does
// everyone else's, all go and the forecast is wrong; if it forecasts
// >=60 and so do others, all stay and the forecast is wrong.
// Click to inject a 10-week wave that biases agents toward "go".

const N_AGENTS = 100;
const CAPACITY = 60;
const HISTORY_MAX = 200;       // weeks of attendance we keep on screen
const TRACK_WINDOW = 40;       // weeks of error each predictor scores over
const TICK_PERIOD = 0.20;      // seconds between weeks

// Predictor library. Each predictor is a function of the attendance
// history (most-recent-last) returning a forecast in [0, N_AGENTS].
const PREDICTORS = [
  {
    name: "last week",
    color: "#ff6b6b",
    fn: (h) => h.length ? h[h.length - 1] : CAPACITY,
  },
  {
    name: "avg last 4",
    color: "#ffd166",
    fn: (h) => {
      const n = Math.min(4, h.length);
      if (!n) return CAPACITY;
      let s = 0;
      for (let i = h.length - n; i < h.length; i++) s += h[i];
      return s / n;
    },
  },
  {
    name: "avg last 12",
    color: "#06d6a0",
    fn: (h) => {
      const n = Math.min(12, h.length);
      if (!n) return CAPACITY;
      let s = 0;
      for (let i = h.length - n; i < h.length; i++) s += h[i];
      return s / n;
    },
  },
  {
    name: "trend (last2)",
    color: "#118ab2",
    fn: (h) => {
      if (h.length < 2) return CAPACITY;
      const a = h[h.length - 2], b = h[h.length - 1];
      return Math.max(0, Math.min(N_AGENTS, b + (b - a)));
    },
  },
  {
    name: "mirror (N-last)",
    color: "#9b5de5",
    fn: (h) => h.length ? N_AGENTS - h[h.length - 1] : CAPACITY,
  },
  {
    name: "always 60",
    color: "#bdb2ff",
    fn: () => 60,
  },
  {
    name: "always 40",
    color: "#a0c4ff",
    fn: () => 40,
  },
];
const P = PREDICTORS.length;

let agents;                    // { active: int, errs: Float32Array(P), buf: Float32Array(P*TRACK_WINDOW), bufPos: Int32Array(P), bufN: Int32Array(P) }
let history;                   // Float32Array(HISTORY_MAX), ring
let histHead = 0, histCount = 0;
let weeksTotal = 0;
let perturb = 0;               // weeks remaining of forced "go" bias
let accumT = 0;
let W = 0, H = 0;
let usageCounts;               // Int32Array(P)

function pushHistory(v) {
  history[histHead] = v;
  histHead = (histHead + 1) % HISTORY_MAX;
  if (histCount < HISTORY_MAX) histCount++;
}

function historyArray() {
  // Returns the history as a plain ordered array (oldest first).
  const out = new Array(histCount);
  const start = (histHead - histCount + HISTORY_MAX) % HISTORY_MAX;
  for (let i = 0; i < histCount; i++) {
    out[i] = history[(start + i) % HISTORY_MAX];
  }
  return out;
}

function pickPredictorsFor(agentIdx) {
  // Each agent gets 3 random predictors (with replacement allowed but
  // we'll dedupe so the choice is meaningful). Stored as the indices it
  // tracks; non-tracked predictors get a high constant error so they're
  // never chosen.
  const chosen = new Set();
  while (chosen.size < 3) chosen.add((Math.random() * P) | 0);
  return Array.from(chosen);
}

function init({ width, height }) {
  W = width;
  H = height;

  history = new Float32Array(HISTORY_MAX);
  histHead = 0;
  histCount = 0;
  weeksTotal = 0;
  perturb = 0;
  accumT = 0;

  // Seed history with a few random pre-weeks so predictors have signal.
  for (let i = 0; i < 8; i++) {
    pushHistory(30 + Math.random() * 60);
  }

  agents = new Array(N_AGENTS);
  for (let i = 0; i < N_AGENTS; i++) {
    const tracked = pickPredictorsFor(i);
    const errs = new Float32Array(P);
    const bufN = new Int32Array(P);
    const bufPos = new Int32Array(P);
    const buf = new Float32Array(P * TRACK_WINDOW);
    for (let p = 0; p < P; p++) {
      if (tracked.indexOf(p) === -1) errs[p] = Infinity;
    }
    agents[i] = {
      active: tracked[(Math.random() * tracked.length) | 0],
      tracked,
      errs,
      buf,
      bufPos,
      bufN,
    };
  }

  usageCounts = new Int32Array(P);
  recountUsage();
}

function recountUsage() {
  usageCounts.fill(0);
  for (let i = 0; i < N_AGENTS; i++) usageCounts[agents[i].active]++;
}

function stepWeek() {
  const hist = historyArray();

  // 1. Each predictor produces a forecast given the current history.
  const forecasts = new Float32Array(P);
  for (let p = 0; p < P; p++) forecasts[p] = PREDICTORS[p].fn(hist);

  // 2. Each agent chooses its best-track-record (tracked) predictor and
  // decides to go iff that predictor says attendance < CAPACITY.
  let attendance = 0;
  for (let i = 0; i < N_AGENTS; i++) {
    const ag = agents[i];

    // Choose lowest-error tracked predictor (already encoded via errs).
    let bestP = ag.tracked[0];
    let bestE = ag.errs[bestP];
    for (let j = 1; j < ag.tracked.length; j++) {
      const p = ag.tracked[j];
      if (ag.errs[p] < bestE) {
        bestE = ag.errs[p];
        bestP = p;
      }
    }
    ag.active = bestP;

    let willGo = forecasts[bestP] < CAPACITY;
    if (perturb > 0) {
      // During a perturbation, 70% of "stay" decisions flip to "go".
      if (!willGo && Math.random() < 0.7) willGo = true;
    }
    if (willGo) attendance++;
  }

  if (perturb > 0) perturb--;

  pushHistory(attendance);
  weeksTotal++;

  // 3. Update each predictor's track record with this week's realized
  // attendance. We keep a rolling window of squared errors.
  for (let i = 0; i < N_AGENTS; i++) {
    const ag = agents[i];
    for (let j = 0; j < ag.tracked.length; j++) {
      const p = ag.tracked[j];
      const f = forecasts[p];
      const err = (f - attendance) * (f - attendance);
      const idx = p * TRACK_WINDOW + ag.bufPos[p];
      if (ag.bufN[p] < TRACK_WINDOW) {
        ag.buf[idx] = err;
        ag.bufN[p]++;
      } else {
        ag.buf[idx] = err;
      }
      ag.bufPos[p] = (ag.bufPos[p] + 1) % TRACK_WINDOW;

      // Mean of buffer.
      let s = 0;
      const n = ag.bufN[p];
      const base = p * TRACK_WINDOW;
      for (let k = 0; k < n; k++) s += ag.buf[base + k];
      ag.errs[p] = s / Math.max(1, n);
    }
  }

  recountUsage();
}

// -------- Rendering --------

function drawTopPanel(ctx, x, y, w, h) {
  // Background.
  ctx.fillStyle = "#0a0f1a";
  ctx.fillRect(x, y, w, h);

  // Axes.
  const padL = 38, padR = 8, padT = 18, padB = 18;
  const plotX = x + padL, plotY = y + padT;
  const plotW = w - padL - padR, plotH = h - padT - padB;

  ctx.strokeStyle = "rgba(255,255,255,0.15)";
  ctx.lineWidth = 1;
  ctx.beginPath();
  ctx.moveTo(plotX, plotY);
  ctx.lineTo(plotX, plotY + plotH);
  ctx.lineTo(plotX + plotW, plotY + plotH);
  ctx.stroke();

  // y-ticks.
  ctx.fillStyle = "rgba(255,255,255,0.55)";
  ctx.font = "10px monospace";
  ctx.textBaseline = "middle";
  ctx.textAlign = "right";
  const yTicks = [0, 25, 50, 75, 100];
  for (const t of yTicks) {
    const py = plotY + plotH - (t / N_AGENTS) * plotH;
    ctx.fillText(String(t), plotX - 4, py);
    ctx.strokeStyle = "rgba(255,255,255,0.06)";
    ctx.beginPath();
    ctx.moveTo(plotX, py);
    ctx.lineTo(plotX + plotW, py);
    ctx.stroke();
  }

  // Capacity dashed line at 60.
  const capY = plotY + plotH - (CAPACITY / N_AGENTS) * plotH;
  ctx.strokeStyle = "rgba(255,209,102,0.7)";
  ctx.setLineDash([5, 5]);
  ctx.lineWidth = 1.25;
  ctx.beginPath();
  ctx.moveTo(plotX, capY);
  ctx.lineTo(plotX + plotW, capY);
  ctx.stroke();
  ctx.setLineDash([]);

  ctx.fillStyle = "rgba(255,209,102,0.9)";
  ctx.textAlign = "left";
  ctx.fillText("capacity = 60", plotX + 6, capY - 8);

  // Attendance series.
  if (histCount > 1) {
    ctx.lineWidth = 1.5;
    ctx.strokeStyle = "#06d6a0";
    ctx.beginPath();
    const start = (histHead - histCount + HISTORY_MAX) % HISTORY_MAX;
    for (let i = 0; i < histCount; i++) {
      const v = history[(start + i) % HISTORY_MAX];
      const px = plotX + (i / (HISTORY_MAX - 1)) * plotW;
      const py = plotY + plotH - (v / N_AGENTS) * plotH;
      if (i === 0) ctx.moveTo(px, py); else ctx.lineTo(px, py);
    }
    ctx.stroke();

    // Latest point.
    const lastV = history[(histHead - 1 + HISTORY_MAX) % HISTORY_MAX];
    const lastPx = plotX + ((histCount - 1) / (HISTORY_MAX - 1)) * plotW;
    const lastPy = plotY + plotH - (lastV / N_AGENTS) * plotH;
    ctx.fillStyle = lastV < CAPACITY ? "#06d6a0" : "#ff6b6b";
    ctx.beginPath();
    ctx.arc(lastPx, lastPy, 3, 0, Math.PI * 2);
    ctx.fill();

    ctx.fillStyle = "rgba(255,255,255,0.85)";
    ctx.font = "11px monospace";
    ctx.textAlign = "right";
    ctx.fillText(
      `week ${weeksTotal}  attendance ${lastV.toFixed(0)}${perturb > 0 ? "  PERTURB " + perturb : ""}`,
      plotX + plotW,
      plotY - 6,
    );
  }

  // Title.
  ctx.fillStyle = "rgba(255,255,255,0.85)";
  ctx.font = "11px monospace";
  ctx.textAlign = "left";
  ctx.textBaseline = "top";
  ctx.fillText("attendance per week (N=100, capacity 60)", plotX, y + 2);
}

function drawBottomPanel(ctx, x, y, w, h) {
  ctx.fillStyle = "#0a0f1a";
  ctx.fillRect(x, y, w, h);

  const padL = 38, padR = 8, padT = 18, padB = 30;
  const plotX = x + padL, plotY = y + padT;
  const plotW = w - padL - padR, plotH = h - padT - padB;

  // Title.
  ctx.fillStyle = "rgba(255,255,255,0.85)";
  ctx.font = "11px monospace";
  ctx.textAlign = "left";
  ctx.textBaseline = "top";
  ctx.fillText("agents currently using each predictor", plotX, y + 2);

  // Bars.
  const slot = plotW / P;
  const barW = Math.max(8, slot * 0.7);
  ctx.font = "10px monospace";
  ctx.textBaseline = "middle";

  // y-axis tick at N_AGENTS.
  ctx.strokeStyle = "rgba(255,255,255,0.06)";
  for (let v = 20; v <= 100; v += 20) {
    const py = plotY + plotH - (v / N_AGENTS) * plotH;
    ctx.beginPath();
    ctx.moveTo(plotX, py);
    ctx.lineTo(plotX + plotW, py);
    ctx.stroke();
    ctx.fillStyle = "rgba(255,255,255,0.4)";
    ctx.textAlign = "right";
    ctx.fillText(String(v), plotX - 4, py);
  }

  for (let p = 0; p < P; p++) {
    const c = usageCounts[p];
    const bx = plotX + slot * p + (slot - barW) * 0.5;
    const bh = (c / N_AGENTS) * plotH;
    const by = plotY + plotH - bh;

    ctx.fillStyle = PREDICTORS[p].color;
    ctx.globalAlpha = 0.85;
    ctx.fillRect(bx, by, barW, bh);
    ctx.globalAlpha = 1;

    // Count on top.
    ctx.fillStyle = "rgba(255,255,255,0.9)";
    ctx.textAlign = "center";
    ctx.textBaseline = "bottom";
    ctx.fillText(String(c), bx + barW * 0.5, by - 2);

    // Label below — short version, rotated would be nicer but keep simple.
    ctx.fillStyle = "rgba(255,255,255,0.7)";
    ctx.textBaseline = "top";
    const label = PREDICTORS[p].name;
    ctx.fillText(label, bx + barW * 0.5, plotY + plotH + 4);
  }
}

function tick({ ctx, dt, width, height, input }) {
  if (width !== W || height !== H) {
    W = width;
    H = height;
  }

  // Handle click → perturbation.
  const clicks = input.consumeClicks();
  if (clicks > 0 && perturb === 0) {
    perturb = 10;
  }

  // Step the model on a fixed cadence so the line plot reads as a clock.
  accumT += dt;
  while (accumT >= TICK_PERIOD) {
    accumT -= TICK_PERIOD;
    stepWeek();
  }

  // Layout: top panel ~58%, bottom ~42%, 8px gutter.
  ctx.fillStyle = "#05060a";
  ctx.fillRect(0, 0, W, H);

  const gutter = 8;
  const topH = Math.floor((H - gutter) * 0.58);
  const botH = H - gutter - topH;

  drawTopPanel(ctx, 0, 0, W, topH);
  drawBottomPanel(ctx, 0, topH + gutter, W, botH);
}