Hi everybody,
Here is my approach in this great contest. This was my 10th contest, and I knew the short time allowed, one week, would not permit to try something new. Multi contests are made for that.
So I didn’t focus on implementing a complete simulator. I did that in the Accountant challenge, and passed 3 days to have it working. So I used my CB strategy because I worked many weeks on this multiplayer game, and I found that FB was similar on many points : free map, multi agent, and a lot of features and possibilities.
So, on CB, I knew that the main feature was how to assign each Buster on each Ghost. It is very important, because the high strategy level of the game follows a logic which is far away from taking the next ghost at the lower distance…
In FB, it is the same. You got two wizard, and many snaffles, and the best snaffle to chose will not always be the nearest, because of the many possible configurations of the game :
- Do I win ?
- Do I lose ?
- How many points do I need to win ?
- How many points does my opponent need to win ?
- Is there sufficient snaffle near opposite camp to win ?
- Those snaffle are they all in front of my wizards or behind them ?
- Is there sufficient snaffle near my camp to let the opponent win ?
- …
Gold League
By the way, the nearest snaffle rule led me in Gold league, and only there I began to think on the assignment problem. No need to say that, to reach Gold league, spells were very important too. I think that all those spell situations were in my code since Silver league :
- Flipendo when snaffle is in alignment on goal
- Flipendo if a snaffle is near my camp (and good orientation too)
- Accio to capture an assigned snaffle if it is in rear
- Accio to protect my camp if a snaffle is to near
- Petrificus to Stop snaffle which is running to my camp
- Petriricus to Stop snaffle which is running fast to my camp
- Petrificus to prevent an opponent wizard to catch a snaffle
- Petrificus to make an opponent wizard miss his catching
- Petriricus to react an opponent throw
- Accio to react an opponent throw
I ignored Obliviate which I found not very valuable in the game. I discussed this point with Magus, and the only positive thing he found would have been to disturb the opponent simulation.
To give priorities to some spells, I implemented a reserve of mana to use it only in emergency. So some spells could use this mana and others could not use it. Prioritizing some spells avoids the lack of mana when you need it the more.
So once in Gold League, the main purpose was to acceed to Legend…
To do that, I specialized my wizards in two kinds : defenders and attackers :
- The defender will search snaffles which are nearest from my base,
- and the attacker will search snaffles… nearest from him (the naive logic is good for attack ;).
An other thing I found very important was not to lose a snaffle, sadly because you are shooting in the goal and an opponent wizard or a Bludger is next ahead. So I implemented a simple test :
- Is there an opponent wizard ahead ?
- Is there a Bludger ahead ?
- Is there one of them at 45° or -45°
- Is there one at North ? at South ?
But what to do if the answer is yes ? In this case, I decided to let my future simulator to decide, but for now (I’m still in Gold), try some interesting things in function of the situation :
- Throw snaffle up, down (mainly when next to my camp)
- Throw snaffle 45° of -45°
- Moving 45° or moving -45° with the snaffle with me. This is made by moving with a thrust of 100 : the snaffle stay in the wizard circle. It should work up to 130 but I’m not sure (? 130 + 130 + 130 = 390 < 400)
This last feature is very interesting, because when a wizard keeps his snaffle in his radius, the opponent cannot get it without casting a spell. It is a very important point of the strategy : If you don’t loose your snaffles, the opponent would use many spells to get them.
But how to decide if my wizard has to keep his snaffle. Well, the fact is that many times, when you shoot in the direction of the goal, your snaffle doesn’t go very far, just because your wizard is going on the other way. So here is the point. If the speed of the wizard is not enough to throw the snaffle with a sufficient speed, so you can keep it. My test was here on a wizard speed of 100 on the X axe to the opponent side (writing that, I’m just now thinking about a more generic direction which could have solved some many other situations…)
Here is a replay from Gold league to show the game experience of this feature : https://www.codingame.com/replay/161493034
So, when Legend league opened, I was in the subway. On my phone I found me 98th in Gold… after the Legend openning !!! I tried out an IDE match against the Gold Boss to find out how it was possible and saw that the boss had a basic strategy but with one attacker and one defender ! Ho ! My code can do that too ! But for now, it had 2 attackers and always try to dodge (keep snaffle while go around opponent). So I just had to change all my parameters.
Still in subway, I assigned 1 attacker and 1 defender, saying them to dodge only if I lose the game (negative difference between my score and the opponent score). The reason is, in Gold legend, many players had very offensive tactics and speed attack is generally better against them, but on top of the ranking, my dodge strategy would be better… The dodge condition would permit to have two game styles within the same unique submit.
I waited to take on the bus to submit, survey the progression all the way, and when I arrived at my destination, I was in Legend league in top 50. My best travel in a bus on a friday evening !
Legend League
But the Legend league was another story. My Gold version was well placed, but while 2 days, I had worked on a new version, with a new assignment function, the beginning of a simulator implementation, and with a lot of new features. I didn’t push it in Gold league because I waited Legend to avoid the risk of a regression in Gold (I have made this mistake too much in league contests). That was my best idea on this contest, because the regression happened… but in Legend.
It was like hell with incomprehensible bugs I spent more than 1 day to find out : Timeouts, Segmentation fault, memory overflow (the worst, when your variables are overflowed by your stack you know ? Oh sorry, stack overflow is not only a great web site, my code is C code)…
On the last day (sunday), my Legend code was ready with my new assignment function and my “half” simulation engine.
Assignment function
Here my wizard can be posted on 4 different roles. Each role can be redesigned so I could have add other roles if I needed, but I had not enough time for that :
- Defender : As in my Gold code, find the snaffle with a good combination with nearest from my camp, nearest from enemy, nearest from me
- Attacker : As in my Gold code, prefer the nearest from me, but nearest the opponent camp too
- Chaser : Only find nearest from me, but also a little nearest from enemy
- Guardian : The guardian is mainly assigned when one snaffle only is left in game, so he can help the other wizard, but he can also play a role in some situations. The guardian has to intercept enemies and protect your camp.
- Isolator : I didn’t implement it, but the idea is to keep snaffles with you in a corner, when the game is nearly ended and the win will be for you (a trick from CB)
I need to say that all distances are calculated on future rounds (t + 1 or more) to anticipate all movements and positions. For snaffle, the evaluated position is an intercept factor between his actual position and the final approximated position.
So now, how to assign your 2 wizards on a role. There, the game is evaluated (win, lose, points left, snaffles positions, enemy positions, …) and the result is the 2 roles you need in this situation. Then the assignment function calculates all possibilities (4 roles x 2 wizards x N snaffles) and returns the best one, principally with distances evaluation.
To catch his snaffle, then each wizard can :
- Go to it, compensating all speeds with a simple logic : calculate the final position of the snaffle, apply the intercept factor, finally substract your speed on this target position (trigo doesn’t disagree too much
)
- If the snaffle is on your back, and if mana allows it, casting an Accio spell can be a good thing, in situations where the game strategy is saying that catching this snaffle far away on your back is a good thing.
- One of a feature coded in the last 2 hours was to kick opponent wizard if you compete vs him on the same snaffle. Simply go to the point between him and the snaffle in this case.
- Another deadline one was to avoid bludgers, with a repulsive vector. But I think this vector was buggy and didn’t work well, or not at all…
Actions
When a snaffle is caught, you know it because of the state input. But because of the different choices we will have among actions, the condition here will be not only the state, but also the distance condition (< 400). With this information, you know that the snaffle is yours or not. Then :
- Throw to the goal (if speed condition is OK)
- If you are in the defense area (near your goal) throw up or throw down (You can throw to the opposite goal but be very sure of that)
- If there are obstacles on the way, throw to other directions (here my simulator will take relay in the last hour of the contest)
- If speed is not enough, go 45° north or 45° south, keeping the snaffle with me (dodging).
All those actions may be different if wizards are on a role or an other. I can regret the lack of time for trying more different combinations, principally the dodge one. Only guardians have it in my final submit.
Simulation
I read all interesting posts made on the CSB contest simulations. I know that it is the way to follow, but also that implemention of all the needed calculations is not a piece of cake. When Magus describes how he cuts the time axis in pieces to detect collisions beteen 2 time units, the first thing I’m saying to myself is “Wow, how all that can be possible… ?”
Actually, all my strategy is based on searching open space to throw my snaffles, so I didn’t need to calculate collisions for that. If collision occurs, so let it be and we’ll see. Nevertheless, I needed to know if my throws were secure to improve my chances of marking points. To do that, my simulation function will only calculate positions and bouncing against walls. If a collision is detected with the snaffle I threw, the simulation rejects this case and go to the next. Detection will simply be made with distance comparison after adding some margin to the radius of entities, when I don’t know exactly where it can be. The speed friction is also adapted because bludgers and wizards never let their thrust to zero.
With this kind of simulator, I could simulate 180 angles (-90 to 90) with a depth of 12 without any performance limit (near 15 to 25 ms). The good thing is that the simulation gives the exact final position of the snaffle I want to throw. The bad thing is I can’t be certain of the position of all others entities. So collisions may occur and I will not detect them.
With a complete simulator, I don’t think I would have change my high level strategy, but I could have simulate other angles (on my back), which would have permit to find improbable moves, to search bludger bouncing to accelerate, to use walls or other bouncing for marking more points, to improve the spell casting decisions, …
Yes ! Simulation is a great thing. I’ll wait the multiplayer game to give it a try
Oh, finally, I ended this contest in 43th position.
This was a great challenge and I enjoyed it.
Thanks to all of you for this.
