Lost in strategies

[Di_Masta]

I feel like I want to share my experience with CG games, so far, and ask you for opinion.

It seems to me that when I’m using some greedy algorithm I’m getting better results rather than when trying to implement “big search algorithm”.

For example in “The Accountant” contest I tried nothing fancy, just plane, well structured, “if else” blocks and I did quite well, compared to my other accomplishments. In Code4Life again I tried simple evaluation of the game state and making conclusions based on that.

But when I try rather complex algorithm like big game search algorithm I cannot accomplish almost anything. Almost all of the attempts end up in slow algorithm or very big branching factor. For example in Mars Lander I tried to study Genetic Algorithms and really want to solve the task with GA I went through many tutorials and my algorithm won’t converge no matter what I try.

Even I wrote animation simulation to see what I’m missing:

(more brighter path has low evaluation)

But still nothing, may be I’m not using the right mutation. But I cannot conquer the randomness. Not to mention it’s slow.

In legends Of Code and Magic I started with simple strategy to play all possible creatures from hand and attack first all opponent creatures then hit the opponent. This strategy was working like charm in the first leagues and then I decided to make tree which first makes all possible hand combinations simulates them then simulates all items for all targets and finally all possible attacks. The branching factor was gigantic. Tried to decrease it, but I was completely tangled with tweaks like when to play charges, which Items to use, when to simulate attacks, each thing depends on the other, so I hadn’t great success there also.

Other thing I thought was to encode my state as narrow as possible, to use every bit of several ints or longs, with big amount of masking and bitwise operations. And I thought this could grant me the possibility to have bigger branching factor, to store more graph nodes with states and to get in the time limit. Nothing like this, not to mention it is hell to debug.

Recently I was solving SkyNet episode 2. At first I thought “this task is great for Dijkstra’s algorithm” after 300 pains and many days I managed to solve it using Dijsktra and after browsing the best solutions I saw that the right algorithm was BFS and I had no clue about that.

Is it me or someone else have similar obstacles. May be I’m not so talented to see which algorithms to use or I’m making implementation mistakes.

Cheers

[accorp]

Hi,

I also had and I’m still having difficulties, after all my “field” is very different from the things going on here (CG). So let’s call it normal. It is also very likely to hit a good hypothesis with a very primitive program that assures a good strategy.

I’m not sure what the problem is with your GA judging only by the animation. In fact it looks OK even. If you’re using some “decay” for the “learning rate”, check if it is not going 0 or negative. If you’re not using a decay, maybe you should try it - limit the range of the random generation values for each iteration, so the convergence is more narrow.

My first attempts at the algo were horrible, but they all turned out to be mistakes and/or bugs. Running a performance analysis is very good for finding bottlenecks and chokes. For instance, you could be having a lot of useless copy operations and such - i had this problem at first, when I was done with the evolution, I copy the generation results in the population buffer, but later on I realized I could just swap the buffers and use the evolution buffer as a source for the next one.

All in all, there are a lot of difficulties along the way, the worst ones being related to randomness. Not being able to reproduce a situation is a pain, and even doing so can also be pain as the error stream printouts can brake literally everything. And that’s way the top coders build/borrow offline tools and such for the sole purpose of dodging the CG IDE. You can think about that also.

My advice is to not give up. You got frustrated a lot I assume, but it will all come together at some point. When dealing with new stuff, try to take it easy and get plenty of rest between coding sessions - new information is sometimes absorbed slowly. Break the task in small steps and test a lot each one after implementing and be thorough about it.

Good luck!

[Di_Masta]

Thanks for the advices, man, they are really nice

Sometimes when I invest much time and effort it is quite frustrating when nothing is solved. Especially when randomness is involved, as you said. I suppose there is solid math theory behind all random related algorithms, may be it’ll become clearer with more experience and studying.