This challenge was really different from the previous ones but it was quite interesting. Unfortunately, the heuristics route I chose didn't give me a bot on which I could hope to reach Legend. However, it was very complicated to use the replays and to know if our modifications really improved our bot. This discouraged me from spending any more time.
Fortunately, there's psyleague to see if my bot improves at least locally. Each version that psyleague considered to be stronger turned out to be the best in the arena. Thanks Psyho for sharing psyleague!
On the last days of the challenge, I changed my goal to finish first in Javascript/Typescript but Waluiji's bot was too strong for me. GG to him. And well done to everyone who made it to Legend! The boss was a tough cookie!
The idea behind my bot is to find, for each mini-game, the direction that would allow me to keep or gain a rank, assuming that the two opponents make the best possible move. For example, if I'm second in the Hurdle and no action allows me to go first and only L and U allow me to stay second, then I'll only use these two actions for this mini-game. If I have several actions, I sort them so that the one that brings me closest to victory is the first on the list. If I'm sure of winning or sure of losing, then I consider that all the actions are possible.
I now sort the games according to the following rules in succession so that I have the most important one first. If A > B means that game A is more important than game B:
- isGameOver: if A.isGameOver && !B.isGameOver then B > A
- isAlreadyLost: if A.isAlreadyLost && !B.isAlreadyLost then B > A
- isAlreadyWon: if A.isAlreadyWon && !B.isAlreadyWon then B > A
- isGoldStillPossible: if A.isAlreadyWon && !B.isAlreadyWon then A > B
- percentagePlayed > 50: if A.percentagePlayed>50 && !B.percentagePlayed>50 then A > B
- score (gold x 3 + silver): if A.score > B.score then B > A
Let's imagine that, in ascending order of importance, I have the following games and actions:
- MiniGames: [Archery,Diving,Hurdle]
- Hurdle : [R,U]
- Archery : [L,U,D]
- Skating : Ignored
- Diving : [U]
I take, if it exists, the following intersection :
- intersection(Archery, Diving, Hurdle)[0]
- intersection(Archery, Diving)[0]
- intersection(Archery, Hurdle)[0]
- Archery[0] In this case, we take U, which is in all three games.
Another example:
- MiniGames: [Hurdle,Diving,Archery]
- Hurdle : [R,U]
- Archery : [U]
- Skating : Ignored
- Diving : [D]
In this case, we take U, which is the intersection between Hurdle and Archery, as Diving does not intersect with Hurdle.
Let's see how to choose the possible actions.
I consider that both opponents are making the best possible move. I test the 4 directions and keep only those that allow me to stay in the same place or those that allow me to gain a place, considering that taking a barrier is equivalent to moving back 4 squares.
For example here (I'm green):
I consider that the actions [L,U,D] are possible because none of them makes me lose 1st place, but that R makes me second because taking a barrier makes me lose 4 squares and therefore becomes second.
Here (also green):
This case is a bit special because there are no barriers and there's no point in crossing the finish line with more cases than the others players. You just have to get there on the same turn.
To do this, I calculate :
Math.ceil((30 - position - 1) / 3)for each player to check that we get to the finish line at the same time.- The modulo
(30 - position - 1) % 3. If it's 0, then I only have to do R's, if it's 1, I can also do U's and D's and if it's 2, I can do any action.
If, by playing as well as possible, I don't finish the race before the end of the 100 days.
If, by playing any action, my opponents play as well as possible, and I always win.
If for each player, Math.ceil(myTurnsLeft / 3) <= Math.ceil(oppTurnsLeft / 2). The difference in divisors is to allow my bot to catch up with the other players in some cases.
To find the best moves I brute force Archery at the beginning of a new Archery game.
The naive way to brute force Archery is 4^15=1 073 741 824 but with a "smart" way, we can achieve that in 40 x 40 x 15 = 24 000
Thanks to Thyl for the idea.
The idea is to create a 40 x 40 x 15 matrix where your store in each case the squared minimal distance to the center you can achieve if you begin at this case with this wind.
For exemple if minDistances[15][35][5] = 1 it means that when i'm at 5th wind, with x = 15 - 20 = -5 and y = 35-20 = 15 I can achieve a minimal distance of 1.
To construct the matrix, you begin from the last wind and iterate to the first wind.
- to compute
minDistances[x][y][n]:- for each direction
newX = x + dir x windandnewY = y + dir x wind- if n=1, compute the squared distance to the center of [newX, newY]
- else retrieve
minDistance[x + dir x wind][y + dir x wind][n - 1]
- take the minimum =>
minDistances[x][y][n]
- for each direction
Here is the code if someone want it:
minDistanceArchery
for (let j = 0; j < windLength; j++) {
const wind = this.wind[windLength - 1 - j];
for (let x = -20; x <= 20; x++) {
for (let y = -20; y <= 20; y++) {
const distances: number[] = [];
let previousScore = 0;
for (let k = 0; k < 4; k++) {
const [directionX, directionY] = this.archeryDirections[k];
let newX = x + directionX * wind;
let newY = y + directionY * wind;
if (newX < -20) newX = -20;
else if (newX > 20) newX = 20;
if (newY < -20) newY = -20;
else if (newY > 20) newY = 20;
if (j === 0) {
const newDistance = this.squaredDistanceToOrigin(newX, newY);
distances.push(newDistance);
} else {
const minDistance = minDistances[newX + 20][newY + 20][j - 1];
const newDistance = minDistance.distance;
previousScore = minDistance.score;
distances.push(newDistance);
}
}
let minDistance = Infinity;
let score = 1;
for (let l = 0; l < distances.length; l++) {
if (distances[l] < minDistance) {
minDistance = distances[l];
score = 1;
} else if (distances[l] === minDistance) {
score++;
}
}
minDistances[x + 20][y + 20][j] = {
distance: minDistance,
score: score + previousScore,
};
}
}
}With this matrix I can know the minimal distance of the two opponent, and always choose a direction where my minimal distance is lower than the minimal distance of the opponent.
If my minDistance is higher than one of my opponent and lower than the second opponent, I can still reach silver. If my minDistance is higher than all the opponents, I give up this mini game.
If I play as well as I can and don't finish the mini-game before the end of the 100 rounds.
always false in this miniGame
Easy to compute with the matrix. myMinDistance > allOpponentMinDistance
I don't deal with this game in my algo. The only thing I added a few days before the end was that if in the last 2 rounds I can move into first place by moving 3 squares twice, then I'll do it.
Easy there is only one option...
If I can't finish before the 100 laps or if I can't catch up with the second or first-placed player by playing perfectly.
If no matter what I play, I always finish first.
If I play optimally and my opponents lose their combo, can I finish first?
My bot has two major problems:
- it assumes that the opponent always plays the best move and, above all, that he plays different moves in each mini-game
- it only has a depth of one and so it doesn't see, for example on Hurdle, that L then R would be equivalent to R then L if there was a barrier at a distance of 4.
To improve it, we need to :
- simulate the opponent a little better so that he chooses an identical move for the 4 games and that we take this move into account when looking for my best move.
- Manage to add depth, at least for Hurdle. I tried it quickly but it didn't work and I had to modify too much code so I didn't have the courage.