NinjaDoggy - 68 legend
Thanks for the contest. It was a lot of fun!
Overall I wasn’t too happy with my bot this contest, so I’ll share only the parts I was proud of:
Search:
I used BFS as opposed to Beam Search and still managed to search incredibly deep with the “secret sauce perfect pruning” I kept hinting at in chat:
If the game consisted of only casts/brews/rest(and a predetermined set of tomes)
I think I’ve basically solved the problem of getting to a specific inventory, set of potions brewed, and resulting tomeCastableBitmask in the shortest number of moves.
The problem can be thought of as a shortest path problem in an unweighted graph(each edge has length 1)
The BFS state consists of 3 things:
-the Inventory(10 bits,0 - 1000 because there are only 1001 distinct inventories possible)
-a bitmask of potions that have been brewed(5 bits, 0-31)
-a bitmask of tomes that need to be refreshed(technically up to 46 bits if you learned every single tome)
So there are up to 2^51 * 1001 nodes in the graph
and each node’s edges are simply all the possible actions(rest,cast,brew)
Start with the initial state and BFS out
3 ways to prune a node from being added into BFS:(All 3 pruning techniques are “perfect” in the sense that they won’t remove any potentially optimal paths)
Pruning Technique 1:
Hashset to check for duplicated state(this is the most obvious one)
The key insight to pruning methods 2 and 3, comes from the fact that we don’t really care too much about the tomeCastableBitmask. Specifically, we know that one state is 100% superior to another state if the inventories and potionBrewedBitmask are the same, and the tomeCastableBitmask completely covers the other:
Example:
State with:
inventory = 5
potionBrewedBitmask = 10010
tomeCastableBitmask = 11111111
is strictly better than a state with:
inventory = 5
potionBrewedBitmask = 10010
tomeCastableBitmask = 10110111
2.So as a result once we’ve reached a node with a all tomes off cooldown, we can prune all nodes after it that have the same inventory and potions brewed
3.If we reach node A without all tomes off cooldown, we can still prune all nodes B after node A
as long as they have the same inventory and potions brewed
and distance to B > distance to A
(more details below)
Pruning Technique 2:
For each combination of inventory and potionBrewedBitmask
store if there has been a state reached with a perfect tomeCastableBitmask(right after a rest)
States that have inventory,potionBrewedBitmask that has been reached previously with a perfect tomeCastableBitmask can be pruned!(because there is a node we’ve visited that’s strictly better than this one, and it had the same or shorter distance)
Pruning Technique 3:
For each combination of inventory and potionBrewedBitmask
store the minimum distance we’ve obtained so far
States that have the same inventory, potionBrewedBitmask with a longer distance can be pruned!
example:
let’s say we’ve previously reached state A:
inventory = 2
potionBrewedBitmask = 00010
tomeCastableBitmask = 0000100100
with a distance of 2
and now we reach state B:
inventory = 2
potionBrewedBitmask = 00010
tomeCastableBitmask = 0010101100
with a distance of 3 or more
this node can be safely pruned because we know we can reach a strictly better state with the same/shorter distance can be reached simply by resting from state A
With these 3 pruning techniques I was able to get my bot to search a much greater depth
While I was trying to find a tierlist for the tomes I ran some offline evaluations that put this to great use:
I fixed the starting inventory to be 3 blues, 0 greens, 0 orange, 0 yellow
and had 11 potions(but restricted it to only brew from the first 5 available ones each time)
so the state became:
-the Inventory(10 bits,0 - 1000 because there are only 1001 distinct inventories possible)
-a bitmask of potions that have been brewed(11 bits, 0-2047)
-a bitmask of tomes that need to be refreshed(technically up to 46 bits if you learned every single tome)
I ran the bfs up to depth 100(to simulate a full game)
and on average it finished in < 500 milliseconds
and rarely did it take more than 1 whole second to compute the shortest distance to all possible combinations of 6 potions brewed out of the 11 with all possible ending inventories