Archived talk:User:Rednaxela 2012-05-16

Slow Algorithms

Well then... I set up some code to via brute force calculate nearly all possible ways a bot could move (restricts turning to 3 possible values and acceleration to integers) within a given amount of time. To calculate for 10 ticks it took about 1 second, which is very good for my purposes. To calculate for 20 ticks however... it didn't seem to stop even after hours so I calculated roughly how long it would take with my algorithm that got 1 second for 10 ticks and it turns out that for 20 ticks would take at least 110 years!!! Wowzers... looks like I'll have to diverge from brute force and work with some methods that drastically reduce calculation at the cost of significant approximation... --Rednaxela 16:07, 26 January 2009 (UTC)

Those exponential algorithms =S, maybe instead of approximating you could prune branches of your search tree, a lot of states will be very similar and some others will have low probability. Hope it gives ideas to improve your algorithm. --zyx 23:42, 26 January 2009 (UTC)

Well, for my purposes, pruning low probability states would be unacceptable, however I am planning to redesign it so it can prune sufficently similar (or exactly the same if I can afford it?) states of each tick. The memory requirement will unavoidably be drasticaly increased however in order to make non-recursive as that would require. Hopefully that memory requirement increase won't get too high. I intend to make these calculation for at least 100 ticks so yeah... Hopefully I won't need to borrow a supercomputer to get SaphireSlippers on the road... --Rednaxela 02:06, 27 January 2009 (UTC)

How about working the other way around? Instead of working out all the different ways you could move, and seeing where you end up, take lots of different places, try to get to them, and see where you end up. (Basically, my style of GoTo Surfing ;-) ) This way it is very easy to limit computational time: just increase or decrease the granularity of the places you are using as 'targets'. And also: what's up with 1 second of computational time being acceptable? Are you pre-computing all possible locations, and then just transforming them at runtime? My guess is that would be slower than precise-prediction due to evaluating the danger at the HUGE number of possible positions. Although I can see it's usefulness... finding optimal locations considering distance etc. For a 'pruning' technique, how about 'merging' all entries that are at the same velocity and have less than a certain amount of difference in the heading and the location? --Skilgannon 10:01, 27 January 2009 (UTC)

Nah, choosing destinations like that defeats the main resons for this method: It allows the robot to be completely aware more optimal ways to get to a location than a robot's typical goto(location), inherently know the perfect amount to smooth movement around a wall, and inherently will know exactly how much slowing down on big turns is right, and so on. And yes, 1 second i extremely acceptable because I'm precomputing a table that designed to be quick to look up at runtime for: what locations can be reached, any possible ways to get to them, and enough just enough information to in order to know at runtime if a wall will be blocking one of the ways to get there. Also, as for runtime performance, I avoid the number of possible locations to evaluate at runtime being too "HUGE" by putting the end resuts into a resonable finite number of 'slices' of sorts. As far as 'pruning' to improve computation speed, what you say is essentially what I'm planning :) --Rednaxela 14:53, 27 January 2009 (UTC)

---

Surfing

Melee Surfing

As you write to me, I now have some new ideas on melee surfing!

I'd agree with your wave detection, but I have some new Surfing ideas to you!

For surfing, you need multiple ways of Precise Prediction (or your Slow Algorithm). Only return set of points before the first wave hit. I think 8 ways should be enough. Now, for each of these points, do minimum risk! Multiply risk by wave danger and move to lowest. And one more ideas, you should surf non-firing wave, too. only weight a little bit lower since many melee GF gun take stats from non-firing wave.

I don't implements it yet but I'll use it in melee-compatible version of BlackHole (not sure for 0.2 but I promise I'll have it in 0.3).

I'd like to named this style WS-MR. You may named it if you finish first, but it a nice name.

» Nat | Talk » 07:20, 14 February 2009 (UTC)

Rambot Surfing

Ha ha, I really like your rambot surfer ideas! Do you have any ideas about it? I have.

In Voidious's Komarious movement, he use a little bit lower than half pi, so you may use a lot over half pi (let say 2.25 or more) in order to surf. Let say more, I think it will have an opposite way of Dive Protection (It avoid getting too close? this form will avoid getting too far.) You may add some factor to your wave surfing to cornered you enemy (like another rambot).

Once you getting enemy cornered or getting very close (say 150px), go ahead and ram him. That's all my ideas.

» Nat | Talk » 07:20, 14 February 2009 (UTC)