Return to Answer

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 32) n++;
            else if (*str == 10) break;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 32) n++;
            else if (*str == 10) break;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

Rationale

By the pigeon-hole principle (aka Dirichlet's principle, hence the name of the bot), if there are N competing bots then there is a number w in [1..1+N/2] which either won or would have won if selected. I therefore conclude that the optimal strategy will not select numbers greater than 1+N/2. But if N is even, selecting 1+N/2 creates a smaller winning slot. Therefore the slots which are worth selecting are [1..(N+1)/2].

That leaves the question of how to select a slot. For small numbers of bots I verified that there's a Nash equilibrium when each bot selects uniformly among the candidates, and I strongly suspect that this will continue to hold true.

The minor deviation in this bot's strategy from the theoretical one is simply metagaming.

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 10) n++;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 32) n++;
            else if (*str == 10) break;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 2;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 10) n++;
    }

    n /= 2;
    if (n > 100) n = 100;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 1 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.

dirichlet.c

#include <fcntl.h>
#include <stdint.h>
#include <stdio.h>

main(int argc, char* argv[])
{
    int handle;
    char *str;
    int32_t bits, val, n = 0;

    if (argc) {
        for (str = argv[1]; *str; str++)
            if (*str == 10) n++;
    }

    n /= 2;
    if (n > 99) n = 99;

    handle = open("/dev/urandom", O_RDONLY);
    do {
        read(handle, &bits, sizeof bits);
        bits &= 0x7fffffff;
        val = bits % n;
    } while (bits - val + (n-1) < 0);
    close(handle);

    printf("%d", 2 + val);
}

I think this goes through random bits too fast to use /dev/random, however much I'd prefer to. If anyone wants to test it on Windows you'll have to port it yourself, because I don't have access to a Windows box with a C compiler.