Scrap book: new AI system core

demo.zig

// How to write your very own MMO --- an introduction to multiplayer game design
// Copyright © 2023 Simon A. Nielsen Knights <levyelara@protonmail.com>
// SPDX-License-Identifier: AGPL-3.0-only
//
// This program is free software: you can redistribute it and/or modify
// it under the terms of the GNU Affero General Public License as
// published by the Free Software Foundation, either version 3 of the
// License, or (at your option) any later version.
//
// This program is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
// GNU Affero General Public License for more details.
//
// You should have received a copy of the GNU Affero General Public License
// along with this program.  If not, see <https://www.gnu.org/licenses/>.

const std = @import("std");
const io = std.io;
const mem = std.mem;
const math = std.math;
const assert = std.debug.assert;

// An example of where "machine learning" is useful within the context of games
// using four charatcters that battle to the death while adjust their behaviour
// based on their guess of what the other will do.
//
// The implementation uses a markov chain to predict what the next move will be
// and acts accordingly based on the prediction along with other data points
// which the character has access to. This allows the charater to change it's
// behaviour when faced with repetitive actions instead of continuing with an
// ineffective strategy (e.g switch to light attacks if the target keeps on
// evading heavy attacks). The markov chain is then used by the infinite-axis
// utility system which uses it to decide which action is the most useful
// given the current situation. The infinite-axis system itself is capable of
// replace all uses of state machines, behaviour trees, and forward planners
// along with driving animation, audio, and other systems which need to be
// aware of the current situation to activate without much change to the code.
//
// This is a simplification of the real system used in the game without access
// to embeddings, influence mapping, optimization, and many other things that
// add further detail to character behaviour.

const Flags = packed struct {
    dry_run: bool = false,
    iterations: bool = false,
    log_actions: bool = false,
    render_response_activations: bool = false,
    render_response_curves: bool = false,
    render_markov_chain_heatmap: bool = false,
    dump_markov_chain_csv: bool = false,

    pub const help = crlf(
        \\Usage: levy-ai-demo [OPTION...]
        \\
        \\ --help
        \\   Display this help message.
        \\
        \\ --dry-run
        \\   Don't execute the battle simulation.
        \\
        \\ --iterations=<integer>
        \\   Number of iterations to run.
        \\
        \\ --log-actions
        \\   Log actions for all characters.
        \\
        \\ --render-response-activations=<name>
        \\   Render a graph for each response activation (verbose).
        \\
        \\ --render-response-curves=<name>
        \\   Render graphs for each of the response curves from the configuration
        \\   of the named character (default: alice).
        \\
        \\ --render-markov-chain-heatmap=<name>,<name>
        \\   (requires ANSI) Render a heatmap of the probability matrix.
        \\
        \\ --dump-markov-chain-csv=<name>,<name>  Dump the probability matrix to CSV.
        \\
        \\ Copyright © 2023 Simon A. Nielsen Knights <levyelara@protonmail.com>
        \\ This work is licensed under AGPL-3.0-only, see https://www.gnu.org/licenses/agpl-3.0.html
        \\
    );

    pub const Int = @Type(.{ .Int = .{ .signedness = .unsigned, .bits = @bitSizeOf(Flags) } });
    pub const Tag = std.meta.FieldEnum(Flags);
    pub const Values = struct {
        name: Name = .alice,
        target: Name = .eve,
        iterations: u8 = 10,
    };

    pub fn bit(tag: Tag) Int {
        return @as(Int, 1) << @intFromEnum(tag);
    }

    pub const map = std.ComptimeStringMap(Tag, .{
        .{ "--dry-run", .dry_run },
        .{ "--iterations", .iterations },
        .{ "--log-actions", .log_actions },
        .{ "--render-response-activations", .render_response_activations },
        .{ "--render-response-curves", .render_response_curves },
        .{ "--render-markov-chain-heatmap", .render_markov_chain_heatmap },
        .{ "--dump-markov-chain-csv", .dump_markov_chain_csv },
    });

    fn crlf(comptime text: []const u8) []const u8 {
        return comptime blk: {
            @setEvalBranchQuota(3000);
            var string: []const u8 = "";
            var it = mem.tokenize(u8, text, "\n");
            while (it.next()) |line| string = string ++ line ++ "\r\n";
            break :blk string;
        };
    }
};

