trolls_vs_castles.md

Trolls vs castles

One commenter said that there wasn't really any strategy.

Yet there's a plentiful amount of strategies.

Timeout

A few of the last placers timeout. This immediately loses the game.

helloworld1 doesn't timeout, that should've gotten at least a few more ranks...

Unrecognized output / Ill formed action

This is practically the same as a timeout

Maybe you didn't output a number. Maybe your comment wasn't separated by a space: 3comment. Maybe you output a non-integer amount of stones: 2.5, 0.0. This can also happen by throwing so many stones it can't be parsed as an int.

Another case is when you throw negative stones -- the game labels you a cheater for trying to "lose a negative amount of stones" and you lose.

Throw 1000 stones

The game is nice and caps this to (all the stones you have) for you sometimes. Other times the economy crashes and you lose.

Throw 15 stones

This is still far too many stones, often causing economy crashes.

Even if you manually cap it to myStones, you never win by sending the troll to the castle, because the castles are too far in the current scenarios:

Road length	Stones
6	15
6	30
14	30
14	50

In games where both players have 15 stones, all the player has to do is throw less than 15 stones.

Otherwise all the player has to do is throw less than 14 stones.

Note that all players except "throw all stones" can theoretically send the troll to the castle in the automatic throw 1 endgame, if the opponent runs out before you. More on that later.

Throw 0 stones

Most of the time the game is nice and throws 1 stone for you if you have stones.

But sometimes you get eaten by a grue.

Throw 1 stone

Even then, this loses a lot because almost every throw will push the troll closer to your castle.

Any remotely efficient player will succeed.

Throw a random amount of stones

This strategy often throws a disproportionate amount of stones.

You often throw most of your stones on turn 1.

Often you still have enough stones to beat "throw 1 stone" but sometimes you lose because you threw all your stones. When only 1 player has stones the game automatically simulates that player throwing "1" stone for "theirStones" turns, pushing the troll "theirStones" back.

"Throw 1 stone" will of course probably have many stones left and so the troll would be pushed back very far.

Sidenote: The game encourages you to have a reproducible bot. My bot is decently but not completely reproducible, but I have this unused prng from wikipedia:

class Prng
 property seed
 constructor (seed) {}
 
 fn next() {
   seed++
   a = seed * 15485863
   return (a * a * a % 2038074743) / 2038074743
 }

Throw 2 stones

If the roads are long enough, then this throw guarantees you never lose.

Throwing 3 or more always risks losing to "throw whatever you throw, but if the troll is not next to my castle and you throw 3 or more, throw 1"

However, in practice, the above sentence can't be implemented because you don't know what your opponent will throw and vice versa. Both players throw their stones at the same time.

Thus there are rock-paper-scissors effects with these strategies.

You either want to throw "opponent + 1 stones", pushing the troll back and pressuring your opponent, or less than "opponent - 1 stones", which if stones were converted into pushes, gains pushes in the long run.

In short, throwing barely more than your opponent but not too much, or throwing 1 if you think the opponent will throw too much.

Observe that "throw 3 stones" always wins against "throw 2 stones". Then keep going... oh look a loop

throw 2 stones
throw 3 stones
throw 4 stones
throw 5 stones (when road length is 14 and num stones is 30, this loses because only 6 spaces is gained when 7 is needed)
alternate 1, 6 (Lose one space, gain one space, and only throw 7 stones instead of 10)
alternate 2, 1
throw 3 stones

Detect opponent pattern

One thing you can try is to detect what pattern your opponent is doing. By assuming the first two turns predict the rest of the game, you can trivially win against every strategy above except random, and most players win against random effortlessly anyways because random is very inefficient.

In short you try to be that perfect "I know what you're doing" AI.

This is probably enough to get into the top 100 already if I remember correctly?

At this point though, your opponent might trick you into throwing.

For example, consider p1's win/loss table against p2:

  1 2 3 4 5
1 W D L L L
2 W W D L L
3 L W W D L
4 L L W W D
5 L L L W W

Your opponent could trick p1 into throwing 1, which only wins if the opponent throws 1. It is easy to see that throwing 2 is strictly a better option.

For p2, throwing 5 is strictly better than 4.

Removing these options gets

  1 2 3 5
2 W W D L
3 L W W L
4 L L W D
5 L L L W

For the opponent, 1 is strictly better than 2
  1 3 5
2 W D L
3 L W L
4 L W D
5 L L W

4 > 3
  1 3 5
2 W D L
4 L W D
5 L L W

Additionally, for p2, throwing 5 maximizes the chance that p1 loses (if p1 was random). So maybe throwing 5 instead would be better.

This is yet another rock-paper-scissors. You could throw 2, the opponent could then throw 5, you could instead throw 5 then, and the opponent instead throws 2, and now you could throw 2.

Maybe try to play a weighted random optimal action (2, 3, 4, 5) so that your opponent cannot predict what you're going to do?

(draft not done)