Here is the chat room for this challenge. This is my first one so I'm open to suggestions!

ALSO: If you don't know Python, try to code up a bot in your language of choice. I'll do my best to convert it.

Reaper is a game concept developed by the Art of Problem Solving which involves patience and greed. After modifying the game to fit a KOTH style contest (Thanks to @NathanMerrill and @dzaima for your suggestions and improvements), here is the challenge.

The game works as the following: we have a value known as the Reap that multiplies by a given constant every tick. After each tick, each bot has the option of "reaping", which means adding the current value of Reap to one's score, and reducing Reap down to 1.

However, there's a fixed number of ticks that a bot must wait in between "reaps", and a fixed number of points necessary to win the game.

Simple enough? Here are your inputs:

I/O

You are to write a function in Python 3 that takes 3 inputs. The first is self, used for referencing class objects (shown later). The second is the Reap, the current value of the Reap that you would earn if you were to "reap". The third is prevReap, a list of the bots that reaped during the previous tick.

Other objects you can access in your function:

self.obj: An object for your use to store information between ticks.
self.mult: The multiplier that Reap is multiplied by each tick
self.win: The score you need to win
self.points: Your current set of points
self.waittime: The amount of ticks that you must wait between reaps during the game
self.time: The number of ticks since your last reap
self.lenBots: The number of bots (including you) in the game.
self.getRandom(): Use to produce a random number between 0 and 1.

You MUST not edit any of the contents of these objects, except for self.obj.

You must output 1 to reap, and anything else (or nothing) to not reap. Note that if you reap when you haven't waited enough ticks, I'll ignore the fact that you have chosen to reap.

Rules

The parameters I will be using are winning_score=10000, multiplier=1.6-(1.2/(1+sqrt(x))), waittime = floor(1.5*x) where x is the number of bots in the KOTH.

  • The game ends when a player (or multiple) reach the winning score.
  • When multiple bots ask to reap at once, priority is given to the bots who have waited longer(in case of ties, the bots that have waited the max time all are allowed to reap and gain the points in the Reap)
  • Your bot must take no more than 100 ms on average across 5 ticks.
  • If you want to import libraries, ask! I'll try to add any libraries that I can run on my desktop version of Python (math is already imported: feel free to use it)
  • All of the standard loopholes for KoTHs, such as duplicate bots, 1-up bots, etc, are similarly banned.
  • Any bots that use any sort of randomness must use the getRandom function I've provided.

Below is the Controller. To use it, add the name of your function to BotList as a string, and then add the function to the code. Modify multiplier to change what the Reap is multiplied by each tick, modify winning_score to change what score is necessary to end the game, and modify waittime to change the number of ticks to wait between reaps.

import random as rn
rn.seed(12321) #subject to change. Do not depend on this exact seed.
import math
#Modify these to use the controller
BotList = []
winning_score = 10000
multiplier=1.6-(1.2/(1+math.sqrt(len(BotList))))
waittime=int(1.5*len(BotList))

#This is the controller. Paste your function above this.
class Moderator:
    def __init__(self,FuncNames,winning_score,multiplier,waittime,lenBots):
        self.ReapBots = [ReapBot(eval(i),waittime,winning_score,multiplier,lenBots) for i in FuncNames]
        self.win = winning_score
        self.mult = multiplier
        self.wait = waittime
        self.Reap = 1
        self.prevReap=[]
        self.winner = []
    def __iter__(self):
        return self
    def winning(self):
        if len(self.winner)==1:
            print("The winner is "+self.winner[0])
        else:
            print("The winners are "+", ".join(self.winner))
    def results(self):
        print("Final Standings")
        for i in self.ReapBots:
            print(i)
    def __next__(self):
        if self.winner!=[]:
                raise StopIteration
        ReapList=[]
        for i in self.ReapBots:
            ReapList.append([i,i.func(self.Reap,self.prevReap)])
            i.time+=1
        Reapers = [i[0] for i in ReapList if i[1]==1 and i[0].time>=self.wait]
        if Reapers == []:
            self.prevReap=[]
            self.Reap*=self.mult
        else:
            waitmax = max([i.time for i in Reapers])
            SuccReaps = [i for i in Reapers if i.time==waitmax]
            for i in SuccReaps:
                i.time=0
                i.points+=self.Reap
            self.winner=[i.name for i in SuccReaps if i.points>=self.win]
            self.Reap=1
            self.prevReap=[i.name for i in SuccReaps]
        return(self.prevReap)
