CodeBuster - Feedback & Strategy

Contests
#41

Thanks for all the great posts everyone. I don’t have many new ideas to contribute, but I wanted to share some small details that I implemented which seemed to help me towards the end of the competition. I ended up rank 15.

  1. When assigning stuns onto enemies I always assigned my carrying busters stuns first. If you have 1 carrier + 1 escort near an enemy buster, the enemy buster almost always will stun your carrier, so it is better to use your carrier’s stun than the escort’s stun. I think the worst case is if your carrier has a stun ready and you use your escort’s stun to stun the enemy. Then your carrier has a stun but is useless for 10 turns. So better to go 1-for-1 with the stuns.

  2. When I escorted my carriers I always positioned my escorts slightly outside the minimum bust range of my carrier. This way if my carrier gets stunned, I can immediately bust the ghost and continue towards my base.

  3. For exploration, ghost locations, and enemy locations, I created these “heatmaps”. I subdivided the map into a 5x6 grid and then created a 2-D array for each. And then I would update them based on certain rules. For example, in the enemy map, every turn I saw an enemy in a zone, I would increment the cell in that array by 1 and the cells of the zones within 4000 range (arbitrary) by 0.5. Then every turn I multiplied each cell’s value by 0.8. So this map gives me a sense of which zones most likely has enemies. The longer that I don’t see an enemy in a zone, the value is decayed by the factor of 0.8. If my home’s zone was one of the top 5 most dangerous zones, I would hide my carrying busters in a corner. (Though this strategy was not significant since the best bots did not base camp anyway).

1 Like
#42

First of all thanks for the excellent contest.
I was not able to get out of gold league and finished 174th.

I tried herding (with 2 or 1 buster) – it was not worth effort (at least against advanced players).
I tried camping - it is easily countered by most players.
I tried different strategiest against campers - didn’t want to do escort thing, hug the wall from 5000, 0 -> base was good enough for me for most cases.

Most effective thing that raised my ranks is interception code (so I can chase enemy busters with ghosts).
Logic is as simple as possible - assume he is moving straight line to base, calculate points 800 units one from other on this line, check if any of my busters can get in 1760 range of this point and have stun on cooldown - go for it.

What I find weird is ranking system: I adjusted code to beat boss 2/3 of times and have draws on almost all other matches - and ended well below 300th in gold leaderboard, so had to revert to code that beats other players, but not boss.

Also, one of the things that raised my ranks was simple logic - if I see enemy busting ghost and do not have enough busters in range to counterbust it – move in position so you can stun enemy and get his ghost right after he finishes busting.

Well, this was fun contest, even that I didn’t enjoy my final results, I could do better.

#43

From Database Managers view, I haven’t coded in anything except SQL in many years, until my brother sucked me in with sample code for ‘Code Strikes Back’, the entry curve was not steep and it didn’t take long to get a working AI. I finished in the silver league, just couldn’t get the camping to work. Personally CG causes my brain to work in ways that it hasn’t in years, very cool. Thanks for the challenge and for the fun. BTW if you finished under 1015, well better luck next time, this Database Manager put the whoop on you!
My strategy: head home to release, travel along wall when getting close. If not carrying stun, maybe should have checked for stun first, if not able to stun and can bust, then do and don’t stop, took awhile to figure it why I kept stuttering when stunning in Silver. Modified code late in game to check stamina prior to busting, 30 was my cut off.
I lost quite a bit of time working out bugs that a more experienced developer would have found quickly. Total time spent, 20-25 hours. Goal was to finish in top half and I missed.
Battling you in September.

2 Likes
#44

Eventually I ended up 5th despite being 1st first half of the contest. I think the reason is that I didn’t pay enough attention to the small details and didn’t believe in herding :slight_smile: I spent about 25 hours in total on coding and watching the replays, 10 hours of this 25 were spent during the Saturday – one day before the contest has ended.

