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

Проблем

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

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

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

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

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

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

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


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

(Enter: изход)

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

Идеята

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

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

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

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

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

static Empire bestScoring(World world) {
    Empire best = null;
    int bestScore = -1;
    for (Empire e : world.empires) {
        if (!e.alive) continue;
        int score = empireScore(world, e);
        if (score > bestScore) {
            bestScore = score;
            best = e;
        }
    }
    return best;
}

static void checkVictory(World world) {
    if (world.victory != null) return;
    if (world.livingCount() == 1) {
        for (Empire e : world.empires) {
            if (e.alive) world.victory = new Victory(e.id, "conquest", world.turn);
        }
        return;
    }
    for (Empire e : world.empires) {
        if (e.human && !e.alive) {
            world.victory = new Victory(bestScoring(world).id, "lost", world.turn);
            return;
        }
    }
    for (Empire e : world.empires) {
        if (e.alive && knows(e, "stargate")) {
            world.victory = new Victory(e.id, "science", world.turn);
            return;
        }
    }
    for (Empire e : world.empires) {
        if (e.alive && e.produced >= ECON_GOAL) {
            world.victory = new Victory(e.id, "economy", world.turn);
            return;
        }
    }
    if (world.turn >= MAX_TURNS) world.victory = new Victory(bestScoring(world).id, "points", world.turn);
}

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

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

class Empire {
    final String name;
    final boolean human;
    boolean alive = true;
    boolean stargate = false;
    int planets;
    int techs;
    int power;
    int produced;

    Empire(String name, boolean human, int planets, int techs, int power, int produced) {
        this.name = name;
        this.human = human;
        this.planets = planets;
        this.techs = techs;
        this.power = power;
        this.produced = produced;
    }

    int score() {
        return planets * 10 + techs * 6 + power / 10 + produced / 40;
    }
}

class Victory {
    final String kind;
    final String winner;

    Victory(String kind, String winner) {
        this.kind = kind;
        this.winner = winner;
    }
}

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

