Skip to content

Instantly share code, notes, and snippets.

@tomsmeding tomsmeding/P.c
Last active Aug 28, 2018

Embed
What would you like to do?
/// -------------------- STANDARD LIBRARY THINGS --------------------
#include <stdbool.h>
#define WASM_EXPORT __attribute__((visibility("default")))
typedef unsigned char uint8_t;
typedef unsigned int uint32_t;
typedef unsigned long long int uint64_t;
// Controller takes 3 * num_bots as arena size; we just assume this is enough for now
#define MAXBOTS 60
#define MAXSZ (3 * MAXBOTS)
#define MAXID (MAXBOTS + 1)
extern void print_int(int);
extern void println(const char *str);
struct __attribute((packed)) bot {
uint8_t id, x, y;
};
WASM_EXPORT void *ptrs[9];
WASM_EXPORT int width;
WASM_EXPORT int height;
WASM_EXPORT int nbots;
WASM_EXPORT int round_idx;
WASM_EXPORT int total_rounds;
WASM_EXPORT int my_id;
WASM_EXPORT uint8_t grid[MAXSZ * MAXSZ];
WASM_EXPORT struct bot bots[MAXBOTS];
static inline int abs(int a) {
return a < 0 ? -a : a;
}
WASM_EXPORT uint32_t rand_state[5];
// The rand_state array must be initialized to not be all zero in the first four words
// Source: wikipedia, which claims this is the generator used in CUDA
static inline uint32_t xorwow(uint32_t state[5]) {
uint32_t s, t = state[3];
t ^= t >> 2;
t ^= t << 1;
state[3] = state[2]; state[2] = state[1]; state[1] = s = state[0];
t ^= s;
t ^= s << 4;
state[0] = t;
return t + (state[4] += 362437);
}
static inline uint32_t rand(void) {
return xorwow(rand_state);
}
static inline uint32_t deterministic_rand(int meIdx) {
static int prev_round_idx = -1;
static uint32_t state[5];
if (round_idx == prev_round_idx) {
return xorwow(state);
}
prev_round_idx = round_idx;
state[0] = my_id ^ 0x1cbc45e7;
state[1] = round_idx ^ 0xaaf4f4c1;
state[2] = bots[meIdx].x ^ 0x8e4c26e0;
state[3] = bots[meIdx].y ^ 0x942d1d6e;
state[4] = 0xbd963e53;
xorwow(state);
xorwow(state);
xorwow(state);
xorwow(state);
return xorwow(state);
}
// static inline int compute0(int otherwise) {
// // return otherwise;
// (void)otherwise; return &width != ptrs[0];
// }
static inline void memcpy_x(void *dst_, const void *src_, int n) {
// println("Performing memcpy with dst src n:");
// print_int((int)dst_);
// print_int((int)src_);
// print_int((int)n);
// println("---");
uint64_t *dst64 = (uint64_t*)dst_;
const uint64_t *src64 = (const uint64_t*)src_;
for (int i = 0; i < n / 8; i++) {
dst64[i] = src64[i];
}
uint8_t *dst8 = (uint8_t*)dst_;
const uint8_t *src8 = (const uint8_t*)src_;
for (int i = n / 8 * 8; i < n; i++) {
dst8[i] = src8[i];
}
// println("memcpy done");
}
static inline void memset_x(void *dst_, uint8_t value, int n) {
uint64_t *dst64 = (uint64_t*)dst_;
for (int i = 0; i < n / 8; i++) {
dst64[i] = value;
}
uint8_t *dst8 = (uint8_t*)dst_;
for (int i = n / 8 * 8; i < n; i++) {
dst8[i] = value;
}
}
/// -------------------- UTILITY FUNCTIONS --------------------
static inline int paint_value(uint8_t floor, uint8_t id) {
if (floor == 0) return id;
switch (abs(id - floor) % 3) {
case 0: return id;
case 1: return 0;
case 2: return floor;
}
__builtin_unreachable();
}
static inline void paint(uint8_t *gr, int x, int y, int id) {
gr[width * y + x] = paint_value(gr[width * y + x], id);
}
/// -------------------- PATH PLAYER --------------------
// static const int dir_dx[4] = {1, 0, -1, 0};
// static const int dir_dy[4] = {0, 1, 0, -1};
#define P_WALK_DISTANCE 8
// keep info over turns
static bool have_been[MAXSZ * MAXSZ];
static bool previous_is_me[MAXSZ * MAXSZ];
static int bot_evil_score[MAXID + 1];
static int bot_prevpos[MAXID + 1];
static int bot_dx[MAXID + 1];
static int bot_dy[MAXID + 1];
// transient
static bool place_has_bot[MAXSZ * MAXSZ];
static float heat_map[MAXSZ * MAXSZ];
static float evil_factor_cache[MAXSZ * MAXSZ];
static inline float p_paintScore(int idx) {
const uint8_t floor = grid[idx];
if (floor == my_id) return 1;
if (paint_value(floor, my_id) != my_id) return 1;
return 10 + !place_has_bot[idx] + !have_been[idx];
}
// higher means a better position
static inline float p_evil_factor(int x, int y) {
float sc = 0;
for (int i = 0; i < nbots; i++) {
if (bot_evil_score[bots[i].id] >= 20) {
int bx = bots[i].x, by = bots[i].y;
for (int j = 0; j < 3; j++) {
float d = abs(by - y) + abs(bx - x);
sc -= 10 / (d + 1);
bx += bot_dx[bots[i].id];
by += bot_dy[bots[i].id];
}
}
}
return sc;
}
static inline void p_fill_evil_factor_cache(int cx, int cy) {
for (int dy = -P_WALK_DISTANCE; dy <= P_WALK_DISTANCE; dy++) {
int y = cy + dy;
if (y < 0) continue;
if (y >= height) break;
for (int dx = -P_WALK_DISTANCE; dx <= P_WALK_DISTANCE; dx++) {
if (abs(dx) + abs(dy) > P_WALK_DISTANCE) continue;
int x = cx + dx;
if (x < 0) continue;
if (x >= width) break;
evil_factor_cache[width * y + x] = p_evil_factor(x, y);
}
}
}
// Returns how many paintable cells can be reached from here,
// depth-limited, and weighted with paintScore.
static inline float p_findpath(int x, int y, int depth) {
const int idx = width * y + x;
if (depth == P_WALK_DISTANCE) {
return heat_map[idx] + p_paintScore(idx);
}
bool orig_have_been = have_been[idx];
have_been[idx] = true;
float maxnum = -1;
#define GO_DIR(cond, newx, newy) \
if ((cond) && p_paintScore(width * (newy) + (newx)) > 0) { \
float n__ = p_findpath((newx), (newy), depth + 1); \
n__ += evil_factor_cache[width * (newy) + (newx)]; \
if (n__ > maxnum) maxnum = n__; \
}
GO_DIR(x < width-1, x + 1, y);
GO_DIR(y < height-1, x, y + 1);
GO_DIR(x > 0, x - 1, y);
GO_DIR(y > 0, x, y - 1);
#undef GO_DIR
have_been[idx] = orig_have_been;
return heat_map[idx] + p_paintScore(idx) + 0.98 * maxnum;
}
static inline void p_populate_heatmap() {
for (int i = 0; i < width * height; i++) {
heat_map[i] = (
/* grid[i] == 0 ? 0.1 :
grid[i] == my_id ? -0.1 :
paint_value(grid[i], my_id) == my_id ? 0.05 :
-0.05 */
grid[i] == 0 ? 1.0 :
grid[i] == my_id ? -1.0 :
paint_value(grid[i], my_id) == my_id ? 0.5 :
-0.5
);
}
}
__attribute__((unused))
static void p_setup_data() {
memset_x(have_been, 0, width * height);
memset_x(previous_is_me, 0, width * height);
memset_x(bot_evil_score, 0, (MAXID + 1) * sizeof(int));
memset_x(bot_dx, 0, (MAXID + 1) * sizeof(int));
memset_x(bot_dy, 0, (MAXID + 1) * sizeof(int));
}
__attribute__((unused))
static int p_calcmove() {
// println("my_id");
// print_int(my_id);
memset_x(place_has_bot, 0, width * height);
for (int i = 0; i < nbots; i++) {
int pos = width * bots[i].y + bots[i].x;
place_has_bot[pos] = true;
if (bots[i].id == my_id || paint_value(my_id, bots[i].id) == my_id) continue;
if (previous_is_me[pos]) {
bot_evil_score[bots[i].id]++;
} else if (bot_evil_score[bots[i].id] > 0) {
bot_evil_score[bots[i].id] >>= 1;
}
if (round_idx > 1) {
bot_dx[bots[i].id] = bots[i].x - bot_prevpos[bots[i].id] % width;
bot_dy[bots[i].id] = bots[i].y - bot_prevpos[bots[i].id] / width;
}
bot_prevpos[bots[i].id] = pos;
}
/* char buffer[MAXID + 1];
for (int i = 0; i < nbots; i++) {
int index = bot_evil_score[bots[i].id];
if (index > 61) index = 61;
buffer[i] = "0123456789abcdefghijklmnopqrstuvwxyzABCDEFGHIJKLMNOPQRSTUVWXYZ"[index];
}
buffer[nbots] = '\0';
println(buffer); */
int meIdx = -1;
for (int i = 0; i < nbots; i++) {
if (bots[i].id == my_id) {
meIdx = i;
break;
}
}
p_populate_heatmap();
int x = bots[meIdx].x, y = bots[meIdx].y;
have_been[width * y + x] = true;
p_fill_evil_factor_cache(x, y);
float maxnum = -1;
int maxat = -1;
#define GO_DIR(cond, newx, newy, dir) \
if (cond) { \
float n__ = p_findpath((newx), (newy), 1); \
n__ += evil_factor_cache[width * (newy) + (newx)]; \
/* println("direction score"); \
print_int(dir); \
print_int(n__); \
print_int(p_paintScore(width * (newy) + (newx))); \
print_int(paint_value(grid[width * (newy) + (newx)], my_id)); */ \
if (n__ > maxnum) { \
maxnum = n__; \
maxat = (dir); \
} \
}
GO_DIR(x < width-1, x + 1, y, 0);
GO_DIR(y < height-1, x, y + 1, 1);
GO_DIR(x > 0, x - 1, y, 2);
GO_DIR(y > 0, x, y - 1, 3);
#undef GO_DIR
if (maxat == -1) maxat = deterministic_rand(meIdx) % 4;
// print_int(maxnum * 10000);
for (int i = 0; i < width * height; i++) {
previous_is_me[i] = grid[i] == my_id;
}
static const int dir_dx[4] = {1, 0, -1, 0};
static const int dir_dy[4] = {0, 1, 0, -1};
previous_is_me[width * (y + dir_dy[maxat]) + x + dir_dx[maxat]] = true;
return maxat;
}
/// -------------------- MONTE CARLO PLAYER --------------------
// static bool can_be_boss[MAXID + 1];
static inline void mc_random_step(
uint8_t *gr, struct bot *bt, int meIdx, int my_last_dir,
int *modify_idxs, int *num_modified, int *score_delta) {
int last_dir[MAXBOTS];
for (int i = 0; i < nbots; i++) last_dir[i] = -1;
last_dir[meIdx] = my_last_dir;
int num_modified_value = *num_modified;
int score_delta_value = *score_delta;
for (int i = 0; i < nbots; i++) {
while (rand() % 20 < 19) {
const int dir = rand() >> 30;
if ((dir + 2) % 4 == last_dir[i]) continue; // don't go backwards
switch (dir) {
case 0: if (bt[i].x < width - 1) bt[i].x++; else continue; break;
case 1: if (bt[i].y < height - 1) bt[i].y++; else continue; break;
case 2: if (bt[i].x > 0) bt[i].x--; else continue; break;
case 3: if (bt[i].y > 0) bt[i].y--; else continue; break;
}
last_dir[i] = dir;
break;
}
const int idx = width * bt[i].y + bt[i].x;
bool pre_score = gr[idx] == my_id;
paint(gr, bt[i].x, bt[i].y, bt[i].id);
bool post_score = gr[idx] == my_id;
modify_idxs[num_modified_value++] = idx;
score_delta_value += post_score - pre_score;
}
*num_modified = num_modified_value;
*score_delta = score_delta_value;
}
static inline int mc_calc_score(const uint8_t *gr, uint8_t id) {
// println("calc_score gives");
int sc = 0;
for (int idx = 0; idx < width * height; idx++) {
sc += gr[idx] == id;
}
// print_int(sc);
return sc;
}
__attribute__((unused))
static void mc_setup_data() {}
__attribute__((unused))
static int mc_calcmove(void) {
const int dxes[5] = {1, 0, -1, 0, 0}, dyes[5] = {0, 1, 0, -1, 0};
int meIdx = -1;
for (int i = 0; i < nbots; i++) {
if (bots[i].id == my_id) {
meIdx = i;
break;
}
}
int maxscore = -1, maxat = -1;
uint8_t grid2[MAXSZ * MAXSZ];
struct bot bots2[MAXBOTS];
uint8_t grid3[MAXSZ * MAXSZ];
struct bot bots3[MAXBOTS];
for (int i = 0; i < 5; i++) {
// println("Main iteration i=");
// print_int(i);
const int nx = bots[meIdx].x + dxes[i];
const int ny = bots[meIdx].y + dyes[i];
if (nx < 0 || nx >= width || ny < 0 || ny >= height) {
continue;
}
memcpy_x(grid2, grid, width * height);
memcpy_x(bots2, bots, nbots * sizeof(struct bot));
// println("After grid2 memcpy");
bots2[meIdx].x = nx;
bots2[meIdx].y = ny;
paint(grid2, nx, ny, my_id);
memcpy_x(grid3, grid2, width * height);
int base_score = mc_calc_score(grid3, my_id);
int score = 0;
for (int playouti = 0; playouti < 100; playouti++) {
// println("Playout iteration playouti=");
// print_int(playouti);
int modified[MAXBOTS * 5];
int num_modified = 0;
memcpy_x(bots3, bots2, nbots * sizeof(struct bot));
score += base_score;
for (int si = 0; si < 5; si++) {
mc_random_step(grid3, bots3, meIdx, i, modified, &num_modified, &score);
}
for (int j = 0; j < num_modified; j++) {
grid3[modified[j]] = grid2[modified[j]];
}
}
// println("Direction score");
// print_int(i);
// print_int(score);
if (score > maxscore) {
maxscore = score;
maxat = i;
}
}
if (maxscore == -1) return rand() % 5;
else return maxat;
}
/// -------------------- ENTRY FUNCTION AND MISC --------------------
__attribute__((unused))
static void square_setup_data() {}
__attribute__((unused))
static int square_calcmove() {
static int num = 0;
int ret = num;
num = (num + 1) % 4;
println("square_calcmove");
print_int(ret);
return ret;
}
static void populate_ptrs() {
ptrs[0] = &width;
ptrs[1] = &height;
ptrs[2] = &nbots;
ptrs[3] = &round_idx;
ptrs[4] = &total_rounds;
ptrs[5] = &my_id;
ptrs[6] = grid;
ptrs[7] = bots;
ptrs[8] = rand_state;
}
#define CAT_(a,b) a##b
#define CAT(a,b) CAT_(a,b)
// The algorithm to use. I love DCE.
#define USED_CALCMOVE_PREFIX p_
WASM_EXPORT
int entry_fn(int mode) {
if (mode == 0) {
populate_ptrs();
// sizeof(void*) == sizeof(int) == 4 in wasm
return (int)ptrs;
}
if (mode == 1) {
CAT(USED_CALCMOVE_PREFIX, setup_data)();
return 0;
}
if (mode == 2) {
return CAT(USED_CALCMOVE_PREFIX, calcmove)();
}
// Do not delete this; these functions NEED to be used at least once
// to emit the imports, and the imports are necessary for the indices
// to work out for the hotpatcher. Even though this mode is never used
// at all.
if (mode == 1234567) {
println("");
print_int(42);
}
return -1;
}
Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
You can’t perform that action at this time.