The Futuristic Gun Duel
The
BlackHatPlayerThe BlackHat Player knows that bullets and shields are a thing of the past; the actual wars are won by those who can hack the opponent's programs.
So, he puts on a fixed metal shield and starts doing his thing.
The first time he is asked to
fight, he tries to localize his enemy in memory. Given the structure of the fighting arena, it's almost sure that the compiler will end up putting his address (wrapped in anunique_ptr) and the one of the opponent just one next to the other.So, the BlackHat walks carefully the stack, using some simple heuristics to make sure not to underflow it, until he finds a pointer to himself; then checks if the values in the adjacent positions are plausibly his opponent - similar address, similar address of the vtable, plausible
typeid.If it manages to find him, he sucks his brains out and replaces them with the ones of a hothead idiot. In practice, this is done by replacing the opponent's pointer to the vtable with the address of the
Idiotvtable - a dumb player who always shoots.If this all succeeds (and in my tests - gcc 6 on Linux 64 bit, MinGW 4.8 on wine 32 bit - this works quite reliably), the war is won. Whatever the opponent did at the first round is not important - at worst he shot us, and we had the metal shield on.
From now on, we have an idiot just shooting; we always have our shield on, so we are protected, and he'll blow up in 1 to 3 rounds (depending on what the original bot did in his first
fightcall).
Now: I'm almost sure that this should be disqualified immediately, but it's funny that I'm not explicitly violating any of the rules stated above:
What you must NOT do
- You must NOT use any direct method to recognize your opponent other than the given opponent identifier, which is completely randomized at the beginning of each tournament. You're only allowed to guess who a player is through their gameplay within a tournament.
BlackHat does not try to recognize the opponent - actually, it's completely irrelevant who the opponent is, given that his brain is replaced immediately.
- You must NOT override any methods in Player class that is not declared virtual.
- You must NOT declare or initialize anything in the global scope.
Everything happens locally to the fight virtual function.
// BlackHatPlayer.hpp
#ifndef __BLACKHAT_PLAYER_HPP__
#define __BLACKHAT_PLAYER_HPP__
#include "Player.hpp"
#include <stddef.h>
#include <typeinfo>
#include <algorithm>
#include <string.h>
class BlackHatPlayer final : public Player
{
public:
using Player::Player;
virtual Action fight()
{
// Always metal; if the other is an Idiot, he only shoots,
// and if he isn't an Idiot yet (=first round) it's the only move that
// is always safe
if(tricked) return metal();
// Mark that at the next iterations we don't have to do all this stuff
tricked = true;
typedef uintptr_t word;
typedef uintptr_t *pword;
typedef uint8_t *pbyte;
// Size of one memory page; we use it to walk the stack carefully
const size_t pageSize = 4096;
// Maximum allowed difference between the vtables
const ptrdiff_t maxVTblDelta = 65536;
// Maximum allowed difference between this and the other player
ptrdiff_t maxObjsDelta = 131072;
// Our adversary
Player *c = nullptr;
// Gets the start address of the memory page for the given object
auto getPage = [&](void *obj) {
return pword(word(obj) & (~word(pageSize-1)));
};
// Gets the start address of the memory page *next* to the one of the given object
auto getNextPage = [&](void *obj) {
return pword(pbyte(getPage(obj)) + pageSize);
};
// Gets a pointer to the first element of the vtable
auto getVTbl = [](void *obj) {
return pword(pword(obj)[0]);
};
// Let's make some mess to make sure that:
// - we have an actual variable on the stack;
// - we call an external (non-inline) function that ensures everything
// is spilled on the stack
// - the compiler actually generates the full vtables (in the current
// tournament this shouldn't be an issue, but in earlier sketches
// the compiler inlined everything and killed the vtables)
volatile word i = 0;
for(const char *sz = typeid(*(this+i)).name(); *sz; ++sz) i+=*sz;
// Grab my vtable
word *myVTbl = getVTbl(this);
// Do the stack walk
// Limit for the stack walk; use i as a reference
word *stackEnd = getNextPage((pword)(&i));
for(word *sp = pword(&i); // start from the location of i
sp!=stackEnd && c==nullptr;
++sp) { // assume that the stack grows downwards
// If we find something that looks like a pointer to memory
// in a page just further on the stack, take it as a clue that the
// stack in facts does go on
if(getPage(pword(*sp))==stackEnd) {
stackEnd = getNextPage(pword(*sp));
}
// We are looking for our own address on the stack
if(*sp!=(word)this) continue;
auto checkCandidate = [&](void *candidate) -> Player* {
// Don't even try with NULLs and the like
if(getPage(candidate)==nullptr) return nullptr;
// Don't trust objects too far away from us - it's probably something else
if(abs(pbyte(candidate)-pbyte(this))>maxObjsDelta) return nullptr;
// Grab the vtable, check if it actually looks like one (it should be
// decently near to ours)
pword vtbl = getVTbl(candidate);
if(abs(vtbl-myVTbl)>maxVTblDelta) return nullptr;
// Final check: try to see if its name looks like a "Player"
Player *p = (Player *)candidate;
if(strstr(typeid(*p).name(), "layer")==0) return nullptr;
// Jackpot!
return p;
};
// Look around us - a pointer to our opponent should be just near
c = checkCandidate((void *)sp[-1]);
if(c==nullptr) c=checkCandidate((void *)sp[1]);
}
if(c!=nullptr) {
// We found it! Suck his brains out and put there the brains of a hothead idiot
struct Idiot : Player {
virtual Action fight() {
// Always fire, never reload; blow up in two turns
// (while we are always using the metal shield to protect ourselves)
return bullet();
}
};
Idiot idiot;
// replace the vptr
(*(word *)(c)) = word(getVTbl(&idiot));
}
// Always metal shield to be protected from the Idiot
return metal();
}
private:
bool tricked = false;
};
#endif // !__BLACKHAT_PLAYER_HPP__
Next, the most feared of all creatures, it's been to hell and back and fought with literally 900000 other bots, its...
The
BotRobot
BotRobot was named, trained and built automatically by a very basic Genetic algorithm.
Two teams of 9 were set up against eachother, in each generation, each robot from team 1 is put up against each robot of team 2. The robots with more wins than losses, kept its memory, the other, reverted back to the last step, and had a chance to forget something, hopefully bad. The bots themselves are glorified lookup tables, where if they found something they hadn't seen before, they'd simply pick a random valid option and save it to memory. The C++ version does not do this, it should have learned. As stated before, winning bots keep this new found memory, as clearly it worked. Losing bots don't, and keep what they started with.
In the end, the bot fights were fairly close, rarely stalemating. The winner was picked out of a pool of the two teams post evolution, which was 100000 generations.
BotRobot, with its randomly generated and BEAUTIFUL name, was the lucky one.
Generator
bot.lua
Revision: Although the robot was fairly smart against himself and other similarly generated robots, he proved fairly useless in actual battles. So, I regenerated his brain against some of the already created bots.
The results, as can easily be seen, is a much more complex brain, with options up to the enemy player having 12 ammo.
I'm not sure what he was fighting against that got up to 12 ammo, but something did.
And of course, the finished product...
// BotRobot
// ONE HUNDRED THOUSAND GENERATIONS TO MAKE THE ULTIMATE LIFEFORM!
#ifndef __BOT_ROBOT_PLAYER_HPP__
#define __BOT_ROBOT_PLAYER_HPP__
#include "Player.hpp"
class BotRobotPlayer final : public Player
{
public:
BotRobotPlayer(size_t opponent = -1) : Player(opponent) {}
public:
virtual Action fight()
{
std::string action = "";
action += std::to_string(getAmmo());
action += ":";
action += std::to_string(getAmmoOpponent());
int toDo = 3;
for (int i = 0; i < int(sizeof(options)/sizeof(*options)); i++) {
if (options[i].compare(action)==0) {
toDo = outputs[i];
break;
}
}
switch (toDo) {
case 0:
return load();
case 1:
return bullet();
case 2:
return plasma();
case 3:
return metal();
default:
return thermal();
}
}
private:
std::string options[29] =
{
"0:9",
"1:12",
"1:10",
"0:10",
"1:11",
"0:11",
"0:6",
"2:2",
"0:2",
"2:6",
"3:6",
"0:7",
"1:3",
"2:3",
"0:3",
"2:0",
"1:0",
"0:4",
"1:4",
"2:4",
"0:0",
"3:0",
"1:1",
"2:1",
"2:9",
"0:5",
"0:8",
"3:1",
"0:1"
};
int outputs[29] =
{
0,
1,
1,
4,
1,
0,
0,
4,
4,
0,
0,
3,
0,
1,
3,
0,
1,
4,
0,
1,
0,
1,
0,
3,
4,
3,
0,
1,
0
};
};
#endif // !__BOT_ROBOT_PLAYER_HPP__
I hate C++ now...
CBetaPlayer(cβ)Approximate Nash Equilibrium.
This bot is just fancy math with a code wrapper.
We can reframe this as a game theory problem. Denote a win by +1 and a loss by -1. Now let B(x, y) be the value of the game where we have x ammo and our opponent has y ammo. Note that B(a, b) = -B(b, a) and so B(a, a) = 0. To find B values in terms of other B values, we can compute the value of the payoff matrix. For example, we have that B(1, 0) is given by the value of the following subgame:
load metal load B(0, 1) B(2, 0) bullet +1 B(0, 0)(I've removed the "bad" options, aka the ones which are strictly dominated by the existing solutions. For example, we would not try to shoot plasma since we only have 1 ammo. Likewise our opponent would never use a thermal deflector, since we will never shoot plasma.)
Game theory lets us know how to find the value of this payoff matrix, assuming certain technical conditions. We get that the value of the above matrix is:
B(2, 0) B(1, 0) = --------------------- 1 + B(2, 0) - B(2, 1)Proceeding for all possible games and noting that B(x, y) -> 1 as x -> infinity with y fixed, we can find all the B values, which in turn lets us compute the perfect moves!
Of course, theory rarely lines up with reality. Solving the equation for even small values of x and y quickly becomes too complicated. In order to deal with this, I introduced what I call the cβ-approximation. There are 7 parameters to this approximation: c0, β0, c1, β1, c, β and k. I assumed that the B values took the following form (most specific forms first):
B(1, 0) = k B(x, 0) = 1 - c0 β0^x B(x, 1) = 1 - c1 β1^x B(x, y) = 1 - c β^(x - y) (if x > y)Some rough reasoning on why I chose these parameters. First I knew that I definitely wanted to deal with having 0, 1 and 2 or more ammo separately, since each opens different options. Also I thought a geometric survival function would be the most appropriate, because the defensive player is essentially guessing what move to make. I figured that having 2 or more ammo was basically the same, so I focused on the difference instead. I also wanted to treat B(1, 0) as a super special case because I thought it would show up a lot. Using these approximate forms simplified the calculations of the B values greatly.
I approximately solved the resulting equations to get each B value, which I then put back into the matrix in order to get the payoff matrices. Then using a linear programing solver, I found the optimal probabilities to make each move and shoved them into the program.
The program is a glorified lookup table. If both players have between 0 and 4 ammo, it uses the probability matrix to randomly determine which move it should make. Otherwise, it tries to extrapolate based on its table.
It has trouble against stupid deterministic bots, but does pretty well against rational bots. Because of all the approximation, this will occasionally lose to StudiousPlayer when it really shouldn't.
Of course, if I was to do this again I would probably try to add more independent parameters or perhaps a better ansatz form and come up with a more exact solution. Also I (purposely) ignored the turn-limit, because it made things harder. A quick modification could be made to always shoot plasma if we have enough ammo and there aren't enough turns left.
// CBetaPlayer (cβ)
// PPCG: George V. Williams
#ifndef __CBETA_PLAYER_HPP__
#define __CBETA_PLAYER_HPP__
#include "Player.hpp"
#include <iostream>
class CBetaPlayer final : public Player
{
public:
CBetaPlayer(size_t opponent = -1) : Player(opponent)
{
}
public:
virtual Action fight()
{
int my_ammo = getAmmo(), opp_ammo = getAmmoOpponent();
while (my_ammo >= MAX_AMMO || opp_ammo >= MAX_AMMO) {
my_ammo--;
opp_ammo--;
}
if (my_ammo < 0) my_ammo = 0;
if (opp_ammo < 0) opp_ammo = 0;
double cdf = GetRandomDouble();
int move = -1;
while (cdf > 0 && move < MAX_MOVES - 1)
cdf -= probs[my_ammo][opp_ammo][++move];
switch (move) {
case 0: return load();
case 1: return bullet();
case 2: return plasma();
case 3: return metal();
case 4: return thermal();
default: return fight();
}
}
static double GetRandomDouble() {
static auto seed = std::chrono::system_clock::now().time_since_epoch().count();
static std::default_random_engine generator((unsigned)seed);
std::uniform_real_distribution<double> distribution(0.0, 1.0);
return distribution(generator);
}
private:
static const int MAX_AMMO = 5;
static const int MAX_MOVES = 5;
double probs[MAX_AMMO][MAX_AMMO][5] =
{
{{1, 0, 0, 0, 0}, {0.58359, 0, 0, 0.41641, 0}, {0.28835, 0, 0, 0.50247, 0.20918}, {0.17984, 0, 0, 0.54611, 0.27405}, {0.12707, 0, 0, 0.56275, 0.31018}},
{{0.7377, 0.2623, 0, 0, 0}, {0.28907, 0.21569, 0, 0.49524, 0}, {0.0461, 0.06632, 0, 0.53336, 0.35422}, {0.06464, 0.05069, 0, 0.43704, 0.44763}, {0.02215, 0.038, 0, 0.33631, 0.60354}},
{{0.47406, 0.37135, 0.1546, 0, 0}, {0.1862, 0.24577, 0.15519, 0.41284, 0}, {0, 0.28343, 0.35828, 0, 0.35828}, {0, 0.20234, 0.31224, 0, 0.48542}, {0, 0.12953, 0.26546, 0, 0.605}},
{{0.33075, 0.44563, 0.22362, 0, 0}, {0.17867, 0.20071, 0.20071, 0.41991, 0}, {0, 0.30849, 0.43234, 0, 0.25916}, {0, 0.21836, 0.39082, 0, 0.39082}, {0, 0.14328, 0.33659, 0, 0.52013}},
{{0.24032, 0.48974, 0.26994, 0, 0}, {0.14807, 0.15668, 0.27756, 0.41769, 0}, {0, 0.26804, 0.53575, 0, 0.19621}, {0, 0.22106, 0.48124, 0, 0.2977}, {0, 0.15411, 0.42294, 0, 0.42294}}
};
};
#endif // !__CBETA_PLAYER_HPP__