const upper_half_block = "▀";
const lower_half_block = "▄";
const fill_block = "█";

pub fn main() !void {
    var instance: std.heap.GeneralPurposeAllocator(.{}) = .{};
    defer assert(instance.deinit() == .ok);

    var stdout_buffer = std.io.bufferedWriter(std.io.getStdErr().writer());
    var stderr_buffer = std.io.bufferedWriter(std.io.getStdErr().writer());

    const stdout = stdout_buffer.writer();
    const stderr = stderr_buffer.writer();

    const gpa = instance.allocator();

    const args = try std.process.argsAlloc(gpa);
    defer std.process.argsFree(gpa, args);

    const flags: Flags, const values: Flags.Values = blk: {
        var options: Flags.Int = 0;
        var values: Flags.Values = .{};

        for (args[1..]) |arg| {
            if (mem.eql(u8, arg, "--help")) {
                try stderr.writeAll(Flags.help);
                options = Flags.bit(.dry_run);
                break;
            }

            const split = mem.indexOfScalar(u8, arg, '=') orelse arg.len;
            const name = arg[0..split];
            const flag = Flags.map.get(name) orelse {
                return error.UnknownFlag;
            };
            const bit = Flags.bit(flag);

            if (options & bit != 0) return error.DuplicateFlag;

            switch (flag) {
                .iterations => {
                    values.iterations = try std.fmt.parseInt(u8, arg[split + 1 ..], 0);
                },

                .render_response_curves => {
                    values.name = Name.map.get(arg[split + 1 ..]) orelse {
                        return error.UnknownName;
                    };
                },

                .render_response_activations => {
                    values.name = Name.map.get(arg[split + 1 ..]) orelse {
                        return error.UnknownName;
                    };
                },

                .render_markov_chain_heatmap, .dump_markov_chain_csv => {
                    const tuple = arg[split + 1 ..];
                    const comma = mem.indexOfScalar(u8, tuple, ',') orelse return error.MissingTarget;
                    values.name = Name.map.get(tuple[0..comma]) orelse return error.UnknownName;
                    values.target = Name.map.get(tuple[comma + 1 ..]) orelse return error.UnknownName;
                },

                else => if (split != arg.len) {
                    try stderr.writeAll(name);
                    try stderr.writeAll(": doesn't support value parameters\r\n");
                    return error.InvalidFlagParameters;
                },
            }

            options |= bit;
        }

        break :blk .{ @bitCast(options), values };
    };

    var game: Game = .{};

    if (!flags.dry_run) {
        // run game simulation

        for (0..values.iterations) |iteration| {
            game.step();

            const out = if (flags.render_markov_chain_heatmap)
                stderr
            else
                stdout;

            if (flags.log_actions) {
                for (&game.choices, 0..) |choice, index| {
                    const action, const utility, const target = choice;
                    const name: Name = @enumFromInt(index);

                    try out.print("{s}(hp: {d:.2}, sp: {d:.2}) performs {s} on {s}: {d:.5}\r\n", .{
                        @tagName(name),
                        game.gladiators[index].status.health,
                        game.gladiators[index].status.stamina,
                        @tagName(action),
                        @tagName(target),
                        utility,
                    });
                }
            }

            try out.print("iteration: {d}\r\n", .{iteration + 1});
            if (flags.render_markov_chain_heatmap) {
                try renderHeatmap(game, values.name, values.target, stderr);
            }
        }
    }

    if (flags.render_response_curves) {
        const actions = &game.gladiators[@intFromEnum(values.name)].behaviour.actions;
        try renderCurves(actions, stderr);
    }

    if (flags.dump_markov_chain_csv) {
        const prediction = game.gladiators[@intFromEnum(values.name)].prediction;
        for (&prediction) |mc| {
            for (&mc.action) |vector| {
                for (&vector, 0..) |prob, i| if (i + 1 == vector.len) {
                    try stdout.print("{d}\r\n", .{prob});
                } else {
                    try stdout.print("{d},", .{prob});
                };
            }
        }
    }

    try stderr_buffer.flush();
    try stdout_buffer.flush();
}

