Към съдържанието
wannacode

Цялата стратегия

Накратко: Играта свършва с първата от пет проверки, която каже „да“: завладяване, поражение, наука, икономика или срок (точки). Записът е текст „ключ=стойност“ с версия и контролна сума, зареждането проверява всичко, преди да пипне играта, а балансът се мери със стотици партии без екран.

Проблем

Кога свършва играта?

Пет урока строихме части: галактика от семе, дърво на технологиите, флоти и битки, съперници с характер и ход с фази и събития. Но играта още няма край. Ако никой никога не победи, партията не свършва, а ако победата е лоша, играчът играе сто и петдесет хода и разбира, че всичко е било решено в първите двайсет.

Този урок затваря модула с три неща, на които стои всяка цяла игра: победа (кога и как свършва партията), запис (как се продължава утре) и баланс (как знаеш, че играта е честна, без да я изиграеш хиляда пъти на ръка). После играта е тук, цяла.

Ето как свършва минаването, с което се проверява играта на четирите езика. Земната империя проучава Звездната врата на ход 59, а екранът на края показва класирането:

КРАЙ НА ИГРАТА


Земна империя проучи Звездната врата на ход 59.


Класиране (планети, технологии, точки):
A Земна империя              7  13   376
C Съюз Лира                  0   3    38  унищожена
D Академия Вега              7  12   319
B Хегемония Орион            2   8   154




Битки 27, загубени единици 159, колонии 12, технологии 36,
събития 27.


(Enter: изход)

Три неща се виждат в този екран: вид на победата (наука), класиране (планети, технологии, точки на всяка империя; Съюз Лира е унищожена) и статистика на партията. Те идват от три малки функции, които ще видиш тук.

Идеята

Четири победи, един ред от проверки

Играта има четири начина да свърши и още един, за да не виси вечно:

  1. Завладяване: остава жива само една империя.
  2. Поражение: играчът е унищожен (партията свършва, а най-силният от останалите се записва като победител).
  3. Наука: някоя жива империя е проучила Звездната врата, технологията в края на дървото.
  4. Икономика: някоя жива империя е произвела общо 9800.
  5. Срок: дошъл е ход 150 и печели този с най-много точки.

Точките на империя са 10 за планета, 6 за технология, мощта на флота делена на 10 и произведеното делено на 40. Ето истинският код от играта:

// Три победи: завладяване (останала е само една империя), наука (проучена Звездна врата) и
// икономика (натрупано производство ECON_GOAL). Ако никой не победи до MAX_TURNS, печели този
// с най-много точки. Ако играчът е унищожен, играта свършва с поражение.
function empireScore(world, empire) {
  return ownedPlanets(world, empire.id).length * 10 + empire.techs.length * 6 + Math.floor(empirePower(world, empire.id) / 10) + Math.floor(empire.produced / 40);
}


function bestScoring(world) {
  let best = null;
  let bestScore = -1;
  for (const e of world.empires) {
    if (!e.alive) continue;
    const score = empireScore(world, e);
    if (score > bestScore) {
      bestScore = score;
      best = e;
    }
  }
  return best;
}


function checkVictory(world) {
  if (world.victory !== null) return;
  if (world.livingCount() === 1) {
    for (const e of world.empires) {
      if (e.alive) world.victory = { empire: e.id, kind: 'conquest', turn: world.turn };
    }
    return;
  }
  for (const e of world.empires) {
    if (e.human && !e.alive) {
      world.victory = { empire: bestScoring(world).id, kind: 'lost', turn: world.turn };
      return;
    }
  }
  for (const e of world.empires) {
    if (e.alive && knows(e, 'stargate')) {
      world.victory = { empire: e.id, kind: 'science', turn: world.turn };
      return;
    }
  }
  for (const e of world.empires) {
    if (e.alive && e.produced >= ECON_GOAL) {
      world.victory = { empire: e.id, kind: 'economy', turn: world.turn };
      return;
    }
  }
  if (world.turn >= MAX_TURNS) world.victory = { empire: bestScoring(world).id, kind: 'points', turn: world.turn };
}

checkVictory не е една проверка, а пет в точен ред, и първата, която каже „да“, решава. Това е ранен изход: щом знаеш отговора, връщаш. Редът не е случаен. Ако е жива само една империя, няма смисъл да питаш за вратата. Ако играчът е унищожен, партията е загубена, колкото и да е произвел някой. А срокът е последен, защото е най-слабата победа.

Малката програма прави същото със същите правила, но с три империи и без галактика. Империята знае колко точки е:

class Empire {
  constructor(name, human, planets, techs, power, produced) {
    this.name = name;
    this.human = human;
    this.alive = true;
    this.stargate = false;
    this.planets = planets;
    this.techs = techs;
    this.power = power;
    this.produced = produced;
  }


  score() {
    return this.planets * 10 + this.techs * 6 + Math.floor(this.power / 10) + Math.floor(this.produced / 40);
  }
}
class Victory {
  constructor(kind, winner) {
    this.kind = kind;
    this.winner = winner;
  }
}

