Let's play some Reaper - Closed for Submissions

Question

NOTE: The winner of this competition is Jack!!!. No more submissions will be accepted.

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

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.

You can find the controller in the TIO link below. 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.

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

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

FINAL RESULTS

WOO THEY ARE FINALLY HERE! Check the TIO Link above to see what code I used to generate the final standings. The results are not terribly interesting. Over the 1000 runs I did with different random seeds, the results were

1000 wins - Jack
0 wins - everyone else

Congratulations to the Bounty winner Jack!! (aka @Renzeee)

Answer 1

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.

Answer 2

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

Bored

Just for fun, this bot was brought along by a friend and doesn't actually want to be here. They roll a d16 until they get a number in 1-9, then they attempt to reap anytime a number contains the chosen digit. (Going to look for a d10 would disrupt the game, which is rude, and 0 is just too easy!)

def Bored(self, Reap, prevReap):
    # if this is the first round, determine your fav number
    if not hasattr(self.obj, "fav_int"):
        r = 0

        while r == 0:
            # 4 bits are required to code 1-9 (0b1001)
            for i in range(0, 4):
                # flip a coin. Puts a 1 in this bit place 50% of the time
                if self.getRandom() >= .50:
                    r += 2**i
            # if your random bit assigning has produced a number outside the range 1-9, try again
            if not (0 < r < 10):
                r = 0

        self.obj.fav_int = r

    # 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
        # do you like this value?
        if str(self.obj.fav_int) in str(Reap):
            return 1
        # do you like your wait time?
        if self.time % int(self.obj.fav_int) == 0:
            return 1

    # default return: do not reap
    return 0

Answer 3

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 3 ticks
• Otherwise do nothing

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

def Jack(self, Reap, prevReap):
    if self.time < self.waittime:
        return 0
    if self.win - self.points < Reap:
        return 1
    if self.mult ** 3 <= 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.

Answer 4

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

Answer 5

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.

Answer 6

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

Answer 7

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.

Answer 8

Target

def target(self,Reap,prevReap):
    if not hasattr(self.obj, "target_time"):
        self.obj.target_time = -1
        self.obj.targeting = False
        self.obj.target = None
    if self.obj.target_time >= 0:
        self.obj.target_time += 1

    if self.time < self.waittime:
            return 0
    if self.points + Reap >= self.win:
        return 1
    if len(prevReap) > 0:
        if not self.obj.targeting:
            self.obj.target_time = 0
            self.obj.target = prevReap[int(self.getRandom() * len(prevReap))]
            self.obj.targeting = True
    if self.waittime <= self.obj.target_time + 1:
        self.obj.targeting = False
        self.obj.target = None
        self.obj.target_time = -1
        return 1
    return 0

My chances of winning with mess are almost none now, so time to mess up all the other bots in as many ways as possible! :)

This bot functions similar to sniper. Whenever someone reaps, it picks a random target from whoever reaped. Then, it simply waits until that target almost can reap again and snipes it. However, it doesn't change focus - once you've been chosen and locked on, you can't escape :)

Answer 9

EveryN

I guess it's time for my second bot right before the deadline.

This bot will:

• Skip when it's still in its waiting time for the last Reap
• Reap when it can win
• Reap when no one reaped for at least n rounds, where n is calculated with n = 3 + ceil(self.waittime / self.lenBots)

Code:

def every_n(self, Reap, prevReap):
    # Initialize obj fields
    if not hasattr(self.obj, "roundsWithoutReaps"):
        self.obj.roundsWithoutReaps = 0

    # Increase the roundsWithoutReaps if no bots reaped last round
    if len(prevReap) < 1:
        self.obj.roundsWithoutReaps += 1
    else
        self.obj.roundsWithoutReaps = 0
  
    # Skip if you're still in your waiting time
    if self.time < self.waittime:
        return 0
    # Reap if you can win
    if self.win - self.points < Reap:
        return 1
  
    # i.e. 25 bots: 3 + ceil(37 / 25) = 5
    n = 3 + math.ceil(self.waittime / self.lenBots)

    # Only reap when no bots have reaped for at least `n` rounds
    if self.obj.roundsWithoutReaps >= n:
        self.obj.roundsWithoutReaps = 0
        return 1
  
    return 0

I don't program in Python very often, so if you see any mistakes let me know.

Answer 10

Ongoing: My project to extend T4T to every open KOTH.

Tit for Tat

def t4t(self, r, p):
    if(not hasattr(self.obj,"last")): self.obj.last = self.win
    if(p):
        self.obj.last = r
        return 0

    # The usual checks
    if self.time < self.waittime:
        return 0
    if self.points + r >= self.win:
        return 1

    if(r >= self.obj.last):
        return 1

Tit for n Tats

def t4nt(self, r, p):
    n = 5 # Subject to change
    if(not hasattr(self.obj,"last")): self.obj.last = [self.win]*n

    if(p):
        self.obj.last.append(r)
        self.obj.last.pop(0)
        return 0

    # The usual checks
    if(self.time < self.waittime):
        return 0
    if(self.points + r >= self.win):
        return 1

    if(r >= self.obj.last[0]):
        return 1

---

Kevin

Just to keep you on your toes.

def kevin(just, a, joke):
    return 0

Answer 11

Average Joe

I got inspired by Averager and created a bot which calculates on average how many turns it takes before someone reaps and tries to reap one turn prior to that.

def average_joe(self, Reap, prevReap):

    if not hasattr(self.obj, "average_turns"):
        self.obj.turns_since_reap = 1
        self.obj.total_turns = 0
        self.obj.total_reaps = 0
        return 1

    if len(prevReap) > 0:
        self.obj.total_turns = self.obj.total_turns + self.obj.turns_since_reap
        self.obj.total_reaps += 1
        self.obj.turns_since_reap = 0
    else:
        self.obj.turns_since_reap += 1

    # Don't reap if you are in cooldown
    if self.time < self.waittime:
        return 0

    # Reap if you are going to win
    if self.win - self.points < Reap:
        return 1

    # Reap if it is one turn before average
    average_turns = self.obj.total_turns / self.obj.total_reaps

    if average_turns - 1 >= self.obj.turns_since_reap:
        return 1
    else:
        return 0

Answer 12

HardCoded

Yes, it is.

def HardCo(self,reap,prevReap):
    return reap > 2

Instead of averaging on the past reaps, use a pre-calculated average on a typical run. It's not going to get better with time anyway.