class ReapBot:
    def __init__(self, function, waittime, winning_score, multiplier,lenBots):
        self.func=lambda Reap, prevReap:function(self,Reap,prevReap)
        self.win = winning_score
        self.mult = multiplier
        self.obj=None
        self.points=0
        self.lenBots=lenBots
        self.waittime=waittime
        self.time=waittime
        self.name = function.__name__
    def __str__(self):
        return("Bot "+self.name+" : "+str(self.points)+" points")
    def getRandom(self):
        return(rn.random())
Mod = Moderator(BotList,winning_score,multiplier,waittime,len(BotList))
Moves = [i for i in Mod]
Mod.winning()
Mod.results()

For your convenience, here are some sample (and rather silly) bots. Submitting bots similar to these will not be permitted. However, they demonstrate how the controller works.

def Greedybot(self,Reap, prevReap):
    return 1
def Randombot(self,Reap, prevReap):
    if self.obj == None:
        self.obj=[]
    self.obj.append(prevReap)
    if self.getRandom()>0.5:
        return 1

The following code has these two bots built into it

import random as rn
rn.seed(12321) #subject to change. Do not depend on this exact seed.
import math
#Modify these to use the controller
BotList = ['Greedybot','Randombot']
winning_score = 10000
multiplier=1.6-(1.2/(1+math.sqrt(len(BotList))))
waittime=int(1.5*len(BotList))
def Greedybot(self,Reap, prevReap):
    return 1
def Randombot(self, Reap, prevReap):
    if self.obj == None:
        self.obj=[]
    self.obj.append(prevReap)
    if self.getRandom()>0.5:
        return 1
#This is the controller. Paste your function above this.
class Moderator:
    def __init__(self,FuncNames,winning_score,multiplier,waittime,lenBots):
        self.ReapBots = [ReapBot(eval(i),waittime,winning_score,multiplier,lenbots) for i in FuncNames]
        self.win = winning_score
        self.mult = multiplier
        self.wait = waittime
        self.Reap = 1
        self.prevReap=[]
        self.winner = []
    def __iter__(self):
        return self
    def winning(self):
        if len(self.winner)==1:
            print("The winner is "+self.winner[0])
        else:
            print("The winners are "+", ".join(self.winner))
    def results(self):
        print("Final Standings")
        for i in self.ReapBots:
            print(i)
    def __next__(self):
        if self.winner!=[]:
                raise StopIteration
        ReapList=[]
        for i in self.ReapBots:
            ReapList.append([i,i.func(self.Reap,self.prevReap)])
            i.time+=1
        Reapers = [i[0] for i in ReapList if i[1]==1 and i[0].time>=self.wait]
        if Reapers == []:
            self.prevReap=[]
            self.Reap*=self.mult
        else:
            waitmax = max([i.time for i in Reapers])
            SuccReaps = [i for i in Reapers if i.time==waitmax]
            for i in SuccReaps:
                i.time=0
                i.points+=self.Reap
            self.winner=[i.name for i in SuccReaps if i.points>=self.win]
            self.Reap=1
            self.prevReap=[i.name for i in SuccReaps]
        return(self.prevReap)
class ReapBot:
    def __init__(self, function, waittime, winning_score, multiplier,lenBots):
        self.func=lambda Reap, prevReap:function(self,Reap,prevReap)
        self.win = winning_score
        self.mult = multiplier
        self.obj=None
        self.points=0
        self.waittime=waittime
        self.time=waittime
        self.lenBots=lenBots
        self.name = function.__name__
    def __str__(self):
        return("Bot "+self.name+" : "+str(self.points)+" points")
    def getRandom(self):
        return(rn.random())
Mod = Moderator(BotList,winning_score,multiplier,waittime,len(BotList))
Moves = [i for i in Mod]
Mod.winning()
Mod.results()

