Return to Revisions

#Sylver Coinage KotH king-of-the-hillnumber-theorypython

Sylver Coinage is a 2-player mathematical game that has the following rules:

1. Two players take turns announcing a natural number each time.
2. Each number announced must be unrepresentable as the sum of non-negative multiples of the numbers announced before.

Eg. if the first three numbers announced are \$\{6, 11, 15\}\$, then you cannot announce any numbers representable as \$6n_1+11n_2+15n_3\$, where \$n_1,n_2,n_3\ge0\$. You can announce, for example, \$16\$, though.

3. The player who announced a number not complying with Rule 2, or the number 1, loses.

Here is a twist -- R. L. Hutchings proved that announcing a prime number as the first play provides a winning strategy for the first player, although the detail of the strategy is not yet known. So I put a restriction here: the first player cannot announce a prime number in the first step.

##Technical Information

A bot playing the game will have to implement a Python 3 class with two methods: announce() and learn(). announce() should receive a list of numbers (possibly empty) and return a single integer, and learn() should receive two integers (id of the first move and second move) and the complete list of the numbers in the last game played.

Here is a sample implementation. Note: DO NOT use this as your submission -- this sample only serves as a demonstration, and it may announce numbers that violate Rule 2.

class SampleBot:
    def __init__(self, id):
        self.id = id

    def announce(self, list):
        import random
        return random.randint(1, 101)

    def learn(self, first, second, list):
        pass

###Test Drive

class SampleBot:
    def __init__(self, id):
        self.id = id

    def announce(self, list):
        import random
        return random.randint(1, 101)

    def learn(self, first, second, list):
        pass

# very inefficient
def islinearcomb(n, l):
    if len(l):
        for i in range(0, n + 1, l[0]):
            if i == n or (len(l) > 1 and islinearcomb(n - i, l[1:])):
                return True
    return False

def isprime(n):
    if n % 2 == 0:
        return False
    i = 3
    while i * i <= n:
        if n % i == 0:
            return False
        i += 2
    return True

lose = -1
turn = 0
nums = []
bots = [SampleBot(0), SampleBot(1)] # replace with your bots here.
while lose < 0:
    v = bots[turn].announce(nums)
    print("{0}({1}) announced {2}".format(type(bots[turn]).__name__, bots[turn].id, v))
    if islinearcomb(v, nums):
        str = ""
        for i in range(0, len(nums)):
            if i:
                str += "+"
            str += "{0}n_{1}".format(nums[i], i)
        print("{0}({1}) announced a number that is representable by {2}".format(type(bots[turn]).__name__, bots[turn].id, str))
        lose = turn
    elif v == 1:
        print("{0}({1}) announced 1".format(type(bots[turn]).__name__, bots[turn].id))
        lose = turn
    elif isprime(v) and len(nums) == 0:
        print("{0}({1}) announced a prime number on the first move".format(type(bots[turn]).__name__, bots[turn].id))
        lose = turn
    nums += [v]
    turn = 1 - turn
print("{0}({1}) wins".format(type(bots[1 - lose]).__name__, bots[1 - lose].id))
for b in bots:
    b.learn(bots[0].id, bots[1].id, nums)

##Schedule

Submissions will be open until todo: date here. After that 100 complete round-robin rounds will be done. Each pair of bots will compete twice in each round, one with the first bot announcing first, and one with the second bot announcing first. Each win brings 3 points, each draw brings 1 point, and each lose brings no points. The bot with the highest points after 100 rounds wins. The tiebreaker will be as follows:

1. Points got
2. Wins achieved
3. Drawing lots