25
\$\begingroup\$

Test DriverChallenge DiscussionSubmit Adventurer

Treasure Room (Image Source)

Several rival adventurers are raiding the ruins for treasure, but they can only carry so much at a time and have their limits of endurance. They want to get the most valuable treasure and get out before they become too tired to continue. They are trying to become as rich as possible from their looting shenanigans.

Gameplay

Each adventurer begins in the first room of the dungeon with 1000 stamina points and 50kg of space in their backpack.

The game operates on a turn-based fashion, with all players resolving their turns simultaneously. Each turn, you can do one of the following actions:

  • Move to the next room.
  • Move to the previous room.
  • Bid stamina to take a treasure.
  • Drop a treasure.

Moving between rooms requires 10 stamina, plus 1 for every 5kg currently in your backpack, rounded up. For instance, an adventurer carrying 3kg of treasure requires 11 stamina to move and one carrying 47kg requires 20 stamina to move.

Dropping treasure requires 1 stamina regardless of the treasure dropped.

Upon exiting the ruins, no more turns will be taken by the player.

If a player cannot take any of these actions (due to shortage of stamina or absence of treasures), their adventurer dies of exhaustion, spilling their held treasure into the currently occupied room. Similarly, if a player attempts to do an invalid action, their adventurer will be killed by a trap instead, resulting in the same treasure spillage.

Bidding

The minimum bid for a treasure is 1 stamina per 1kg that the treasure weighs. You may also bid additional stamina points to be more likely to obtain the treasure. The stamina that was bid is consumed no matter what the outcome is.

In the event that multiple players have bid to take the same treasure, the player who bid highest gets the treasure. If more than one player made the highest bid, none of them will receive the treasure.

Win Condition

The player with the largest total value of treasures is the winner. In the unlikely event of a tie, ties go to the smallest total weight, then smallest number of treasures, then value of the most valuable treasure, second most valuable, third... until the tie is broken. In the near-impossible event that there is still a tie at this point, the test driver says "screw it" and the winner is thereby determined arbitrarily.

In the context of the tournament, players will be ranked with first place receiving 10 points, second place with 9 points, third place with 8 points, etc..., with dead players and adventurers with no treasures scoring 0 points.

About the Ruins

  • Each room initially contains between \$\lfloor{r \over 3}\rfloor + 3\$ and \$\lfloor{r \over 2}\rfloor + 5\$ treasures. (Where \$r\$ is the room number)
  • There are arbitrarily many rooms, limited only by adventurers' stamina and willingness to explore.
  • Each treasure will have a monetary value (in whole $) and a weight (in whole kg).
    • Treasures tend to be more valuable and plentiful as you go deeper into the ruins.
  • The specific formulas for generating treasures are as follows: (using \$xdy\$ notation for dice rolls)
    • Weight is generated first using the formula \$2d6 - 2\$ (minimum of 1)
    • Treasure value then is generated via \$1d[10 * w] + 2d[5 * r+ 10]\$ (where \$r\$ is the room number and \$w\$ is the weight)

Information Visible to Players

At each turn, players get the following information:

  • The number of the room they are currently in. This is 1-indexed, so conceptually the exit is at "room 0"
  • A list of treasures currently in the room
  • A list of other players who are also currently in the room.
  • Your current inventory of treasures
  • Your current stamina level

Coding

The test driver can be found here.

You should implement a subclass of this Adventurer class:

class Adventurer:
    def __init__(self, name, random):
        self.name = name
        self.random = random

    def get_action(self, state):
        raise NotImplementedError()

    def enter_ruins(self):
        pass

You only need to override the get_action method. enter_ruins is run before a game begins and is your chance to prepare whatever you wish to have ready for the game. You do not need to override __init__, and you really shouldn't. If your __init__ crashes, you will be disqualified.

get_action recieves a single argument which is a namedtuple with the following fields (in this order, if you prefer destructuring):

  • room: the number of the room you are currently in
  • treasures: the list of treasures in the room
  • players: the list of other players in the room. You only get the player name this way, so you do not know what bot is controlling them or their inventory/stamina.
  • inventory: the list of treasures in your backpack
  • stamina: your current stamina level

This object additionally provides two utility properties:

  • carry_weight: the total weight of all the treasures you are carrying
  • total_value: the total value of all the treasures you are carrying

The treasures and inventory lists contain namedtuples with these attributes:

  • name: the treasure's name (for cosmetic purposes)
  • value: the monetary value of the treasure in $.
  • weight: the treasure's weight in kg

get_action should return one of the following values/patterns:

  • 'next' or 'previous' to move to the next/previous rooms
  • 'take', <treasure index>, <bid> (yes, as a tuple, though any sequence will technically work as well) to bid on the treasure at the given index in the room's treasure list. Both arguments should be integers. Floats will be rounded down.
  • 'drop', <inventory index> to drop the carried treasure found at the given index. The index should (naturally) be an integer.

Other Restrictions

  • You may only use the random instance provided to you during initialization for pseudorandomness.
    • Anything else that might introduce behavioral nondeterminism is not allowed. The intent here is to make bots behave identically when given the same seed to aid in testing new bots (and potentially bugs in the test driver). Only cosmic radiation should cause any deviation/nondeterminism.
    • Keep in mind that hash codes are randomized in Python 3, so using hash for any decision making is not allowed. dicts are fine even when using iteration order for decisions since order has been guaranteed consistent since Python 3.6.
  • You may not circumvent the test driver using ctypes hacks or inspect stack voodoo (or any other method). There are some impressively scary things you can do with those modules. Please don't.
    • Each bot is sandboxed reasonably well via defensive copies and the natural immutability of namedtuples, but there are some unpatchable loopholes/exploits.
    • Other functionality from inspect and ctypes may be used as long as neither is used to circumvent controller functionality.
    • Any method of grabbing instances of the other bots in your current game is not allowed.
  • Bots should operate solo and may not coordinate with any other bots in any way for any purpose. This includes creating two bots with different goals such that one sacrifices itself for the success of the other. Once there are more than 10 competitors, you won't actually be guaranteed to have the two bots in the same game and adventurer names don't give any indication of the bot class, so these types of strategies are limited anyway.
  • There is currently no hard restriction on execution time, however I reserve the right to hard-restrict it in the future if tournaments start taking too long. Be reasonable and try to keep turn processing under 100ms, as I don't anticipate needing to restrict it below that threshold. (Tournaments will run in about 2 hours if all bots take about 100ms per turn.)
  • Your bot class must be named uniquely among all submissions.
  • You may not remember anything between games. (However, you can remember things between turns)
    • Don't edit sys.modules. Anything outside instance variables should be treated as a constant.
  • You may not modify any bot's code programmatically, including your own.
    • This includes deleting and restoring your code. This is to make debugging and tournaments more streamlined.
  • Any code that causes the controller to crash will be immediately disqualified. While most exceptions will be caught, some may slip through and segfaults are uncatchable. (Yes, you can segfault in Python thanks to ctypes)

Submissions

In order to aid answer scraping, indicate the name of your bot at the top of the answer with a #Header1 and ensure your answer includes at least one code block (only the first one in your answer will be used). You do not need to include any imports or docstrings, as they will be added automatically by the scraper.

I will be more inclined to upvote answers with detailed and understandable explanations. Others are likely to behave the same.

Roughly speaking, your answer should be formatted something like this:

# Name of Bot
Optional blurb

    #imports go here

    class BotName(Adventurer):
        #implementation

Explanation of bot algorithm, credits, etc...

(rendered as)

Name of Bot

Optional blurb

#imports go here

class BotName(Adventurer):
    #implementation

Explanation of bot algorithm, credits, etc...

Running the Test Driver Locally

You will need Python 3.7+ and I recommend you also install tabulate via pip. Scraping this page for submissions additionally requires lxml and requests. You should also use a terminal with support for ANSI color escapes for best results. Info on how to set this up in Windows 10 can be found here.

Add your bot to a file in a subdirectory within the same directory as ruins.py (ruins_bots by default) and be sure to add from __main__ import Adventurer to the top of the module. This is added to the modules when the scraper downloads your submission, and while it is definitely hacky, this is the most straightforward way of making sure your bot properly has access to Adventurer.