Final Notes

The way I intend to score the bots is by running the Controller on the bots for 1000 different random seeds, and count the number of wins per bot. I hope that this will reduce the effect of randomness on the success of the bots. I'll probably stop accepting submissions in around 1-2 weeks

Edits

  • Thanks to @Renzee's idea, I've just added len(BotList) as a parameter usable to your bots. Just use self.lenBots. Just as before, do not change the value of the parameter.
  • the two sample bots I've provided will not be participating, nor will any bots similar.

Edits2

  • I spent around an hour debugging all of the typos in the submissions so far, as well as converting them to Python 3. I would ask kindly as for future submissions to both be written in Python 3, and be tested with the Controller I've provided.

For those interested, here is the Controller with the 7 submissions so far built into it: Try it Online

The results were as follows:

The winner is Averager
Final Standings
Bot Sniper : 6240.226527490211 points
Bot grim_reaper : 1 points
Bot Every50 : 0 points
Bot Jack : 4798.317108743723 points
Bot mess : 7812.425255928748 points
Bot BetterRandom : 0 points
Bot Averager : 10001.974786438755 points

This question has an open bounty worth +50 reputation from Rushabh Mehta ending in 3 days.

This question has not received enough attention.

I need more bots yall. This challenge won't work without them

  • Let's say two bots reap at the same time, and the one with the longest waiting time wins. Will the other bot also have its waiting time enabled despite that it wasn't able to actually reap this round, basically wasting its 'reap'? And what happens when two bots reap at the same time, with the same waiting time? – Kevin Cruijssen Sep 13 at 8:06
  • 1
    It is allowed to use len(BotList)? – Renzeee Sep 13 at 13:05
  • 1
    @Renzeee Ooo didn't think about that! I'll make a quick modification. – Rushabh Mehta Sep 13 at 13:06
  • 1
    @Renzeee Oh, that's certainly something useful to consider. Might make a second bot similar to my Every 50, but with actual calculations in the bot itself, instead of what I did in my description based on 25 bots in play. Will first wait a bit too see other people's bots however. Rushabh Mehta, will there be a deadline / final date when all the bots will be run and a winner is determined? – Kevin Cruijssen Sep 13 at 13:21
  • 1
    @Rushabh Mehta Gotcha, I'll refrain. I just asked b/c I was independently tracking other bots' scores and waittimes in order to snipe them, and I am lazy. :) – Triggernometry Sep 13 at 21:19

Sniper

A bot fueled by spite. Keeps track of opponent's cooldowns and scores. Attempts to keep others from winning. Pretty much never actually wins, but makes the game frustrating to play for others.

EDIT:

  • If reaping would cause it to win, reap.
  • If no one is >= 70% of the winning score:

    • If everyone else is on their cooldown, wait until the last possible moment to reap.
    • If anyone else would win by reaping the current value, and they are active now or would be active next turn, reap.
    • If at least half of the other users are on their cooldown, attempt to reap. This makes it difficult to target specific opponents, and so was removed.
    • Otherwise, reap 25% of the time (essentially to guarantee that this bot does reap SOMETIMES, just in case something weird happens, like everyone is waiting several turns).
  • If someone IS >= 70% of the winning score:

    • If Sniper can win a tiebreaker, and next round would be above the average Reap value for the highest scoring opponent, reap
    • If highest scoring opponent will leave their cooldown next turn, reap.