// zig fmt: off
const arena: [Name.len]Gladiator = .{
    .{ .name = .alice,   .resources = .{ .potions = 3, .weapon = .axe } },
    .{ .name = .bob,     .resources = .{ .potions = 0, .weapon = .knife } },
    .{ .name = .charlie, .resources = .{ .potions = 8, .weapon = .sword } },
    .{ .name = .eve,     .resources = .{ .potions = 1, .weapon = .spear } },
};
// zig fmt: on

const Game = struct {
    gladiators: [Name.len]Gladiator = arena,
    choices: [Name.len]struct { Action, f32, Name } = undefined,

    pub fn step(game: *Game) void {
        for (&game.gladiators, &game.choices) |gladiator, *choice| {
            choice.* = gladiator.behaviour.choice(&.{
                .{ .self = &gladiator, .target = &game.gladiators[0] },
                .{ .self = &gladiator, .target = &game.gladiators[1] },
                .{ .self = &gladiator, .target = &game.gladiators[2] },
                .{ .self = &gladiator, .target = &game.gladiators[3] },
            });
        }

        for (&game.gladiators, &game.choices) |*gladiator, choice| {
            for (&game.choices, 0..) |chosen, i| {
                if (gladiator.name.indexOf(@enumFromInt(i))) |enemy| {
                    const action, _, const target = chosen;
                    gladiator.prediction[enemy].observe(.{
                        .action = action,
                        .target = target,
                    });
                }
            }

            const action, _, const target = choice;
            const reaction, _, const enemy = game.choices[@intFromEnum(target)];
            const victim = &game.gladiators[@intFromEnum(target)];
            switch (action) {
                .pass, .evade, .block => {
                    gladiator.status.stamina += 5;
                },

                .light_attack => if (!(reaction == .block and enemy == gladiator.name)) {
                    victim.status.health -= gladiator.resources.weapon.attack(.light);
                    gladiator.status.stamina -= 5;
                },

                .heavy_attack => if (!(reaction == .evade and enemy == gladiator.name)) {
                    victim.status.health -= gladiator.resources.weapon.attack(.heavy);
                    gladiator.status.stamina -= 10;
                },

                .heal => {
                    victim.status.health += 0.1;
                    victim.resources.potions -= 1;
                },
            }
        }
    }
};

const Name = enum {
    alice,
    bob,
    charlie,
    eve,

    pub fn indexOf(name: Name, other: Name) ?usize {
        if (name == other) return null;

        const this: usize = @intFromEnum(name);
        const that: usize = @intFromEnum(other);

        return if (this > that) that else (that - 1);
    }

    pub const len = @typeInfo(Name).Enum.fields.len;

    pub const map = std.ComptimeStringMap(Name, .{
        .{ "Alice", .alice },
        .{ "alice", .alice },
        .{ "Bob", .bob },
        .{ "bob", .bob },
        .{ "Charlie", .charlie },
        .{ "charlie", .charlie },
        .{ "Eve", .eve },
        .{ "eve", .eve },
    });
};

const Weapon = enum {
    axe,
    knife,
    sword,
    spear,

    const len = @typeInfo(Weapon).Enum.fields.len;

    pub const damage: [2][len]f32 = .{
        .{ 0.30, 0.10, 0.20, 0.25 },
        .{ 0.45, 0.15, 0.30, 0.40 },
    };

    pub const time: [2][len]f32 = .{
        .{ 0.5, 0.1, 0.2, 0.4 },
        .{ 0.8, 0.1, 0.3, 0.5 },
    };

    pub const Mode = enum { light, heavy };

    pub fn attack(weapon: Weapon, mode: Mode) f32 {
        return damage[@intFromEnum(mode)][@intFromEnum(weapon)];
    }

    pub fn delay(weapon: Weapon, mode: Mode) f32 {
        return time[@intFromEnum(mode)][@intFromEnum(weapon)];
    }
};

const Action = enum {
    light_attack,
    heavy_attack,
    block,
    evade,
    heal,
    pass,
};

const Event = struct {
    action: Action,
    target: Name,
};