static Victory checkVictory(List<Empire> empires, int turn) {
    int living = 0;
    Empire last = null;
    for (Empire e : empires) {
        if (e.alive) {
            living++;
            last = e;
        }
    }
    if (living == 1) return new Victory("завладяване", last.name);
    for (Empire e : empires) {
        if (e.human && !e.alive) return new Victory("поражение", bestScoring(empires).name);
    }
    for (Empire e : empires) {
        if (e.alive && e.stargate) return new Victory("наука", e.name);
    }
    for (Empire e : 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 без друга победа дава точки.

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

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

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

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

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

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

show("ход 150, без друга победа", fresh(), 150);

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

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

Виж го

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

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

static Victory checkVictory(List<Empire> empires, int turn) {
    int living = 0;
    Empire last = null;
    for (Empire e : empires) {
        if (e.alive) {
            living++;
            last = e;
        }
    }
    if (living == 1) return new Victory("завладяване", last.name);
    for (Empire e : empires) {
        if (e.human && !e.alive) return new Victory("поражение", bestScoring(empires).name);
    }
    for (Empire e : empires) {
        if (e.alive && e.stargate) return new Victory("наука", e.name);
    }
    for (Empire e : 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;
}

Стъпка по стъпка, с думи

След всеки ход светът пита пет въпроса по ред: останала ли е една империя, унищожен ли е играчът, има ли Звездна врата, има ли 9800 произведено, дошъл ли е ход 150. Първото „да“ решава.
Ход 40. И трите империи са живи, никой няма Звездна врата, никой не е стигнал 9800.
Пет пъти „не“. checkVictory връща null и играта върви към следващия ход.
Академия Вега: Звездната врата е проучена и 9800 са произведени, и двете в един и същ ход. Две победи наведнъж.
Третата проверка (наука) казва „да“ и връща веднага. Четвъртата, икономиката, не се стига: редът на проверките решава кой печели.
Хегемония Орион и Академия Вега са унищожени. Остава една империя: Земна империя.
Първата проверка казва „да“: завладяване. Четирите след нея не се изпълняват.
Ход 150: срокът. Никой не е победил по друг начин.
Четири „не“ и накрая срокът: печели този с най-много точки. Земна империя и Хегемония Орион имат равни точки, а равенството го печели по-ранният.

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

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

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

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

Идеята

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

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

static Empire bestScoring(List<Empire> empires) {
    Empire best = null;
    int bestScore = -1;
    for (Empire e : empires) {
        if (!e.alive) continue;
        int score = e.score();
        if (score > bestScore) {
            bestScore = score;
            best = e;
        }
    }
    return best;
}

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

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

for (Empire e : rivals) {
    String note = e.alive ? "" : " (унищожена)";
    System.out.println(e.name + ": " + e.score() + note);
}
System.out.println("Най-много точки: " + bestScoring(rivals).name);

Земна империя: 219
Хегемония Орион: 219
Академия Вега: 168
Съюз Лира: 404 (унищожена)
Най-много точки: Земна империя

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

Идеята

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

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

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

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

static String saveWorld(World world) {
    List<String> lines = new ArrayList<>();
    put(lines, "format", SAVE_FORMAT);
    put(lines, "version", SAVE_VERSION);
    put(lines, "summary", saveSummary(world));
    put(lines, "seed", world.seed);
    put(lines, "rng", world.rng.state);
    put(lines, "turn", world.turn);
    put(lines, "systems", world.systems.size());
    put(lines, "planets", world.planets.size());
    put(lines, "empires", world.empires.size());
    for (Planet planet : world.planets) {
        put(lines, "planet." + planet.id, joinInts(concat(new int[] {planet.owner, planet.mines, planet.lab, planet.yard, planet.fort, planet.siege}, planet.rich), ","));
    }
    for (Empire empire : world.empires) {
        String prefix = "empire." + empire.id;
        put(lines, prefix, empire.def.id + "," + empire.personality.id + "," + (empire.alive ? 1 : 0) + "," + empire.progress + "," + empire.produced + "," + empire.flare + "," + joinInts(empire.res, ","));
        put(lines, prefix + ".researching", empire.researching.equals("") ? "-" : empire.researching);
        put(lines, prefix + ".techs", joinOrDash(empire.techs));
        put(lines, prefix + ".war", joinInts(empire.war, ","));
        put(lines, prefix + ".since", joinInts(empire.since, ","));
        put(lines, prefix + ".grudge", joinInts(empire.grudge, ","));
        List<String> orders = new ArrayList<>();
        for (Order order : empire.orders) orders.add(joinInts(concat(new int[] {order.from, order.to, order.dest}, order.ships), ":"));
        put(lines, prefix + ".orders", joinOrDash(orders));
    }
    put(lines, "fleets", world.fleets.size());
    for (int i = 0; i < world.fleets.size(); i++) {
        Fleet fleet = world.fleets.get(i);
        put(lines, "fleet." + i, joinInts(concat(new int[] {fleet.owner, fleet.systemId}, fleet.ships), ","));
    }
    put(lines, "queue", world.queue.size());
    for (int i = 0; i < world.queue.size(); i++) {
        QueueItem item = world.queue.get(i);
        put(lines, "queue." + i, joinInts(new int[] {item.owner, item.planetId, item.kind, item.count, item.left}, ","));
    }
    List<String> offers = new ArrayList<>();
    for (Offer offer : world.offers) offers.add(offer.from + ":" + offer.to + ":" + offer.turn);
    put(lines, "offers", joinOrDash(offers));
    Stats s = world.stats;
    put(lines, "stats", joinInts(new int[] {s.battles, s.lost, s.colonies, s.techs, s.events}, ","));
    String body = String.join("\n", lines) + "\n";
    return body + "checksum=" + checksum(body) + "\n";
}

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

class Game {
    final int seed;
    int turn;
    final List<int[]> empires = new ArrayList<>();

    Game(int seed, int turn) {
        this.seed = seed;
        this.turn = turn;
    }
}

static String save(Game game) {
    List<String> lines = new ArrayList<>();
    lines.add("format=COSMOS");
    lines.add("version=" + VERSION);
    lines.add("seed=" + game.seed);
    lines.add("turn=" + game.turn);
    lines.add("empires=" + game.empires.size());
    for (int i = 0; i < game.empires.size(); i++) {
        int[] e = game.empires.get(i);
        lines.add("empire." + i + "=" + e[0] + "," + e[1] + "," + e[2]);
    }
    String body = String.join("\n", lines) + "\n";
    return body + "checksum=" + checksum(body) + "\n";
}

System.out.print(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

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

Идеята

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

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

// Сумата минава милиард: sum * 31 не се побира в int, затова е long.
static long checksum(String text) {
    long sum = 0;
    for (int i = 0; i < text.length(); i++) sum = (sum * 31 + text.charAt(i)) % 1000000007L;
    return sum;
}

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

String[] texts = {"ab", "ba", "turn=12", "turn=21"};
for (String word : texts) {
    System.out.println(word + " -> " + checksum(word));
}

ab -> 3105
ba -> 3135
turn=12 -> 408655515
turn=21 -> 408655545

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

static long checksum(String text) {
    long sum = 0;
    for (int i = 0; i < text.length(); i++) {
        sum = (sum * 31 + text.charAt(i))  1000000007;
    }
    return sum;
}

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

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

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

Идеята

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

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

static class SaveReader {
    Map<String, String> values = new LinkedHashMap<>();

    SaveReader(String text) {
        List<String> lines = split(text, "\n");
        while (lines.size() > 0 && lines.get(lines.size() - 1).length() == 0) lines.remove(lines.size() - 1);
        if (lines.size() == 0 || !lines.get(0).equals("format=" + SAVE_FORMAT)) throw new SaveError(t("load.badHeader"));
        for (int i = 0; i < lines.size(); i++) {
            int eq = lines.get(i).indexOf('=');
            if (eq <= 0) throw new SaveError(t("load.badLine", "line", i + 1));
            this.values.put(lines.get(i).substring(0, eq), lines.get(i).substring(eq + 1));
        }
        String version = this.text("version");
        if (!version.equals(String.valueOf(SAVE_VERSION))) throw new SaveError(t("load.badVersion", "found", version, "expected", SAVE_VERSION));
        String last = lines.get(lines.size() - 1);
        if (!last.startsWith("checksum=")) throw new SaveError(t("load.missing", "key", "checksum"));
        String body = String.join("\n", lines.subList(0, lines.size() - 1)) + "\n";
        long actual = checksum(body);
        Long given = parseIntStrict(last.substring(9));
        if (given == null || given != actual) {
            throw new SaveError(t("load.badChecksum", "expected", last.substring(9), "actual", actual));
        }
    }

    String text(String key) {
        if (!this.values.containsKey(key)) throw new SaveError(t("load.missing", "key", key));
        return this.values.get(key);
    }

    // Число в граници [low, high]. Връща long: семето стига до 4294967295.
    long integer(String key, long low, long high) {
        Long value = parseIntStrict(this.text(key));
        if (value == null || value < low || value > high) throw new SaveError(t("load.badValue", "key", key));
        return value;
    }

    // Списък от точно count числа, всяко в границите си.
    int[] ints(String key, int count, int low, int high) {
        List<String> parts = split(this.text(key), ",");
        if (parts.size() != count) throw new SaveError(t("load.badValue", "key", key));
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            Long value = parseIntStrict(parts.get(i));
            if (value == null || value < low || value > high) throw new SaveError(t("load.badValue", "key", key));
            result[i] = (int) (long) value;
        }
        return result;
    }

    List<String> list(String key) {
        return splitList(this.text(key));
    }
}

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

В Java и C# функциите са в класа на програмата (Main и Program), а SaveReader е отделен клас и ги вика с името на класа. В канона всичко е във вътрешни класове на един клас и името не е нужно.

class SaveReader {
    final Map<String, String> values = new HashMap<>();

    SaveReader(String text) {
        List<String> lines = new ArrayList<>(Arrays.asList(text.split("\n", -1)));
        while (!lines.isEmpty() && lines.get(lines.size() - 1).isEmpty()) lines.remove(lines.size() - 1);
        if (lines.isEmpty() || !lines.get(0).equals("format=COSMOS")) throw new SaveError("това не е запис на Epic Cosmos");
        for (int i = 0; i < lines.size(); i++) {
            int eq = lines.get(i).indexOf('=');
            if (eq <= 0) throw new SaveError("ред " + (i + 1) + " не е „ключ=стойност“");
            values.put(lines.get(i).substring(0, eq), lines.get(i).substring(eq + 1));
        }
        String version = text("version");
        if (!version.equals(String.valueOf(Main.VERSION))) throw new SaveError("версия " + version + ", а играта чете версия " + Main.VERSION);
        String last = lines.get(lines.size() - 1);
        if (!last.startsWith("checksum=")) throw new SaveError("липсва „" + "checksum" + "“");
        String body = String.join("\n", lines.subList(0, lines.size() - 1)) + "\n";
        long actual = Main.checksum(body);
        if (Main.digits(last.substring(9)) != actual) {
            throw new SaveError("сумата не съвпада (записана " + last.substring(9) + ", изчислена " + actual + "), файлът е пипан");
        }
    }

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

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

    int[] numbers(String key, int count, int low, int high) {
        String[] parts = text(key).split(",", -1);
        if (parts.length != count) throw new SaveError("грешна стойност на „" + key + "“");
        int[] result = new int[count];
        for (int i = 0; i < count; i++) {
            long value = Main.digits(parts[i]);
            if (value < low || value > high) throw new SaveError("грешна стойност на „" + key + "“");
            result[i] = (int) value;
        }
        return result;
    }
}

static Game load(String text) {
    SaveReader reader = new SaveReader(text);
    Game game = new Game(reader.integer("seed", 0, 99999), reader.integer("turn", 1, MAX_TURNS));
    int count = reader.integer("empires", 1, 9);
    for (int i = 0; i < count; i++) {
        game.empires.add(reader.numbers("empire." + i, 3, 0, 99999));
    }
    return game;
}

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

static void showLoad(String label, String text) {
    try {
        Game game = load(text);
        int produced = 0;
        for (int[] e : game.empires) produced += e[1];
        System.out.println(label + ": " + "ход " + game.turn + ", империи " + game.empires.size() + ", произведено " + produced);
    } catch (SaveError error) {
        System.out.println(label + ": " + error.getMessage());
    }
}

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

String good = save(sample());
String 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 }: или новият свят, или съобщение какво не е наред.
static LoadResult loadWorld(String text) {
    try {
        return new LoadResult(readWorld(text), null);
    } catch (SaveError error) {
        return new LoadResult(null, error.getMessage());
    }
}

Идеята

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

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

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

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

static void simulate(Io io, int games, long seed) {
    io.write(t("sim.title", "games", games, "seed", seed) + "\n");
    io.write(t("sim.note1", "turns", MAX_TURNS, "goal", ECON_GOAL) + "\n\n");
    int[] played = {0, 0, 0};
    int[] wins = {0, 0, 0};
    int[] winTurns = {0, 0, 0};
    int[] kinds = {0, 0, 0, 0};
    int totalTurns = 0;
    int totalSystems = 0;
    for (int i = 0; i < games; i++) {
        String[] order = new String[4];
        for (int k = 0; k < 4; k++) order[k] = PERSONALITY_IDS[(i + k) % 3];
        World world = newWorld(seed + i, false, order, true);
        totalSystems += world.systems.size();
        while (world.victory == null) runTurn(world);
        for (Empire empire : world.empires) played[empire.personality.index]++;
        Empire winner = world.empires.get(world.victory.empire);
        wins[winner.personality.index]++;
        winTurns[winner.personality.index] += world.victory.turn;
        for (int k = 0; k < VICTORY_KINDS.length; k++) {
            if (VICTORY_KINDS[k].equals(world.victory.kind)) {
                kinds[k]++;
                break;
            }
        }
        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 (Personality personality : PERSONALITIES.values()) {
        int i = personality.index;
        int avg = wins[i] == 0 ? 0 : winTurns[i] / wins[i];
        io.write(pad(cap(nm(personality)), 20) + padLeft(String.valueOf(played[i]), 10) + padLeft(String.valueOf(wins[i]), 10) + padLeft(percent(wins[i], played[i]) + "%", 8) + padLeft(String.valueOf(avg), 12) + "\n");
    }
    List<String> parts = new ArrayList<>();
    for (int k = 0; k < VICTORY_KINDS.length; k++) parts.add(t("victory." + VICTORY_KINDS[k]) + " " + kinds[k]);
    io.write("\n" + t("sim.kinds", "list", String.join(", ", parts)) + "\n");
    io.write(t("sim.averages", "turns", totalTurns / games, "systems", totalSystems / games) + "\n");
}

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

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

static int[] playGame(Random rng, int[] seats) {
    int[] produced = new int[seats.length];
    int turn = 0;
    while (true) {
        turn++;
        for (int k = 0; k < seats.length; k++) {
            int p = seats[k];
            produced[k] += BASE[p] + rng.nextInt(SPREAD[p]);
        }
        for (int k = 0; k < seats.length; k++) {
            if (produced[k] >= GOAL) return new int[] {seats[k], turn};
        }
    }
}

int games = 200;
Random rng = new Random(7);
int[] played = new int[3];
int[] wins = new int[3];
int[] winTurns = new int[3];
int totalTurns = 0;
for (int i = 0; i < games; i++) {
    int[] seats = new int[4];
    for (int k = 0; k < 4; k++) {
        seats[k] = (i + k) % 3;
        played[seats[k]]++;
    }
    int[] result = playGame(rng, seats);
    wins[result[0]]++;
    winTurns[result[0]] += result[1];
    totalTurns += result[1];
}

String[] names = {"Воин", "Строител", "Учен"};
System.out.println("Симулация на баланса: " + games + " партии, семе 7, цел " + GOAL + ".");
System.out.println();
System.out.println(pad("Характер", 20) + padLeft("Партии", 10) + padLeft("Победи", 10) + padLeft("Дял", 8) + padLeft("Ср. ход", 12));
for (int i = 0; i < 3; i++) {
    int share = wins[i] * 100 / played[i];
    int avg = wins[i] == 0 ? 0 : winTurns[i] / wins[i];
    System.out.println(pad(names[i], 20) + padLeft("" + played[i], 10) + padLeft("" + wins[i], 10) + padLeft(share + "%", 8) + padLeft("" + avg, 12));
}
System.out.println();
System.out.println("Среден ход на победата: " + 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. Файлът е част от проверката, както и минаването:

Характер	Партии	Победи	Дял	Среден ход
Воин	223	61	27%	47
Строител	220	59	26%	57
Учен	213	80	37%	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). Сложи го в празна папка и го пусни:

java Cosmos.java

С --plain печата кадрите като обикновен текст, с --seed=42 галактиката е винаги една и съща, с --lang=en е на английски (има и de и es). Симулацията, която видя, е --simulate=200 (с --seed=7 дава същата таблица). Записите са във файлове в папка saves до играта, а --memory-saves ги държи в паметта.

Java 21 пуска файл с много класове направо, без javac.

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

Идеята

Идеи за продължение

Играта е твоя: имаш целия код. Ето неща, които са точно по мярка и всяко ползва нещо от този урок.

Дипломатическа победа. Нова проверка в checkVictory: мир с всички живи империи за 20 хода подред. Къде в реда трябва да е? Преди или след икономиката? Сложи я и пусни симулацията, за да видиш колко партии свършват така.
Автозапис. При всяко end записвай в слот 0. Какво става, ако играта падне посред запис? (Подсказка: пиши във временен файл и го преименувай.)
Нова версия на записа. Добави ключ (например difficulty) и вдигни версията на 2. Зареждането да чете и стара версия 1, като слага стойност по подразбиране. Така минава от версия към версия всяка игра.
Запис на партията като команди. Семето и списъкът с командите са цялата партия: това е самото минаване, с което проверяваш играта. Направи replay <файл>.
Баланс по твой вкус. Пусни --simulate=1000 с различни числа за цена на технология и приход и опиши в таблица кое е най-честно.
Друга галактика. Карти от файл вместо от семе, или по-голяма галактика (мащабът на пътищата, графът от първия урок).
Играч срещу играч по мрежа. Командите вече са текст по един ред: ходовете могат да пътуват по сокет. Играта не се променя, променя се само откъде идва редът.
Нов език. Пренеси играта на Go, Rust или Kotlin и пусни същото минаване: изходът трябва да е същият файл.

Пробвай

Предвиди изхода

Какво печата програмата?

static long checksum(String text) {
    long sum = 0;
    for (int i = 0; i < text.length(); i++) {
        sum = (sum * 31 + text.charAt(i)) % 1000000007;
    }
    return sum;
}

System.out.println(checksum("ab") + ", " + checksum("ba") + ", " + checksum("abc"));

Отговор

195, 195, 294

3105, 3135, 96354

3105, 3105, 96354

Пробвай

Намери грешката

Колега реши да „поправи“ един ред в 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: в Java и C# трябва да е long, иначе препълва за по-дълъг ред.

Още задачи

Нова победа. Добави дипломатическа победа към програмата victory (мир с всички живи империи 20 хода подред). Къде в реда да е?
Версия 2. Добави в записа ключ difficulty и вдигни VERSION на 2. Нека load приема и версия 1 със стойност по подразбиране 1. Какво става с контролната сума на стар запис?
Равен баланс. В програмата balance подбери числата на строителя (приход и разсейване) така, че и трите характера да печелят между 30% и 36% от партиите, като средният приход остане 30.
Хващане на втори запис. Какво става, ако в записа два реда имат един и същ ключ? Прочети SaveReader: коя стойност остава? Напиши проверка, която го отказва.

Тест

Провери се

1. Една империя е проучила Звездната врата и в същия ход е стигнала 9800 произведено. Коя победа се отчита?Икономиката: 9800 е точно число, а вратата е само технологияИ двете, и играта показва две победиНауката: проверката ѝ е преди икономиката в checkVictory и първото „да“ връща веднага

2. В края на ход 150 две живи империи имат по 219 точки. Коя печели?По-ранната в списъка: сравнението е строго (score > bestScore), равният не измества водачаНикоя, играта продължаваПо-късната: последният равен е най-близо до края

bestScoring пази най-добрия до момента и го сменя само ако новият е строго по-добър. Равенството остава при по-ранния. С >= щеше да е обратното (задачата „Намери грешката“). Унищожените империи не се броят изобщо: пропускат се с if (!alive) continue.

3. Защо контролната сума е sum × 31 + код на знака, а не просто сбор на кодовете?Защото умножението е по-бързо от събиранетоЗащото 31 е най-малкото число, което не препълваТака редът има значение: „ab“ и „ba“ дават различни суми

4. Някой промени ръчно стойност в записа и сам преизчисли контролната сума. Какво прави зареждането?Отказва го винаги: ръчно променен файл е недопустимСумата минава, но проверката на границите на всяка стойност още може да откаже записаПриема го: щом сумата съвпада, записът е верен

5. Защо симулацията върти характерите по местата ((i + k) % 3), вместо да ги слага винаги в един и същ ред?За да е по-бърза симулациятаЗа да се играят повече партииПри равенство печели по-ранният, затова място първо не бива да е винаги на един характер

6. Симулацията на Cosmos показва „точки 0“ от 200 партии. Какво значи това?Точките са счупени и никога не се смятатИзкуственият интелект не знае да събира точкиНикоя партия не стига ход 150: срокът е предпазна мрежа, а не начин, по който изкуственият интелект печели

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

Бисквитки