Проверките са същите пет, в същия ред (ECON_GOAL е 9800, MAX_TURNS е 150):

function checkVictory(empires, turn) {
  const living = empires.filter((e) => e.alive);
  if (living.length === 1) return new Victory("завладяване", living[0].name);
  for (const e of empires) {
    if (e.human && !e.alive) return new Victory("поражение", bestScoring(empires).name);
  }
  for (const e of empires) {
    if (e.alive && e.stargate) return new Victory("наука", e.name);
  }
  for (const e of empires) {
    if (e.alive && e.produced >= ECON_GOAL) return new Victory("икономика", e.name);
  }
  if (turn >= MAX_TURNS) return new Victory("точки", bestScoring(empires).name);
  return null;
}

Седем света, седем отговора. Последните два показват най-важното: унищожен играч дава поражение, а ход 150 без друга победа дава точки.

let game = fresh();
show("ход 40, нищо не е свършило", game, 40);


game = fresh();
game[2].stargate = true;
show("проучена Звездна врата", game, 40);


game = fresh();
game[1].produced = ECON_GOAL;
show("произведено 9800", game, 40);


game = fresh();
game[2].stargate = true;
game[2].produced = ECON_GOAL;
show("и врата, и 9800 в един ход", game, 40);


game = fresh();
game[1].alive = false;
game[2].alive = false;
show("останала е една империя", game, 40);


game = fresh();
game[0].alive = false;
show("играчът е унищожен", game, 40);


show("ход 150, без друга победа", fresh(), 150);
Изход
ход 40, нищо не е свършило: -
проучена Звездна врата: наука (Академия Вега)
произведено 9800: икономика (Хегемония Орион)
и врата, и 9800 в един ход: наука (Академия Вега)
останала е една империя: завладяване (Земна империя)
играчът е унищожен: поражение (Хегемония Орион)
ход 150, без друга победа: точки (Земна империя)

Всеки случай започва от една и съща свежа игра и променя едно-две неща. Четвъртият е хитрият: Академия Вега е проучила Звездната врата и е произвела 9800 в един и същ ход. Печели науката, защото е по-рано в реда.

Виж го

Първото „да“ решава

Четири от тези случаи в движение. Следи кои проверки се изпълняват и кои потъмняват, защото никога не стигат до тях:

function checkVictory(empires, turn) {
  const living = empires.filter((e) => e.alive);
  if (living.length === 1) return new Victory("завладяване", living[0].name);
  for (const e of empires) {
    if (e.human && !e.alive) return new Victory("поражение", bestScoring(empires).name);
  }
  for (const e of empires) {
    if (e.alive && e.stargate) return new Victory("наука", e.name);
  }
  for (const e of empires) {
    if (e.alive && e.produced >= ECON_GOAL) return new Victory("икономика", e.name);
  }
  if (turn >= MAX_TURNS) return new Victory("точки", bestScoring(empires).name);
  return null;
}
Стъпка по стъпка, с думи
  1. След всеки ход светът пита пет въпроса по ред: останала ли е една империя, унищожен ли е играчът, има ли Звездна врата, има ли 9800 произведено, дошъл ли е ход 150. Първото „да“ решава.
  2. Ход 40. И трите империи са живи, никой няма Звездна врата, никой не е стигнал 9800.
  3. Пет пъти „не“. checkVictory връща null и играта върви към следващия ход.
  4. Академия Вега: Звездната врата е проучена и 9800 са произведени, и двете в един и същ ход. Две победи наведнъж.
  5. Третата проверка (наука) казва „да“ и връща веднага. Четвъртата, икономиката, не се стига: редът на проверките решава кой печели.
  6. Хегемония Орион и Академия Вега са унищожени. Остава една империя: Земна империя.
  7. Първата проверка казва „да“: завладяване. Четирите след нея не се изпълняват.
  8. Ход 150: срокът. Никой не е победил по друг начин.
  9. Четири „не“ и накрая срокът: печели този с най-много точки. Земна империя и Хегемония Орион имат равни точки, а равенството го печели по-ранният.

Защо първото „да“ връща веднага? Защото после няма какво да се решава: победата е една на партия. Но има и практическа причина. Ако четвъртата проверка се изпълнеше след третата, функцията трябваше да избира между две победи, а това е ново правило. С ранния изход правилото е редът, и се чете направо от кода: сменяш два реда и си сменил кой печели при равенство на условията.

По-точно, за любопитните

Тук победата се проверява веднъж на ход, след като всичко друго в хода е свършило. Така играчът, който е стигнал 9800, не печели по средата на хода, преди съперниците му да са изиграли своя. В региона turn на канона checkVictory(world) е последната фаза на хода, след производството, науката и събитието.

Играта пази победата в света (world.victory), а не я връща: екранът на края, записът и симулацията четат едно и също място. Така същата проверка върши работа и за играч, и за симулация без екран.

Идеята

Точките: равенство и унищожените