def Sniper(self, Reap, prevReap):
    # initialize opponents array
    if not hasattr(self.obj, "opponents"):
        self.obj.opponents = {}

    # initialize previous Reap value
    if not hasattr(self.obj, "lastReap"):
        self.obj.lastReap = 0

    # increment all stored wait times to see who will be "active" this turn
    for opponent in self.obj.opponents:
        self.obj.opponents[opponent]["time"] += 1

    # update opponents array
    for opponent in prevReap:
        # don't track yourself, since you're not an opponent
        if opponent != "Sniper":
            # initialize opponent
            if opponent not in self.obj.opponents:
                self.obj.opponents[opponent] = {"time": 0, "points": 0, "num_reaps": 0, "avg": 0}
            self.obj.opponents[opponent]["time"] = 0
            self.obj.opponents[opponent]["points"] += self.obj.lastReap
            self.obj.opponents[opponent]["num_reaps"] += 1
            self.obj.opponents[opponent]["avg"] = self.obj.opponents[opponent]["points"] / self.obj.opponents[opponent]["num_reaps"]

    # done "assigning" points for last round, update lastReap
    self.obj.lastReap = Reap

    # get current 1st place(s) (excluding yourself)
    winner = "" if len(self.obj.opponents) == 0 else max(self.obj.opponents, key=lambda opponent:self.obj.opponents[opponent]["points"])

    # you are ready now
    if self.time >= self.waittime:
        # current Reap is sufficient for you to win
        if self.points + Reap >= self.win:
            return 1

        if (
                # a 1st place exists
                winner != ''
                # if current 1st place is close to winning
                and self.obj.opponents[winner]["points"] / self.win >= .7
        ):
            if (
                    # next round's Reap value will be above opponent's average Reap
                    (Reap * self.mult >= self.obj.opponents[winner]["avg"])
                    # we have been waiting at least as long as our opponent (tiebreaker)
                    and self.time >= self.obj.opponents[winner]["time"]
            ):
                return 1

                # current 1st place opponent will be active next round
            if self.obj.opponents[winner]["time"] + 1 >= self.waittime:
                return 1

        else:
            if (
                    # everyone is waiting for their cooldown
                    all(values["time"] < self.waittime for key, values in self.obj.opponents.items())
                    # and we're tracking ALL opponents
                    and len(self.obj.opponents) == self.lenBots - 1
                    # at least one person will be ready next turn
                    and any(values["time"] + 1 >= self.waittime for key, values in self.obj.opponents.items())
            ):
                return 1

            if (
                    # opponent will be active next round
                    any( (values["time"] + 1 >= self.waittime)
                         # current Reap value would allow opponent to win
                         and (values["points"] + Reap >= self.win) for key, values in self.obj.opponents.items())
            ):
                return 1

            if (
                    # a 1st place exists
                    winner != ''
                    # current 1st place opponent will be active next round
                    and (self.obj.opponents[winner]["time"] + 1 >= self.waittime)
                    # next round's Reap value will be above their average Reap
                    and (Reap * self.mult >= self.obj.opponents[winner]["avg"])

            ):
                return 1

            # # at least half of opponents are waiting for their cooldown
            # if sum(values["time"] < self.waittime for key, values in self.obj.opponents.items()) >= (self.lenBots - 1) / 2:
            #     return 1

            # 25% of the time
            if self.getRandom() <= .25:
                return 1

    # default return: do not snipe
    return 0
  • Nice bot! +1. It'll be interesting to see how this does. – Rushabh Mehta Sep 13 at 23:56
  • 1
    I think you should use self.obj.opponents[opponent]["time"] += 1 in the first for-loop and self.obj.lastReap at the end of the second for-loop. Besides that, nice ideas. I'm curious how it would work out against a lot of other bots. When I'm using a lot of greedy and random bots it will just reap asap because most of the time half of the bots cannot reap. But of course those are not realistic competitors. – Renzeee Sep 14 at 7:24
  • @Triggernometry You should join the chat. Also, check the edits I've posted. Please ensure that the changes I made to your bot are correct. – Rushabh Mehta Sep 14 at 13:17

Indecisive Twitchy Mess

def mess(self, Reap, prevReap):
    if not hasattr(self.obj, "start"):
            self.obj.start = False
    if self.time < self.waittime:
        return 0
    if self.points + Reap >= self.win:
            return 1
    if Reap >= self.waittime / (self.lenBots + 2):
        self.obj.start = True
    if self.obj.start:
        return 1 if self.getRandom() > 0.2 else 0
    return 1 if self.getRandom() > 0.8 else 0

This bot does the usual checks first(Can I reap, can I win?) and then looks for a target value before it reaps. However, it's indecisive, so after it reaches the target, it wonders how much longer it can wait and doesn't reap immediately. In addition, it's twitchy, so it might accidentally "hit the button" and reap before the target.