const Gladiator = struct {
    /// Given name an table offset.
    name: Name,
    /// Status of the gladiator.
    status: Status = .{},
    /// Predictions for each character in the playing field excluding self.
    prediction: [Name.len - 1]MarkovChain = [_]MarkovChain{.{}} ** (Name.len - 1),
    /// Behaviour configuration for the gladiator.
    behaviour: Behaviour = .{},
    /// Resources for use in combat.
    resources: Resources,
    /// Action sequence the gladiator is forced to perform.
    initial_sequence: []const Event = &.{},

    const dim: comptime_int = @typeInfo(Action).Enum.fields.len;

    const Status = struct {
        health: f32 = health_max,
        stamina: f32 = stamina_max,
        cooldown: f32 = 0,

        pub const health_max = 10;
        pub const stamina_max = 30;
    };

    /// A structure which records the probaility of each state transition and adjusts as new events unfold.
    const MarkovChain = struct {
        /// Frequency table encoding the probability of the next action given the last action performed.
        action: [dim][dim]f32 = .{.{1} ** dim} ** dim,
        /// Frequency table encoding the probability of the next target given the last action performed.
        target: [dim][Name.len]f32 = .{.{1} ** Name.len} ** dim,
        /// The current state reached after processing the previous event.
        state: Action = Action.pass,
        /// Cached sum of the probability vector.
        one: [dim]struct { f32, f32 } = .{.{ dim, Name.len }} ** dim,

        /// Adjust the probability of transitioning to the given state from the last.
        pub fn observe(mc: *MarkovChain, event: Event) void {
            const action: usize = @intFromEnum(event.action);
            const target: usize = @intFromEnum(event.target);
            const state: usize = @intFromEnum(mc.state);

            mc.one[state][0] += 1; // increment cached total of the probability vector
            mc.one[state][1] += 1;
            mc.action[state][action] += 1; // increment the probability for this action to be performed
            mc.target[state][target] += 1; // increment the probability of the target the action will affect
            mc.state = event.action; // advance to the new state
        }

        /// Extract the probability of the next action being the given from the current state.
        pub fn probability(mc: *const MarkovChain, event: Event) struct { f32, f32 } {
            const action: usize = @intFromEnum(event.action);
            const target: usize = @intFromEnum(event.target);
            const state: usize = @intFromEnum(mc.state);

            const action_freq, const target_freq = mc.one[action];

            return .{
                mc.action[state][action] / action_freq,
                mc.target[state][target] / target_freq,
            };
        }
    };

    const Behaviour = struct {
        /// The complete list of actions that a character can perform along with a default list of reasons why
        /// the character should execute each action.
        actions: Actions = .{},
        /// Bias vector used to adjust action utility at runtime.
        bias: Bias = .{1} ** dim,

        pub const Bias = [dim]f32;

        fn dummy(_: Context) f32 {
            return 0;
        }

        const off = .{ .description = "off", .response = .{ .constant = 0 }, .function = &dummy };

        pub const Actions = struct {
            evade: []const Consideration = &.{off},
            heal: []const Consideration = &.{off},
            heavy_attack: []const Consideration = &.{
                .{
                    .description = "useless if stamina is depleted",
                    .response = .{ .bezier = .{ 0, 0, 1, 1 } },
                    .function = &struct {
                        fn eval(context: Context) f32 {
                            return context.self.status.stamina / Status.stamina_max;
                        }
                    }.eval,
                },
                .{
                    .description = "more useful when target is healty",
                    .response = .{ .bezier = .{ 0.5, 0.5, 1, 1 } },
                    .function = &struct {
                        fn eval(context: Context) f32 {
                            return context.target.status.health / Status.health_max;
                        }
                    }.eval,
                },
            },
            light_attack: []const Consideration = &.{
                .{
                    .description = "useless if stamina is depleted, useful near depletion",
                    .response = .{ .logistic = .{ -7, 1, 0, 0 } },
                    .function = &struct {
                        fn eval(context: Context) f32 {
                            return context.self.status.stamina / Status.stamina_max;
                        }
                    }.eval,
                },
            },
            block: []const Consideration = &.{
                .{
                    .description = "more useful when low on health",
                    .response = .{ .logistic = .{ 7, 1, 0, 0 } },
                    .function = &struct {
                        fn eval(context: Context) f32 {
                            return context.self.status.health / Status.health_max;
                        }
                    }.eval,
                },
                .{
                    .description = "more useful as the chance to be attacked increases",
                    .response = .{ .linear = .{ 1, 0, 0 } },
                    .function = &struct {
                        fn eval(context: Context) f32 {
                            if (context.self.name.indexOf(context.target.name)) |index| {
                                const chance, _ = context.self.prediction[index].probability(.{
                                    .action = .light_attack,
                                    .target = context.self.name,
                                });
                                return chance;
                            } else return 0;
                        }
                    }.eval,
                },
            },
        };

        pub const Context = struct {
            self: *const Gladiator,
            target: *const Gladiator,
        };

        pub const Consideration = struct {
            description: []const u8,
            response: Response,
            function: *const fn (Context) f32,

            pub fn eval(con: Consideration, context: Context) f32 {
                return con.y(con.function(context));
            }

            pub const Response = union(enum) {
                logistic: Four,
                logit: Three,
                normal: Four,
                linear: Three,
                bezier: Four,
                constant: f32,

                pub const Four = struct { f32, f32, f32, f32 };
                pub const Three = struct { f32, f32, f32 };
            };

            pub fn y(consideration: Consideration, x: f32) f32 {
                switch (consideration.response) {
                    inline else => |params, tag| {
                        const f = @field(Consideration, @tagName(tag));
                        const response = f(params, x);
                        return @min(1, @max(0, response));
                    },
                }
            }

            /// Calculate the degree of reponse / acctivation based on the given stimulus using
            /// a logistic curve.
            fn logistic(params: Response.Four, x: f32) f32 {
                const m, const k, const c, const b = params;
                return k / (1 + @exp(m * (x - 0.5 - c))) + b;
            }

            /// Calculate the degree of reponse / acctivation based on the given stimulus using
            /// a logit curve.
            fn logit(params: Response.Three, x: f32) f32 {
                const m, const c, const b = params;
                return (m * @log10((x - c) / (1.0 - (x - c))) / 5.0) + 0.5 + b;
            }

            /// Calculate the degree of response / activation based on the given stimulus mapped
            /// over a normal distribution.
            fn normal(params: Response.Four, x: f32) f32 {
                const m, const k, const c, const b = params;
                const t = x - c - 0.5;
                return m * @exp(-30.0 * k * t * t) + b;
            }

            /// Adjust the linear response.
            fn linear(params: Response.Three, x: f32) f32 {
                const m, const c, const b = params;
                return m * (x - c) + b;
            }

            /// Calculate the degree of response / activation based on the given stimulus mapped
            /// over a bezier curve.
            fn bezier(params: Response.Four, x: f32) f32 {
                const a, const b, const c, const d = params;

                const @"(1-x)^3" = (1 - x) * (1 - x) * (1 - x);
                const @"3x(1-x)^2" = 3 * x * (1 - x) * (1 - x);
                const @"3x^2(1-x)" = 3 * x * x * (1 - x);
                const @"x^3" = x * x * x;
                return a * @"(1-x)^3" + b * @"3x(1-x)^2" + c * @"3x^2(1-x)" + d * @"x^3";
            }

            fn constant(c: f32, _: f32) f32 {
                return c;
            }
        };

        pub fn select(be: *const Behaviour, context: Context) struct { Action, f32 } {
            const fields = @typeInfo(Actions).Struct.fields;

            var best: struct { value: f32 = 0, name: Action = .pass } = .{};

            inline for (fields) |field| {
                const considerations = @field(be.actions, field.name);
                const len: f32 = @floatFromInt(considerations.len);

                // Reduce the rate of decline for items with many considerations otherwise items
                // with only a few considerations will be interpreted as being of higher utility
                // which defeats the point of the infinite-axis utility system.
                const modification = 1 - (1 / len);

                var total: f32 = 1;

                for (considerations) |con| {
                    const score = con.eval(context);
                    total *= @max(0, @min(1, score + (1 - score) * score * modification));
                }

                if (best.value < total) {
                    best.value = total;
                    best.name = @field(Action, field.name);
                }
            }

            return .{
                best.name,
                best.value,
            };
        }

        pub fn choice(be: *const Behaviour, contexts: []const Context) struct { Action, f32, Name } {
            assert(contexts.len != 0);

            var action: Action = .pass;
            var best: f32 = 0;
            var name: Name = undefined;

            for (contexts, 0..) |context, index| {
                const act, const utility = be.select(context);
                if (utility >= best) {
                    action = act;
                    best = utility;
                    name = @enumFromInt(index);
                }
            }

            return .{ action, best, name };
        }
    };

    const Resources = struct {
        weapon: Weapon,
        potions: u4,

        pub const max_potions = 15;
    };
};

