How can you be so fast

AI Battles
#1

Hello,

I’m doing “The Great Escape” challenge and I was wondering how top players are so fast to code good AI.

I mean that I need around 80% of the time challenge to implements all the datas obejct, and rules.
I’m using TDD so my AI never do invalid moves, and the code is quite clean.

The only problem is, that for me the actual challenge : coding the AI of my bot, is starting only a few days (in best cases) before the deadline.

For now I have a very simple AI, witch build wall (if possible) on the shortest path of the ennemy if he can finish before me. With that my AI is around the 350 position.

I have of course many ideas that I want to implements, but there is no way that I’ll have time to do it.

So my question is :
How can you be so fast to implement good IA?

#2

This is a tricky question, I myself code what you call “rules and data objects” on the first day for a two week contest and then code the AI.

I think speed is gained with experience. As i’m not a senior developper myself, you can’t really compare but I think I’m faster than you based on your standard because I did and redid a lot of those puzzles. (and some before codingame too)

Basically, what I’m doing is doing from worst to better, a minimum viable project(MVP)
For example on this contest (even if I didn’t had time to really participate in it) I did:

  • Move my dragon to the other side of the board (up, down, left and right)
  • Do a best-path algorithm to be able to get out of maze

And that’s it for the basic rules. After that, it’s the AI and how to evaluate when to block. There is one more rule on how to put wall but after that it is full AI.

So that’s it, considers simplify the problem like I did, even ignore some rules at first and then upgrade your product until you’ve done it entirely. This way it’ll show result (even bad ones) sooner and it will encourage you to keep going.

Hope that’s help :wink:

#3

Thanks for your answer,

I guess you pointed the right thing, I need a bit more experience on this kind of challenge to be faster.
I now have a general architecture that I can reuse for the next challenge.
Hopefuly, I’ll be able to finish “the rules and data objects” much faster next time.

#4

Hello Cerobe,

without being a lightning fast coder myself it took me a few hours to get the basic architecture of my code, so parsing the input, building a graph of Cells connected to each other and trying to move in the right direction without looking for walls.

After that I added the logic of wall parsing, being able to disconnect cells and I tried to move around walls on the field.

Third phase: writing an A* to find shortest path for each player.
Fourth phase: write a basic IA to place walls on opponent paths.
Then play with it to add depth management (MaxN /Negamax whatever).

Realize you timeout too often… try to optimize and limit the positions you consider.

And i’m not using TDD, and not even test outside of codingame, which is a BAD habit :wink:

Like this you have a sense of progression and you enjoy seeing your IA improve. Of course to be really good you need to have good ideas, to look at other IA, and to spend more time I guess.

But maybe you are only spending a few hours coding for this game ?

#5

Hi Nergal,

I guess i spend a bit more than 10H so far, between work, friend, and sport, I can’t really have more than that. Unfortunately.

Like you I’m doing all of these steps, with TDD it’s easy to do incremental steps. The thing is that I need to be more efficient to code a good AI in less than 20H. So I was wondering if there was something else except experience and good ideas, that could help me to save time.

As my code is quite generic, I think I’ll be able to reuse it for the next challenge, and be able to focus much more in the “Intelligence” part of my AI.

Thanks for your anser

#6

I think if you practice with the single player games you can get better at building up your data structures and stuff quickly. I find that an object oriented approach makes it much easier. I use java and I have my own class which I use to manage state and data. The “Player” class provided by codingame does nothing but instantiate my own class and feed data to it. For TGE I had 8-9 classes.

#7

I guess practice is the key factor :slight_smile:
what took too long for you ?

  • having an idea on how to organize the code and which structure could be used
  • writing the tests
  • writing the code

On all cases as some elements are very common in such contests after several trainings you will probably be able to quickly have an idea on what to do. Good luck for next time :slight_smile:

#8

One thing that can help is if you save any algorithms that you write for future use. For example, I have Dijkstra and A* algorithms saved some where, and whenever I need them for a puzzle/contest I can just copy-paste them. Then I only have to define transition function, cost function, and heuristic for the specific task.

#9

I don’t write tests for something like this. Not sure if there is a payoff for spending so much time on tests. The thing that definitely takes the most time is refining the logic and algorithms. Initial data structures for parsing and holding the data is very quick. I think I had a basic algorithm that could find a path around walls after 2-3 hours. Of course as the algorithm gets more complicated, more data structures get added and refined. I don’t try to plan much out at the beginning. Chances are if you do that, you will end up rewriting a bit.