Fun fact: This is basically how I play reaper as a human.

  • Nice bot +1. I'll take a closer look at it in a bit. Join the chat if u haven't already – Rushabh Mehta Sep 15 at 21:46
  • @RushabhMehta Now with less indecision ;p – Quintec 20 hours ago
  • I'll add your changes when I can! – Rushabh Mehta 20 hours ago

Every 50

This bots will reap every time the Reap amount is above 50.

Why 50?

If I make the assumption there will be 25 bots in play, it means the multiplier = 1.6-(1.2/(1+sqrt(25))) = 1.4 and the waittime = floor(1.5*25) = 37. Since the Reap starts at 1, it will go up like this:

Round: 1  2    3     4      5      6      7      8       9       10      11      12      13      14      15       16       17       18       19       20       etc.
Reap:  1  1.4  1.96  2.744  ~3.84  ~5.39  ~7.53  ~10.54  ~14.76  ~20.66  ~28.92  ~40.50  ~56.69  ~79.37  ~111.12  ~155.57  ~217.79  ~304.91  ~426.88  ~597.63  etc.

As you can see, it reaches above 50 after 13 ticks. Since the Reap will reset to 1 every time a bot reaps, and the waittime for a bot that reaps is 37, the likelihood a bot reaps sooner than later is pretty high, especially with bots similar to the example GreedyBot, which will reap as soon as their waittime is available again. At first I wanted to do 200 which is the 17th tick, somewhat in the middle of the 37 waiting time ticks, but with the assumption there are 25 bots in play there is a pretty high chance someone else snatches the Reap before me. So I lowered it to 50. It's still a nice rounded number, but especially because it's the 13th tick (with 25 bots), and 13 and 'reaping' also fit a bit in that same 'evil' genre.

Code:

The code is laughable trivial..

def Every50(self, Reap, prevReap):
  return int(Reap > 50)

Notes:

This bot is pretty bad with low amount of bots in play. For now I will leave it, and I might make a better bot actually calculating the best time to Reap. With an extremely low amount of bots in play the waittime is much lower as well of course, so even GreedyBot might win quite easily from this bot if the waittime is low enough.

Hopefully more people will add a lot more bots. ;p

  • def Every49(self, Reap, prevReap): return Reap > 49 Your move. – Quintec Sep 13 at 13:19
  • @Quintec Hehe. With 25 bots in play it would mean it's still the 13th tick and we both win the Reap, so I don't mind sharing the victory with you, lol. ;p – Kevin Cruijssen Sep 13 at 13:23
  • You might want to put int around the inequality, since 1 is the real command – Rushabh Mehta Sep 13 at 13:23
  • @Quintec i'm aware ur kidding, but I won't allow 1-up or duplicate bots – Rushabh Mehta Sep 13 at 13:24
  • @RushabhMehta I don't program in Python very often, so was indeed already doubting whether I should add the cast to make the True an explicit 1. Figured the True == 1 check would still return True for my bot adding it to the lists of Reapers in your next function, but I added the cast to int anyway as you suggested. – Kevin Cruijssen Sep 13 at 13:26

Jack

This is a simple bot with 4 rules:

  • Don't reap when it doesn't do anything
  • Always reap when reaping lets us win
  • Also reap when there has not been reaped for 4 ticks
  • Otherwise do nothing

I have optimized the 4 ticks versus the current existing bots (Sniper, grim_reaper, Every50, mess, BetterRandom, Averager).

def Jack(self, Reap, prevReap):
    if self.time < self.waittime:
        return 0
    if self.win - self.points < Reap:
        return 1
    if self.mult ** 4 <= Reap:
        return 1
    return 0

I have tried to stay with my old solution (5 ticks) but also reap if you haven't reap for longer than X ticks, and then reap after fewer ticks have been passed during non-reaping (i.e. 5, if waited longer than self.waittime + 5, also reap if not been reaped for 4 ticks). But this didn't improve just always reaping after 4 ticks instead of 5.

Grim Reaper