Срокът е най-простото от четирите, но има две скрити правила. Първо, унищожените империи не се броят: империя с много точки, която вече е изчезнала, не бива да печели. Второ, равенството: две империи с еднакви точки трябва да имат предвидим победител, иначе симулацията не е детерминистична.

function bestScoring(empires) {
  let best = null;
  let bestScore = -1;
  for (const e of empires) {
    if (!e.alive) continue;
    const score = e.score();
    if (score > bestScore) {
      bestScore = score;
      best = e;
    }
  }
  return best;
}

bestScore започва от −1, за да може и империя с нула точки да стане водач. Сравнението е строго (>), затова при равенство остава по-ранният. Програмата сравнява четири империи, една унищожена и две с еднакви точки:

const rivals = [
  new Empire("Земна империя", false, 5, 9, 400, 3000),
  new Empire("Хегемония Орион", false, 3, 11, 450, 3120),
  new Empire("Академия Вега", false, 4, 8, 300, 2000),
];
const lyra = new Empire("Съюз Лира", false, 8, 14, 900, 6000);
lyra.alive = false;
rivals.push(lyra);


for (const e of rivals) {
  const note = e.alive ? "" : " (унищожена)";
  console.log(e.name + ": " + e.score() + note);
}
console.log("Най-много точки: " + bestScoring(rivals).name);
Изход
Земна империя: 219
Хегемония Орион: 219
Академия Вега: 168
Съюз Лира: 404 (унищожена)
Най-много точки: Земна империя

Съюз Лира има най-много точки (404), но е унищожена и отпада. Земна империя и Хегемония Орион са на 219, а победител е първата. Деленията са целочислени, както навсякъде в играта (Math.floor в JavaScript), и по тях точките са еднакви на четирите езика.

Идеята

Запис: текст „ключ=стойност“

Играч, който затваря играта на ход 80, иска утре да продължи от ход 80. Записът е четене на света обратно, и има три въпроса: какво се записва, в какъв вид и как се знае, че файлът е цял.

Какво. Не всичко. Галактиката (системи, пътища, видове планети) се прави от семето: същото семе, същата галактика (урок 1 от модула). Затова записът пази само нещата, които се променят: чия е всяка планета, какво е построено, ресурсите, технологиите, флотовете, опашката за строеж, мира и войната и състоянието на генератора, за да продължат заровете от същото място.

Във вид. Текст, ред по ред, ключ=стойност. Може да се прочете с поглед, да се сравни с друг запис, да се поправи на ръка в краен случай и форматът не е вързан за езика на играта: същият текст може да го пише и чете версия на всеки език. Първият ред е заглавие (format=COSMOS), вторият е версия на формата, а последният е контролна сума на всичко над него.

function saveWorld(world) {
  const lines = [];
  const put = (key, value) => lines.push(key + '=' + value);
  put('format', SAVE_FORMAT);
  put('version', SAVE_VERSION);
  put('summary', saveSummary(world));
  put('seed', world.seed);
  put('rng', world.rng.state);
  put('turn', world.turn);
  put('systems', world.systems.length);
  put('planets', world.planets.length);
  put('empires', world.empires.length);
  for (const planet of world.planets) {
    put('planet.' + planet.id, [planet.owner, planet.mines, planet.lab, planet.yard, planet.fort, planet.siege].concat(planet.rich).join(','));
  }
  for (const empire of world.empires) {
    const prefix = 'empire.' + empire.id;
    put(prefix, [empire.def.id, empire.personality.id, empire.alive ? 1 : 0, empire.progress, empire.produced, empire.flare].concat(empire.res).join(','));
    put(prefix + '.researching', empire.researching === '' ? '-' : empire.researching);
    put(prefix + '.techs', joinOrDash(empire.techs));
    put(prefix + '.war', empire.war.join(','));
    put(prefix + '.since', empire.since.join(','));
    put(prefix + '.grudge', empire.grudge.join(','));
    const orders = [];
    for (const order of empire.orders) orders.push([order.from, order.to, order.dest].concat(order.ships).join(':'));
    put(prefix + '.orders', joinOrDash(orders));
  }
  put('fleets', world.fleets.length);
  for (let i = 0; i < world.fleets.length; i++) {
    const fleet = world.fleets[i];
    put('fleet.' + i, [fleet.owner, fleet.systemId].concat(fleet.ships).join(','));
  }
  put('queue', world.queue.length);
  for (let i = 0; i < world.queue.length; i++) {
    const item = world.queue[i];
    put('queue.' + i, [item.owner, item.planetId, item.kind, item.count, item.left].join(','));
  }
  const offers = [];
  for (const offer of world.offers) offers.push(offer.from + ':' + offer.to + ':' + offer.turn);
  put('offers', joinOrDash(offers));
  const s = world.stats;
  put('stats', [s.battles, s.lost, s.colonies, s.techs, s.events].join(','));
  const body = lines.join('\n') + '\n';
  return body + 'checksum=' + checksum(body) + '\n';
}

