| Author |
Thread Statistics | Show CCP posts - 0 post(s) |
baktul
   |
Posted - 2010.03.16 18:16:00 -
[1]
When I first started playing Eve... I found it kinda fun that looting wrecks was a 3d version of the travelling salesman... except you don't have to roundtrip.
Once I got a tractor beam... the mini-game kind of expanded quite a bit. Now I didn't need to stop at each wreck.. but I had to figure out a path that got close enough within tractor range and move along that.
Now that I have started salvaging.. the mini-game has changed yet again... now it is good to get to a location where I am in range of a decent number of wrecks so that I can gather them around me so that they are in range of the salvager. Since the salvager can take some time... I don't want to move from my cluster until I have only one ship left... then I tractor it while salvaging and moving to the next location.
Has anyone else found the looting "mini-game" fun? Maybe people hate it.. but I have had fun with it (maybe not months from now). It seems like there are fairly simple heuristics for the travelling salesman... but the tractor beam and salvager complicate it a bit.
Anyone have a guess which variation would be the most difficult to get a working algorithm for? Does anyone think that the tractor beam or salvager simplify it? I kind of wish I had a dev mode where I could set up the mini game and see how long it takes a novice to loot vs. someone who has practiced a bit.
|
baktul
|
Posted - 2010.03.18 00:21:00 -
[2]
Ahh.. always nice to be greeted your first time on a forum with a troll.
So yeah... it is true that the label for this section is "Eve Technology Lab" and the subtitle indicates that it is dedicated to 3rd party apps. I was hoping to get another eve-playing developer's opinion of the problem and figured my best chance of contacting another developer was this section. Could you suggest another section that I would have been likely to find a developer in? I suppose I could have gone for general or new citizens... but I doubt my chances of finding someone who had heard of the travelling salesman problem would have been very high.
I have not been playing for a super long time... and it would seem to me that you might have battleships spread around you out at 150km. Perhaps when I get more skillpoints... it will become trivial. However.. currently my tractor beam goes to 20km and my salvager goes to 5km. I often have to look at the wreckage and decide on a way to gather everything the fastest. Perhaps I am only saving a minute... but I can imagine that sometimes you save 10 minutes.
The travelling salesman problem is the same as trying to loot a spread out wreckage site... except that you don't have to return to your starting point. You might not have heard of big-O notation... or complexity theory... but you cannot solve this problem in the guaranteed shorted time... but you can use heuristics to solve it reasonably well with a high probability of success.
I am more interested in the difficulty in writing a program to loot wreckage the fastest... not in what a human can do sitting at the console.
|
baktul
|
Posted - 2010.03.18 03:54:00 -
[3]
@Johnathan.. do you know what the travelling salesman problem is?
http://en.wikipedia.org/wiki/Travelling_salesman_problem
You have a set of points in space and you need to visit each one (and in the original problem return to the starting location). You want to do it as efficiently as possible. If you don't have a salvager or a tractor beam.. you have to get within 2500m of each wreck to loot it. How is this not like the travelling salesman problem?
@Tonto.. I never requested advice with salvaging/looting in game. I never asked for a procedure for how to do it. I even said that I am not interested in how a human player does it... I am interested in how to make a computer do it. And no... its not to write a program to do it... it IS a hypothetical. Feel free not to answer if it really irritates you that an abstract discussion might take place in this forum. Just move on to the next topic if it doesn't interest you.
Both of your posts gave instructions to a human player. You cannot translate that so easily into code. When you look at the screen and see that there are two clusters and perhaps decide to aim between them.. there is a lot going on in your brain... stuff you are taking for granted if you were to try to write an algorithm for it.
My original post was simple.. I stated that looting wrecks without a tractor or salvager is the travelling salesman. I was interested in how the tractor beam and salvager change the problem. I was hoping that there might be a dev out there who has thought of it that way before and would like to chat about it. The heuristics for the travelling salesman most likely break when you introduce a tractor beam. A solution with a tractor beam breaks if you have to salvage. I don't care how you think I should do it in game... I care about the complexity of making a program do it. And if you think it is trivial to write... you probably have never heard of complexity theory up to this point.
|
baktul
|
Posted - 2010.03.18 17:51:00 -
[4]
Well... all I've really learned is this was not a friendly place to look for a like-minded dev.
You said "Also, don't really see any practical way Traveling salesman could be applied to looting and salvaging." It is not a question of applying the travelling saleman problem to looting and salvaging. The case where you are looting without a tractor or salvager IS the travelling salesman problem at least as far as complexity goes. A perfect solution has not been proposed for almost 200 years. It is a classic problem in computational theory and so many computer scientists think about it (obviously neither of you are terribly interested in it or familiar with it).
You say it is not practical. A very simple heuristic that will generally give decent results is to visit the nearest neighbor, loot, then visit the next nearest. It's pretty practical for a computer. Not complicated at all. Practical enough that a human can do it without much thought.
Generally people who have thought about complexity theory would expect an algorithm to be run on a computer.... unless you assume the moment you hear algorithm that I am going to bust out my pencil and paper to solve a problem. I assumed a certain level of experience with algorithms from anyone who could provide a meaningful answer (so far zero answers to my three questions in the original post, just snippy 'you are playing the game wrong', 'you shouldn't post this garbage here', etc.).
The nearest neighbor heuristic fails if you are using a tractor beam. If you have two clusters where each ship in a cluster is more than 5km apart from a neighbor... you will have to visit each cluster and visit each ship. If you have a tractor beam and the clusters were set up correctly... you could just move to one position between them and tractor everything in from one spot. Using nearest neighbor would be wasting time.
Dead thread... waste of time... disregard.
|
baktul
|
Posted - 2010.03.19 17:46:00 -
[5]
Yeah... I suppose it just seemed easier to discuss with someone who had played Eve... instead of trying to explain the game mechanics through text to someone who is interested in algorithms but has never played.
The other problem is I imagine the API does not allow you to control navigation of your ship. I also imagine it would violate the EULA to do so. Soooo... even if it was something of interest.. it would be kind of foolish to even discuss it here. |
baktul
|
Posted - 2010.03.24 03:35:00 -
[6]
 Originally by: AndrewNardella
I have found this mini game fun as well. You should try your hand at scanning, it it also a fun mini game.
Yes.. I have enjoyed scanning. It was fun when I was just a couple weeks in to scan down a battleship doing what I am guessing was a level 4 mission (I am only doing 3's at the moment). Seeing a torpedo explode was fun considering I only had rockets or something at that point. He incidentally had another account flying a destroyer doing the salvaging.
Originally by: Krathos Morpheus
Now that we have put into consideration all eve modifications to the problem, let's go back to the Traveling salesman. We start by choosing the closest wrecks to move, but we don't make long trips changing the direction, I mean if we left no wrecks behind when going towards the closest wreck, then that's the next wreck, but if we left wrecks behind then we group the wrecks depending on their distances using the farer wreck behind to stablish how we make the groups, cleaning the group we are in or if we are not inside a group, we calculate the best route with those groups in mind, going for the closest but without going back to where we come from.
People are apparently quite good at solving the travelling salesman problem. We don't really know how our minds do it.. but apparently psychologists have made note of it. I am betting a lot of it is spacial thinking and the ability to see a mistake fairly quickly and adjust without losing too much time. A computer algorithm doesn't generally adjust as it goes.. it just follows its procedure. So if it is headed down a bad path.. it is doomed. Although.. it all depends on the algorithm.
Originally by: carmo pereira
now you calculate in pairs of points.
the middle point from wreck A to B, C to D, E to F, etc...
then you have 14points... you do the same procedure, till you got 1 unique point.
that point is the best place to get the minimum distance to all.
At first I wasn't sure that this would give you the "center of mass"... but after drawing a number of test patterns.. it does seem to wittle down to the center. Does this work for all cases and choices of pairs? I am guessing it is sort of averaging out the x,y,z components of the points. Sorry... my geometry is a bit rusty. The only issue I would see would be deciding where to go next after you are done with your cluster that is in range.
When I first posed the question... I was thinking more of the ideal, perfect solution. I also was not thinking so much of the constraints of Eve. For example... I was imagining you having 1000 wrecks scattered about... not so clustered as a result of game mechanics. My bet is the level designers intentionally setup fields so that you don't have to spend too much time worrying about it. It would be really annoying to have to spend hours cleaning up the wrecks.
I imagine if you were able to sit behind "God" and watch him solve a large scattered field.. there would be lots of tiny tweaks that would shave the seconds off... for example... instead of moving to a center point of a cluster and stopping his ship... he would probably continue to make small adjustments to his position well before the cluster was depleted. Also... perhaps when there are five ships left to loot... and if the next cluster was a decent distance away... go ahead and start moving there and relocate the leftovers as he moves to the new position.
I would think a perfect solution would be kind of insane. However... it might only shave a minute off of the total time that a player would do naturally... and sometimes its nice to sacrifice a few minutes to not have to think so deeply on it (or to brainstorm your char sheet or browse the market during transit times). I am betting there are plenty of simple heuristics that would solve these problems reasonably well. I am doubting we can get optimal though. |
| |
|