Most of the ideas were already mentioned in this topic, so I’ll try to keep this comment short.
0) I coded my exploration algorithm in the first hour after the contest has started and didn’t change it during the whole contest. I consider a grid on the playing area with step = 100. I have a set of “unseen” nodes of this grid which I update every turn. When my buster wants to pick up new target to go to, he selects the closest node from this set, but adding to all distances random number from 0 to 3000. I could not decide what is better: to explore large area with all busters walking alone, or to explore small part of the map with the group of busters in order to defend against opponent and to catch found ghosts faster, so this random change of the distance could lead to either of this scenarios.

  1. I had two modes: “usual” and “careful”. Second one was enabled if I see half or more of opponents’ busters near my base or there is one ghost left for my victory. In the “careful” mode the whole team worked as a support for the buster who was carrying the ghost. If my buster who is carrying a ghost finds himself significantly closer to base than it’s support guys, he waits for them.
  2. I didn’t try to steal ghost by sneaking at the opp base, because I’ve found it boring :slight_smile: But I did try to intercept enemies going to their base assuming they will use straight path, so I could not intercept Khao’s busters that moved along the walls.
  3. I didn’t come to the idea of chain zapping used by Hohol as I am not Dota player :slight_smile: Still, if I need to choose between stuning enemy busters with stun cooldowns equal to 0 and 5, I will choose one with cooldown=5, as buster with zero cooldown will use its stun anyway.
  4. I had absolutely no time to code during last Sunday. When I woke up in the morning, I saw matches vs Recar who proved that herding can be done efficiently. I tried to implement something similar, that I ended to code in my friend’s car and submitted when we arrived to our picnic location :slight_smile: After a few hours I decided to check how it’s doing and found some bugs that I fixed while my friends were playing frisbee.

Now some words about code organization.
I had base class for Entity and two derived classes for Ghost and Buster. All game information such arrays of busters, ghosts, base locations was stored in class Game. It could read information about new turn and update corresponding fields. I also had class GameAI which possessed tactical information such as behaviour mode, movingTargets, lists of enemy busters to intercept and so on. There was one main method named “makeDecisions” that subsequently called methods dedicated to particular activity. Part of it was as follows:

setSupportWhenEnemyNearby();
setInterceptors();
setBusting();
setStunEnemyBustingGhost();
setExplorers();
for (int index : movingToBase)
    setHerding(game.myBusters[index]);
setFancyChat();

Each method considered only busters that weren’t used in the previous methods (with a few exceptions, for example, for herding). Last one was the most useful method, of course :slight_smile:

I didn’t use any unit tests as I’m totally fine with controlling code of this small size (1.5k lines of code, including empty lines – about 50kb in total). I had a bunch of asserts here and there, though. Asserts are great way to prevent using some methods in the way you didn’t suppose to use them earlier :slight_smile: So for those of you who is thinking that unit tests are taking too much time to write I can suggest to try asserts. Nevertheless, I liked the way Hohol organized his testing: maybe I’ll try his recipe in the future.

I do not want to share my code as the game will be available for multiplayer soon, but I can answer any questions that you may have about some details of my implementation.

I enjoyed this contest a lot because I like to write team-oriented AI very much. This kind of games always include at least two levels of AI: high-level AI to determine current mode and goals for each unit and low-level AI which makes unit to achieve its goal in some optimal way. I hope similar contests will be conducted in the future :slight_smile:

10 Likes
#45

i liked your approach my one was similar to yours but i ended in 324 place i thought that to be in top rank i need to implement some exotic algorithms but seems from your explanation that you didn’t use a particular algorithm or did you :+1:

#46