Малката програма записва същото в малко: семе, ход и три империи (планети, произведено, технологии), с версия и контролна сума в края:

class Game {
  constructor(seed, turn) {
    this.seed = seed;
    this.turn = turn;
    this.empires = [];
  }
}
function save(game) {
  const lines = ["format=COSMOS", "version=" + VERSION];
  lines.push("seed=" + game.seed);
  lines.push("turn=" + game.turn);
  lines.push("empires=" + game.empires.length);
  game.empires.forEach((e, i) => lines.push("empire." + i + "=" + e.join(",")));
  const body = lines.join("\n") + "\n";
  return body + "checksum=" + checksum(body) + "\n";
}
process.stdout.write(save(sample()));
Изход
format=COSMOS
version=1
seed=2026
turn=12
empires=3
empire.0=5,3120,9
empire.1=4,2750,7
empire.2=3,4180,10
checksum=987468948

Ето записа, ред по ред. Версията стои там не за днес, а за утре: когато формата се промени (нов ключ, друг ред), старите записи трябва да се познаят и да се откажат, или да се преобразуват. Без версия един запис от стара версия би се прочел погрешно и тихо.

Идеята

Контролна сума: една промяна и сумата не съвпада

Последният ред на записа е числото, което се получава от всичко над него. При зареждане играта го смята наново и го сравнява със записаното: ако файлът е отрязан, развален или пипнат на ръка, числата са различни. Алгоритъмът е малък:

function checksum(text) {
  let sum = 0;
  for (let i = 0; i < text.length; i++) sum = (sum * 31 + text.charCodeAt(i)) % 1000000007;
  return sum;
}

За всеки знак сумата се умножава по 31, добавя се кодът на знака и се взема остатък по 1000000007. Умножението по 31 е важното: така редът има значение. Сборът на кодовете би дал едно и също число за „ab“ и „ba“, а разменени две цифри в записа са точно онази грешка, която искаме да хванем.

const texts = ["ab", "ba", "turn=12", "turn=21"];
for (const word of texts) {
  console.log(word + " -> " + checksum(word));
}
Изход
ab -> 3105
ba -> 3135
turn=12 -> 408655515
turn=21 -> 408655545

„ab“ е 97 × 31 + 98 = 3105, а „ba“ е 98 × 31 + 97 = 3135. Остатъкът държи числото под милярд, така че да се събира в 32 бита, а JavaScript смята точно до 253, а тук междинният резултат е много по-малък.

function checksum(text) {
  let sum = 0;
  for (let i = 0; i < text.length; i++) {
    sum = (sum * 31 + text.charCodeAt(i))  1000000007;
  }
  return sum;
}
По-точно, за любопитните

Контролната сума хваща грешки, не подправяне. Който знае формулата, променя стойност и преизчислява сумата (програмата по-долу прави точно това с reseal, за да провери другите си защити). За игра, която се пази на твоя диск, това е достатъчно: целта е да не заредиш половин запис. За състезателна класация на сървър е нужно друго: подпис с таен ключ (HMAC), който играчът няма как да смята.

Алгоритъмът е от семейството на „полиномиалните сборове“, същият като hashCode на низ в Java. За истински хешове (SHA-256) има готови библиотеки, но играта пази 32-битова проверка без нищо отвън: тя се чете с поглед и дава еднакви числа на четирите езика.

Идеята

Зареждане, което не вярва на никого

Записът идва от диска, а дискът може да върне всичко: отрязан файл, запис от друга версия на играта, файл, редактиран в бележник. Ако играта го чете с вяра, един лош запис я срива или (по-лошо) я оставя в половин състояние, което се вижда чак на ход 90. Затова зареждането проверява всичко, преди да пипне играта, и казва точно какво не е наред.

class SaveReader {
  constructor(text) {
    this.values = new Map();
    const lines = text.split('\n');
    while (lines.length > 0 && lines[lines.length - 1].length === 0) lines.pop();
    if (lines.length === 0 || lines[0] !== 'format=' + SAVE_FORMAT) throw new SaveError(t('load.badHeader'));
    for (let i = 0; i < lines.length; i++) {
      const eq = lines[i].indexOf('=');
      if (eq <= 0) throw new SaveError(t('load.badLine', { line: i + 1 }));
      this.values.set(lines[i].substring(0, eq), lines[i].substring(eq + 1));
    }
    const version = this.text('version');
    if (version !== String(SAVE_VERSION)) throw new SaveError(t('load.badVersion', { found: version, expected: SAVE_VERSION }));
    const last = lines[lines.length - 1];
    if (!last.startsWith('checksum=')) throw new SaveError(t('load.missing', { key: 'checksum' }));
    const body = lines.slice(0, lines.length - 1).join('\n') + '\n';
    const actual = checksum(body);
    if (parseIntStrict(last.substring(9)) !== actual) {
      throw new SaveError(t('load.badChecksum', { expected: last.substring(9), actual: actual }));
    }
  }