fn renderHeatmap(game: Game, name: Name, target: Name, writer: anytype) !void {
    const prediction = game.gladiators[@intFromEnum(name)].prediction;
    const mc = prediction[name.indexOf(target) orelse return error.CannotTargetSelf];

    for (&mc.one, &mc.action) |one, vector| {
        const total, _ = one;

        for (vector) |action| {
            const heat: u8 = @intFromFloat(254.999 * (action / total));
            try writer.print("\x1b[48;2;{d};{d};0m  ", .{ heat, heat >> 1 });
        }

        try writer.writeAll("\x1b[0m\n");
    }
}

fn renderCurves(actions: *const Gladiator.Behaviour.Actions, writer: anytype) !void {
    const prime: u24 = 7919;
    const Rgb = packed struct { r: u8, g: u8, b: u8 };
    const fields = @typeInfo(Gladiator.Behaviour.Actions).Struct.fields;
    inline for (fields) |field| {
        const considerations = @field(actions, field.name);

        try writer.writeByteNTimes('-', 80);
        try writer.writeAll("\r\n");

        if (considerations.len != 0) for (0..40) |_y| {
            const y = 39 - _y;
            for (0..80) |x| {
                var upper: u24 = 0;
                var lower: u24 = 0;
                var hit: u2 = 0;

                for (considerations, 1..) |con, index| {
                    const colour: u24 = @intCast(index);
                    const signal = @as(f32, @floatFromInt(x)) / 79;
                    const response: u8 = @intFromFloat(con.y(signal) * 79);

                    const y2: u2 = @intFromBool(response == y * 2);
                    const y1: u2 = @intFromBool(response == y * 2 + 1);

                    const local_hit: u2 = (y1 << 1) | y2;
                    hit |= local_hit;

                    switch (local_hit) {
                        0b00 => {},
                        0b10 => upper = colour,
                        0b01 => lower = colour,
                        0b11 => {
                            upper = colour;
                            lower = colour;
                        },
                    }
                }

                const top: Rgb = @bitCast(upper *% prime);
                const bot: Rgb = @bitCast(lower *% prime);

                switch (hit) {
                    0b00 => try writer.writeByte(' '),
                    0b10 => try writer.print(
                        "\x1b[38;2;{d};{d};{d}m" ++ upper_half_block ++ "\x1b[0m",
                        .{ top.r, top.g, top.b },
                    ),
                    0b01 => try writer.print(
                        "\x1b[38;2;{d};{d};{d}m" ++ lower_half_block ++ "\x1b[0m",
                        .{ bot.r, bot.g, bot.b },
                    ),
                    0b11 => try writer.print(
                        "\x1b[38;2;{d};{d};{d}m\x1b[48;2;{d};{d};{d}m" ++ upper_half_block ++ "\x1b[0m",
                        .{ top.r, top.g, top.b, bot.r, bot.g, bot.b },
                    ),
                }
            }

            try writer.writeAll("\r\n");
        };

        for (considerations, 1..) |con, index| {
            const c: Rgb = @bitCast(@as(u24, @intCast(index)) *% prime);

            try writer.writeAll("[ ");
            try writer.writeAll(con.description);
            try writer.writeAll(" ] ");
            try writer.print("\x1b[38;2;{d};{d};{d}m", .{ c.r, c.g, c.b });
            for (0..80 - con.description.len - 10 - field.name.len) |_| {
                try writer.writeAll("━");
            }
            try writer.writeAll("\x1b[0m [ " ++ field.name ++ " ]\r\n");
        }
    }
}