#10

Another tip, try to keep track of your changes in git. I have my code stored on github. It’s free and private, but I can always revert back to some previous code if I want to abandon some changes I made that weren’t working.

#11

GitHub has free private repos only for classrooms, but you can use Bitbucket or local git repo (dropboxed in my case, several times it helped found uncommitted versions, but it isn’t recommended way).

I think you can have some tests, but only for common parts like Dijkstra. You should be ready significantly rebuild your solution in any time when you understood, that some features are required and you can’t just do it in the current solution. On TGE I had several such rebuilds (big or small):

  • simple decision tree with movement and walls (like your, and also about top-350 on the finish, but this AI was in top-10 first days, so you on the right way ;))
  • some heuristics
  • minimax (it had to be the first step, but I was not familiar with these algorithms previously)
  • alfa-beta pruning (for 3 players too)
  • some optimizations (partially renewal of paths matrix during wall addition, caching
    of paths matrices by walls set and so on)
  • some heuristics

You should be ready write fast code for proof of concept, and remove or optimize it later.

And finally - fast coding is necessary, but also you must have a lot of good ideas on the all stages of such contests, and time to analyze tens and even hundreds of replays (why enemy do this? why I do this? where is bug in my code? ohh, no any bugs, my AI just prevent another bad situation…). Without ideas and time you can hope only on top-100 result (my case on TGE :().

#12

Correction, GitLAB. Typographical error on my part.

#13

Hi Cerobe,

I think most of the contestants are simply not writing tests. They potentially just observe their AI and certainly output some kind of debug infos on the err.

It’s been a while I participate to contests now (started with planetwars google AI challenge in 2011) and it’s been almost 10 years I am a professional developer.

I believe tests are a must when you write code in a professional context, But for the contests, I think you might skip them and end in the top.

Personnaly I always have tests aside of my AI. Knowing what to test and how is a difficult task. I tried different approach, and I would recommand to:

  • Write tests on the basic part of the code you know that won’t change. For example, game state, game transition, pathfinding algorythms, game evaluation etc. Those are the key pieces of your AI, and you can’t affort a bug in it.
  • Write tests on the behavior you expect any AI would do. For this you will need to write simple tests such as if I can win and it is my turn then do it. If the opponent can win, I must place a wall etc. I would see them as integration tests, and you can rely on them even when you rewrite completely your AI. On my side I always have methods in my IA that allows me to write tests using only the same inputs we receive from the standard input in the string form.

As you see, when I write my AI, I rely on solid tested blocks, and I have integration tests that guaranty that my AI is behaving correctly in more or less evident situations.
Then watch your AI play against other players, and select your opponent accordingly to the level you expect to be. If you find an issue, a good idea is to write the testing code on standard error, so you can directly copy paste any step of the game, and directly debug your AI in your favorite IDE.

On TGE I also rewrite the game engine. Assuming my bot was only producing correct moves, the rules are super simple to write : I think in an hour I had the game ready. I used the trueskill comparison tool I wrote when studying trueskill (you can read more in french on this post : https://groups.google.com/forum/#!topic/codingame-game-of-drones-fr/jOf9LZdOXl0) and I just had a local working the great escape tournament were I can make play matches between my AIs and rank them using trueskill. It was for me a great opportunity to define my evaluation function parameters in a genetic algorythm approach.

Top players are certainly spending a lot of time on their AI. I have the chance (or not :D) to have arround 1h30 of train every working day, so I code on my laptop. With one or two evening on the subject, that’s generally more than 20 hours spent coding on a contest like TGE.

One last thing, do not skip the documentation phases : TGE was for example very close to a game named Quoridor, and you were able to find on the internet thesis on building an AI for this game. Even if you have to adapt to the rules, it gave several ideas (even if I found them quite basics…)
I also always spent a couple of hours with a pen and a paper, just to write some ideas, try to find a way to optimize things. Sometimes you see obvious things you would not have catch in your code.

#14

Hello Manwe,

Nice post and congratulations for your rank. I’m very interested by how you evaluate your bot in a local mode. Would you have time to make a code review on your trueskill system ?

Cheers,
Hui