All bots in that directory will be loaded dynamically at runtime, so no further changes are necessary.

Tournament

The ultimate victor will be determined in a series of games with up to 10 bots in each game. If there are more than 10 total submissions, the top 10 bots will be determined by systematically partitioning them into groups of 10 until every bot has played (exactly) 20 games. The top 10 bots will be selected from this group with reset scores and will play games until the first place bot has achieved a 50 point lead over the second place bot or until 500 games have been played.

Until there are at least 10 submissions, empty slots will be filled with "Drunkards" which wander randomly through the ruins and take (and occasionally drop) random treasures until they run out of stamina and have to beeline to the exit.

Tournaments will be re-run weekly if there are new submissions. This is an open KOTH challenge with no set end date.

Leaderboard

From run on May 4, 2019 at 4:25PM MDT: (2019-05-04 4:25 -6:00)

Seed: K48XMESC
 Bot Class    |   Score |   Mean Score
--------------+---------+--------------
 BountyHunter |     898 |        7.301
 Scoundrel    |     847 |        6.886
 Accountant   |     773 |        6.285
 Ponderer     |     730 |        5.935
 Artyventurer |     707 |        5.748
 PlanAhead    |     698 |        5.675
 Sprinter     |     683 |        5.553
 Accomodator  |     661 |        5.374
 Memorizer    |     459 |        3.732
 Backwards    |     296 |        2.407

Update - Apr 15: a couple rule updates/clarifications

Update - Apr 17: banning a couple of notable edge cases of nefarious actions such as modifying other bots' code.

Update - May 4: Bounty awarded to Sleafar for absolutely destroying Backwards. Congratulations!