This bot keeps a running average of the values of all the previous reaps as well as the time each bot has been waiting. It reaps when it has been waiting longer than 3/4 of the other bots and the reap is at least 3/4 the size of the average reap seen so far. The goal is to grab a lot of reasonably sized, low risk reaps.

def grim_reaper(self, Reap, prevReap):
    if self.obj == None:
        self.obj = {}
        self.obj["reaps"] = []
        self.obj["prev"] = 1
        self.obj["players"] = {i:0 for i in range(math.ceil(self.waittime / 1.5))}
    if Reap == 1 and len(prevReap) > 0:
        self.obj["reaps"].append(self.obj["prev"])
        for player in prevReap:
            self.obj["players"][player] = 0

    retvalue = 0
    if (len(self.obj["reaps"]) > 0 
         and Reap > sum(self.obj["reaps"]) / len(self.obj["reaps"]) * 3. / 4.
         and sum([self.time >= i for i in self.obj["players"].values()]) >= len(self.obj["players"].values()) * 3 / 4):
        retvalue = 1

    for player in self.obj["players"]:
        self.obj["players"][player] += 1
    self.obj["prev"] = Reap
    return retvalue

Edit: Fixed some embarrassing syntax errors.

Try it Online

  • 1
    You should use self.obj.reaps instead of self.reaps and self.obj instead of self.object and prevReap instead of prevLeap and add () after self.obj.players.values twice. And I think self.obj.reaps = [] won't work unless self.obj is an object. I'm not completely sure if everything then still works as intended and if all of what I said is true, but after these changes and using a dummy Object for self.obj when it doesn't exists yet, your code compiles for me. – Renzeee Sep 13 at 11:46
  • @ZacharyColton You don't need to import math. It's already imported – Rushabh Mehta Sep 13 at 13:27
  • @RushabhMehta I added class Object(object): [newline] pass on top and used self.obj = Object() in the if not hasattr(..) (if I remember correctly). – Renzeee Sep 13 at 14:28
  • @Renzeee aha ic – Rushabh Mehta Sep 13 at 14:30
  • @ZacharyCotton You should join chat. – Rushabh Mehta Sep 14 at 13:34

Averager

def Averager(self,Reap,prevReap):
    returner = 0
    if not hasattr(self.obj,"last"):
        self.obj.last = Reap
        self.obj.total = 0
        self.obj.count = 0
        returner = 1
    else:
        if len(prevReap) > 0:
            self.obj.total += self.obj.last
            self.obj.count += 1
        self.obj.last = Reap
    if self.obj.count > 0 and Reap > self.obj.total / self.obj.count:
        returner = 1
    return returner

This bot tries to reap any time the current Reap value is above the average Reaped value.

BetterRandom

def BetterRandom(self,reap,prevReap):
    return self.getRandom()>(reap/self.mult**self.waittime)**-0.810192835

The bot is based on the assumption that the chance to reap should be proportional to the reap size because a point is a point, no matter when it's gotten. There is always a very small chance to reap, this keeps the behavior exploitable. First I thought it would be directly proportional and assumed the proportionality constant to be around 1/mult^waittime (the maximum reap assuming at least one bot plays greedy) after running some simulations I found that this was indeed the optimal constant. But the bot was still outperformed by Random so I concluded the relation wasn't directly proportional and added a constant to calculate what the relation was. After some simulations I found that against my test set of bots -1.5 was optimal. This actually corresponds to an inversely proportional relationship between the reap chance and reap*sqrt(reap) which is surprising. So I suspect this is highly depended on the specific bots so a version of this bot that calculates k while playing would be better. (But I don't know if you are allowed to use data from previous rounds).

EDIT: I made program to find the kind of proportionality automatically. On the test set ["myBot("+str(k)+")","Randombot","Greedybot","Every50","Jack","grim_reaper","Averager","mess"] I found the new value.

  • i'll add some new stats using your bot soon – Rushabh Mehta yesterday
  • It looks like (reap/self.mult**self.waittime)**-0.810192835 is always above 1, i.e. self.getRandom() is never higher. – Renzeee yesterday

Your Answer

 

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.