Optimizing fighting bots

Question

Imagine you are supposed to write an algorithm for a bot that will fight other similarly prepared bots. Your bot has 200 HP for a whole fight and gets a set value of 12 energy points per every round (maximum 100 rounds). Your bot have to attack every round and can, but doesn't have to, defend himself. There are 4 types of attacks and 4 corresponding defenses. The fight ends when either one bot loses all his health or you get past 100 rounds in which case the winner is the one that had more HP after the end of the fight. Each defence is worth 4 energy points and blocks all attacks of the given type in a round. There are 4 different attacks - Hook kick, worth 4 energy points, deals 10 hp, hook punch, worth 3 energy points, deals 6 hp, uppercut punch, worth 2 energy points, deals 3 hp, lowkick, worth 1 deals 1. You are able to collect all data from all previous rounds (both bots hp and energy points, both bots attack sets, bot bots defences, damage dealt and received). Obviously I don't expect anyone to come up with a whole solution however I can't wrap my head around it and I don't really see a way to approach such a thing, so any suggestions or related topics to read about would be really helpful. Note that this shouldn't be anything ML or AI in general related. Just an algorithm.

Answer 1

You can simulate a random action by your bot, then a random action of another bot, and so on a few turns forward and calculate the outcome (in points). Repeat it, say, a million times, and select the best move for your bot out of million variants. This method is called Monte-Carlo simulation. It is very simple, but it works. It would not give you the best move, but it will give you good enough move, a plausible move. You can improve it by storing all possible actions a few turns in advance to a tree and then use Monte Carlo tree search, but it is a little bit harder to implement. For the Monte-Carlo simulation to be quick and efficient, use a fast pseudorandom generator, not that one provided by your programming language, e.g., The "XorShift" Pseudorandom Number Generator. For more information, see about XorShift on Wikipedia or see the paper "Xorshift RNGs" by George Marsaglia from The Florida State University, published in 2003 in the Journal of Statistical Software, DOI: 10.18637/jss.v008.i14 or just search for "Xorshift RNGs" on Semantic Scholar. You can solve various tasks by the Monte-Carlo simulation, like puzzles, or even a good computer player for a Hex game.

Here are the code examples for 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;
}