\$\endgroup\$
  • 1
    \$\begingroup\$ It's finally here! Guess I'll have to start making my bot now. \$\endgroup\$ – Belhenix Apr 12 at 17:56
  • 12
    \$\begingroup\$ Why the limit to one bot? I have several mutually exclusive ideas, and I'd rather not have to throw out a perfectly good bot each time I come up with a new one. \$\endgroup\$ – Mnemonic Apr 12 at 19:10
  • \$\begingroup\$ @Mnemonic, mostly it's to prevent displacing new submissions by using multiple near-identical bots. The other reason was to prevent bots from working together, but that is explicitly banned anyway. I'll consider allowing it. Those in favor of allowing multiple submissions, upvote Mnemonic's comment above. \$\endgroup\$ – Beefster Apr 12 at 19:14
  • 1
    \$\begingroup\$ @Draco18s If you have pip installed and on PATH (which is default for newer installations AFAIK) then from windows you can run pip install modulename in the command prompt. For other circumstances (which I don't know about), go to pip, search for the module needed and choose an option. \$\endgroup\$ – Artemis Fowl Apr 13 at 22:51
  • 1
    \$\begingroup\$ I'm guessing this will be a 'no', but are we allowed to save information through the tournament? (e.g when a bid worked) \$\endgroup\$ – Artemis Fowl Apr 13 at 22:54

13 Answers 13

4
\$\begingroup\$

Accountant

import math

class Accountant (Adventurer):
    def enter_ruins(self):
        self.goal = 5000
        self.diving = True

    def expected_rooms_left(self, state):
        if not self.diving:
            return state.room

        else:
            return (state.stamina - (50 - state.carry_weight)) / 14

    def ratio(self, state, treasure):
        stamina_cost = treasure.weight * (1 + 1/5 * self.expected_rooms_left(state)) + bool(state.players)
        ratio = (treasure.value / (self.goal - state.total_value)) / (stamina_cost / state.stamina)

        return ratio

    def get_action(self, state):
        room, treasures, players, inventory, stamina = state

        if stamina < room * (math.ceil(state.carry_weight / 5) + 10) + 40:
            self.diving = False
            return 'previous'

        worthwhile = []
        for i, treasure in enumerate(treasures):
            ratio = self.ratio(state, treasure)
            if ratio >= 1 and state.carry_weight + treasure.weight <= 50:
                worthwhile.append((ratio, i))

        if worthwhile:
            ratio, index = sorted(worthwhile, reverse=True)[0]
            treasure = treasures[index]
            return 'take', index, treasures[index].weight + bool(players)

        return 'next'

The Accountant is a very risk-averse person. He likes to be sure that what he does really is the best option in the given situation. So, he sets himself a goal, and only ever picks up treasure if his calculations show this sets him on the right track towards that goal. However, he is very bureaucratic and does not like dropping items he had already decided he wanted; any attempts to teach him to do so have so far resulted in the Accountant dropping an item, and then picking it up again immediately afterwards.

Possibly to be continued.

\$\endgroup\$
  • 1
    \$\begingroup\$ Nice job determining treasure worth. I definitely had in mind to write up some better "is it worth it" code, but hadn't gotten there yet. The scoundrel is coming for the accountant's bottom line, though... \$\endgroup\$ – Draco18s Apr 16 at 20:47
  • \$\begingroup\$ " any attempts to teach him to do so have so far resulted in the Accountant dropping an item, and then picking it up again immediately afterwards.". You could get around this by keeping a set of dropped treasure names. I had a feeling that treasure names would come in handy (even though they're just numbered right now) \$\endgroup\$ – Beefster Apr 17 at 22:37
  • \$\begingroup\$ Thanks, but I already figured out why it happened. Don't know if I'll fix it immediately though, since he rarely uses it when I tested putting it in. \$\endgroup\$ – ArBo Apr 18 at 7:17
2
\$\begingroup\$

Accomodator

Based loosly on my other LightWeight bot. Where LightWeight bot was simple, this bot is much more complex in order to accomodate interactions with other bots: both benign and deliberatly distruptive.

This bot will firstly sprint to a randomly assigned room and then will try to bid for the best value/weight ratio treasure, if there are any other players in the room then assume that they will also bid so instead bid for the second best treasure. If that bid fails then on the next turn bid for the next best treasure.

Once a bid was successful, repeat bidding for best/secondbest until no more treasures exist in the room then move deeper into the ruin

For each room enter into the ruin repeat bidding for best/secondbest until no more treasures exist in the room then move deeper into the ruin or if we detect that we cannot go any deeper then swap to 'Exiting' state and start to drop the worst treasure until we can guarantee that we can exit the ruin alive.

When in exiting state we will check to see if we can add 1kg treasure and still make it out alive, if so then we shall attempt to bid on a 1kg treasure, if not then we shall head to previous room.

Its performance is quite variable... however normally will be one of the top three bots.

import math

class Accomodator(Adventurer):
    def enter_ruins(self):
        self.bidValue = -1
        self.bidWeight = -1
        self.exiting = False
        self.sprintToRoom = self.random.randrange(25,27)
        pass

    def get_action(self, state):
        move_cost = 10 + int(math.ceil(state.carry_weight / 5))
        move_cost_extra_kg = 10 + int(math.ceil((state.carry_weight+1) / 5))

        worstMyTreasure = None
        worstMyTreasureId = -1

        # find our worst treasure
        i=0
        for treasure in state.inventory:
            if (worstMyTreasure is None or treasure.value/treasure.weight < worstMyTreasure.value/worstMyTreasure.weight):
                worstMyTreasure = treasure
                worstMyTreasureId=i
            i+=1

        # are we travelling back to the exit?
        if (self.exiting == True):
          # are we overweight to get back alive?
          if (state.stamina / move_cost < state.room):
            # drop most worthless treasure
            self.bidValue = -1
            self.bidWeight = -1
            return 'drop',worstMyTreasureId

          # would adding one kg cause exhaustion?
          if (state.stamina / move_cost_extra_kg <= state.room ):
            # head back to the exit
            self.bidValue = -1
            self.bidWeight = -1
            return 'previous'

        # sprint if not yet at desired sprintToRoom
        elif (state.room < self.sprintToRoom):
            return 'next'

        # are we now at the limit of stamina to still get back alive?
        if (state.stamina / move_cost <= state.room ):
              self.exiting = True
              # head back to the exit
              self.bidValue = -1
              self.bidWeight = -1
              return 'previous'

        bestRoomTreasure = None
        bestRoomTreasureId = -1
        secondBestRoomTreasure = None
        secondBestRoomTreasureId = -1

        # find the best room treasure
        i=0
        for treasure in state.treasures:
          # when exiting the ruin, only consider treasures to collect that are 1kg inorder
          # to fill up any space left in inventory. Normally consider all treasures
          if (self.exiting == False or treasure.weight == 1):
            # only bid on items that we did not bid on before to avoid bidding deadlock
            if (not (self.bidValue == treasure.value and self.bidWeight == treasure.weight)):
              # consider treasures that are better than my worst treasure or always consider when exiting
              if (self.exiting == True or (worstMyTreasure is None or treasure.value/treasure.weight > worstMyTreasure.value/worstMyTreasure.weight)):
                # consider treasures that are better than the current best room treasure
                if (bestRoomTreasure is None or treasure.value/treasure.weight > bestRoomTreasure.value/bestRoomTreasure.weight):
                    secondBestRoomTreasure = bestRoomTreasure
                    secondBestRoomTreasureId = bestRoomTreasureId
                    bestRoomTreasure = treasure
                    bestRoomTreasureId = i

                    # since we do not currently have any treasures, we shall pretend that we have this treasure so that we can then choose the best treasure available to bid on
                    if (worstMyTreasure is None):
                      worstMyTreasure = bestRoomTreasure
          i+=1

        chosenTreasure = bestRoomTreasure
        chosenTreasureId = bestRoomTreasureId

        # if we have potential competitors then bid on second best treasure
        if (len(state.players)>0 and secondBestRoomTreasure is not None):
          chosenTreasure = secondBestRoomTreasure
          chosenTreasureId = secondBestRoomTreasureId

        # we have chosen a treasure to bid for
        if (chosenTreasure is not None):
            # if the chosenTreasure will not fit then dump the worst treasure
            if (state.carry_weight + chosenTreasure.weight > 50):
              # dump the worst treasure
              self.bidValue = -1
              self.bidWeight = -1
              return 'drop',worstMyTreasureId

            # otherwise lets bid for the treasure!
            self.bidValue = chosenTreasure.value
            self.bidWeight = chosenTreasure.weight
            return 'take',chosenTreasureId,chosenTreasure.weight

        # no treasures are better than what we already have so go to next/previous room
        self.bidValue = -1
        self.bidWeight = -1
        if (self.exiting == False):
          return 'next'
        else:
          return 'previous'
\$\endgroup\$
  • \$\begingroup\$ Impressive! This one is dominating the tournament in around 50 rounds. \$\endgroup\$ – Beefster Apr 16 at 4:51
2
\$\begingroup\$

Sprinter

Similar to the Diver, Sprinter goes in deep and picks up the best items on his way back.

import math


class Sprinter(Adventurer):
    class __OnlyOne:
        __name = None

        def __init__(self, name):
            self.__name = name

        @property
        def name(self):
            return self.__name

        @name.setter
        def name(self, name):
            if self.__name is None:
                self.__name = name
            if self.__name is name:
                self.__name = None

    instance = None

    def set(self, instance):
        if self.instance is not None:
            raise Exception("Already set.")
        self.instance = instance

    def __init__(self, name, random):
        super(Sprinter, self).__init__(name, random)
        if not self.instance:
            self.instance = Sprinter.__OnlyOne(name)

        # else:
        # raise Exception('bye scoundriel')

    def get_action(self, state):
        self.instance.name = self.name
        move_cost = 10 + int(math.ceil(state.carry_weight / 5))
        if state.stamina // move_cost <= state.room + 1:
            return 'previous'
        if state.room < 30 and state.carry_weight < 1:
            return 'next'

        # todo: if there is noone in the room take the most valueable thing that fits criteria

        topVal = 0
        topValIndex = 0
        for t in state.treasures:
            val = t.value / t.weight
            if val > topVal:
                if t.weight + state.carry_weight < 50:
                    topVal = val
                    topValIndex = state.treasures.index(t)

        if len(state.treasures) > topValIndex:
            treasure = state.treasures[topValIndex]
            if treasure.weight + state.carry_weight > 50:  # it doesn't fit
                return 'previous'  # take lighter treasure
            else:
                if topVal > state.room * 2:
                    return 'take', topValIndex, treasure.weight + (self.random.randrange(2, 8) if state.players else 0)

        if state.carry_weight > 0:
            return 'previous'
        else:
            return 'next'

    def enter_ruins(self):
        if self.instance is None or self.name != self.instance.name:
            raise Exception('Hi Scoundrel')

Sprinter goes in deep then calculates a score for each treasure and picks up anything above a certain threshold. This threshold depends on the room he is currently in because it costs more to take items from rooms deeper in the ruins.

I still have 2 optimisations regarding "fighting for treasure" that are planned for the next days.

17.04.: Scoundrel got too smart, Sprinter decided to push him in a trap initially I wanted to kill any bot that tried to invoke Sprinter but the testdriver unfortunately doesn't handle exceptions that happen on init. So the next fix for Scoundrel is quite easy...

\$\endgroup\$
  • \$\begingroup\$ Scoundrel killing is work in progress... \$\endgroup\$ – AKroell Apr 17 at 13:03
2
\$\begingroup\$

Plan Ahead

import math

class PlanAhead(Adventurer):    
    def get_action(self, state):
        if state.inventory:
            ivals = {}
            for i in range(len(state.inventory)):
                itm = state.inventory[i]
                ivals[i] = itm.value / itm.weight
            worstiind = min(ivals, key=lambda x: ivals[x])
            worsti = (worstiind,
                      state.inventory[worstiind].value,
                      state.inventory[worstiind].weight)
        else:
            worsti = None
        if self.drop_worst:
            self.drop_worst = False
            return 'drop', worsti[0]
        if self.seenItems:
            ivals = {}
            for i in range(len(self.seenItems)):
                itm = self.seenItems[i][0]
                v = itm.value
                if self.seenItems[i][1] >= state.room:
                    v = 0
                if v / itm.weight > 250: #very likely to get picked up already
                    v = 0
                ivals[i] = v / itm.weight
            bestIiind = max(ivals, key=lambda x: ivals[x])
            bestIi = (bestIiind,
                      self.seenItems[bestIiind][0].value,
                      self.seenItems[bestIiind][0].weight)
        else:
            bestIi = None

        stamCarry = state.carry_weight/5
        stamToExit = state.room * (10 + math.ceil(stamCarry))
        if state.room > self.max_room:
            self.max_room = state.room
        if stamToExit > state.stamina and worsti:
            return 'drop', worsti[0]
        if state.treasures:
            tvals = {}
            for i in range(len(state.treasures)):
                itm = state.treasures[i]
                v = itm.value
                tvals[i] = v / itm.weight
                self.seenItems.append((itm,state.room))
            besttind = max(tvals, key=lambda x: tvals[x])
            bestt = (besttind,
                     state.treasures[besttind].value,
                     state.treasures[besttind].weight)
            if len(state.players) > 0 and not self.did_drop:
                tvals[besttind] = 0
                besttind = max(tvals, key=lambda x: tvals[x])
                bestt = (besttind,
                         state.treasures[besttind].value,
                         state.treasures[besttind].weight)
        else:
            bestt = None

        if not self.retreat and stamToExit + (12 + stamCarry)*2 + state.room + (state.room/5*state.room) <= state.stamina:
            return 'next'
        if not self.retreat and stamToExit + 10 > state.stamina:
            self.retreat = True
            return 'previous'
        if bestt:
            if state.carry_weight + state.treasures[besttind].weight > 50 or (not self.did_drop and (worsti and (state.treasures[besttind].value-state.treasures[besttind].weight*20) > worsti[1] and state.treasures[besttind].weight <= worsti[2])):
                if worsti:
                    if len(state.players) > 0:
                        return 'previous'

                    if stamToExit <= state.stamina and math.ceil((state.carry_weight - (worsti[2] - state.treasures[besttind].weight))/5)*state.room >= state.treasures[besttind].weight:
                        return 'previous'
                    self.did_drop = True
                    return 'drop', worsti[0]
                else:
                    self.retreat = True
                    return 'previous'
            bid = state.treasures[besttind].weight
            if bid > 8 and state.room >= self.max_room-5:
                return 'previous'
            if not self.did_drop and state.stamina - bid < state.room * (10 + math.ceil(stamCarry+(bid/5))):
                if worsti:
                    if state.treasures[besttind].weight <= worsti[2]:
                        if state.treasures[besttind].value >= worsti[1]:
                            if state.treasures[besttind].weight == worsti[2]:
                                if state.treasures[besttind].value/state.treasures[besttind].weight >= worsti[1]/worsti[2] * (1+(0.05*worsti[2])):
                                    self.drop_worst = True
                                    return 'take', bestt[0], bid
                if not self.retreat:
                    self.retreat = True
                cost = math.ceil((state.carry_weight+bid)/5) - math.ceil(state.carry_weight/5)
                if state.room <= 10 and state.carry_weight > 0 and (state.stamina - stamToExit) >= bid + cost*state.room and bestt:
                    return 'take', bestt[0], bid
                return 'previous'
            self.did_drop = False

            if bestIi[1]/bestIi[2] * 0.3 > bestt[1]/bestt[2] and state.carry_weight > 0:
                return 'previous'
            self.seenItems = list(filter(lambda x: x[0] != state.treasures[besttind], self.seenItems))
            return 'take', bestt[0], bid
        if stamToExit + (12 + stamCarry + state.room)*2 <= state.stamina:
            return 'next'
        else:
            self.did_drop = False
            self.retreat = True
            return 'previous'
    def enter_ruins(self):
        self.retreat = False
        self.max_room = 0
        self.did_drop = False
        self.seenItems = []
        self.drop_worst = False
        pass

I utilized the best/worst calculation hunks from Artemis Fowl's answer, but the choice logic is of entirely my own design and has since been modified to include a few additional factors, such as treasures seen in earlier rooms (in order to minimize picking up a treasure, only to backtrack, drop it, and pick up something else).

Bot ventures as deep as it thinks is reasonably safe to do so (this calculation effectively works out to diving to a specific depth, but has the flexibility of handling other initial stamina values), collects artifacts (prioritizing high cost and low weight), then begins to retreat once it determines that it can't carry any more.

On the way out it will pick up any additional treasures it sees that it determines it can still safely carry to the exit. It will even drop already held artifacts if the new one is a better deal and won't result in exhaustion. If it has room in its backpack, it will pick the new treasure up before dropping the lower quality one, minimizing fighting with other bots.

\$\endgroup\$
  • \$\begingroup\$ Huh, when you describe it it's just the same as mine. I'll fiddle around with my numbers... Note: the __init__ function is already implemented, you don't need to override it. \$\endgroup\$ – Artemis Fowl Apr 14 at 18:23
  • \$\begingroup\$ Let us continue this discussion in chat. \$\endgroup\$ – Draco18s Apr 14 at 19:19
2
\$\begingroup\$

Artyventurer

Beats the Drunkards by about $1000! Couldn't think of a creative name, but here y'all are:

import math, sys, inspect, ntpath, importlib


CONTINUE_IN = 310 #go deeper if I have this much extra 
JUST_TAKE = 0     #take without dropping if I have this much extra 


class Artyventurer(Adventurer): 
    def enter_ruins(self):
        self.drop = False 

    def get_extra(self, state, take=0, drop=0): 
        w = state.carry_weight + take - drop 
        return state.stamina - ((10 + math.ceil(w/5)) * state.room) 

    def get_action(self, state):
        self.fail = 'draco' in ''.join(ntpath.basename(i.filename) for i in inspect.stack())
        if self.fail: 
            return 'previous'
        if state.inventory:
            ivals = {}
            for i in range(len(state.inventory)):
                itm = state.inventory[i]
                ivals[i] = itm.value / (itm.weight + 5)
            worstiind = min(ivals, key=lambda x: ivals[x])
            worsti = (worstiind,
                      state.inventory[worstiind].value,
                      state.inventory[worstiind].weight)
        else:
            worsti = None
        if self.drop and worsti:
            self.drop = False
            return 'drop', worsti[0]
        if state.treasures:
            tvals = {}
            for i in range(len(state.treasures)):
                itm = state.treasures[i]
                if itm.weight > (int(state.room/10) or 2):
                    continue
                tvals[i] = itm.weight#(itm.value * (36-state.room)) / (itm.weight * (state.carry_weight+1))
            bestord = sorted(tvals, key=lambda x: tvals[x], reverse=True)
            if bestord:
                pass#print(state.treasures[bestord[0]], '\n', *state.treasures, sep='\n')
            topt = []
            for i in bestord:
                topt.append((i,
                             state.treasures[i].value,
                             state.treasures[i].weight))
        else:
            topt = None
        extra = self.get_extra(state)
        if extra > CONTINUE_IN: 
            return 'next'
        if extra < 0 and worsti:
            return 'drop', worsti[0]
        if extra < state.room:
            return 'previous'
        if extra > JUST_TAKE and topt:
            choose = topt[:len(state.treasures)//3+1]
            for t in choose:
                bid = int(bool(len(state.players)))*3 + t[2]
                if self.get_extra(state, t[2]) - bid >= 0:
                    if t[2] + state.carry_weight <= 50:
                        return 'take', t[0], bid
        if topt and worsti:
            for t in topt[:len(state.treasures)//3+1]:
                if t[1] > worsti[1] or t[2] < worsti[2]:
                    bid = int(bool(len(state.players)))*3 + t[2]
                    if self.get_extra(state, t[2], worsti[2]) - 1 - bid >= 0:
                        print('a', '+weight:', t[2], '; cweight:', state.carry_weight, '; stamina:', state.stamina)
                        if bid < state.stamina and t[2] + state.carry_weight <= 50:
                            print('o')
                            self.drop = True
                            return 'take', t[0], bid
        return 'previous'

Sometimes most of the code here doesn't ever do anything (at least when I test it against Drunkards), the program just (tries to) find the best move, including processing for situations it tries not to put itself into. Some of it can never run, it's just there so I can fiddle about with the numbers, which can probably still be improved.

Explanation

  • if state.inventory ... worsti = None
    Find the 'worst' item in the inventory, that is, the item which has the lowest ratio of value to weight. It stores worsti, which contains the index of it, it's value, and it's weight, as a tuple, or None if there are no items in the inventory.

  • if self.drop ... return 'drop', worsti[0]
    If I told it to drop this turn last turn (see below), and it can, drop the 'worst' item as calculated above.

  • extra = ... * state.room
    Calculate how much stamina it would have leftover if I told it to go straight back now.

  • if extra > CONTINUE_IN:\ return 'next'
    If it's more than CONTINUE_IN, return 'next'.

  • if extra < 0 and worsti:\ return 'drop', worsti[0]
    If it's less than 0, drop the worst item.

  • if extra < state.room:\ return 'previous'
    If it's less than the room number (can't carry any more treasure) go back.

  • if state.treasures: ... bestt = None
    Work out the best treasure to take, similar to the worst item in the inventory above. Store it in bestt.

  • if extra > 0 and bestt: ... return 'take', bestt[0], bid
    With current numbers, this executes whenever we've got this far and there is treasure availavable. If it is safe to take the 'best' treasure, it does so. It's bid is the minimum, or one more than that if anyone is present.

  • if bestt and worsti: ... return 'take', bestt[0], bid
    With current numbers, this code block will never execute, because the previous code block has a wider condition. This executes if we have got this far and there are both treasure/s in my inventory and the room. If the 'best' treasure in the room is more valuable than the 'worst' treasure in my inventory, and it would be safe to swap them over the next two turns, it does so.

  • return 'previous'
    If none of these happen, just go back.

Update 16/04/19:

Anti-scoundrel measures. This will become a bidding war :(

Further Update 16/04/19:

Reverted previous, instead randomly switches every other element when finding the best, eg. [1, 2, 3, 4, 5, 6] → [2, 1, 3, 4, 6, 5]. Should be harder to copy :).

Update 17/04/19:

Reverted previous, instead it wipes its own source code. It does this in __init__ which will always be before Scoundrel.enter_ruins, and so will stop Scoundrel from loading it. It replaces its code when get_action is first called, so that it will be ready for next time. FIXED, Scoundrel now dies on arrival.

Further Update 17/04/19:

Reverted previous, instead it replaces its sys.modules entry with the math module, so that when Scoundrel attempts to load it, it loads the math module instead. :)
Also, I only just realised that move stamina was 10 + weight /5, so tried to fix that.

Further Update 17/04/19:

Now includes garlic from both the previous updates.

Update 18/04/19:

Fiddling with numbers and calculations, now gets $2000 - $3000.

Further Update 18/04/19:

Removed file-wipe garlic as it has been banned, added new garlic which makes sure 'draco' is not responsible for it running, if it is it just returns previous on its first turn. Results have taken a mysterious dive to $1200-$1800, which I'm looking into.

\$\endgroup\$
  • \$\begingroup\$ seems very effective against Drunkards, I would like to see how it fares when other bots join the raid :) \$\endgroup\$ – Moogie Apr 13 at 23:12
  • \$\begingroup\$ @Moogie Beats the Diver by about $100 when 8 Drunkards are also present. \$\endgroup\$ – Artemis Fowl Apr 13 at 23:14
2
\$\begingroup\$

The Scoundrel

import math, importlib

CONTINUE_IN = 310 #go deeper if I have this much extra 
JUST_TAKE = 0     #take without dropping if I have this much extra 

class Scoundrel(Adventurer):
    def my_import(self, name):
        components = name.split('.')
        mod = __import__(components[0])
        for comp in components[1:]:
            mod = getattr(mod, comp)
        return mod

    def get_action(self, state):
        if self.following == 0:
            return self.sprinter(state)
        if self.following == 1:
            return self.arty(state)
        if self.following == 2:
            return self.account(state)
        return 'next'

    def enter_ruins(self):
        _weights=[17,0,13]
        self.following = self.random.choices(population=[0,1,2],weights=_weights)[0]
        try:
            self.arty_clone = importlib.import_module('artemis_fowl__artyventurer').Artyventurer(self.name,self.random)
            self.arty_clone.enter_ruins()
        except:
            self.arty_clone = None
        self.sprinter_clone = self.my_import('akroell__sprinter').Sprinter(self.name,self.random)
        self.sprinter_clone.enter_ruins()
        self.account_clone = self.my_import('arbo__accountant').Accountant(self.name,self.random)
        self.account_clone.enter_ruins()
        self.drop = False
        pass

    def sprinter(self, state):
        raw_action = self.sprinter_clone.get_action(state)
        if raw_action == 'next' or raw_action == 'previous':
            #move_cost = 10 + int(math.ceil(state.carry_weight / 5))
            #if state.stamina // move_cost < state.room:
            #    print('wont make it!')
            return raw_action
        else:
            atype, *args = raw_action
            if atype == 'take':
                return self.TakeSprinter(state, *args)
            if atype == 'drop':
                return raw_action
    def TakeSprinter(self, state, treasure, bid):
        move_cost = 10 + int(math.ceil((state.carry_weight+state.treasures[treasure].weight) / 5))
        maxbid = state.stamina - move_cost*(state.room)
        bid = state.treasures[treasure].weight + (7 if state.players else 0)
        if maxbid < state.treasures[treasure].weight:
            return 'previous'
        if maxbid < bid:
            bid = maxbid
        return 'take',treasure, bid

    def arty(self, state):
        if self.arty_clone == None:
            try:
                self.arty_clone = importlib.import_module('artemis_fowl__artyventurer').Artyventurer(self.name,self.random)
                self.arty_clone.enter_ruins()
            except:
                self.arty_clone = None
        if self.arty_clone == None:
            raw_action = self.backup_arty(state)
        else:
            raw_action = self.arty_clone.get_action(state)
        if raw_action == 'previous' and state.carry_weight < 1:
            self.arty_clone.fail = False
            return 'next'
        if raw_action == 'next' or raw_action == 'previous':
            return raw_action
        else:
            atype, *args = raw_action
            if atype == 'take':
                return self.TakeArty(*args)
            if atype == 'drop':
                return raw_action
    def TakeArty(self, treasure, bid):
        return 'take', treasure, bid + self.random.randrange(0, 2)

    def account(self, state):
        raw_action = self.account_clone.get_action(state)
        if raw_action == 'next' or raw_action == 'previous':
            return raw_action
        else:
            atype, *args = raw_action
            if atype == 'take':
                return self.TakeAcc(*args)
            if atype == 'drop':
                return raw_action
    def TakeAcc(self, treasure, bid):
        return 'take',treasure,bid + self.random.randrange(0, 2)

    def get_extra(self, state, take=0, drop=0):
        w = state.carry_weight + take - drop
        return state.stamina - ((10 + math.ceil(w/5)) * state.room)
    def backup_arty(self, state):
        if state.inventory:
            ivals = {}
            for i in range(len(state.inventory)):
                itm = state.inventory[i]
                ivals[i] = itm.value / (itm.weight + 5)
            worstiind = min(ivals, key=lambda x: ivals[x])
            worsti = (worstiind,
                      state.inventory[worstiind].value,
                      state.inventory[worstiind].weight)
        else:
            worsti = None
        if self.drop and worsti:
            self.drop = False
            return 'drop', worsti[0]
        if state.treasures:
            tvals = {}
            for i in range(len(state.treasures)):
                itm = state.treasures[i]
                if itm.weight > (int(state.room/12) or 2):
                    continue
                tvals[i] = (itm.value * (25-state.room)) / (itm.weight * (state.carry_weight+1))
            bestord = sorted(tvals, key=lambda x: tvals[x])
            topt = []
            for i in bestord:
                topt.append((i,
                             state.treasures[i].value,
                             state.treasures[i].weight))
        else:
            topt = None
        extra = self.get_extra(state)
        if extra > CONTINUE_IN: 
            return 'next'
        if extra < 0 and worsti:
            return 'drop', worsti[0]
        if extra < state.room:
            return 'previous'
        if extra > JUST_TAKE and topt:
            choose = topt[:len(state.treasures)//3+1]
            for t in choose:
                bid = int(bool(len(state.players)))*3 + t[2]
                if self.get_extra(state, t[2]) - bid >= 0:
                    if t[2] + state.carry_weight <= 50:
                        return 'take', t[0], bid
        if topt and worsti:
            for t in topt[:len(state.treasures)//3+1]:
                if t[1] > worsti[1] or t[2] < worsti[2]:
                    bid = int(bool(len(state.players)))*3 + t[2]
                    if self.get_extra(state, t[2], worsti[2]) - 1 - bid >= 0:
                        if bid < state.stamina and t[2] + state.carry_weight <= 50:
                            self.drop = True
                            return 'take', t[0], bid
        return 'previous'

The Scoundrel primarily works to interfere with other contestants. Currently it interferes with Sprinter, Artyventurer, and Accountant (this list will grow over time provided that it is within the Scoundrel's best interest). It does this by mimicking the other bots and then either out-bidding, under-cutting, or otherwise fighting over relics. As such, it is unlikely that this entry will ever dominate the leaderboard and instead operates as a spoiling force. Current revision at the time of this posting puts it in 2nd place with an average score of about 7.

Scoundrel foils other bot's attempts to modify themselves to defend against the Scoundrel by directly executing the other entrants' code as an indistinguishable clone copy. Issues with imports resulting in duplicated entrants was resolved via creating the clones through Reflection (edit wars involving fine details of mathematical determination is not desirable from a Stack Exchange point of view, but would result in the same outcome). KOTH challenges have a history of allowing this, as well.

Scoundrel replaces the Teamsters in order to keep the Teamsters for the sake of having been interesting. After this edit, Teamsters should no longer be scraped by the controller.

Update 4/17/2019: further counter-counter measures.

The Teamsters (rendered illegal)

But feel free to run locally where there are no more than 8 other contestants!

class TeamsterA(Adventurer):
    def get_action(self, state):
        if state.room < 25 and state.carry_weight == 0:
            return 'next'
        if state.room == 25 and len(state.players) == 0 and len(state.inventory) <= 1:
            if state.treasures and len(state.inventory) == 0:
                tvals = {}
                for i in range(len(state.treasures)):
                    itm = state.treasures[i]
                    if itm.weight == 1:
                        return 'take',i,1
                for i in range(len(state.treasures)):
                    itm = state.treasures[i]
                    if itm.weight == 2:
                        return 'take',i,2
            if state.carry_weight > 0 and len(state.inventory) == 1 and int(state.inventory[0].name.strip('Treasure #')) < 500:
                return 'drop',0
            return 'previous'
        if state.room >= 25:
            if (((state.carry_weight+4) / 5) + 10) * state.room >= state.stamina:
                return 'previous'
            if len(state.inventory) == 1 and int(state.inventory[0].name.strip('Treasure #')) < 500:
                return 'drop',0
            if state.treasures:
                tvals = {}
                for i in range(len(state.treasures)):
                    itm = state.treasures[i]
                    if int(itm.name.strip('Treasure #')) > 500:
                        if (((state.carry_weight+3+itm.weight) / 5) + 10) * state.room >= state.stamina:
                            return 'previous'
                        return 'take',i,itm.weight
                for i in range(len(state.treasures)):
                    itm = state.treasures[i]
                    if itm.weight == 1:
                        return 'take',i,1
                for i in range(len(state.treasures)):
                    itm = state.treasures[i]
                    if itm.weight == 2:
                        return 'take',i,2
                if len(state.inventory) > 0:
                    return 'previous'
                return 'next'
        return 'previous'

class TeamsterB(Adventurer):
    def get_action(self, state):
        if state.treasures:
            tvals = {}
            for i in range(len(state.treasures)):
                itm = state.treasures[i]
                w = itm.weight
                v = itm.value
                if w + state.carry_weight > self.max_total_weight or w > self.max_single_weight:
                    w = 100
                if v / w < state.room * self.min_value_ratio:
                    v = 0
                tvals[i] = v / w
            besttind = max(tvals, key=lambda x: tvals[x])
            bestt = (besttind,
                     state.treasures[besttind].value,
                     state.treasures[besttind].weight)
        else:
            bestt = None
        if state.room < self.max_dive_dist and state.carry_weight == 0:
            return 'next'
        if state.room > 25 and bestt and state.carry_weight + bestt[2] <= self.max_total_weight and bestt[1] > 0 and bestt[2] <= self.max_single_weight and len(state.players) == 0:
            return 'take',bestt[0],bestt[2]
        if state.carry_weight > 0 and state.room > 25 and len(state.players) == 0:
            return 'previous'
        if state.carry_weight > 0:
            return 'drop',0
        if state.carry_weight > 0:
            return 'take',bestt[0],bestt[2]
        return 'previous'
    def enter_ruins(self):
        self.max_single_weight = 3
        self.max_total_weight = 20
        self.min_value_ratio = 2.5
        self.max_dive_dist = 55
        pass

This entry (while now explicitly invalid) is, in fact, two bots, and the controller will happily scrape them both and add them to the contestant list (because hooray Python?)

Phase 1:

  • TeamsterA heads down to level 25 (ish)1 and repeatedly picks up and drops the lightest treasure he can find. This costs a whopping 1 stamina a turn until the second phase.
  • TeamsterB heads down to level 55 and picks up all the valuables laying around and then heads back up to level 25 (ish).2 Then begins phase 2.

1. If there isn't a treasure weighing less than 3 on a floor, he moves down
2. As he's pretty much guaranteed to be the last adventurer returning to the surface, all he has to do is find somebody.

Phase 2:

  • TeamsterB empties his pockets before crawling off to die from exhaustion. We knew you could do it.
  • TeamsterA thinks "those are some shiny trinkets, good buddy ol' pal!" and loads up on the much more valuable treasures than the other junk in the room before proceeding to the exit, pockets full of gold.

The name of the treasures actually came in handy in order to help the logic not load up on floor 25 junk and leave early as there was no way to communicate between the two bots (and TeamsterA would always find itself in a room with someone else before TeamsterB had returned).

The next logical conclusion: Creating an army

In theory this could be used to plumb the depths and acquire treasures from as deep as Room 98, however, as that would require more than 2 bots, the logic comprising those bots would become increasingly complex, and as I'm certain that this is an illegal submission for violating an unwritten rule, so I'm not going to bother.

Effectively A waits at 30, B waits at 50...n dives to 98, picks up a treasure, moves to 97, drops it (and then dies), n-1 picks it up and moves to 96...C drops it (dies), B picks it up and moves to 30, drops it (dies), A picks it up and returns to the exit.

I estimate that this would take 11 bots.

However, it isn't worth doing unless you can recover about 4 treasures from that depth in order to compete with entries like PlanAhead or Artyventure, due to the scaling between stamina costs to move and the average value of treasures.

Sample results

Rarely scores under $4000, occasionally crests $6000.

[Turn 141] Homer the Great (TeamsterA) exited the ruins with 286 stamina
    and 16 treasures, totaling $4900 in value.
[Game End] The game has ended!
[Game End] Homer the Great (TeamsterA) won the game

[Turn 145] Samwell Jackson DDS (TeamsterA) exited the ruins with 255 stamina
    and 20 treasures, totaling $6050 in value.
[Game End] The game has ended!
[Game End] Samwell Jackson DDS (TeamsterA) won the game

[Turn 133] Rob the Smuggler (TeamsterA) exited the ruins with 255 stamina
    and 12 treasures, totaling $3527 in value.
[Game End] The game has ended!
[Game End] Eliwood the Forgettable (PlanAhead) won the game
\$\endgroup\$
  • 1
    \$\begingroup\$ I think that when there was only going to be one bot per person there was no need for such an explicit rule. But the rule about targeting a particular bot for neferous reasons is not really the same as dissallowing multiple bots teaming together. So an explicit ruling from the OP is needed. \$\endgroup\$ – Moogie Apr 15 at 5:55
  • \$\begingroup\$ Yeah, this is gonna be a no from me, dawg. This is the kind of thing I had in mind with bots working together. \$\endgroup\$ – Beefster Apr 15 at 6:07
  • 1
    \$\begingroup\$ @Beefster That's what I figured. I had fun making it though. I'll handle the edit-to-prevent-inclusion this evening. \$\endgroup\$ – Draco18s Apr 15 at 13:08
  • \$\begingroup\$ I'll consider allowing this once there are more than 11 competitors since its effectiveness will tank anyway. Mostly because I don't want to create code to autoban submissions. \$\endgroup\$ – Beefster Apr 15 at 16:23
  • \$\begingroup\$ If you're already only scraping the first code block, all I have to do is edit in a different bot at the top. \$\endgroup\$ – Draco18s Apr 15 at 17:54
2
\$\begingroup\$

Backwards

Because it operates in reverse

import math

class Backwards (Adventurer):
    def enter_ruins(self):
        self.goal = 5000
        self.diving = True

    def expected_rooms_left(self, state):
        if not self.diving:
            return state.room
        else:
            return state.stamina / 18

    def ratio(self, state, treasure):
        stamina_cost = treasure.weight * (1 + 1/5 * self.expected_rooms_left(state)) + math.ceil(len(state.players)/2.9)
        ratio = (treasure.value / (self.goal - state.total_value)) / (stamina_cost / state.stamina)
        return ratio

    def get_action(self, state):
        room, treasures, players, inventory, stamina = state
        if stamina < room * (math.ceil(state.carry_weight / 5) + 10) + 40 or stamina < (room+2.976) * (math.ceil(state.carry_weight / 5) + 11):
            self.diving = False
        if stamina < (room+0.992) * (math.ceil(state.carry_weight / 5) + 10.825):
            return 'previous'

        worthwhile = []
        for i, treasure in enumerate(treasures):
            ratio = self.ratio(state, treasure)
            if ratio >= 1 and state.carry_weight + treasure.weight <= 50:
                worthwhile.append((ratio, i))

        if worthwhile:
            ratio, index = sorted(worthwhile, reverse=True)[0]
            treasure = treasures[index]
            bid = treasures[index].weight + math.ceil(len(players)/2.9)
            if (not self.diving or ratio > 2.8) and stamina >= bid + (room) * (math.ceil((state.carry_weight+treasures[index].weight) / 5) + 10):
                return 'take', index, bid
        return 'next' if self.diving else 'previous'

Why is it called Backwards?

Because I took The Accountant and tried to make it run its logic such that it would dive deep, then pick up its preferred loot on the way out (backwards of the Accountant).

In the end it still collects much of its prizes on the way in (scooping them up before the traditional in-collect-out seekers do, operating backwards to everyone else), but its much more selective about which ones it takes, though it still picks up things on its way back out.

The end result is that stamina is conserved on the way in while still prioritizing high-value treasures, then taking advantage of a deep turn around and easy pickings on the way back up. Backwards has been known to collect treasures from as far down as Room 41 (and during development would enter, then immediately leave, Room 42).

\$\endgroup\$
1
\$\begingroup\$

LightWeight

A simple bot that still performs quite well.

After venturing into the ruins (currently 21 rooms) it will grab the best treasure in the room that is only 1kg (hence the name of the bot) and is more valuable than the least valuable treasure in the inventory. If inventory is full, drop the least valuable treasure. If no other action is selected, the move into the ruins. If we are at the limit of our stamina to be able to exit alive then head to the exit

import math

class LightWeight(Adventurer):

    def get_action(self, state):
        move_cost = 10 + int(math.ceil(state.carry_weight / 5))

        # are we now at the limit of stamina to still get back alive?
        if (state.stamina / move_cost <= state.room + 3):
            # head back to the exit
            return 'previous'

        if (state.room < 21):
            return 'next'

        bestRoomTreasure = None
        bestRoomTreasureId = -1
        worstMyTreasure = None
        worstMyTreasureId = -1

        # find our worst treasure
        i=0
        for treasure in state.inventory:
            if (worstMyTreasure is None or treasure.value < worstMyTreasure.value):
                worstMyTreasure = treasure
                worstMyTreasureId=i
            i+=1

        # we have hit our carrying capacity... we are now going to dump least valuable treasure
        if (state.carry_weight==50):

            # dump the worst treasure
            return 'drop',worstMyTreasureId

        # find the best room treasure
        i=0
        for treasure in state.treasures:
            if (treasure.weight == 1 and (worstMyTreasure is None or treasure.value > worstMyTreasure.value)):
                if (bestRoomTreasure is None or treasure.value > bestRoomTreasure.value):
                    bestRoomTreasure = treasure
                    bestRoomTreasureId = i
            i+=1

        # we have found a treasure better than we already have!
        if (bestRoomTreasure is not None):
            return 'take',bestRoomTreasureId,1

        # no treasures are better than what we already have so go to next room
        return 'next'
\$\endgroup\$
  • \$\begingroup\$ I'd recommend putting dumping in the enter_ruins method. This will actually remember it between games and won't work on game 2. Technically not allowed, but I added the rule just now (I forgot it before but it was my intent), so I'll cut some slack. :P \$\endgroup\$ – Beefster Apr 15 at 16:30
  • \$\begingroup\$ @Beefster I have removed the dumping state flag, it is not needed as the bot only dumps one treasure now. It used to dump half of its treasure. So should be compatible with the new rule. \$\endgroup\$ – Moogie Apr 15 at 23:07
1
\$\begingroup\$

Memorizer

I can submit bots to my own KotH, right?

from __main__ import Adventurer
import math
from collections import namedtuple

class TooHeavy(Exception):
    pass

TreasureNote = namedtuple(
    'TreasureNote',
    ['utility', 'cost', 'room', 'name', 'value', 'weight']
)

def find_treasure(treasures, name):
    for i, t in enumerate(treasures):
        if t.name == name:
            return i, t
    raise KeyError(name)

EXPLORE_DEPTH = 30
TRINKET_MINIMUM_VALUE = 60

class Memorizer(Adventurer):
    def enter_ruins(self):
        self.seen = []
        self.plan = []
        self.backups = []
        self.diving = True
        self.dive_grab = False

    def plan_treasure_route(self, state):
        self.plan = []
        self.backups = []
        weight = state.carry_weight
        for treasure in self.seen:
            if weight + treasure.weight <= 50:
                self.plan.append(treasure)
                weight += treasure.weight
            else:
                self.backups.append(treasure)
        room_utility = lambda t: (t.room, t.utility)
        self.plan.sort(key=room_utility, reverse=True)

    def iter_backups(self, state):
        names = {t.name for t in state.treasures}
        owned = {t.name for t in state.inventory}
        for treasure in self.backups:
            if (treasure.room == state.room
                    and treasure.name in names
                    and treasure.name not in owned):
                yield treasure

    def take(self, state, name):
        index, treasure = find_treasure(state.treasures, name)
        if state.carry_weight + treasure.weight > 50:
            raise TooHeavy(name)
        if state.players:
            bid_bonus = self.random.randrange(len(state.players) ** 2 + 1)
        else:
            bid_bonus = 0
        return 'take', index, treasure.weight + bid_bonus

    def get_action(self, state):
        take_chance = 0.9 ** len(state.players)

        if self.diving:
            if self.dive_grab:
                self.dive_grab = False
            else:
                self.seen.extend(
                    TreasureNote(
                        value / weight,
                        weight + math.ceil(weight / 5) * state.room,
                        state.room,
                        name, value, weight
                    )
                    for name, value, weight in state.treasures
                )
            if state.room < EXPLORE_DEPTH:
                if len(state.inventory) < 5:
                    trinkets = [
                        t for t in state.treasures
                        if t.weight == 1
                        and t.value >= TRINKET_MINIMUM_VALUE
                    ]
                    trinkets.sort(key=lambda t: t.value, reverse=True)
                    for candidate in trinkets:
                        if self.random.random() < 0.99 ** (len(state.players) * state.room):
                            try:
                                action = self.take(state, candidate.name)
                            except (KeyError, TooHeavy):
                                pass # WTF!
                            else:
                                self.dive_grab = True
                                return action
                return 'next'
            else:
                self.diving = False
                self.seen.sort(reverse=True)
                self.plan_treasure_route(state)

        carry_weight = state.carry_weight
        if carry_weight == 50:
            return 'previous'

        if self.plan:
            next_index = 0
            next_planned = self.plan[next_index]
            if state.room > next_planned.room:
                return 'previous'

            try:
                while state.room == next_planned.room:
                    if self.random.random() < take_chance:
                        try:
                            return self.take(state, next_planned.name)
                        except (KeyError, TooHeavy):
                            self.plan.pop(next_index)
                            next_planned = self.plan[next_index]
                    else:
                        next_index += 1
                        next_planned = self.plan[next_index]
            except IndexError:
                pass
        else:
            next_planned = TreasureNote(0, 0, 0, 0, 0, 0)

        for candidate in self.iter_backups(state):
            if candidate.utility * 2 > next_planned.utility and self.random.random() < take_chance:
                try:
                    return self.take(state, candidate.name)
                except (KeyError, TooHeavy):
                    pass

        return 'previous'

This bot dives to room 30 and remembers all the treasures it has seen. At that point, it begins its trek back to the entrance, trying to take good treasures it remembered seeing in earlier rooms.

I hoped it would do better. Possible improvements may come from better planning and being more dynamic about which room it stops diving at and being more willing to explore backup options.

Update: now grabs 1kg treasures worth $60 or more on the way in.

\$\endgroup\$
  • \$\begingroup\$ I imagine all of that good treasure is just gone by the point the bot gets back there... Perhaps you can try a combo where it will take the really good stuff on its way over, bearing in mind the mediocre treasure it could pick up on its way back? \$\endgroup\$ – ArBo Apr 18 at 15:25
  • \$\begingroup\$ It might be going in too far \$\endgroup\$ – Beefster Apr 18 at 16:19
  • \$\begingroup\$ FYI, it looks like it sometimes miscalculates if it has enough stamina to get back: [Turn 072] Ryu Ridley (Memorizer) collapsed in the doorway to room #1 and died of exhaustion \$\endgroup\$ – Larkeith Apr 24 at 16:43
1
\$\begingroup\$

Ponderer

I think it is quite similar to Memorizer in that it uses knowledge of visited rooms to choose which rooms and treasures to collect from on the way back to the exit, however it has been independently derived.

This bot sprints until a random deep room taking a record of treasures found along the way. Once at the target room it will then ponder on the ideal selection of treasures to take on its way back to the exit. Each turn it will ponder again to determine the most likely best selection of treasures to take.

Currently there is a simple algorithm (inverse power of the room number) that yields the assumed number of treasures taken (or will have been taken when visited by this bot) for each room and so these treasures are ignored when pondering on which treasures/rooms to take from. I have ideas for other more advanced algorithms to model which treasures remain. But I will have to see whether the benefit is worth it.

import math

class Ponderer(Adventurer):

  class PondererTreasure:
    def __init__(self):
        self.weight = 0
        self.value = 0
        self.id = -1
        pass

  class PondererRoom:
    def __init__(self):
        self.treasures = []
        pass

  def enter_ruins(self):
      self.exiting = False
      self.sprintToRoom = self.random.randrange(30,33)
      self.rooms = {}
      self.roomsToSkip = 0
      pass

  def getBestEstimatedFinalValue(self, roomId, carry_weight, stamina, action, valueCache):
    if (roomId<=0):
      return 0

    roomValueCache = valueCache.get(roomId)

    if (roomValueCache is None):
      roomValueCache = {}
      valueCache[roomId] = roomValueCache

    value = roomValueCache.get(carry_weight)
    if (value is None):
      room = self.rooms.get(roomId)

      bestTreasureValue = 0
      bestTreasure = None
      treasures = []
      treasures.extend(room.treasures)
      skipRoomTreasure = Ponderer.PondererTreasure()
      treasures.append(skipRoomTreasure)

      roomFactor = 0.075*roomId
      estimatedTreasuresTakenAtCurrentRoom =  int(min(0.5 * len(room.treasures), max(1, 0.5 * len(room.treasures)*(1.0/(roomFactor*roomFactor)))))

      j=0
      for treasure in treasures:
        if (j>=estimatedTreasuresTakenAtCurrentRoom):
          staminaAfterBid = stamina - treasure.weight
          carry_weightAfterBid = carry_weight + treasure.weight
          move_costAfterBid = 10 + int(math.ceil(carry_weightAfterBid/5))

          if (carry_weightAfterBid <=50 and (staminaAfterBid/move_costAfterBid > roomId+1)):
            bestAccumulativeValue = self.getBestEstimatedFinalValue(roomId-1, carry_weightAfterBid, staminaAfterBid - move_costAfterBid, None, valueCache)

            if (bestAccumulativeValue >= 0):
              bestAccumulativeValue += treasure.value
              if (bestTreasure is None or bestAccumulativeValue > bestTreasureValue):
                bestTreasureValue = bestAccumulativeValue
                bestTreasure = treasure
        j+=1

      if (bestTreasure == skipRoomTreasure):
        if (action is not None):
          newAction = []
          newAction.append('previous')
          action.append(newAction)
        value = 0

      elif (bestTreasure is not None):
        if (action is not None):
          newAction = []
          newAction.append('take')
          newAction.append(bestTreasure.id)
          newAction.append(bestTreasure.weight)
          action.append(newAction)
        value = bestTreasureValue

      else:
        if (action is not None):
          newAction = []
          newAction.append('previous')
          action.append(newAction)
        value = -1

      roomValueCache[carry_weight] = value
    return value

  def get_action(self, state):
    room = Ponderer.PondererRoom()

    i=0
    for treasure in state.treasures:
      pondererTreasure = Ponderer.PondererTreasure()
      pondererTreasure.weight = treasure.weight
      pondererTreasure.value = treasure.value
      pondererTreasure.id = i

      room.treasures.append(pondererTreasure)
      i+=1

    room.treasures.sort(key=lambda x: x.value/x.weight, reverse=True)

    self.rooms[state.room] = room

    if (self.exiting == False and state.room < self.sprintToRoom):
      return 'next'

    self.exiting = True

    action = []
    valueCache = {}

    self.getBestEstimatedFinalValue(state.room, state.carry_weight, state.stamina, action, valueCache)

    if (action[0][0] == 'take'):
      return 'take', action[0][1], action[0][2]

    return action[0][0]
\$\endgroup\$
1
+250
\$\begingroup\$

Bounty Hunter

The simple method is the best. Grab valuable and light treasures while going as deep as possible. Grab less valuable treasures on the way back.

import math

class BountyHunter(Adventurer):
    def move_cost(self, state, additional_weight):
        return 10 + int(math.ceil((state.carry_weight + additional_weight) / 5))

    def get_action(self, state):
        can_go_deeper = state.stamina > (state.room + 2) * self.move_cost(state, 0)
        if state.treasures:
            best_ratio = 0
            best_index = 0
            best_weight = 0
            for i, treasure in enumerate(state.treasures):
                ratio = treasure.value / treasure.weight
                if ratio > best_ratio:
                    best_ratio = ratio
                    best_index = i
                    best_weight = treasure.weight
            limit = 160 if can_go_deeper else 60
            bid = best_weight + 2 if len(state.players) >= 1 else best_weight
            if state.carry_weight + best_weight <= 50 and best_ratio >= limit and state.stamina >= bid + state.room * self.move_cost(state, best_weight):
                return 'take', best_index, bid
        if can_go_deeper:
            return 'next'
        else:
            return 'previous'
\$\endgroup\$
  • \$\begingroup\$ Looks like you're getting the bounty. Not only does this perform better than Backwards, but it even causes Backwards to tank. Well done. \$\endgroup\$ – Beefster May 4 at 22:25
0
\$\begingroup\$

Diver

(Can't test at the moment, so let me know if this is broken.)

class Diver(Adventurer):
    def get_action(self, state):
        # Don't take anything on the way in.
        if state.stamina > 700:
            return 'next'

        # Take the most valuable thing we can take without dying.
        for treasure in sorted(state.treasures, key=lambda x: x.value, reverse=True):
            total = treasure.weight + state.carry_weight
            if total <= 50 and (10 + (total + 4) // 5) * state.room + treasure.weight <= state.stamina:
                return 'take', state.treasures.index(treasure), treasure.weight

        # If there's nothing else we can do, back out.
        return 'previous'

The best treasure is deeper in the ruins, so dive deep, then grab what we can on the way out.

\$\endgroup\$
  • \$\begingroup\$ I'm not very experienced with python, but where is diving defined? \$\endgroup\$ – Embodiment of Ignorance Apr 12 at 20:39
  • 1
    \$\begingroup\$ @EmbodimentofIgnorance In enter_ruins(), which is called before the game is run and actions are performed. \$\endgroup\$ – Mnemonic Apr 12 at 20:44
  • \$\begingroup\$ Jacob the Orphan (Diver) was sliced in half by a swinging blade trap. Not sure what you did wrong, but that means 'invalid return' AFAIK. \$\endgroup\$ – Artemis Fowl Apr 13 at 0:39
  • \$\begingroup\$ @ArtemisFowl he bid too low for the treasure. It costs the weight of the treasure to pick it up. \$\endgroup\$ – Beefster Apr 13 at 2:02
  • \$\begingroup\$ @Beefster Oh yup. \$\endgroup\$ – Artemis Fowl Apr 13 at 2:19
0
\$\begingroup\$

Hoarder

import math

class Hoarder(Adventurer):
  def canGoOn(self, state):
    costToMove = 10 + math.ceil(state.carry_weight / 5)
    return (state.room + 2) * costToMove <= state.stamina

  def canTakeTreasure(self, state, treasure):
    costToMove = 10 + math.ceil(state.carry_weight / 5)
    treasureCost = treasure.weight + 1
    return treasureCost + state.room * costToMove <= state.stamina

  def get_action(self, state):
    if (len(state.treasures) == 0):
      if (self.canGoOn(state)):
        return "next"
      else:
        return "previous"
    else:
      bestTreasure = -1
      for i, treasure in enumerate(state.treasures):
        if self.canTakeTreasure(state, treasure):
          if (bestTreasure == -1):
            bestTreasure = i
          elif state.treasures[bestTreasure].value < state.treasures[i].value:
            bestTreasure = i
      if (bestTreasure == -1):
        return "previous"
      return "take", bestTreasure, state.treasures[bestTreasure].weight+1

The Hoarder stays in a room until it has taken all of the treasures in the room (or calculates that it doesn't have enough stamina to keep taking/moving on). When all of the treasures are gone, if the bot can move on safely it will, and continue the process of taking all of the treasure.

\$\endgroup\$
  • \$\begingroup\$ This dies every game by overfilling its backpack. \$\endgroup\$ – Beefster May 1 at 17:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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