  text(key) {
    if (!this.values.has(key)) throw new SaveError(t('load.missing', { key: key }));
    return this.values.get(key);
  }


  // Число в граници [low, high].
  int(key, low, high) {
    const value = parseIntStrict(this.text(key));
    if (value === null || value < low || value > high) throw new SaveError(t('load.badValue', { key: key }));
    return value;
  }


  // Списък от точно count числа, всяко в границите си.
  ints(key, count, low, high) {
    const parts = this.text(key).split(',');
    if (parts.length !== count) throw new SaveError(t('load.badValue', { key: key }));
    const result = [];
    for (const part of parts) {
      const value = parseIntStrict(part);
      if (value === null || value < low || value > high) throw new SaveError(t('load.badValue', { key: key }));
      result.push(value);
    }
    return result;
  }


  list(key) {
    return splitList(this.text(key));
  }
}

Редът на проверките е важен: заглавие, всеки ред да е ключ=стойност, версия, контролна сума, и чак тогава стойностите. Всяка стойност се чете през int или ints, които проверяват границите (ход от 1 до 150, брой империи от 1 до 9). Малката версия е същата в малко:

class SaveReader {
  constructor(text) {
    this.values = new Map();
    const lines = text.split("\n");
    while (lines.length > 0 && lines[lines.length - 1].length === 0) lines.pop();
    if (lines.length === 0 || lines[0] !== "format=COSMOS") throw new SaveError("това не е запис на Epic Cosmos");
    for (let i = 0; i < lines.length; i++) {
      const eq = lines[i].indexOf("=");
      if (eq <= 0) throw new SaveError("ред " + (i + 1) + " не е „ключ=стойност“");
      this.values.set(lines[i].substring(0, eq), lines[i].substring(eq + 1));
    }
    const version = this.text("version");
    if (version !== String(VERSION)) throw new SaveError("версия " + version + ", а играта чете версия " + VERSION);
    const last = lines[lines.length - 1];
    if (!last.startsWith("checksum=")) throw new SaveError("липсва „" + "checksum" + "“");
    const body = lines.slice(0, lines.length - 1).join("\n") + "\n";
    const actual = checksum(body);
    if (digits(last.substring(9)) !== actual) {
      throw new SaveError("сумата не съвпада (записана " + last.substring(9) + ", изчислена " + actual + "), файлът е пипан");
    }
  }


  text(key) {
    if (!this.values.has(key)) throw new SaveError("липсва „" + key + "“");
    return this.values.get(key);
  }


  integer(key, low, high) {
    const value = digits(this.text(key));
    if (value < low || value > high) throw new SaveError("грешна стойност на „" + key + "“");
    return value;
  }


  numbers(key, count, low, high) {
    const parts = this.text(key).split(",");
    if (parts.length !== count) throw new SaveError("грешна стойност на „" + key + "“");
    const result = [];
    for (const part of parts) {
      const value = digits(part);
      if (value < low || value > high) throw new SaveError("грешна стойност на „" + key + "“");
      result.push(value);
    }
    return result;
  }
}
function load(text) {
  const reader = new SaveReader(text);
  const game = new Game(reader.integer("seed", 0, 99999), reader.integer("turn", 1, MAX_TURNS));
  const count = reader.integer("empires", 1, 9);
  for (let i = 0; i < count; i++) {
    game.empires.push(reader.numbers("empire." + i, 3, 0, 99999));
  }
  return game;
}

load създава нова игра от прочетеното и връща нея, без да пипа текущата. Грешката е изключение SaveError, което носи думите за играча. Този, който вика, я хваща и показва, а играта продължава със стария свят:

function showLoad(label, text) {
  try {
    const game = load(text);
    let produced = 0;
    for (const e of game.empires) produced += e[1];
    console.log(label + ": " + "ход " + game.turn + ", империи " + game.empires.length + ", произведено " + produced);
  } catch (error) {
    if (!(error instanceof SaveError)) throw error;
    console.log(label + ": " + error.message);
  }
}

Шест записа, шест отговора. Два от тях са преправени така, че сумата да мине (затова проверката на границите и на ключовете е нужна), а един е пипнат на ръка и сумата го хваща:

const good = save(sample());
const body = good.substring(0, good.indexOf("checksum="));
showLoad("цял запис", good);
showLoad("пипан на ръка", good.replace("3120", "99999"));
showLoad("друга версия", good.replace("version=1", "version=2"));
showLoad("число извън границите", reseal(body.replace("turn=12", "turn=999")));
showLoad("липсва ред", reseal(body.replace("seed=2026\n", "")));
showLoad("не е запис", "hello");
Изход
цял запис: ход 12, империи 3, произведено 10050
пипан на ръка: сумата не съвпада (записана 987468948, изчислена 410613307), файлът е пипан
друга версия: версия 2, а играта чете версия 1
число извън границите: грешна стойност на „turn“
липсва ред: липсва „seed“
не е запис: това не е запис на Epic Cosmos

