mathematical-optimization - 优化战斗机器人

Question

想象一下，您应该为一个机器人编写一个算法，该算法将与其他类似准备的机器人战斗。你的机器人整场战斗有 200 点生命值，每轮获得 12 个能量点的设定值（最多 100 轮）。您的机器人必须每一轮都进行攻击，并且可以但不必保护自己。有4种攻击类型和4种相应的防御。当一个机器人失去所有生命值或您超过 100 轮时，战斗结束，在这种情况下，获胜者是战斗结束后拥有更多 HP 的人。每个防御值 4 能量点，并在一轮中阻止给定类型的所有攻击。有 4 种不同的攻击方式 - 钩踢，价值 4 能量点，造成 10 hp，钩拳，价值 3 能量点，造成 6 hp，上勾拳，价值 2 能量点，造成 3 hp，lowkick，价值 1 交易 1。您可以收集所有先前回合的所有数据（机器人 hp 和能量点、机器人攻击集、机器人防御、造成和接收的伤害）。显然，我不希望任何人提出一个完整的解决方案，但是我无法理解它，我也没有真正看到解决这个问题的方法，所以任何要阅读的建议或相关主题都是真的很有帮助。请注意，这通常与 ML 或 AI 无关。只是一个算法。因此，任何要阅读的建议或相关主题都会非常有帮助。请注意，这通常与 ML 或 AI 无关。只是一个算法。因此，任何要阅读的建议或相关主题都会非常有帮助。请注意，这通常与 ML 或 AI 无关。只是一个算法。

标签： mathematical-optimizationmontecarlodiscrete-mathematicsgame-theorymonte-carlo-tree-search

Answer 1

您可以模拟您的机器人的随机动作，然后模拟另一个机器人的随机动作，依此类推，向前转几圈并计算结果（以点为单位）。重复它，比如说，一百万次，然后从数百万变体中为你的机器人选择最佳动作。这种方法称为蒙特卡罗模拟。这很简单，但它确实有效。它不会给你最好的移动，但它会给你足够好的移动，一个合理的移动。您可以通过提前几圈将所有可能的动作存储到树中来改进它，然后使用蒙特卡洛树搜索，但实现起来有点困难。为了使蒙特卡罗模拟快速有效，请使用快速伪随机生成器，而不是您的编程语言提供的生成器，例如“XorShift”伪随机数生成器。有关更多信息，请参阅Wikipedia 上的 XorShift或参阅佛罗里达州立大学的 George Marsaglia 于 2003 年在 Journal of Statistical Software 上发表的论文“Xorshift RNGs”，DOI：10.18637/jss.v008.i14 或仅搜索“ Xorshift RNGs”在语义学者。您可以通过蒙特卡洛模拟解决各种任务，例如谜题，甚至是 Hex 游戏的优秀计算机玩家。

以下是 XorShift 的代码示例：

const uint64_t initial_seed = 88172645463325252LL; // the intial seed value from the paper above mentioned

uint64_t current_seed = initial_seed;

// a basic xorshift routiine, returns a value in range [0..2^64)
inline uint64_t xorshift64(uint64_t& seed)
{
    seed ^= (seed << 13);
    seed ^= (seed >> 7);
    return (seed ^= (seed << 17));
}

// use one xorshift call to return one pseudorandom byte, each in the given range from 0, but less than the given limit, i.e. [0..limit), but the limit is not larger than 255
inline uint8_t rand_byte_lim(uint64_t& seed, const uint8_t limit)
{
    uint64_t x = xorshift64(seed);
    x &= 0xffffffffffffff; // 7 bytes
    x *= limit;
    x >>= 56; // 7 bytes * 8 bits = 56 bits
    return x & 0xff;
}

// use one xorshift call to return 8 pseudorandom bytes each in own range [0..limN), but a limN is not larger than 255
inline void rand_8_bytes(uint64_t& seed, const uint8_t lim1, uint8_t& res1, const uint8_t lim2, uint8_t& res2, const uint8_t lim3, uint8_t& res3, const uint8_t lim4, uint8_t& res4, const uint8_t lim5, uint8_t& res5, const uint8_t lim6, uint8_t& res6, const uint8_t lim7, uint8_t& res7, const uint8_t lim8, uint8_t& res8
)
{
    uint64_t x = xorshift64(seed);
    uint32_t t1 = (x >> (0 * 8)) & 0xff;
    uint32_t t2 = (x >> (1 * 8)) & 0xff;
    uint32_t t3 = (x >> (2 * 8)) & 0xff;
    uint32_t t4 = (x >> (3 * 8)) & 0xff;
    uint32_t t5 = (x >> (4 * 8)) & 0xff;
    uint32_t t6 = (x >> (5 * 8)) & 0xff;
    uint32_t t7 = (x >> (6 * 8)) & 0xff;
    uint32_t t8 = (x >> (7 * 8)) & 0xff;
    t1 *= lim1;
    t2 *= lim2;
    t3 *= lim3;
    t4 *= lim4;
    t5 *= lim5;
    t6 *= lim6;
    t7 *= lim7;
    t8 *= lim8;
    res1 = (t1 >> 8) & 0xff;
    res2 = (t2 >> 8) & 0xff;
    res3 = (t3 >> 8) & 0xff;
    res4 = (t4 >> 8) & 0xff;
    res5 = (t5 >> 8) & 0xff;
    res6 = (t6 >> 8) & 0xff;
    res7 = (t7 >> 8) & 0xff;
    res8 = (t8 >> 8) & 0xff;
}