I’d be interested to know what advanced players thought were the keys to getting out of Gold and into Legend. I spent a lot of time in Gold, but my tweaks never seemed to be enough. After reading this thread, I think the key ideas I missed were:

  • Mirrored ghost positions (If you see a ghost at 100, 1400, then its pair will be at something like 1400, 100, but skewed for the rectangular field
  • Chain stunning opponent busters (knowing when an opponent will come out of stun and stunning them again)
  • Guarding your own ghost carriers, or coming to help them if they get stunned
  • Using stamina to affect ghost busting priority
  • Cutting off enemy busters carrying back to base and stunning them.

Any other “advanced” ideas?

My exploration was a breadth-first-search of grid blocks based on previously seen grid points. At the beginning of the step, I would mark any block my busters were standing in as “seen,” and if they needed to explore, they would do a BFS of their nearest grid neighbors looking for unseen grid points.

#47

This was my first attempt at particpating into a coding challenge and i have to say that you (CG + All) made it a pleasant (and dangerously addictive) experience !

A quick feedback on what would have been appreciated to make this experience even better:
. A detailed analysis on played battles would have be great so that we now in which context out IA performs well and where it should be improved
. A debug feature feature in the java IDE would be nice: being able to view the values of some variable at some frozen moement in time
. It would be nice to be able to launch a good number of battles against the boss (10 ? 100 ? ) at the same time, in order to be able to statistically determine wehter this option or that option is the best when you are unsure

Anyway, thanks again !

1 Like
#48

I’m trying to implementing your strategies according to your post and your github. I have no problem at all for reading your code but i have 2 questions:

  • Your github code is separated in multiple files. But you can’t just copy/paste multiple files in codingame. I was looking for an Ant task or something similar to “build” the final artifact. But i can’t find it. I’m curious on the process / tool you use to compute all this classes in a single file

  • I just can’t find your “real” main function. I found a main function but it tries to read an “input.txt” file and obvioulsy it does not work on codingame :smiley: Coding a main is easy but i’m also curious of how you generate this main. Do you have a tool for that ?

I suppose my questions are linked to the both files chelper.properties and CodeBusters.iml, but i can’t find how (or with what tool) to use them properly.

I don’t often use java for contests (but i use it massively at work). If you have a working process that permit you to code in multiple files, i would be really glad to learn it.

#49

I used CHelper plugin for IDEA. It both combines source files into one and creates an entry point for program.

1 Like
#50

Thank for the response, i’ll check that

#51

Is there any plugin for Eclipse ? (I didn’t find one)

#52

I really like the idea of running a larger number of battles against an opponent for get some statistical knowledge. I’d really like to know if I’ve improved my algorithm, or I just got lucky!

1 Like
#53

That sure would be neat, but it’s unlikely to be featured since it would discourage people from pushing their AI in the arena :cry:

1 Like
#54

You mean people would hold off submitting so as to not give away their AI strengths? Why would they not still check their ranking vs all AIs? I would love to see a way to run a large simulation vs an opponent to check how well my changes are really doing.

#55

I think the issue is that people would hold off submitting if they knew for sure that their AI was not better than the previous one. Right now, people can only run a handful of times, and then submit if they think they are close or slightly better than their previous run. If I knew that my last submission beat the AI 45 out of 100 times, and now it beats the AI 47 out of 100, I might not bother to submit, but wait until I have 55 out of 100 or something.

#56

Hi everybody,

Codebuster is a very nice and interesting game. After full four weeks improving the full shepherd strategy (thx to Recar for showing the way), I think the game is not yet finished because new strategies will come for sure to beat it.

I think the best thing to do before doing the shepherd, is having a well improved strategy in searching ghosts and manage opponent, because Shepherd can have fatal issues if some errors are made. The point is that this strategy pays only at the end of the game, when a sufficient number of ghosts are collected. All you have to do before that is pushing ghosts in your base the faster you can. It is not so easy because other strategies are based on speed collect. So the game is a real course vs time to win it.

The shepherd logic is organized in 2 phases. The first consists in pushing all possible ghosts in your base. The second is busting all ghosts. To do that, the score is controled all the time to see if the game is winable or not, for example, when there are not enough pushable ghosts on the board. In this case, we have to abandon shepherd for another tactic until the score is reachable.

To identify the 2 phases, I use a simple flag (win == 0 or win == 2), based on the simple formula : my score (you have to calculate it… not easy) + my ghosts in hand (state == 1) + ghosts near my base (dist constant 1600 works well but 1000 is better) > total number of ghosts / 2.
(win == 1 is for the case my score and my ghosts in hand are enough to win, but it is never the case when shepherd strategy is active.)

Notice that time is limited (only 250 turns). So the game can be lost if you cannot kill all ghosts you have collected in your base before the end of the game. All the first part of the game must be focused on pushing ghosts, and nothing else. The difficult part of the strategy is to know what you can do to annoy your opponent without losing time to push your ghosts. The priority is the shepherd rule which consists principally in determining which ghosts are to push (inner) and which are not (outer). The rules here are very simple : push all ghosts you can. I tried few global limitations but that did’nt help more. But indeed every buster will have his own limitations… and knowing if a ghost is pushable or not is not so easy in fact…

While pushing, I can do some other fun actions :

  • Always stun an opponent if he is busting a ghost : he will lose time and the ghost will be free to be pushed
  • But wait before ghost is very weak : the opponent will lose more time :slight_smile:
  • Intercepting opponent when he has captured a ghost is a good thing too, because he will lose time and generally, the battle is on the good side of your shepherd perimeter. For real, in this strategy, all is on the good side (except your starting point). Even the opponent has to push “your” ghosts to approach them. It is the really really funny thing here :slight_smile: :slight_smile: :slight_smile:
  • Bust weak outer ghosts
  • don’t bust outer ghosts if they are far or to tough (tougher than 3)
  • If you captured a ghost, don’t go straight to your base (this would ruin the shepherd strategy), but go on pushing other ghosts
  • But you can defend your capture ghost : dodge, come with other busters, and the best thing EJECT it in the shepherd perimeter (but I think I can improve my EJECT skills to pass ghost from buster to buster in some situations)
  • A very good thing to do instead of RELEASE is to BUST another ghost (there are many) in your base, because you gain time for your future busting phase.
  • Don’t bust inner ghosts (in the perimeter), prefer push them
  • But you can bust them to save time for later, when pushing other ghosts doesn’t need to move, until endurance is 1
  • If there is not enough ghosts possible for the shepherd, do the classic game :slight_smile: (here I have to improve my exploring skill because it is very poor)

When the first part of the game is done (win == 2) the thing is to bust and bust and bust.

Here, the stunning rules are not the same because you have to do that just in time to keep charge and to avoid opponent to steal your ghosts.
If an opponent succeed in stealing a ghost, don’t go after him is better than go. If you have to do that, the win formula will say it :). A lot of good news here. If you captured a ghost and the opponent stuns you… 1 point for you. Idem if you stun him and he is in the 1600 limit. And if finally he managed to steal one ghost, he has to return it to his base, letting you time and a superiority in combat. So a lot of fun for you ! :slight_smile:

But sometimes, at the end, some game may be lost because time is out. You may lose too if the opponent is the best in combat and he got some great advance in score during the first phase. Or if you have a lot of tough ghosts to bust, and there is not enough time.

Other cool things you have to do with CodeBuster :

  • Good exploration because when all other actions failed, this is the only one option left
  • Counting score : this is not so easy because ghosts can disappear (captured by opponent, dropped in a base because of stun, …) The worst thing I saw was in my base : 3 busters of mine vs 2 enemy busters (the 3rd was stunned). When the ghost has been captured, there was this “neutral” turn where the ghost is floating between all busters, without changing any state for them Just on this turn, a buster of mine shot a STUN on opponent. No luck, it was the buster who had to collect the ghost (I think the rule of nearest buster collecting is not working because it was not the case). The ghost was dropped in my base and collapsed… no point in my score counter (how to get it ? it’s a complicate rule)… bad win flag… my busters go out to collect this ghost which disappeared… game lost… I think I could anticipate the capture, but this means using a lot of conditions for a very rare situation… perhaps the score would be worth in the input data… :slight_smile:
  • Evaluate enemy position : you can’t predict where enemy are when you don’t see them, but you can say if enemy cannot be at a point because you’ve seen them elsewhere some turns before and enemy could’nt have the time to go there.
  • Radar and symetry : At the very beginning, with the symetry rule, some RADAR action can give mostly all ghost positions.
  • Enemy position : At start, you can be sure of all the opponent positions (I needed time to figure that :))
  • Calculate the best interception point for an enemy captured ghost
  • In combat, let the enemy bust the ghost, and stun him at the end…
  • In combat, go between ghost and the enemy buster… he will stun you… and the ghost will fly :slight_smile:
  • The bug was fixed, but till Silver league, you could RELEASE a ghost and BUST it with another buster, in the same turn. What about EJECT + BUST in the same turn ? No sorry, that cannot work.
  • EJECT : I did’nt explore this new feature a lot yet, but I think this new Gold rule will be the key when we will have several shepherd players trying to push in opposite directions… :). The fact is that today, pushing ghosts without push resistance, is winning nearly all the time. Even the fast EJECT strategy (like Levatol) encounters some difficulties vs massive STUN and just let the ghosts go away. But what if the two players are pushing. I know that Recar was difficult to beat because of that, and I don’t have the good solution now…

And the good news is that my shepherd algorithm is very very simple. I didn’t try to optimize ways a lot, didn’t avoid opponent blocking, didn’t make a far deep evaluation of the game, etc… So all yet can be done ! :slight_smile:

Perhaps, in this game with no AI interest at first glance, the AI time is coming. And I’d like to see that, because the strategy I applied is only a “gamer” strategy, without lot of AI (next turn evaluation only). So the best thing in all of that is the great question : AI or Human?

Very good game and a lot of fun :smile:

Thanks to Codingame for all the work

edit : Combining Pushing and Eject was finally a good thing. Taohbi who used both the technics has reached the top now. It was a great challenge for me (I think for Taohbi too) to stay in the game against Levatol because he has improved his strategy with a good “attack other base and get back ghosts with EJECT” technic. So pushing ghosts is not sufficient now, and you have to :

  • Optimize collect with EJECT at the beginning
  • Choose a strategy : Push or Collect other ghosts (personnaly, I always push when I can win with that)
  • Attack other base or defend your base
  • Good combat skills and EJECT technics make the difference
5 Likes
#57

Thanks for your feedback ! Very interesting. However, I didn’t get clearly the following point :

Not sure what you mean ? When a buster has a ghost, instead of releasing it, you bust another ghost, so the carried ghost is automatically released and you win one turn by busting the ghost ?

#58

Hi Aveuh.

Yes exactly that. The ghost is dropped and gives you the point. The purpose is to save time for the end of game, when you will have a stack of 40 endurance ghosts to bust, and there is only 40 turns to do that :slight_smile:
I think I could optimize busting while pushing ghost too, for example : push, bust, push, bust, etc… because i’m losing some games with this turn limitation.

2 Likes
#59

Hi people. I have a question. Is that true that in all games, we play relativity of the beginning coordinates?

#60

what do you mean?