Истинската игра прави същото. В слот 3 на минаването стои нарочно развален запис, като ръчно вдигнати ресурси, и играта го отказва, без да падне и без да пипне текущата партия:

> slots
Записи (save N, load N)
Слот 1: Ход 5, Земна империя, 2 планети
Слот 2: празен
Слот 3: Ход 99, без пазач
> load 3
Записът е развален: сумата не съвпада (записана 123456,
изчислена 285754014), файлът е пипан.

Накрая канонът свързва двете: loadWorld хваща SaveError и връща или нов свят, или съобщение. Така екранът никога не вижда счупена игра.

// Връща { world, error }: или новият свят, или съобщение какво не е наред.
function loadWorld(text) {
  try {
    return { world: readWorld(text), error: null };
  } catch (error) {
    if (error instanceof SaveError) return { world: null, error: error.message };
    throw error;
  }
}

Идеята

Баланс: как знаеш, че играта е честна

В играта има три характера на изкуствения интелект: воин (цени нападението), строител (разширяването и строежа) и учен (науката и Звездната врата): характерът е набор от тегла за решенията на империята. Честни ли са? Ако един печели в 80% от партиите, останалите са украса. Да изиграеш хиляда партии на ръка не може, а компютърът го прави за секунди: играе сам срещу себе си.

--simulate=200 пуска двеста партии без екран, изкуствен интелект срещу изкуствен интелект. Всичко, което помага: играта не печата сама (екранът е отделно), случайността е със семе (резултатът е повторяем) и характерите се въртят по местата:

// Балансът: стотици партии без екран, изкуствен интелект срещу изкуствен интелект. Характерите се
// въртят по местата, така че всеки играе еднакво често на всяка позиция; таблицата казва колко
// партии печели всеки характер и как свършват партиите.
const PERSONALITY_IDS = ['warlord', 'builder', 'scholar'];
const VICTORY_KINDS = ['conquest', 'science', 'economy', 'points'];


function simulate(io, games, seed) {
  io.write(t('sim.title', { games: games, seed: seed }) + '\n');
  io.write(t('sim.note1', { turns: MAX_TURNS, goal: ECON_GOAL }) + '\n\n');
  const played = [0, 0, 0];
  const wins = [0, 0, 0];
  const winTurns = [0, 0, 0];
  const kinds = [0, 0, 0, 0];
  let totalTurns = 0;
  let totalSystems = 0;
  for (let i = 0; i < games; i++) {
    const order = [];
    for (let k = 0; k < 4; k++) order.push(PERSONALITY_IDS[(i + k) % 3]);
    const world = newWorld(seed + i, false, order, true);
    totalSystems += world.systems.length;
    while (world.victory === null) runTurn(world);
    for (const empire of world.empires) played[empire.personality.index]++;
    const winner = world.empires[world.victory.empire];
    wins[winner.personality.index]++;
    winTurns[winner.personality.index] += world.victory.turn;
    kinds[VICTORY_KINDS.indexOf(world.victory.kind)]++;
    totalTurns += world.victory.turn;
  }
  io.write(pad(t('sim.personality'), 20) + padLeft(t('sim.played'), 10) + padLeft(t('sim.wins'), 10) + padLeft(t('sim.share'), 8) + padLeft(t('sim.avgTurn'), 12) + '\n');
  for (const personality of PERSONALITIES.values()) {
    const i = personality.index;
    const avg = wins[i] === 0 ? 0 : Math.floor(winTurns[i] / wins[i]);
    io.write(pad(cap(nm(personality)), 20) + padLeft(String(played[i]), 10) + padLeft(String(wins[i]), 10) + padLeft(percent(wins[i], played[i]) + '%', 8) + padLeft(String(avg), 12) + '\n');
  }
  const parts = [];
  for (let k = 0; k < VICTORY_KINDS.length; k++) parts.push(t('victory.' + VICTORY_KINDS[k]) + ' ' + kinds[k]);
  io.write('\n' + t('sim.kinds', { list: parts.join(', ') }) + '\n');
  io.write(t('sim.averages', { turns: Math.floor(totalTurns / games), systems: Math.floor(totalSystems / games) }) + '\n');
}

Въртенето (i + k) % 3 дава на всеки характер всяко място еднакво често. Иначе първото място (при равенство печели по-ранният) би качвало процента на онзи, който е винаги първи.

Малка версия на същата идея. Три характера с еднакъв среден приход, 30 на ход, но различно разсейване: воинът има късмет и пропуски, строителят е равен. Първият до 600 печели:

function playGame(rng, seats) {
  const produced = seats.map(() => 0);
  let turn = 0;
  while (true) {
    turn++;
    for (let k = 0; k < seats.length; k++) {
      const p = seats[k];
      produced[k] += BASE[p] + rng.nextInt(SPREAD[p]);
    }
    for (let k = 0; k < seats.length; k++) {
      if (produced[k] >= GOAL) return [seats[k], turn];
    }
  }
}
const games = 200;
const rng = new Random(7);
const played = [0, 0, 0];
const wins = [0, 0, 0];
const winTurns = [0, 0, 0];
let totalTurns = 0;
for (let i = 0; i < games; i++) {
  const seats = [0, 1, 2, 3].map((k) => (i + k) % 3);
  for (const p of seats) played[p]++;
  const [winner, turn] = playGame(rng, seats);
  wins[winner]++;
  winTurns[winner] += turn;
  totalTurns += turn;
}


const names = ["Воин", "Строител", "Учен"];
console.log("Симулация на баланса: " + games + " партии, семе 7, цел " + GOAL + ".");
console.log();
console.log(pad("Характер", 20) + padLeft("Партии", 10) + padLeft("Победи", 10) + padLeft("Дял", 8) + padLeft("Ср. ход", 12));
for (let i = 0; i < 3; i++) {
  const share = Math.floor((wins[i] * 100) / played[i]);
  const avg = wins[i] === 0 ? 0 : Math.floor(winTurns[i] / wins[i]);
  console.log(pad(names[i], 20) + padLeft(String(played[i]), 10) + padLeft(String(wins[i]), 10) + padLeft(share + "%", 8) + padLeft(String(avg), 12));
}
console.log();
console.log("Среден ход на победата: " + Math.floor(totalTurns / games) + ".");
Изход
Симулация на баланса: 200 партии, семе 7, цел 600.


Характер                Партии    Победи     Дял     Ср. ход
Воин                       267        79     29%          19
Строител                   267        46     17%          20
Учен                       266        75     28%          20


Среден ход на победата: 19.

Средният приход е еднакъв, а строителят печели само 17% срещу 29% при воина и 28% при учения. Защо? В състезание до цел печели този, който в някой момент е най-напред, а не този с най-добра средна. Равният играч никога не е далеч от средата, но и рядко е пръв; разсеяният понякога се откъсва. Затова средното не е достатъчно, и затова се симулира: числото излиза само от играта.

Ето и истинската симулация на Epic Cosmos: двеста партии, семе 7, от simulate.bg.out. Файлът е част от проверката, както и минаването:

ХарактерПартииПобедиДялСреден ход
Воин2236127%47
Строител2205926%57
Учен2138037%56

Победи по вид: завладяване 50, наука 90, икономика 60, точки 0. Средният край на партията е на ход 53, а в галактика има средно 15 системи.

Какво казва таблицата? Ученият печели най-често (37%), воинът и строителят са близо. Точки: 0 от 200. Нито една партия не стига ход 150, защото някой завладява, проучва вратата или произвежда 9800 много по-рано. Срокът е предпазна мрежа, не победа, която изкуственият интелект избира. Това е добър знак: точките са за партия, в която никой не прави нищо.

Балансът се настройва с числата в данните (цена на технология, приход от мина, сила на кораб), като след всяка промяна пускаш симулацията отново. Ако ученият е 37%, пробваш по-скъпа Звездна врата и гледаш как се движи таблицата.

По-точно, за любопитните

Симулацията е и тест на играта. Две двеста партии със същото семе трябва да дадат един и същ файл, и това е проверката: simulate.bg.out се сравнява байт по байт на четирите езика. Ако порт има разлика в един зар, партията тръгва другояче и таблицата се различава. Така една таблица от стотици партии хваща грешки, които минаването от 192 команди не стига.

Пробвай

Играй

Това е цялата игра, JavaScript версията на канона, пусната на страницата. Ти си Земната империя; на картата са системите и пътищата между тях. Три начина да спечелиш: проучи Звездната врата, произведи 9800 или остави на съперниците да се унищожат. Колкото по-рано, толкова по-добре, но срокът е ход 150.

Epic Cosmos: империята

Четири империи, една галактика и сто и петдесет хода. Победата е наука, икономика или завладяване.

Пиши командите на реда отдолу и натисни Enter (help показва всички; празен ред е map). Записите остават в този браузър.
Команди (пиши ги на реда под екрана): help показва всички, map е картата, sys 3 е система 3, tech е дървото на технологиите, r stargate проучва Звездната врата, b mine 2 строи мина на планета 2, ship i 2 1 строи два прехващача, go 1 3 праща флота, emp са империите, а end и wait 3 довършват хода (или до три хода). save 1, load 1 и slots работят със записите: те остават в браузъра.
Пробвай всичко от урока: запиши в слот 1, играй още малко, зареди слот 1 и виж, че си се върнал. Погледни emp: колко точки има всеки. Кара ли те играта да искаш друга цена на технология? Това е балансът.
Идеята
Пусни я на компютъра
Целият файл е тук: [Cosmos.java](/games/cosmos/Cosmos.java), [Cosmos.cs](/games/cosmos/Cosmos.cs), [cosmos.py](/games/cosmos/cosmos.py), [cosmos.js](/games/cosmos/cosmos.js). Сложи го в празна папка и го пусни:
Терминал
node cosmos.js
С --plain печата кадрите като обикновен текст, с --seed=42 галактиката е винаги една и съща, с --lang=en е на английски (има и de и es). Симулацията, която видя, е --simulate=200 (с --seed=7 дава същата таблица). Записите са във файлове в папка saves до играта, а --memory-saves ги държи в паметта.
Трябва Node 20 или по-нов. Файлът е ES модул (import), затова ако Node се оплаче, преименувай го на cosmos.mjs.
Играта е написана четири пъти със същите имена и дава байт по байт един и същ изход на всички езици. Проверката на сайта пуска всяка версия със записаното минаване (192 команди) и със симулацията и ги сравнява с един файл. Затова можеш да четеш играта на езика, който знаеш, и да си сигурен, че е същата.
Идеята
Идеи за продължение
Играта е твоя: имаш целия код. Ето неща, които са точно по мярка и всяко ползва нещо от този урок.
    

  • Дипломатическа победа. Нова проверка в checkVictory: мир с всички живи империи за 20 хода подред. Къде в реда трябва да е? Преди или след икономиката? Сложи я и пусни симулацията, за да видиш колко партии свършват така.
    • 

  • Автозапис. При всяко end записвай в слот 0. Какво става, ако играта падне посред запис? (Подсказка: пиши във временен файл и го преименувай.)
    • 

  • Нова версия на записа. Добави ключ (например difficulty) и вдигни версията на 2. Зареждането да чете и стара версия 1, като слага стойност по подразбиране. Така минава от версия към версия всяка игра.
    • 

  • Запис на партията като команди. Семето и списъкът с командите са цялата партия: това е самото минаване, с което проверяваш играта. Направи replay <файл>.
    • 

  • Баланс по твой вкус. Пусни --simulate=1000 с различни числа за цена на технология и приход и опиши в таблица кое е най-честно.
    • 

  • Друга галактика. Карти от файл вместо от семе, или по-голяма галактика (мащабът на пътищата, графът от първия урок).
    • 

  • Играч срещу играч по мрежа. Командите вече са текст по един ред: ходовете могат да пътуват по сокет. Играта не се променя, променя се само откъде идва редът.
    • 

  • Нов език. Пренеси играта на Go, Rust или Kotlin и пусни същото минаване: изходът трябва да е същият файл.
    • 

Пробвай
Предвиди изхода
Какво печата програмата?
function checksum(text) {
  let sum = 0;
  for (let i = 0; i < text.length; i++) {
    sum = (sum * 31 + text.charCodeAt(i)) % 1000000007;
  }
  return sum;
}


console.log(checksum("ab") + ", " + checksum("ba") + ", " + checksum("abc"));
Отговор
Пробвай
Намери грешката
Колега реши да „поправи“ един ред в bestScoring. Двете империи имат еднакви точки, а програмата печата, че печели по-късната (Хегемония Орион). Правилото е да печели по-ранната. Кой ред е виновен?
Избери реда с грешката.
Упражнение
Контролна сума на всеки ред
Реши задачата в редактора си.
Контролна сума на всеки ред. Програмата чете редове до края на входа и за всеки непразен ред печата реда, интервал и контролната му сума (по формулата от урока, остатък по 1000000007).
С вход turn=12 | turn=13 | seed=2026 | COSMOS (по един на ред) изходът е:
Изход
turn=12 408655515
turn=13 408655516
seed=2026 801283199
COSMOS 993660451
Провери с „ab“ и „ba“: 3105 и 3135. Внимавай с междинния резултат sum * 31: в Python и JavaScript го смятат без препълване, но формулата си остава същата.
Още задачи
    

  • Нова победа. Добави дипломатическа победа към програмата victory (мир с всички живи империи 20 хода подред). Къде в реда да е?
    • 

  • Версия 2. Добави в записа ключ difficulty и вдигни VERSION на 2. Нека load приема и версия 1 със стойност по подразбиране 1. Какво става с контролната сума на стар запис?
    • 

  • Равен баланс. В програмата balance подбери числата на строителя (приход и разсейване) така, че и трите характера да печелят между 30% и 36% от партиите, като средният приход остане 30.
    • 

  • Хващане на втори запис. Какво става, ако в записа два реда имат един и същ ключ? Прочети SaveReader: коя стойност остава? Напиши проверка, която го отказва.
    • 

Тест
Провери се
1. Една империя е проучила Звездната врата и в същия ход е стигнала 9800 произведено. Коя победа се отчита?
2. В края на ход 150 две живи империи имат по 219 точки. Коя печели?
3. Защо контролната сума е sum × 31 + код на знака, а не просто сбор на кодовете?
4. Някой промени ръчно стойност в записа и сам преизчисли контролната сума. Какво прави зареждането?
5. Защо симулацията върти характерите по местата ((i + k) % 3), вместо да ги слага винаги в един и същ ред?
6. Симулацията на Cosmos показва „точки 0“ от 200 партии. Какво значи това?


Създаден от Иво Гергов като част от кампанията на Evo Tech за достъпно обучение по програмиране ·